Matpic
mathematics, in pictures
Series

Ehrenfeucht–Fraïssé games — the series

7 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. 3 rounds on chains of 4 and 5. Two chains of dots with pebbles placed in turn, and the transcript of a play: Spoiler picks an element of one chain, Duplicator answers in the other, and the pebbles must keep the same order.

    A game that decides what can be said

    Two players take turns pointing at elements of two structures; if the second can survive k rounds, then no sentence with k quantifiers tells the structures apart — a statement about infinitely many formulas, settled by a finite search.

    part 1 · logic
  2. Three properties that leave the middle, and one that cannot. Four measured curves of the share of random graphs having a property, plotted against the number of points: three first-order properties running to zero or one, and the parity of the edge count sitting on a half throughout.

    Nearly always, or nearly never

    Toss a coin for every pair of points and ask whether the graph that results has some property. For a property a first-order sentence can state, the answer in the limit is never a genuine probability — it is zero or it is one, and the game is what proves it.

    part 2 · logic
  3. What a sentence of depth 2 can reach. Two rings of points, of 14 and 19 points, each with a run of 9 consecutive points marked as the neighbourhood a sentence of depth 2 can inspect.

    The distance a sentence can see

    A first-order sentence with three quantifiers cannot notice anything about a graph beyond a fixed distance from the points it names. That single limitation is why it cannot say connected, and why the failure survives every attempt to add more quantifiers.

    part 3 · logic
  4. A 6-cycle and two 3-cycles: refinement cannot tell them apart. Two graphs side by side — one cycle and two smaller cycles — with the same number of points, the same number of edges and every point of the same degree.

    The game the algorithm was playing

    Change what Duplicator has to offer — a whole bijection instead of one element — and the game stops measuring first-order logic and starts measuring colour refinement, the algorithm every practical graph-isomorphism test begins with. Two subjects that grew apart are one game with the moves relabelled.

    part 4 · logic
  5. Where a word of m letters stops being distinguishable from one of m + 1. A row for each quantifier depth and a cell for each length, shaded where Duplicator survives the game between words of that length and one longer.

    A language that can name a set

    Allow a sentence to quantify over sets of positions as well as positions, and on words the answer changes completely: the sets buy exactly the languages a finite automaton recognises. Whether the number of letters is even is the smallest example of what the sets are for.

    part 5 · logic
  6. Two graphs every count agrees on, and one question that does not. Two sixteen-point graphs drawn on a four-by-four grid, with one point marked and its six neighbours highlighted in each, the neighbours forming two triangles in one and a six-cycle in the other.

    One gadget defeats every refinement

    Colour refinement fails on two triangles against a hexagon; its two-dimensional version fixes that and fails on a pair of strongly regular graphs. For every k there are two graphs the k-dimensional version cannot separate, and they are built from one local piece whose only symmetry is a parity.

    part 6 · logic
  7. Who survives with two pebbles and who with three, over 4 rounds. A table of three pairs of graphs with, for each, whether the duplicating player survives a two-pebble game and a three-pebble game played to a fixed depth.

    The boundary at three variables

    Restrict a sentence to two variable names and it can still be arbitrarily long, because the names are reused. What it cannot be is deep: every satisfiable two-variable sentence has a small model, so asking whether one is satisfiable is a bounded search. Allow a third name and the question becomes undecidable.

    part 7 · logic

All series