# Equivalence Relation

DEFINITION1: Let $X$ be a set and $R\subset{X\times{X}}$. If the relation $R$ is reflexive, symmetric and transitive, then the relation $R$ is called an "equivalence relation" and denoted by $R=\sim$ in general.

DEFINITION2: Let $\sim$ be an equivalence relation over a set $X$ and $a\in{X}$. The set defined as $\{x\in{X}\:|\:a\sim{x}\}\subset{X}$ is called the “equivalence class” of $a$ under $\sim$ and denoted by $\overline{a}$, $[a]$ or $[a]_{\sim}$. Since $a\sim{a}$ for every $a\in{X}$, then $a\in{\overline{a}}$. So the equivalence class $\overline{a}$ is non-empty for every $a\in{X}$. The family of all the equivalence classes of the relation $\sim$ is called the “quotient set” of $X$ by $\sim$ and denoted by ${^X}/{_\sim}$

I.e.,

${^X}/{_\sim}=\{\overline{a}\:|\:a\in{X}\}\subset{\mathbf{P}(X)}$.

DEFINITION3: Let $\sim$ be an equivalence relation over a set $X$ and $a,b\in{X}$. If $b\in{\overline{a}}$, then $b$ is called a “representative class” of the equivalence class $\overline{a}$.

PROPOSITION1: Let $\sim$ be an equivalence relation over a set $X$ and $a,b\in{X}$. Then,

$a\sim{b}\Leftrightarrow{a\in{\overline{b}}}\Leftrightarrow{\overline{a}=\overline{b}}\Leftrightarrow{b\in{\overline{a}}}$.

PROOF:

THEOREM1: Let $\sim$ be an equivalence relation over a set $X$. Then the quotient set ${^X}/{_\sim}$ is a partition of $X$.

PROOF:

EXAMPLE1: Define $R\subset{\mathbb{Z}\times{\mathbb{}Z}}$ as $xRy\Leftrightarrow{n\mid{x-y}}\Leftrightarrow{\exists{k\in{\mathbb{Z}}}: x-y=kn}$. (Where $n$ is an arbitrary constant in $\mathbb{N}$).

(i) $R$ is reflexive because $\forall{x}\in{\mathbb{Z}}, x-x=0=0.n\Rightarrow{xRx}$.

(ii) $R$ is symmetric because

$xRy\Rightarrow{\exists{k}\in{\mathbb{Z}}: x-y=k.n}\Rightarrow{y-x=(-k).n\land{-k\in{\mathbb{Z}}}}\Rightarrow{yRx}$.

(iii) $R$ is transitive because

$xRy\land{yRz}\Rightarrow{\exists{k,l}\in{\mathbb{Z}}: x-y=k.n\land{y-z=l.n}}$ $\Rightarrow{x-z=(x-y)+(y-z)=k.n+l.n=(k+l)n\land{k+l\in{\mathbb{Z}}}}\Rightarrow{xRz}$.

Consequently $R$ is an equivalence relation over $\mathbb{Z}$. We write $R=\sim_{n}$. Let’s examine the equivalence classes of this equivalence relation in case of $n=2$: For this, we will separately find the equivalence classes of the numbers $0$ and $1$. According to Theorem1, $\overline{0}\cap{\overline{1}}=\varnothing$ because $0\nsim_{2}1$. Let $x$ be an even integer. Since $\exists{k}\in{\mathbb{Z}}: x-0=2k$, then $x\sim_{2}0$. Hence, $x\in{\overline{0}}$. Now, let $x$ be an odd integer. Since $\exists{k}\in{\mathbb{Z}}: x-1=2k$, then $x\sim_{2}1$. Hence, $x\in{\overline{1}}$. If $2\mathbb{Z}$ and $2\mathbb{Z}+1$ denote the even integers and the odd integers respectively, then $\overline{0}=2\mathbb{Z}$ and $\overline{1}=2\mathbb{Z}+1$. There is no another equivalence class of this equivalence relation because any integer is either even or odd. Hence, according to Theorem1, $2\mathbb{Z}\cap{2\mathbb{Z}+1}=\varnothing$ and $2\mathbb{Z}\cup{2\mathbb{Z}+1}=\mathbb{Z}$. More generally, all the equivalence classes of the relation $\sim_{n}$ are $n\mathbb{Z}, n\mathbb{Z}+1, n\mathbb{Z}+2,\dots, n\mathbb{Z}+(n-1)$. Consequently, according to Theorem1, for all distinct ${k,l}\in{\{0,1,\dots,n-1\}}$,

$n\mathbb{Z}+k\cap{n\mathbb{Z}+l}=\varnothing$

and the following equality are true:

$\displaystyle{\bigcup_{k=1}^{n-1}(n\mathbb{Z}+k)=\mathbb{Z}}$

EXAMPLE2: Let $X$ be the set of all the lines lying on the plane. Since a line isn’t orthogonal to itself, the orthogonality isn’t an equivalence relation among all the lines.

EXAMPLE3: Let $R$ be the parallelism relation over the set of all the lines lying on the plane. I.e., $R=//$

(i) $R$ is reflexive because every line is parallel to itself.

(ii) $R$ is symmetric because $l_{1}//l_{2}\Rightarrow{ l_{2}//l_{1}}$.

(iii) $R$ is transitive because $l_{1}//l_{2}\land{ l_{2}//l_{3}}\Rightarrow{ l_{1}//l_{3}}$.

(Where $l_{1}, l_{2}, l_{3}$ are arbitrary lines on the plane)

Hence, the parallelism is an equivalence relation among all the lines.

EXAMPLE4: Let f be a function from $X$ to $Y$. Define $R\subset{X\times{X}}$ as $aRb\Leftrightarrow{f(a)=f(b)}$.

(i) $R$ is reflexive because $\forall{a}\in{X}, f(a)=f(a)\Rightarrow{aRa}$.

(ii) $R$ is symmetric because $aRb\Rightarrow{f(a)=f(b)}\Rightarrow{f(b)=f(a)}\Rightarrow{bRa}$.

(iii) $R$ is transitive because

$aRb\land{bRc}\Rightarrow{f(a)=f(b)\land{f(b)=f(c)}}\Rightarrow{f(a)=f(c)}\Rightarrow{aRc}$.

Hence, $R$ is an equivalence relation over the domain of the function $f$.

Theorem1 shows that all the equivalence classes of an equivalence relation over a non-empty set is a partition of this set. Now, we will show the opposite. I.e., we will prove that when it’s given a partition of a non-empty set, there is one and only one equivalence relation, the equivalence classes of which are the parts of the partition.

THEOREM2: Let $\{A_{i}\}_{i\in{I}}$ be a partition of a set $X$. (Where $I\ne{\varnothing}$, $X\ne{\varnothing}$ and $\forall{i\in{I}}, A_{i}\ne{\varnothing}$) Define $R\subset{X\times{X}}$ as $aRb\Leftrightarrow{\exists{i\in{I}}: a,b\in{A_{i}}}$. Then $R$ is an equivalence relation, the equivalence classes of which are the sets of the family $\{A_{i}\}_{i\in{I}}$.

PROOF: