LARA

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$.