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:

Leave a Reply

Your email address will not be published. Required fields are marked *