Axiomatization of equivalence relations having finite equivalence classes

equivalence-relationsfirst-order-logicmodel-theory

The problem is this:

Let $\mathcal{L}$ be the language with a binary relation symbol $\it{R}$. Determine whether the collection $\mathcal{C}_{<\omega}$ of all equivalence relations having equivalence classes of finite size is axiomatizable or finitely axiomatizable.

I have the feeling that this collection is not axiomatizable, but I wasn't able to prove it. I was trying to show that the "complement" of $\mathcal{C}_{<\omega}$, the class of equivalence relations with at least one infinite equivalence class, is not finitely axiomatizable, without success. Can you give me a hint?

EDIT: This is an exercize in the first chapter of an introductory course in mathematical logic, so the solution should be rather simple and not involve advanced concepts.

Best Answer

You are right that $\mathcal{C}_{< \omega}$ is not axiomatisable. The usual argument using compactness goes by contradiction. It goes as follows (I'll leave it to you to fill in the details).

  1. Suppose that there is an axiomatisation $T$.
  2. Let $\phi_n$ express "every equivalence class has at least $n$ elements" (exercise: write down such a formula).
  3. Show that $T \cup \{\phi_n : n \in \mathbb{N}\}$ is consistent, using compactness.
  4. Note that $T \cup \{\phi_n : n \in \mathbb{N}\}$ is inconsistent, because any model of it must be in $\mathcal{C}_{< \omega}$, while also satisfying $\phi_n$ for all $n$.
  5. Conclude that we have a contradiction, and so we are done.