Oops! It appears that you have disabled your Javascript. In order for you to see this page as it is meant to appear, we ask that you please re-enable your Javascript!
pornolar

Denklik Bağıntısı-Equivalence Relation

Denklik Bağıntısı-Equivalence Relation

TANIM1: X bir küme R\subset{X\times{X}} bir bağıntı olsun. Eğer R, yansıyan, simetrik ve geçişken bir bağıntı ise R'ye bir denklik bağıntısı denir ve genelde R=\sim biçiminde gösterilir.

TANIM2: \sim, X üzerinde bir denklik bağıntısı, a\in{X} olsun. \overline{a}=\{x\in{X}\text{ }\vert\text{ }a\sim{x}\}\subset{X}kümesine a'nın denklik sınıfı denir. a'nın denklik sınıfı bazı kaynaklarda [a]_{\sim} olarak da gösterilir. \forall{a}\in{X}, a\in{\overline{a}} olduğundan \overline{a}\ne{\emptyset}'dir.

TANIM3: \sim, X üzerinde bir denklik bağıntısı, a,b\in{X} olsun. Eğer b\in{\overline{a}} ise b'ye \overline{a} sınıfının bir temsilcisi denir.

ÖNERME1: \sim, X üzerinde bir denklik bağıntısı, a,b\in{X} olsun. Bu taktirde:

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

dir.

İSPAT:

TEOREM1: \sim, X üzerinde bir denklik bağıntısı olsun. Bu takdirde \{\overline{a}\text{ }\vert\text{ }a\in{X}\}\subset{\mathbf{P}(X)} kümelerailesi X'in bir ayrışımını verir.

İSPAT:

ÖRNEK1: n sabit bir pozitif tamsayı olsun. R\subset{\mathbb{Z}\times{\mathbb{Z}}} bağıntısını xRy\Leftrightarrow{n\mid{x-y}}\Leftrightarrow{\exists{k\in{\mathbb{Z}}}: x-y=kn} olarak tanımlayalım.

(i) \forall{x}\in{\mathbb{Z}}, x-x=0 ve n\mid{0} olduğundan xRx'tir. Dolayısıyla R yansıyandır.

(ii) xRy olsun. O halde \exists{k\in{\mathbb{Z}}}: x-y=kn \Rightarrow{y-x=(-k)n} ve -k\in{\mathbb{Z}} olduğundan yRx'tir. Dolayısıyla R simetriktir.

(iii) xRy ve yRz olsun. O halde \exists{k,l\in{\mathbb{Z}}}: x-y=kn ve y-z=ln \Rightarrow{x-z=(x-y)+(y-z)=kn+ln=(k+l)n} ve k+l\in{\mathbb{Z}} olduğundan xRz'dir. Dolayısıyla R geçişkendir.

O halde R bir denklik bağıntısıdır. Bu denklik bağıntısını R=\sim_{n} olarak gösterelim. Şimdi n=2durumunda bu bağıntının denklik sınıflarını inceleyelim. 0\in{\mathbb{Z}} ve 1\in{\mathbb{Z}} elemanlarının denklik sınıflarını bulalım. Teorem1'e göre biliyoruz ki 0\nsim_{2}1 olduğundan \overline{0}\cap{\overline{1}}=\emptyset'dir. x\in{\mathbb{Z}} bir çift sayı olsun. 2\mid{x-0} olduğundan x\sim_{2}0'dır. y\in{\mathbb{Z}} bir tek sayı olsun. 2\mid{y-1} olduğundan y\sim_{2}1'dir. Çift sayılar kümesini 2\mathbb{Z} ile, tek sayılar kümesini de 2\mathbb{Z}+1 ile gösterirsek \overline{0}=2\mathbb{Z} ve \overline{1}=2\mathbb{Z}+1'dir. Tüm tamsayılar ya 0'a ya da 1'e denk olduğundan tamsayılar kümesinde bu bağıntının başka bir denklik sınıfı yoktur. O halde Teorem1'e göre 2\mathbb{Z}\cap{2\mathbb{Z}+1}=\emptyset ve 2\mathbb{Z}\cup{2\mathbb{Z}+1}=\mathbb{Z}'dir. Daha genel olarak \sim_{n} bağıntısının denklik sınıfları n\mathbb{Z}, n\mathbb{Z}+1, n\mathbb{Z}+2,\dots, n\mathbb{Z}+(n-1)'dir. Dolayısıyla Teorem1'e göre k\ne{l} olan \forall{k,l}\in{\{0,1,\dots,n-1\}},

(n\mathbb{Z}+k)\cap{(n\mathbb{Z}+l})=\emptyset

ve

\displaystyle{\bigcup_{k=0}^{n}(n\mathbb{Z}+k)=\mathbb{Z}}

dir.

ÖRNEK2: X ile düzlemdeki tüm doğruları gösterelim. R\subset{X\times{X}} doğrular arasındaki diklikbağıntısı olsun. Doğrular kendilerine dik olmadığından R bir denklik bağıntısı değildir.

ÖRNEK3: X ile düzlemdeki tüm doğruları gösterelim. R\subset{X\times{X}} doğrular arasındaki paralellik bağıntısı olsun.

(i) \forall{d}\in{X}, d//d olduğundan R yansıyan,

(ii) d_{1}, d_{2}'ye paralel ise d_{2} de d_{1}'e paralel olduğundan R simetrik,

(iii) d_{1}, d_{2}'ye ve d_{2}, d_{3}'e paralel ise d_{1}d_{3}'e paralel olduğundan R geçişkendir. Dolayısıyla düzlemdeki doğrular arasındaki paralellik bağıntısı bir denklik bağıntısıdır.

ÖRNEK4: X,Y herhangi iki küme, f:X\rightarrow{Y} bir fonksiyon olsun. R\subset{X\times{X}} bağıntısını aRb\Leftrightarrow{f(a)=f(b)} olarak tanımlayalım.

(i) \forall{a}\in{X}, f(a)=f(a)\Rightarrow{aRa} olduğundan R yansıyan,

(ii) aRb\Rightarrow{f(a)=f(b)}\Rightarrow{f(b)=f(a)}\Rightarrow{bRa} olduğundan R simetrik,

(iii) aRb\land{bRc}\Rightarrow{f(a)=f(b)\land{f(b)=f(c)}}\Rightarrow{f(a)=f(c)}\Rightarrow{aRc} olduğundan Rgeçişkendir.

O halde R bir denklik bağıntısıdır.

Teorem1'de gösterdik ki boştan farklı bir küme üzerindeki bir denklik bağıntısının denklik sınıfları o kümenin boştan farklı bir parçalanışını verir. Şimdi ise bunun tersini gösterelim. Yani boştan farklı bir kümenin boştan farklı bir parçalanışı verildiğinde o parçalanışı denklik sınıfları kabul eden bir denklik bağıntısının varlığını ispat edelim:

TEOREM2: X\ne{\emptyset} bir küme, I\ne{\emptyset} bir indis kümesi, \{A_{i}\}_{i\in{I}} ailesi X'in bir parçalanışı olsun ve \forall{i\in{I}}, A_{i}\ne{\emptyset} sağlansın. R\subset{X\times{X}} bağıntısını,  a,b\in{X} olmak üzere aRb\Leftrightarrow{\exists{i\in{I}}: a,b\in{A_{i}}} olarak tanımlayalım. Bu takdirde R, denklik sınıfları \{A_{i}\}_{i\in{I}} ailesi olan bir denklik bağıntısıdır.

 

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 everya\in{X}. The family of all the equivalence classes of the relation \sim is called the “quotient set” of Xby \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}}.

Share this post

Bir cevap yazın