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:
  1. x~y <=> [x]=[y] , &
  2. !(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.