Relacionet e ekuivalencës

Relacionet e ekuivalencës janë shumë të rëndësishme në matematikë dhe shkenca kompjuterike.Një ndër arsyet është se kur në një relacion të ekuivalencës dy elemente janë të lidhura ,ka kuptim të themi se ato elemente janë ekuivalente.

Përkufizimi

• Relacioni binar R quhet relacion i ekuivalencës në bashkësinë A nëse ai është:
  1. Refleksiv
  2. Simetrik
  3. Tranzitiv

1)Relacioni refleksiv:

Relacioni binar R në bashkësinë A quhet refleksiv nëse:

$\forall$x$\in$A, (x , x)$\in$ R

2)Relacioni simetrik

Relacioni binar R në bashkësinë A quhet simetrik nëse:

(x , y)$\in$R $\Rightarrow$ (y , x)$\in$R

3)Relacioni tranzitiv

Relacioni binar R në bashkësinë A quhet tranzitiv nëse:

((x , y)$\in$R $\land$(y , z)$\in$R) $\Rightarrow$ (x , z)$\in$R

Shembuj

• Le të jetë dhënë bashkësia A={1,2,3,4} dhe një relacion R={(1,1),(1,3),(2,2),(2,4),(3,1),(3,3),(4,2),(4,4)} në bashkësinë A .Tregoni se a është R relacion i ekuivalencës.

Zgjidhje:

Atëherë R është refleksiv sepse i përmbanë dyshet (1,1),(2,2),(3,3),(4,4) d.m.th për çdo x element i A , (x,x) është element i relacionit.

R është simetrik sepse nëse xRy atëherë edhe yRx .Në rastinë tonë kemi : (1,3)$\in$R => (3,1)$\in$R , (2,4)$\in$R => (4,2)$\in$R .

R është tranzitiv sepse nëse xRy dhe yRz atëhere edhe xRz ,Në rastinë tonë kemi : ((1,3)$\in$R dhe (3,1)$\in$R) => (1,1)$\in$R , ((2,4)$\in$R dhe (4,2)$\in$R) => (2,2)$\in$R ....etj.

Pasi që relacioni R është refleksiv,simetrik dhe tranzitiv atëherë R është një relacion i ekuivalenës.

Relacione të ndryshme të ekuivalencës

Relacionet e mëposhtme janë të gjitha relacione të ekuivalencës:

• "është e barabartë me" në bashkësinë e numrave.
• "ka ditëlindjen e njejtë me" në bashkësinë e njerëzve.
• "ka të njejtën vlerë absolute me" në bashkësinë e numrave real.

Relacione të ndryshme të cilat nuk janë relacione të ekuivalencës

• Relacioni ">" në mes të dy numrave real sepse ky relacion është refleksiv dhe tranzitiv por jo simetrik,për shembull 7>5 nuk është njësoj si 5>7
• "Ka pjestues të përbashkët më të madh se 1 me " në mes të numrave natyrorë më të mëdhenj se 1 sepse ky relacion është refleksiv dhe simetrik por jo tranzitiv, për shembull 2 dhe 6 e kanë një pjestues të përbashkët më të madh se 1 , 6 dhe 3 e kanë një pjestues të përbashkët më të madh se 1, mirëpo 2 dhe 3 nuk kanë pjestuesë të përbashkët më të madh se 1.