= Solution
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 formula
$$
\operatorname{Rep}(x)=\forall y\,[y<x\longrightarrow\neg E(y,x)]
$$
selects exactly those least elements. Apply part (b) to this formula, using $k=3$, to obtain $\operatorname{Rep}_n\in L^3$ saying that at least $n$ representatives exist. The required sentence is
$$
\boxed{\eta_n=\operatorname{Lin}(<)\land\operatorname{Eq}(E)\land\operatorname{Rep}_n.}
$$
This 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$.
Back to article page
