Relacioni i ekuivalencës

Nga Wikibooks
Shko tek: lundrim, kërko
Jeni duke lexuar pjesë nga libri në punim e sipër:
Algjebra e përgjithëshme

Shkalla UNI
Gjykimet

Bashkësitë

Relacionet

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[redakto]

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

Simboli i përgjithëshem[redakto]

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[redakto]

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 aA, atëhetë elementet e bashkësisë A që janë ekuivalent me elementin a (d.m.th. xA x~a) formojnë nënbashkësinë

Ca{xxAx~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[redakto]

Ç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 Ca, Cb nuk janë disjunkte : CaCb . Atëherë del se :

(cA) cCacCb ,

nga marrim

a~cc~ba~b,

meqë relacioni ~ është transitiv.

Tani, në bazë të formulës së përftuar a~b, mund të provojmë se CaInkluzion.PNGCb dhe CbInkluzion.PNGCa . Vërtet:

1 (xCa) x~a , andaj kemi:
x~aa~bx~bxCb ,

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

2 (yCb) y~b , andaj:
y~bb~ay~ayCa ,

d.m.th. CbInkluzion.PNGCa .

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

CaInkluzion.PNGCbCbInkluzion.PNGCaCaCb .

Pra, nga supozimi CaCb del se klasat e ekuivalencës Ca, Cb nuk janë të ndryshme (CaCb) , andaj konkludojmë se pohimi i parë i teoremës është i saktë.

b) Për të vërtetuar pohimin e anasjelltë supozojmë se Ca, Cb, Cc... 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 A) x ρ y (!Ct, x, y Ct) .

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

(i) Refleksiv : (xA) x ρ x, sepse çdo x (A) i përket njërës klasë të ekuivalencës Ca, Cb, Cc,... ;
(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ë Ca, Cb, Cc,... , 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[redakto]

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

A/~ {CaaA} (...28)

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

Relacion i kongruencës[redakto]

Në bashkësinë e zgjeruar të numrave, natyralë 0 ({0}) është përkufizuar relacioni binar ρ me :

a ρ bamq1+rbmq2 +r, ku 0Mavogëlbarabart.PNGr<m

i cili mund të shprehet edhe kështu :

a ρ b(a - b)m.

Meqë:

(1) (a0) a ρ a ose (a-a)m ;
(2) (a, b0) a ρ b b ρ a ose (a - b) m (b - a) m ;
(3) (a, b, c0) (a ρ b b ρ c)a ρ c ose (a - b) m (b - c) m(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 b (mod m).

Me relacionin e kongruencës sipas modulit m bashkësia 0 zbërthehet në këto m klasa të ekuivalencës :

Cr{nn0 nmq+rq0 }, r0,1,2,...,m-1

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

Të konkludojmë : bashkësia 0 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 C0 , C1, C2 ,..., Cm-1 ngandonjëherë shënohen me : (0), (1), (2),... , (m -1) .

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

(bl) C0{nn0n3qq0 } ose C0{0,3,6,9,...},
(b2) C1{nn0n3q+1q0} ose C1{1,4,7,10,...},
(b3) C2{nn0n3q+2q0} ose C2{2,5,8,11,...},
(a1) (n0) nC0nC1nC2 ;
(a2) CiCj, ij, i, j0, 1, 2 ;
(a3) Ck0

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


  1. Matematika I dhe II i Entit të Teksteve dhe Mjeteve Mësimore të KSA të Kosovës, Fakulteti Teknik në Prishtinë (1979).