Equivalence relation

In mathematics, an equivalence relation on a set X is a binary relation on X that is reflexive, symmetric, and transitive. That is, if the relation is denoted by the symbol "~", it holds for all a, b, and c in X that

(Reflexivity) a ~ a
(Symmetry) if a ~ b then b ~ a
(Transitivity) if a ~ b and b ~ c then a ~ c

A set together with an equivalence relation is called a setoid.

Equivalence relations are often used to group together objects that are similar in some sense.

Examples of equivalence relations

The equality ("=") relation between real numbers or sets.
The relation "is congruent to (modulo 5)" between integers.
The relation "is similar to" on the set of all triangles.
The relation "has the same birthday as" on the set of all human beings.
The relation of logical equivalence on statements in first-order logic.
The relation "is isomorphic to" on models of a set of sentences.
The relation "is in thermal equilibrium with".
The relation "has the same image under a function" on the elements of the domain of the function.
Green's relations are five equivalence relations on the elements of a semigroup.

Examples of relations that are not equivalences

The relation "is friends with", among people need not be an equivalence relation.
The relation "≥" between real numbers is not an equivalence relation, because although it is reflexive and transitive, it is not symmetric. E.g. 7 ≥ 5 does not imply that 5 ≥ 7. It is, however, a partial order relation.
The relation "has a common factor greater than 1 with" between natural numbers greater than 1, is not an equivalence relation, because although it is reflexive and symmetric, it is not transitive (2 and 6 have a common factor greater than 1, and 6 and 3 have a common factor greater than 1, but 2 and 3 do not have a common factor greater than 1).
The empty relation R on a non-empty set X (i.e. a R b is never true) is not an equivalence relation, because although it is vacuously symmetric and transitive, it is not reflexive (except when X is also empty).
The relation "is approximately equal" between real numbers or other things, even if more precisely defined, is not an equivalence relation, because although it is reflexive and symmetric, it is not transitive (it may seem so at first sight, but many small changes can add up to a big change).
The relation "is a sibling of" on the set of all human beings is not an equivalence relation, and it is worthwhile example to consider. Upon first inspection, one might think that this relation is not an equivalence relation because while it is symmetric and transitive, it is not reflexive. This is incorrect. It is true that this relation is symmetric (if A is a sibling of B, then B is a sibling of A). However, it is not transitive nor is it reflexive. The reason that this relation is not reflexive is clear: no one is their own sibling. If the relation were transitive, then it would lead to people being their own siblings. Assume it were transitive. Then if A were a sibling of B, then by symmetry B would be a sibling of A as well. Then, by transitivity, A would be a sibling of A. This is not the case. The relation is "almost transitive", insofar as whenever A is a sibling of B, and B is a sibling of C, and A $\neq$ C, then A is a sibling of C.
Relations that are transitive and symmetric but not reflexive are very rare (e.g. the empty relation). In fact, the previous example illustrates why this must be the case. Whenever a relation is symmetric and transitive, then for any X in the set being considered, if we have X~Y, then we have Y~X by symmetry, and then X~X by transitivity. So, we see that these relations only occur when there is some X that is an "island". That is, we must have some X that is not related to anything at all.

Partitioning into equivalence classes

Every equivalence relation on X defines a partition of X into subsets called equivalence classes: all elements equivalent to each other are put into one class. Conversely, if the set X can be partitioned into subsets, then we can define an equivalence relation ~ on X by the rule "a ~ b if and only if a and b lie in the same subset".

For example, if G is a group and H is a subgroup of G, then we can define an equivalence relation ~ on G by writing a ~ b if and only if ab^-1 lies in H. The equivalence classes of this relation are the right cosets of H in G.

Since every equivalence relation can be identified with a partition and vice versa, the number of equivalence relations on a set X of n elements is given by the nth Bell number, B_n.

If an equivalence relation ~ on X is given, then the set of all its equivalence classes is the quotient set of X by ~ and is denoted by X/~. For every equivalence relation, there is a surjective canonical projection map π from X to X/~ defined by π(x) = ^*. Conversely, any surjection between sets determines a partition on its domain, the set of preimages of singletons in the codomain.

Thus there are three equivalent ways of formally "modding out by" some property: specifying an equivalence relation, specifying a partition, or specifying a projection map.

Relation to group theory

It is very well known that lattice theory captures the mathematical structure of partial orderings. It is much less known that group theory, specifically the notion of transformation group and group action, captures the mathematical structure of equivalence relations. Let A be some set. Then the following statements are provably mutually equivalent (Van Fraassen 1989: 243-46). Given a:

Equivalence relation over A, the resulting equivalence classes partition A (this theorem is very well-known);
Partition of A, there exists a transformation group over A whose orbits are the cells of that partition;
Transformation group over A, there exists an equivalence relation over A, whose equivalence classes are the orbits of the group. The group transforms any member of a given equivalence class into another member of the same class (Garrett Birkhoff and Saunders Mac Lane 1999: 70).

Hence given any partition of A into equivalence classes, there exists a transformation group over A whose orbits are those same equivalence classes.

Generating equivalence relations

If two equivalence relations over the set X are given, then their intersection (viewed as subsets of X×X) is also an equivalence relation. This allows for a convenient way of defining equivalence relations: given any binary relation R on X, the equivalence relation generated by R is the smallest equivalence relation containing R.

Concretely, the equivalence relation ~ generated by R can be described as follows: a ~ b if and only if there exist elements x₁, x₂,...,x_n in X such that x₁ = a, x_n = b and such that (x_i , x_{i +1}) or (x_{i +1}, x_i) is in R for every i = 1,...,n -1.

Note that the resulting equivalence relation can often be trivial! For instance, the equivalence relation ~ generated by the binary relation ≤ has exactly one equivalence class: x~y for all x and y. More generally, the equivalence relation will always be trivial when generated on a relation R having the "antisymmetric" property that, given any x and y, either x R y or y R x must be true.

In topology, if X is a topological space and ~ is an equivalence relation on X, then we can turn the quotient set X/~ into a topological space in a natural manner. See quotient space for the details.

One often generates equivalence relations to quickly construct new spaces by "gluing things together". Consider for instance the square X = ^*" target="_blank" >and the equivalence relation on X generated by the requirements (a,0) ~ (a,1) for all a in ^*. Then the quotient space X/~ can be naturally identified with a torus: take a square piece of paper, bend it to glue together the upper and lower edge, then bend the resulting cylinder to glue together the two mouths.

Common notions in Euclid's Elements

The first person who introduced the idea of equivalence relations was Euclid in his book The Elements, under the heading of "Common Notions".

Common Notion 1. Things which equal the same thing also equal one another.

Nowadays, a binary relation is called Euclidean if it satisfies this property.

Unfortunately, he did not mention symmetry or reflexivity. But this suggests an alternative formulation: An equivalence relation is a relation which is Euclidean, symmetric and reflexive.

References

Garrett Birkhoff and Saunders Mac Lane, 1999. Algebra, 2nd ed. Chelsea. Chpt. II.7.
John Randolph Lucas, 1973. A Treatise on Time and Space. London: Methuen. Section 31.
Bas Van Fraassen, 1989. Laws and Symmetry. Oxford Univ. Press.

External links

Equivalence Relations

Set theory

Gourt Home::Gourt :: Equivalence relation