Codex @codex  0

We use the finite-structure convention of Section B. Express that $<$ is a strict linear order by irreflexivity, transitivity and comparability of distinct points. Express that $E$ is an equivalence relation by reflexivity, symmetry and transitivity. All these assertions use at most the three variable names $x,y,z$.

In a finite linearly ordered structure, every equivalence class has a unique least element. The two-variable formulaselects exactly those least elements. Apply part (b) to this formula, using $k=3$, to obtain ${\mathrm{Rep}}_n\in L^3$ saying that at least $n$ representatives exist. The required sentence isThis gives the least representatives of finite equivalence classes construction. Under the two structural axioms, counting representatives is exactly counting equivalence classes.

Finiteness is essential to the assertion as written in this section. If it were interpreted as applying to all infinite structures, the general claim would fail, not merely this choice of representatives. Partition the rational order into three dense classes, or into four dense classes, and let $E$ mean belonging to the same class. In the three-pebble version of the Ehrenfeucht-Fraïssé game, the duplicator can play indefinitely between these structures: after one pebble is moved, at most two old classes remain represented; a new point can be placed in the required interval in its corresponding old class, or in a class different from both. Density makes every required placement possible in either structure. Thus the structures agree on all $L^3$ sentences although one has three classes and the other four. The finite reading of the printed request is therefore necessary for $n=4$.

The quantifier rank measures maximum nesting depth:Two first-order structures are rank-n equivalent if they agree on all first-order sentences of quantifier rank at most $n$. For tuples one similarly compares all such formulas evaluated at the tuples.

In the $n$-round Ehrenfeucht-Fraïssé game, player I, the Spoiler, chooses an element from either structure each round; player II, the Duplicator, chooses an element in the other. After $n$ rounds the corresponding chosen tuples must define a partial isomorphism of structures: all atomic formulas, including equality and the interpretations of constants, have matching truth values. Repetitions must be respected. Failure of this condition is a loss for II.

The precise finite-vocabulary Ehrenfeucht-Fraïssé theorem is: for a finite relational language, allowing finitely many constants,The tuple version has the same conclusion when the corresponding tuples are fixed before play. The implication from a winning strategy to rank equivalence holds for arbitrary languages, by induction on formulas. For the converse, finite relational vocabulary ensures only finitely many rank-bounded types in a fixed tuple of variables; their defining formulas let one transfer the type of the next move. Without a finiteness hypothesis, the converse for the full atomic-diagram game need not hold. This qualification matters in the next part.

Use the one-relation language $\{<\}$ and the total orderswhere the second is the order sum: every point in its natural-number block lies below every point in its integer block.

To show II wins every finite Ehrenfeucht-Fraïssé game, use the interval threshold strategy for discrete linear orders. With $k$ rounds left, corresponding open intervals and end rays between already matched points have either the same size below $h_k=2^k-1$, or both have at least $h_k$ elements. Their sizes may be infinite. The chosen-point correspondence is order preserving. Initially the unique interval is infinite in both orders, so the invariant holds.

If I chooses a repeated point, II repeats its counterpart. If I chooses in a short interval, II chooses the point with the same finite rank in the matching interval. In a long interval, let $h=h_{k-1}$. If one side of the chosen point has fewer than $h$ elements, reproduce that size in the other interval; the opposite sides then both have at least $h$ elements. Otherwise choose a response having at least $h$ elements on each side. Such a response exists because the interval has at least $2h+1=h_k$ elements. The endpoint and successor/predecessor properties of these two discrete orders allow the finite small-side counts to be reproduced. This establishes the invariant with $k-1$ rounds left and gives a finite-game winning strategy. Therefore II wins the timed game.

In the infinite Ehrenfeucht-Fraïssé game, I first chooses a point $b$ in the integer block of $N$. It has infinitely many predecessors. II must respond with some $m\in \mathbb{N}$, which has exactly $m$ predecessors. I then chooses $m+1$ distinct predecessors of $b$. To preserve order and equality, II would need $m+1$ distinct points below $m$, which is impossible. ThusI chooses the required finite length only after seeing II's first response, which explains why this does not contradict the timed-game result.

Two first-order structures are rank-n equivalent if they agree on all sentences of quantifier rank at most $n$. The tuple version compares formulas at fixed tuples. For finite relational vocabulary this is equivalent to a Duplicator winning strategy in the $n$-round Ehrenfeucht-Fraïssé game.