Using first order sentences, axiomize the $\mathcal{L}$-theory of an equivalence relation with infinitely many infinite classes.

Question

Problem

Let $\mathcal{L} = \{E\}$ where $E$ is a binary relation symbol. Let $T$ be the $\mathcal{L}$-theory of an equivalence relation with infinitely many infinite classes.

Current Solution

First, the axioms for equivalence class:

\begin{alignat*}{3} &\forall x &&E(x,x),\\ &\forall x \forall y &&(E(x,y) \rightarrow E(y,x)),\\ &\forall x \forall y \forall z &&(E(x,y) \wedge E(y,z) \rightarrow E(x,z))).\\ \end{alignat*}

Then to express infinitely many equivalence classes, we add infinitely many senteneces $\phi_n ~(n \ge 2$): $$\phi_n = \exists x_1 \ldots \exists x_n ~ \bigwedge_{i < j \le n} \neg E(x_i,x_j).$$

That is we have sentences $\phi_2,\phi_3,\ldots$. Finally, we add infinitely many sentences $\psi_n ~(n \ge 1)$ $$\psi_n = \forall x \exists x_1 \ldots \exists x_n ~ \bigwedge_{i < j \le n} x_i \neq x_j \wedge \bigwedge_{i=1}^n E(x,x_j)$$

to axiomize each class is infinite.

Problem

I am not confident that $\{\phi_n\}$ and $\{\psi_n\}$ are not contradicting each other

Answer 1

You have axiomatized the theory asserting that $E$ is an equivalence relation with infinitely many classes, ALL of which are infinite. Your statement $\psi_n$ says that every class has at least $n$ elements.

But the theory mentioned in the title problem was just that $E$ should have infinitely many infinite classes (and perhaps also some finite classes). It turns out that this problem is impossible.

Theorem. The collection of equivalence relations with infinitely many infinite classes is not first-order axiomatizable in the language of one binary relation with equality.

Proof. Let $E_0$ be an equivalence relation on a set $X$ with infinitely many classes of arbitrarily large finite size, and no infinite classes at all. So $\langle X,E_0\rangle$ is not one of the desired models. Let $T$ be the elementary diagram of $\langle X,E_0\rangle$, plus the assertions with infinitely many new constants $c^n_i$, that $c^n_i\mathrel{E} c^n_j$ and $c^n_i\neq c^n_j$ and $\neg (c^n_i\mathrel{E} c^m_j)$, whenever $n\neq m$ and $i\neq j$. This theory is finitely consistent, and so it is consistent. Any model of $T$ will be an expansion of an elementary extension of the original model $\langle X,E_0\rangle$, but it will now have infinitely many infinite classes.

Thus, the property of having infinitely many infinite classes is not first-order expressible, since the original model did not have that property but the new model did, even though they were elementary equivalent. QED