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?


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.