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

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.