Relacije ekvivalencije, klase i kvocijentni skup
S Rekli smo da se binarna relacija zove RE (relacija
ekvivalencije) ako je refleksivna, simetrična i tranzitivna.
U tom slučaju možemo definirati još neke pojmove, i uspostaviti vezu
s nečim što smo radili prije, s particijama.
Da vidimo...
D Neka je ~
RE na skupu S
i neka je
x@S
. Skup svih y@S
koji su u relaciji s
x
zove se klasa ekvivalencije
(od x
, po relaciji ~
), ili jednostavno
klasa od x
po ~
. Ako se radi samo o
jednoj RE, često se i ona ispušta i govori se samo o klasi od
x
.
[x]~:={y@S:xry}
.
S Zbog toga što je ~
RE, klase imaju razna dobra
svojstva. Refleksivnost znači da je svaki element u svojoj klasi.
Simetričnost znači da je svejedno gledamo li sve y
koji
su u relaciji s x
, ili s kojima je x
u
relaciji – inače bismo morati napraviti tu distinkciju. Tranzitivnost
zapravo znači da su klase međusobno disjunktne:
Pp Neka su [x]
i
[y]
dvije klase ekvivalencije,
relacije ~
na univerzalnom skupu S
.
Dokažite:
x~y <=> [x]=[y] , &
!(x~y) <=> [x]n[y]=0
Rj (a=>) Neka je x~y
. Treba dokazati jednakost
dva skupa, [x]
i [y]
. No jasno je da je
zadatak simetričan s obzirom na zamjenu x
i y
(~
je simetrična), pa je dovoljno dokazati ("BSOMD":)
samo jednu inkluziju. Neka to bude [x] C= [y]
.
Dakle, neka je z@[x]
proizvoljan. z@[x]
znači
z~x
, a imamo pretpostavku x~y
. Po
tranzitivnosti, z~y
, odnosno z@[y]
.
(a<=) Ovo je zgodan dokaz: pretpostavimo [x]=[y]
. No tada
je x@[x]
zbog refleksivnosti, pa i x@[y]
jer
je to jedna te ista klasa. Dakle, x~y
.
Za dokaz (b), primijetimo da su tvrdnje ekvivalentne ako su im negacije
ekvivalentne. Dakle, dovoljno je dokazati
(b') x~y <=> [x]n[y] != 0
.
(b'=>) Ako je x~y
, vidjeli smo u (a) da su
[x]
i [y]
ista klasa, pa se stvar svodi na
dokazivanje da je [x]n[x]=[x]
neprazna, što jest
zbog x@[x]
(refleksivnost).
(b'<=) Ako je [x]n[y] != 0
, znači da postoji neki
z
koji je u obje klase. Dakle,
(E_z)(z~x&z~y)
. No tada po simetričnosti
x~z
, što sa z~y
daje po tranzitivnosti
x~y
.
S Rekapitulirajmo: klase ekvivalencije su neprazne
(refleksivnost), disjunktne su (ie, one koje su različite – tj. one
čiji generatori nisu u relaciji), i u uniji daju cijeli univerzalni
skup (jer je svaki element u nekoj (konkretno, svojoj) klasi, pa time i
u uniji svih klasā). Po definiciji particije, vidimo da T
klase ekvivalencije čine particiju.
D Ta particija, odnosno skup svih klasā neke RE
~
na skupu S
, naziva se kvocijentni skup
od S
po ~
:
S/~:={[x]~;x@S}
.
S Ono što je zanimljivo je da
vrijedi i obrat – od bilo koje particije možemo doći do relacije
ekvivalencije, čiji će kvocijentni skup biti upravo polazna
particija:
T Neka je P:={Bi;i@I}
neka particija
univerzalnog skupa S
. Definiramo relaciju
~:S--S
s
x~y:<=>(E_i@I)({x,y}C=Bi)
. Tada je
~
RE, i S/~=P
.