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:

  • Reflexivityx x~x;
  • Symmetryxy x~yy~x;
  • Transitivity: ∀xyz (x~yy~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 E0 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.

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

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

Tensor Product of Vector Spaces
... ⊗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 ...
Free Object - Examples
... 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 ...
Generating 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)