Relacioni i ekuivalencës

Jeni duke lexuar pjesë nga libri në punim e sipër: Algjebra e përgjithëshme

Shkalla UNI

Gjykimet Bashkësitë Relacionet Kuptimi i tyre Relacionet binare Relacioni i ekuivalencës Relacioni i renditjes Relacionet ndërmjet dy bashkësive Pasqyrimet Veprimet binare Grupi dhe nëngrupi Unaza, Trupi dhe Fusha

Relacione më të rëndësishme të ekuivalencës janë : barazia, paralelshmëria, kongruenca dhe ngjashmëria.

Përkufizimi i ekuivalencës

Relacion binar ρ në A quhet relacion i ekuivalencës, nëse është refleksiv, simetrik dhe transitiv.

Simboli i përgjithëshem

Relacionet e ekuivalencës luajnë një rol të rëndësishëm në matematikë dhe shënohen me një simbol të përbashkët ~.

Klaset e ekuivalencës

Relacioni i ekuivalencës ~ i përkufizuar në bashkësinë A e zbërthen atë në nënbashkësi që quhen klaset e ekuivalencës. Kështu, nëse a$\in$A, atëhetë elementet e bashkësisë A që janë ekuivalent me elementin a (d.m.th. $\mathrm{\forall }$x$\in$A x~a) formojnë nënbashkësinë

C_a$=${x$\mid$x$\in$A$\wedge$x~a}, (...27)

e cila quhet klasa e ekuivalencës ~ me përfaqësuesin a.

Kur bashkësia A, lidhur me ekuivalencën ~, zbërthehet në klasa, atëherë:

1. Çdo element i bashkësisë A i përket një klase ;
2. Asnjë element nuk u përket dy klasave të ndryshme ; dhe
3. Unioni i të gjitha klasave është i barabartë me bashkësinë A.

Pra konkludojmë se klasat e ekuivalencës janë disjunkte ndërmjet tyre.

Teorema e klasave

Çdo ekuivalencë ~ në bashkësinë A e përkufzon një zbërthim të A-së në klasa të ekuivalencës dhe e anasjellta, çdo zbërthim të bashkësisë A në klasa të ekuivalencës e përkufzon një relacion të ekuivalencës në bashkësinë A.

V ë r t e t i m : a) Le të supozojmë të kundërtën - se dy klasa të ndryshme C_a, C_b nuk janë disjunkte : C_a$\cap$C_b$\ne$$\varnothing$ . Atëherë del se :

($\mathrm{\exists }$c$\in$A) c$\in$C_a$\wedge$c$\in$C_b ,

nga marrim

a~c$\wedge$c~b$\Rightarrow$a~b,

meqë relacioni ~ është transitiv.

Tani, në bazë të formulës së përftuar a~b, mund të provojmë se C_aC_b dhe C_bC_a . Vërtet:

1 ($\mathrm{\forall }$x$\in$C_a) x~a , andaj kemi:

x~a$\wedge$a~b$\Rightarrow$x~b$\iff$x$\in$C_b ,

çka, sipas përkufizimit 2.1.1., del se C_aC_b ;

2 ($\mathrm{\forall }$y$\in$C_b) y~b , andaj:

y~b$\wedge$b~a$\Rightarrow$y~a$\Rightarrow$y$\in$C_a ,

d.m.th. C_bC_a .

Në fund, në bazë të përkufizimit 2.1.3., marrim :

C_aC_b$\wedge$C_bC_a$\Rightarrow$C_a$=$C_b .

Pra, nga supozimi C_a$\cap$C_b del se klasat e ekuivalencës C_a, C_b nuk janë të ndryshme (C_a$=$C_b) , andaj konkludojmë se pohimi i parë i teoremës është i saktë.

b) Për të vërtetuar pohimin e anasjelltë supozojmë se C_a, C_b, C_c... paraqet një zbërthim çfarëdo të bashkësisë A në klasa të ekuivalencës ... Në bashkësinë A e përkufizojmë relacionin binar ρ në këtë mënyrë : Për elementet

(x, y $\in$ A) x ρ y $\iff$ ($\mathrm{\exists }$!C_t, x, y $\in$ C_t) .

Relacioni binar ρ , i përkufizuar në këtë mënyrë, është relacion i ekuivalencës, sepse është

(i) Refleksiv : ($\mathrm{\forall }$x$\in$A) x ρ x, sepse çdo x ($\in$A) i përket njërës klasë të ekuivalencës C_a, C_b, C_c,... ;

(ii) Simetrik : Ngase kur x ρ y, atëherë edhe y ρ x, meqë kur elementet e dyshes (x, y) i përkasin njërës klasë C_a, C_b, C_c,... , asaj klase i përkasin edhe elementet e dyshes (y, x) ; dhe

(iii) Transitiv : Nga se kur x ρ y dhe y ρ z, atëherë edhe x ρ z, meqë kur elementet e dysheve (x, y) dhe (y, z) i përkasin njërës klasë të ekuivalencës, asaj klase u përkasin edhe elementet e dyshes (x, z).

Bashkësia e klasave të ekuivalencës

Bashkësia e klasave të ekuivalencës ~ shënohet me

A/~ $=${C_a$\mid$a$\in$A} (...28)

dhe quhet faktor-bashkësi e bashkësisë A në lidhje me ekuivalencën

Relacion i kongruencës

Në bashkësinë e zgjeruar të numrave, natyralë $\mathbb{N}$₀ ($=$$\mathbb{N}$$\cup${0}) është përkufizuar relacioni binar ρ me :

a ρ b$\iff$a$=$mq₁+r$\wedge$b$=$mq₂ +r, ku 0r<m

i cili mund të shprehet edhe kështu :

a ρ b$\iff$(a - b)$⋮$m.

Meqë:

(1) ($\mathrm{\forall }$a$\in$$\mathbb{N}$₀) a ρ a ose (a-a)$⋮$m ;

(2) ($\mathrm{\forall }$a, b$\in$$\mathbb{N}$₀) a ρ b $\Rightarrow$ b ρ a ose (a - b)$⋮$ m $\Rightarrow$ (b - a) $⋮$ m ;

(3) ($\mathrm{\forall }$a, b, c$\in$$\mathbb{N}$₀) (a ρ b $\wedge$ b ρ c)$\Rightarrow$a ρ c ose (a - b) $⋮$m $\wedge$ (b - c) $⋮$m$\Rightarrow$(a - c) $⋮$ m,

konkludojmë se ρ është relacion i ekuivalencës. Ky relacion quhet relacion i kongruencës sipas modulit m dhe shënohet me a $\equiv$ b (mod m).

Me relacionin e kongruencës sipas modulit m bashkësia $\mathbb{N}$₀ zbërthehet në këto m klasa të ekuivalencës :

C_r$=${n$\mid$n$\in$$\mathbb{N}$₀ $\wedge$ n$=$mq+r$\wedge$q$\in$$\mathbb{N}$₀ }, r$=$0,1,2,...,m-1

ku secila klasë karakterizohet me vlerën e mbetjes r. Pra, klasën C_r e përbëjnë të gjithë numrat natyralë të cilët kur pjesëtohen me m japin mbetjen r, andaj C_r quhet edhe klasa e mbetjes r.

Të konkludojmë : bashkësia $\mathbb{N}$₀ në lidhje me relacionin e kongruencës sipas modulit m zbërthehet në m klasa : në klasën e mbetjes 0, në klasën e mbetjes 1,... , në klasën e mbetjes m-1. Klasat C₀ , C₁, C₂ ,..., C_m-1 ngandonjëherë shënohen me : (0), (1), (2),... , (m -1) .

Për m $=$ 3 kemi këto tri klasa:

(bl) C₀$=${n$\mid$n$\in$$\mathbb{N}$₀$\wedge$n$=$3q$\wedge$q$\in$$\mathbb{N}$₀ } ose C₀$=${0,3,6,9,...},

(b2) C₁$=${n$\mid$n$\in$$\mathbb{N}$₀$\wedge$n$=$3q+1$\wedge$q$\in$$\mathbb{N}$₀} ose C₁$=${1,4,7,10,...},

(b3) C₂$=${n$\mid$n$\in$$\mathbb{N}$₀$\wedge$n$=$3q+2$\wedge$q$\in$$\mathbb{N}$₀} ose C₂$=${2,5,8,11,...},

(a₁) ($\mathrm{\forall }$n$\in$$\mathbb{N}$₀) n$\in$C₀$\vee$n$\in$C₁$\vee$n$\in$C₂ ;

(a₂) C_i$\cap$C_j$=$$\varnothing$, $\mathrm{\forall }$i$\ne$j, i, j$=$0, 1, 2 ;

(a₃) $\bigcup _{i=1}^n$ C_k$=$$\mathbb{N}$₀

Pra: 4 $\equiv$ 7 (mod 3), 2 - 8 (mod 3), ndërsa 5 $\equiv ̸$7 (mod 3).

---