Equivalence relation

An equivalence relation $\sim$ is a binary relation on set $A$ (that is, a subset of $A^2$ ) that is reflexive, symmetric, and transitive, that is, the following three properties hold:

$x \sim x$

$x \sim y\ \rightarrow\ y \sim x$

$x \sim y\ \land\ y \sim z\ \rightarrow\ x \sim z$

Given an equivalence relation $\sim$ , we define the set of equivalence classes $A_{/\sim}$ by

$\begin{equation*} A_{/\sim} = \{ \{y \mid x \sim y\} \mid x \in A \} \end{equation*}$

The equivalence classes of a non-empty set form a partition of $A$ .

Conversely, given a partition $P \subseteq 2^A$ of set $A$ , the relation defined by

$\begin{equation*} x \sim y\ \iff\ \exists S \in P. \{x,y\} \subseteq S \end{equation*}$

is an equivalence relation such that $A_{/\sim} = P$ .