Matpic
mathematics, in pictures
Concept

Elementary equivalence

The relation holding between two structures when every sentence of first-order logic true of one is true of the other. It is weaker than isomorphism — a structure can have elementarily equivalent companions of every infinite size — and games are how it is established.

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

Also named here as strategy — the same set of essays touches all of them, so they are one junction rather than several.

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.

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

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

logic · Ehrenfeucht–Fraïssé games

Named alongside it

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

Exhaustive searchExpressive powerQuantifierStrategyAsymptoticConnectivityDecision procedureLocalityModelNeighbourhoodProbabilityQuantifier order

All concepts