# Expressing infinite elements each equivalence class in First Order logic

I was going through some FO-logic ideas for my logic exam revision and came across some problems...

Equivalence relations can be expressed in FO-logic by the set of axioms:

$\{\forall x Rxx, \forall x \forall y(Rxy \rightarrow Ryx), \forall x \forall y \forall z (Rxy \wedge Ryz \rightarrow Rxz)\}$, where $R$ is a congruence relation

How can we then express the additional requirement that every equivalence class has infinitely many elements? I believe this axiomatic system is infinite but nonetheless axiomatizable.

A similar requirement would be that a universe has infinitely many equivalence classes. How do we generally go about formulating an axiomatic system for such expressions?

## 1 Answer

We assume that your system is the usual first-order logic with equality.

For $n\ge 2$, let $S_n$ be the sentence that says $\forall x\exists y_1\exists y_2\cdots \exists y_n\phi(x,y_1,y_2,\dots, y_n)$. Here $\phi$ is the conjunction of (i) formulas $R(x,y_i)$, where $i$ ranges over the integers from $1$ to $n$ and (ii) formulas of the shape $\lnot(y_i=y_j)$, for all $i,j$ where $1\le i\lt j\le n$.

Adding all the $S_n$ to your axiom system forces all the equivalence classes to have infinitely many elements.

Forcing infinitely many equivalence classes is simpler. Let $T_n$ be the sentence that says that $\exists x_1\exists x_2\cdots \exists x_n\psi(x_1,x_2,\dots,x_n)$. Here $\psi$ is the conjunction of all $\lnot R(x_i,x_j)$, where $i,j$ ranges over all $1\le i\lt j\le n$. Adding $T_n$ for all $n\ge 2$ forces the existence of infinitely many equivalence classes.