Home > Equivalence relation
In mathematics, an equivalence relation on a set X is a binary relation on X that is reflexive, symmetric and transitive, i.e., if the relation is written as ~ 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
Equivalence relations are often used to group together objects that are similar in some sense.
1 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 modelsIn mathematics, model theory is the study of the representation of mathematical concepts in terms of set theory, or the study of the models which underlie mathematical systems. It assumes that there are some pre-existing mathematical objects out there, an of a set of sentences.
- The relation "is in thermal equilibrium with".
- Green's relationsIn mathematics, Green's relations are five equivalence relations that characterise the elements of a semigroup in terms of the principal ideals they generate. The relations are named for J. Green, who introduced them in a paper of 1951. John Mackintosh Ho are five equivalence relations on the elements of a semigroupAbstract algebra Semigroup theory In mathematics, a semigroup is a set with an associative binary operation on it. There is some disagreement on whether the empty set should be admitted as a semigroup. Many authors insist that a semigroup should be non-em.
2 Examples of relations that are not equivalences
- 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.
- The relation "has a common factor with" between natural numbers is not an equivalence relation, because although it is reflexive and symmetric, it is not transitive (2 and 6 have a common factor, and 6 and 3 have a common factor, but 2 and 3 do not have a common factor).
- 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 the mother of" on the set of all human beings is not an equivalence relation, because it not reflexive (A is not the mother of A), symmetric (If A is the mother of B, then B is not the mother of A), and is not transitive (if A is the mother of B, and B is the mother of C, it does not necessarily mean A is the mother of C)
3 Partitioning into equivalence classes
Every equivalence relation on X defines a partitionA partition of U into 6 blocks: a Venn diagram representation. In mathematics, a partition of a set X is a division of X into non-overlapping parts or blocks that cover all of X''. Definition A partition of a set X is a set of nonempty subsets of X such t 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.
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/~.
