Matpic
mathematics, in pictures
Concept

Ehrenfeucht fraisse game

A two-player game on a pair of structures whose outcome decides which sentences can tell them apart. Spoiler picks a point and Duplicator answers in the other structure, and surviving k rounds means no sentence of quantifier depth k separates them.

Named by 5 essays across one field — each of them below, with the objects they name alongside it.

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.

logic · Ehrenfeucht–Fraïssé games 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.

logic · Ehrenfeucht–Fraïssé games 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.

logic · Ehrenfeucht–Fraïssé games 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.

logic · Ehrenfeucht–Fraïssé games Three-colourability as a sentence: there exist three sets such that …. Petersen graph coloured with three colours; witness sets R = {0,2,6}, G = {1,3,5,9}, B = {4,7,8}; all 25 first-order checks pass.

There is a relation such that

A graph can be coloured with three colours exactly when there are three sets of its points such that every point lies in one and no edge joins two points of the same set. The sets are a guess; once guessed, the rest is a list of simple checks. Ronald Fagin proved in 1974 that this shape of sentence — 'there exist relations such that' followed by first-order conditions — describes exactly the problems whose solutions can be checked quickly, the class called NP. The central question of computer science is therefore also a question about what sentences can say.

logic · Quantifiers

Named alongside it

The objects these essays reach for when they reach for this one.

Exhaustive searchQuantifier depthColour refinementExpressive powerGraph isomorphismInvariantQuantifierSecond-order logicCounting argumentDecision procedureFinite automatonGraph colouring

All concepts