= Equivalence relation
{title2=$x\sim y$}
{wiki}
An equivalence relation says which <set elements> should count as the same for a particular purpose. In <modular arithmetic>, for example, distinct <integers> with the same <remainder> are equivalent. The relation gathers interchangeable <set elements> into <equivalence classes>; the <quotient set> then treats each whole <equivalence class> as one object.
Formally, an equivalence relation on a <set> $X$ is a <binary relation> $R\subseteq X\times X$, written $x\sim y$, satisfying three conditions for all $x,y,z\in X$:
* <Reflexivity>: $x\sim x$.
* <Symmetric relation>: $x\sim y$ implies $y\sim x$.
* <Transitivity>: $x\sim y$ and $y\sim z$ imply $x\sim z$.
These conditions make the <equivalence classes> a <partition of a set>: each <set element> belongs to exactly one class. https://www.jirka.org/ra/html/sec_basicset.html[Jiří Lebl, Basic Analysis, §0.3.4, Definitions 0.3.21 and 0.3.23 and Proposition 0.3.24]{ref}
For a worked example, take the <finite set> $X=\{0,1,\ldots,8\}$ and restrict <integer congruence> modulo three to $X$:
$$
x\sim y\quad\Longleftrightarrow\quad x\equiv y\pmod3\quad\Longleftrightarrow\quad3\mid(x-y).
$$
<Reflexivity> follows because $x-x=0$. The <symmetric relation> property follows by changing the sign of a difference, and <transitivity> follows by adding $x-y$ and $y-z$: <divisibility> by three is preserved in both steps. Thus $0\sim3$ and $3\sim6$ force $0\sim6$. The three <equivalence classes> are $\{0,3,6\}$, $\{1,4,7\}$ and $\{2,5,8\}$. Their members alternate along the <number line>; membership in an <equivalence class> need not mean being close together.
\Image[/equivalence-classes-modulo-three.png]
{title=Congruence modulo three divides the integers from zero through eight into three equivalence classes}
The <transitivity> requirement rules out a tempting alternative. On $\{0,1,2\}$, define nearness by the <absolute value> condition $|x-y|\leq1$. This <binary relation> is <reflexive> and <symmetric>, but $0$ is near $1$ and $1$ is near $2$ while $0$ is not near $2$. Its neighborhoods $\{0,1\}$, $\{0,1,2\}$ and $\{1,2\}$ overlap without being equal. They are not <equivalence classes> or a <partition of a set>.
Back to article page
