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

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

• The best way to see that a set of sentences is not contradictory is to find a structure satisfying all of them. If you can find a $\mathcal L$-structure satisfying all the $\phi_n$ and $\psi_n$, you will be sure they are not contradicting each other.
– Pece
Feb 4 '15 at 16:08

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