Questions: Ehrenfeucht-Fraïssé Games and Elementary Equivalence

Question 1

A logician sets up EF_n games between structure A (a set of 30 elements with no relations) and structure B (a set of 200 elements with no relations). For which values of n does Duplicator have a winning strategy?

• A. For all n, since two pure sets look identical locally regardless of their sizes
• B. For all n < 30, since Duplicator can always respond while unused elements remain in the smaller structure
• C. For no value of n, since the structures have different sizes and one round is enough to distinguish them
• D. Only for n = 1, since Duplicator can match the first move but no further

Answer: (B)

In a pure set (no relations in the signature), the only atomic formulas involve equality. Spoiler's only winning move is to force Duplicator to map two distinct elements to the same element (violating injectivity). With 30 elements in A, Duplicator can always respond to Spoiler's selections with fresh elements until A is exhausted. For n < 30, after n rounds only n elements of A have been selected, leaving 30−n unused. Duplicator always has a valid response. For n ≥ 30, Spoiler can exhaust all elements of A and pick a 31st from B with no corresponding element — winning the game.

Question 2

What does it mean, in logical terms, for Duplicator to have a winning strategy in EF_n(A, B)?

• A. A and B are isomorphic — they have the same structure in every detail
• B. A and B satisfy all the same first-order sentences of quantifier depth at most n
• C. A and B satisfy all the same first-order sentences of quantifier depth exactly n, but may differ on simpler sentences
• D. Every sentence true in A of depth ≤ n is also true in B, but not necessarily vice versa

Answer: (B)

The fundamental theorem of EF games: Duplicator wins EF_n(A, B) if and only if A ≡_n B, meaning A and B agree on all first-order sentences of quantifier depth at most n. More rounds correspond to a richer logical language. Winning for all n simultaneously means A ≡ B (full elementary equivalence). The game translates an infinite logical question — do A and B agree on all FO sentences? — into a sequence of finite combinatorial games, each certifying agreement up to a specific logical complexity.

Question 3

If Duplicator has a winning strategy in EF_n(A, B) for nearly every natural number n, then A and B should be isomorphic.

• T. True
• F. False

Answer: False

Winning for all n implies elementary equivalence (A ≡ B) — they agree on all first-order sentences. But elementary equivalence is strictly weaker than isomorphism. The dense linear order of the rationals (ℚ, <) and the reals (ℝ, <) are elementarily equivalent (both satisfy the same first-order theory of dense linear orders without endpoints) but are not isomorphic — ℝ is uncountable and ℚ is countable. First-order logic cannot express uncountability, so the EF game never produces a Spoiler win, yet the structures are structurally very different.

Question 4

The Ehrenfeucht-Fraïssé game is particularly powerful for proving inexpressibility results — showing that certain properties cannot be captured by any first-order sentence.

• T. True
• F. False

Answer: True

Inexpressibility proofs are the game's signature application. To show a property P is not first-order expressible, exhibit two structures A (with P) and B (without P) such that Duplicator wins EF_n(A, B) for all n. This means no FO sentence of any quantifier depth can distinguish them — so no FO sentence can capture P. Classic results proved this way: parity of domain size, finiteness, connectivity of graphs, and transitive closure are all inexpressible in first-order logic. The game converts what would otherwise be an unwieldy argument over infinitely many sentences into a constructive winning strategy.

Question 5

Explain why Duplicator winning EF_n(A, B) for every natural number n does not imply that A and B are isomorphic.

Model answer: Duplicator winning for all n implies A ≡ B — elementary equivalence — meaning the two structures satisfy exactly the same first-order sentences. But first-order logic has limited expressive power: it cannot distinguish structures that differ only in properties inexpressible in FO, such as cardinality. The canonical example is the dense linear order of the rationals (ℚ, <) and the reals (ℝ, <). Both satisfy the same first-order theory of dense linear orders without endpoints (DLO), so Duplicator wins every EF game between them. Yet they are not isomorphic: ℝ is uncountable while ℚ is countable. No FO sentence detects this difference, so the games cannot reveal it — illustrating the expressive gap between FO and full model-theoretic equivalence.

This gap between elementary equivalence and isomorphism is one of the central themes of model theory. The compactness theorem and Löwenheim-Skolem theorems together imply that any first-order theory with an infinite model has models of every infinite cardinality — so distinct cardinalities are always elementarily equivalent in the absence of cardinality-constraining axioms (which FO cannot express). EF games are precisely calibrated to this expressive power.