# 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*

## 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 triangless.
- 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"

## 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**and equivalence relation, because although it is reflexive and symmetric, it 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**)

## 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*.

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*/~.

## Generating equivalence relations

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* = [0,1]x[0,1] and the equivalence relation on *X* generated by the requirements (*a*,0) ~ (*a*,1) for all *a* in [0,1] and (0,*b*) ~ (1,*b*) for all *b* in [0,1]. 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 is Euclid in his book the Elements under 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 didn't mention symmetry or reflexitivity. But this suggests an alternative formulation: An equivalence relation is a relation which is Euclidean, symmetric and reflexive.

In music see octave equivalency, transpositional equivalency, inversional equivalency, enharmonic equivalency, rotationalal equivalency.