List of First-order Theories - Equivalence Relations

Equivalence Relations

The signature of equivalence relations has one binary infix relation symbol ~, no constants, and no functions. Equivalence relations satisfy the axioms:

• Reflexivity ∀x x~x;
• Symmetry ∀x ∀y x~y → y~x;
• Transitivity: ∀x ∀y ∀z (x~y ∧ y~z) → x~z.

Some first order properties of equivalence relations are:

• ~ has an infinite number of equivalence classes;
• ~ has exactly n equivalence classes (for any fixed positive integer n);
• All equivalence classes are infinite;
• All equivalence classes have size exactly n (for any fixed positive integer n).

The theory of an equivalence relation with exactly 2 infinite equivalence classes is an easy example of a theory which is ω-categorical but not categorical for any larger cardinal.

The equivalence relation ~ should not be confused with the identity symbol '=': if x=y then x~y, but the converse is not necessarily true. Theories of equivalence relations are not all that difficult or interesting, but often give easy examples or counterexamples for various statements.

The following constructions are sometimes used to produce examples of theories with certain spectra; in fact by applying them to a small number of explicit theories T one gets examples of complete countable theories with all possible uncountable spectra. If T is a theory in some language, we define a new theory 2T by adding a new binary relation to the language, and adding axioms stating that it is an equivalence relation, such that there are an infinite number of equivalence classes all of which are models of T. It is possible to iterate this construction transfinitely: given an ordinal α, define a new theory by adding an equivalence relation E_β for each β<α, together with axioms stating that whenever β<γ then each E_γ equivalence class is the union of infinitely many E_β equivalence classes, and each E₀ equivalence class is a model of T. Informally, one can visualize models of this theory as infinitely branching trees of height α with models of T attached to all leaves.