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$\scriptstyle \in$A, atëhetë elementet e bashkësisë A që janë ekuivalent me elementin a (d.m.th. $\scriptstyle {\forall }$x$\scriptstyle \in$A x~a) formojnë nënbashkësinë

C_a$\scriptstyle {=}${x$\scriptstyle \mid$x$\scriptstyle \in$A$\scriptstyle \land$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$\scriptstyle {\cap }$C_b$\scriptstyle {\neq }$$\scriptstyle {\varnothing }$ . Atëherë del se :

($\scriptstyle {\exists }$c$\scriptstyle \in$A) c$\scriptstyle \in$C_a$\scriptstyle \land$c$\scriptstyle \in$C_b ,

nga marrim

a~c$\scriptstyle \land$c~b$\scriptstyle {\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 ($\scriptstyle {\forall }$x$\scriptstyle \in$C_a) x~a , andaj kemi:

x~a$\scriptstyle \land$a~b$\scriptstyle {\Rightarrow }$x~b$\scriptstyle \Leftrightarrow$x$\scriptstyle \in$C_b ,

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

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

y~b$\scriptstyle \land$b~a$\scriptstyle {\Rightarrow }$y~a$\scriptstyle {\Rightarrow }$y$\scriptstyle \in$C_a ,

d.m.th. C_bC_a .

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

C_aC_b$\scriptstyle \land$C_bC_a$\scriptstyle {\Rightarrow }$C_a$\scriptstyle {=}$C_b .

Pra, nga supozimi C_a$\scriptstyle {\cap }$C_b del se klasat e ekuivalencës C_a, C_b nuk janë të ndryshme (C_a$\scriptstyle {=}$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 $\scriptstyle \in$ A) x ρ y $\scriptstyle \Leftrightarrow$ ($\scriptstyle {\exists }$!C_t, x, y $\scriptstyle \in$ C_t) .

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

(i) Refleksiv : ($\scriptstyle {\forall }$x$\scriptstyle \in$A) x ρ x, sepse çdo x ($\scriptstyle \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/~ $\scriptstyle {=}${C_a$\scriptstyle \mid$a$\scriptstyle \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ë $\scriptstyle \mathbb {N}$₀ ($\scriptstyle {=}$$\scriptstyle \mathbb {N}$$\scriptstyle {\cup }${0}) është përkufizuar relacioni binar ρ me :

a ρ b$\scriptstyle \Leftrightarrow$a$\scriptstyle {=}$mq₁+r$\scriptstyle \land$b$\scriptstyle {=}$mq₂ +r, ku 0r<m

i cili mund të shprehet edhe kështu :

a ρ b$\scriptstyle \Leftrightarrow$(a - b)$\vdots$m.

Meqë:

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

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

(3) ($\scriptstyle {\forall }$a, b, c$\scriptstyle \in$$\scriptstyle \mathbb {N}$₀) (a ρ b $\scriptstyle \land$ b ρ c)$\scriptstyle {\Rightarrow }$a ρ c ose (a - b) $\vdots$m $\scriptstyle \land$ (b - c) $\vdots$m$\scriptstyle {\Rightarrow }$(a - c) $\vdots$ m,

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

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

C_r$\scriptstyle {=}${n$\scriptstyle \mid$n$\scriptstyle \in$$\scriptstyle \mathbb {N}$₀ $\scriptstyle \land$ n$\scriptstyle {=}$mq+r$\scriptstyle \land$q$\scriptstyle \in$$\scriptstyle \mathbb {N}$₀ }, r$\scriptstyle {=}$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 $\scriptstyle \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 $\scriptstyle {=}$ 3 kemi këto tri klasa:

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

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

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

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

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

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

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

---