Equivalence Relation

Definition

Let $X$ be a set. A relation $\sim :X\to X\to \mathrm{Prop}$ is an equivalence relation iff it is:

• reflexive: $\forall x:X.x\sim x$
• symmetric: $\forall x,y:X.x\sim y\to y\sim x$
• transitive: $\forall x,y,z:X.x\sim y\to y\sim z\to x\sim z$

Equivalence Classes

Given an equivalence relation $\sim$ on $X$, the equivalence class of an element $x\in X$ is $[x{]}_{\sim }=\{y\in X\mid x\sim y\}.$ The equivalence classes partition $X$: they are pairwise disjoint and their union is all of $X$.

Relationship to Partitions

Equivalence relations on $X$ and partitions of $X$ are in bijective correspondence. Given $\sim$, the set $X/\sim =\{[x{]}_{\sim }\mid x\in X\}$ is a partition; given a partition $C$, define $x{\sim }_{C}y$ iff $x$ and $y$ lie in the same block.

Quotients

The quotient $X/\sim$ is the set of equivalence classes, equipped with the canonical surjection $q:X\to X/\sim$ sending each element to its class. It is universal among functions out of $X$ that identify $\sim$-related elements.

Examples

• Equality $=$ on any set is an equivalence relation (the finest one).
• The total relation $x\sim y$ for all $x,y$ is an equivalence relation (the coarsest one).
• Congruence modulo $n$ on $\mathbb{Z}$: $x\sim y$ iff $n\mid (x-y)$.
• Homotopy of paths in a topological space.

Related Concepts

• Reflexive Relation
• Symmetric Relation
• Transitive Relation
• Partition (Mathematics)
• Quotient
• Predicate

References

• munkres2000-topology