Equivalence relation

2020 Mathematics Subject Classification: Primary: 03E [MSN][ZBL]

Let $X$ be a set. An equivalence relation on $X$ is a subset $R\subseteq X\times X$ that satisfies the following three properties:

1) Reflexivity: for all $x\in X$, $(x,x)\in R$;

2) Symmetry: for all $x,y\in X$, if $(x,y)\in R$ then $(y,x)\in R$;

3) Transitivity: for all $x,y,z \in X$, if $(x,y)\in R$ and $(y,z)\in R$ then $(x,z)\in R$.

When $(x,y)\in R$ we say that $x$ is equivalent to $y$.

Instead of $(x,y)\in R$, the notation $xRy$, or even $x\sim y$, is also used.

An equivalence relation is a binary relation.

Example: If $f$ maps the set $X$ into a set $Y$, then $R=\{(x_1,x_2)\in X\times X\,:\, f(x_1)=f(x_2)\}$ is an equivalence relation (cf. Kernel of a function).

For any $y\in X$ the subset of $X$ that consists of all $x$ that are equivalent to $y$ is called the equivalence class of $y$. Any two equivalence classes either are disjoint or coincide, that is, any equivalence relation on $X$ defines a partition (decomposition) of $X$, and vice versa.