Relacioni i ekuivalencës

Nga Wikibooks

Shko te: navigacion, 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.

Tabela e përmbajtjeve

[redaktoni] Përkufizimi i ekuivalencës

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

[redaktoni] 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 ~.

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

Ca\scriptstyle{=}{x\scriptstyle \midx\scriptstyle \inA\scriptstyle \landx~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.

[redaktoni] 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 Ca, Cb nuk janë disjunkte : Ca\scriptstyle { \cap }Cb \scriptstyle { \neq }\scriptstyle { \varnothing } . Atëherë del se :

(\scriptstyle{ \exists }c\scriptstyle \inA) c\scriptstyle \inCa\scriptstyle \landc\scriptstyle \inCb ,

nga marrim

a~c\scriptstyle \landc~b\scriptstyle { \Rightarrow } a~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 (\scriptstyle{ \forall }x\scriptstyle \inCa) x~a , andaj kemi:
x~a\scriptstyle \landa~b\scriptstyle { \Rightarrow } x~b\scriptstyle \Leftrightarrowx\scriptstyle \inCb ,

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

2 (\scriptstyle{ \forall }y\scriptstyle \inCb) y~b , andaj:
y~b\scriptstyle \landb~a\scriptstyle { \Rightarrow } y~a\scriptstyle { \Rightarrow } y\scriptstyle \inCa ,

d.m.th. CbInkluzion.PNGCa .

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

CaInkluzion.PNGCb\scriptstyle \landCbInkluzion.PNGCa\scriptstyle { \Rightarrow } Ca\scriptstyle{=}Cb .

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

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

(i) Refleksiv : (\scriptstyle{ \forall }x\scriptstyle \inA) x ρ x, sepse çdo x (\scriptstyle \inA) 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).

[redaktoni] Bashkësia e klasave të ekuivalencës

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

A/~ \scriptstyle{=}{Ca\scriptstyle \mida\scriptstyle \inA} (...28)

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

[redaktoni] Relacion i kongruencës

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

a ρ b\scriptstyle \Leftrightarrowa\scriptstyle{=}mq1+r\scriptstyle \landb\scriptstyle{=}mq2 +r, ku 0Mavogëlbarabart.PNGr<m

i cili mund të shprehet edhe kështu :

a ρ b\scriptstyle \Leftrightarrow(a - b)\vdotsm.

Meqë:

(1) (\scriptstyle{ \forall }a\scriptstyle \in\scriptstyle \mathbb{N}0) a ρ a ose (a-a)\vdotsm ;
(2) (\scriptstyle{ \forall }a, b\scriptstyle \in\scriptstyle \mathbb{N}0) 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}0) (a ρ b \scriptstyle \land b ρ c)\scriptstyle { \Rightarrow } a ρ c ose (a - b) \vdotsm \scriptstyle \land (b - c) \vdotsm\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}0 zbërthehet në këto m klasa të ekuivalencës :

Cr\scriptstyle{=}{n\scriptstyle \midn\scriptstyle \in\scriptstyle \mathbb{N}0 \scriptstyle \land n\scriptstyle{=}mq+r\scriptstyle \landq\scriptstyle \in\scriptstyle \mathbb{N}0 }, r\scriptstyle{=}0,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 \scriptstyle \mathbb{N}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 \scriptstyle{=} 3 kemi këto tri klasa:

(bl) C0\scriptstyle{=}{n\scriptstyle \midn\scriptstyle \in\scriptstyle \mathbb{N}0\scriptstyle \landn\scriptstyle{=}3q\scriptstyle \landq\scriptstyle \in\scriptstyle \mathbb{N}0 } ose C0\scriptstyle{=}{0,3,6,9,...},
(b2) C1\scriptstyle{=}{n\scriptstyle \midn\scriptstyle \in\scriptstyle \mathbb{N}0\scriptstyle \landn\scriptstyle{=}3q+1\scriptstyle \landq\scriptstyle \in\scriptstyle \mathbb{N}0} ose C1\scriptstyle{=}{1,4,7,10,...},
(b3) C2\scriptstyle{=}{n\scriptstyle \midn\scriptstyle \in\scriptstyle \mathbb{N}0\scriptstyle \landn\scriptstyle{=}3q+2\scriptstyle \landq\scriptstyle \in\scriptstyle \mathbb{N}0} ose C2\scriptstyle{=}{2,5,8,11,...},
(a1) (\scriptstyle{ \forall }n\scriptstyle \in\scriptstyle \mathbb{N}0) n\scriptstyle \inC0\scriptstyle \lorn\scriptstyle \inC1\scriptstyle \lorn\scriptstyle \inC2 ;
(a2) Ci\scriptstyle { \cap }Cj\scriptstyle{=}\scriptstyle { \varnothing }, \scriptstyle{ \forall }i \scriptstyle { \neq }j, i, j\scriptstyle{=}0, 1, 2 ;
(a3) \bigcup_{i=1}^n Ck\scriptstyle{=}\scriptstyle \mathbb{N}0

Pra: 4 \scriptstyle \equiv 7 (mod 3), 2 - 8 (mod 3), ndërsa 5 \scriptstyle \not \equiv 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).
Marrë nga "http://sq.wikibooks.org/wiki/Relacioni_i_ekuivalenc%C3%ABs"