Matpic
mathematics, in pictures
Concept

Quantifier depth

How deeply the quantifiers in a sentence are nested, which bounds how many objects it can refer to at once. It is the resource an Ehrenfeucht-Fraisse game measures, and a fixed depth is always defeated by structures that are large enough.

Named by 3 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 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

Named alongside it

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

Ehrenfeucht fraisse gameExhaustive searchColour refinementDecision procedureExpressive powerFinite automatonGraph isomorphismInvariantModelMonoidQuantifierRegular language

All concepts