Past exam of the mathematics course of the University of Cambridge / 2002 / iii / Paper 23 / 10

Use only the variable names $x,y$. Define mutually renamed formulas bywhere $D_m^y$ is obtained from $D_m^x$ by globally interchanging $x$ and $y$, including their bound occurrences. By induction, $D_m^x(a)$ means that an increasing chain of $m$ elements starts at $a$. Henceholds exactly when the linear order has at least $n$ elements. Inner quantifiers may bind the name $x$ again, but their scope is only the nested subformula; the comparison $x<y$ still refers to the preceding point. This finite-variable logic construction works on finite and infinite linear orders.

Choose a variable name $y\ne x$ among the $k$ available names and defineThe formula $C_m^y$ is obtained by interchanging the names $x,y$ throughout $C_m^x$, including bound occurrences. Its only free variable is $y$. A permutation of variable names preserves membership in $L^k$, so every formula in this recursion still uses at most the original $k$ names. In particular, bound variables inside a copy of $\varphi$ do not accidentally capture the previous comparison: their scope stays inside that copy.

Induction proves that $C_m^x(a)$ holds exactly when there is an increasing $m$-tuple of satisfying elements whose first entry is $a$. Any set of $m$ distinct points in a linear order can be put in increasing order. Therefore the variable-recycling count on a linear orderis the required sentence. This does not use counting quantifiers or additional variable names, and it applies equally to infinite linear orders.

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$.