**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 2*T* 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

_{0}*T*. Informally, one can visualize models of this theory as infinitely branching trees of height α with models of

*T*attached to all leaves.

Read more about this topic: List Of First-order Theories

### Other articles related to "relations, equivalence relations, equivalence, equivalence relation":

... ⊗K W of two vector spaces V and W over a field K can be defined by the method of generators and

**relations**... the underlying field K is understood.) The tensor product arises by defining the following four

**equivalence relations**in F(V × W) where v, v1 and v2 are vectors from V, while w, w1, and w2 are ... Denoting by R the space generated by these four

**equivalence relations**, the tensor product of the two vector spaces V and W is then the quotient space ...

... Then one imposes a set of

**equivalence relations**upon the words, where the

**relations**are the defining

**relations**of the algebraic object at hand ... The free object then consists of the set of

**equivalence**classes ... In the next step, one imposes a set of

**equivalence relations**...

**Equivalence Relations**

... Given any set X, there is an

**equivalence relation**over the set of all possible functions X→X ... Functions equivalent in this manner form an

**equivalence**class on, and these

**equivalence**classes partition ... An

**equivalence relation**~ on X is the

**equivalence**kernel of its surjective projection π X → X/~ ...

### Famous quotes containing the word relations:

“Children, who play life, discern its true law and *relations* more clearly than men, who fail to live it worthily, but who think that they are wiser by experience, that is, by failure.”

—Henry David Thoreau (1817–1862)