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 5 essays across one field — each of them below, with the objects they name alongside it.

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 A countable structure grown by adding witnesses. Stages of a structure built from 0 and 1 by adding sums, products, negatives and roots of quadratics: 2, 4, 12, 158 elements between −3 and 3.

A countable field that passes for the line

The real numbers are uncountable, and every first-order sentence about their addition, multiplication and order is also true of a countable field inside them — the real algebraic numbers. Löwenheim and Skolem showed this is no quirk of the reals: every theory with an infinite model has a countable one, including set theory, which then contains sets it calls uncountable.

logic · Models The rationals and the dyadic fractions, matched 12 times without a crossing. Two number lines from 0 to 1, rationals above and dyadic fractions below, with 12 back-and-forth matchings: 1/2↔1/2, 1/3↔1/4, 2/3↔3/4, 1/4↔1/8, 3/4↔7/8, 2/5↔3/8, 1/5↔1/16, 3/5↔5/8, 4/5↔15/16, 2/7↔3/16, 1/6↔1/32, 3/8↔5/16.

Two lists that are one order

The rationals and the fractions with a power of two below are different sets of numbers, and as orders they are exactly the same — any two countable orders that are dense and have no ends can be matched, point for point, keeping every comparison. The proof is a zigzag, and it settles every question the language of order can ask.

logic · Models

Named alongside it

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

QuantifierExhaustive searchExpressive powerModelStrategyCountabilityAlgebraic numberAsymptoticAxiomatic set theoryBack and forthCardinalityCategoricity

All concepts