Equivalence Relation¶

Definition¶

An equivalence relation on a set $A$ is a relation $\sim$ on $A$ such that, for all $a,b,c\in A$ $A$ , it is:

reflexive: $a\sim a$ $a$ ;
symmetric: if $a\sim b$ $b$ , then $b\sim a$ $a$ ;
transitive: if $a\sim b$ and $b\sim c$ $c$ , then $a\sim c$ $c$ .

Interpretation¶

An equivalence relation formalizes when different objects should be treated as the same for a particular purpose, for example integers that leave the same remainder after division by $3$ , or sets of the same cardinality.

The numbers 0 to 8 grouped into three shaded ovals by their remainder modulo 3: {0, 3, 6}, {1, 4, 7} and {2, 5, 8}, the equivalence classes that partition the set.

In the figure $x\sim y$ if and only if $x$ and $y$ leave the same remainder after division by $3$ , on the set $A=\{0,1,\ldots,8\}$ ${0, 1, \dots, 8}$ , labelled $X$ in the figure. The relation sorts the nine numbers into the three equivalence classes $[0]=\{0,3,6\}$ ${0, 3, 6}$ , $[1]=\{1,4,7\}$ and $[2]=\{2,5,8\}$ ${2, 5, 8}$ , where $[x]=\{y\in A\colon y\sim x\}$ $x}$ . The classes partition $A$ : every element lies in exactly one class, and $[x]=[y]$ if and only if $x\sim y$ $y$ .

Each property has a job. Reflexivity puts $x$ into its own class $[x]$ , so no element is left out. Symmetry and transitivity prevent classes from overlapping without being equal: if $z$ lies in both $[x]$ and $[y]$ , then $x\sim z$ and $z\sim y$ $y$ , so $x\sim y$ and the two classes coincide. Without one of them this breaks down. The relation $\le$ on $\mathbb{R}$ is reflexive and transitive but not symmetric, and "differ by at most $1$ " is reflexive and symmetric but not transitive: $0$ is related to $1$ and $1$ to $2$ , but $0$ is not related to $2$ .

Equal cardinality is another example: it relates two sets when there is a bijection between them.

Key Results¶

Equal cardinality is an equivalence relation on sets.

Examples¶

Congruence modulo $n$ is an equivalence relation on integers.

Prerequisites¶

Set

Sources¶

Math II: Linear Algebra · Week 1

Aliases: equivalency relation Keywords: equivalence class Symbols: element of, real numbers

Last updated: 20 October 2026 03:02