Equivalence Relation

On September 18, 2010, in Analysis, by ufukkaya

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