Editing Equivalence relation (section)

== Equivalence relations and mathematical logic ==
Equivalence relations are a ready source of examples or counterexamples. For example, an equivalence relation with exactly two infinite equivalence classes is an easy example of a theory which is ω-[[Morley's categoricity theorem|categorical]], but not categorical for any larger [[cardinal number]].

An implication of [[model theory]] is that the properties defining a relation can be proved independent of each other (and hence necessary parts of the definition) if and only if, for each property, examples can be found of relations not satisfying the given property while satisfying all the other properties. Hence the three defining properties of equivalence relations can be proved mutually independent by the following three examples:
* ''Reflexive and transitive'':  The relation ≤ on '''N'''. Or any [[preorder]];
* ''Symmetric and transitive'': The relation ''R'' on '''N''', defined as ''aRb'' ↔ ''ab'' ≠ 0. Or any [[partial equivalence relation]];
* ''Reflexive and symmetric'': The relation ''R'' on '''Z''', defined as ''aRb'' ↔ "''a'' &minus; ''b'' is divisible by at least one of 2 or 3." Or any [[dependency relation]].

Properties definable in [[first-order logic]] that an equivalence relation may or may not possess include:
* The number of equivalence classes is finite or infinite;
* The number of equivalence classes equals the (finite) natural number ''n'';
* All equivalence classes have infinite [[cardinality]];
* The number of elements in each equivalence class is the natural number ''n''.