Relacije ekvivalencije, klase i kvocijentni skup
S Rekli smo da se binarna relacija zove RE (relacija ekvivalencije) ako je refleksivna, simetri~cna i tranzitivna. U tom slu~caju mo~zemo definirati jo~s neke pojmove, i uspostaviti vezu s ne~cim ~sto 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, ~cesto se i ona ispu~sta i govori se samo o klasi od x. [x]~~:={y@S:xry}.
S Zbog toga ~sto je ~~ RE, klase imaju razna dobra svojstva. Refleksivnost zna~ci da je svaki element u svojoj klasi. Simetri~cnost zna~ci da je svejedno gledamo li sve y koji su u relaciji s x, ili s kojima je x u relaciji ~ ina~ce bismo morati napraviti tu distinkciju. Tranzitivnost zapravo zna~ci da su klase me~dusobno disjunktne:
Pp Neka su [x] i [y] dvije klase ekvivalencije, relacije ~~ na univerzalnom skupu S. Doka~zite:
  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~can s obzirom na zamjenu x i y (~~ je simetri~cna), pa je dovoljno dokazati ("BSOMD":) samo jednu inkluziju. Neka to bude [x] C= [y].
Dakle, neka je z@[x] proizvoljan. z@[x] zna~ci 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, ~sto jest zbog x@[x] (refleksivnost).
(b'<=) Ako je [x]n[y] != 0, zna~ci da postoji neki z koji je u obje klase. Dakle, (E_z)(z~~x&z~~y). No tada po simetri~cnosti x~~z, ~sto sa z~~y daje po tranzitivnosti x~~y.
S Rekapitulirajmo: klase ekvivalencije su neprazne (refleksivnost), disjunktne su (ie, one koje su razli~cite ~ tj. one ~ciji 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~a). Po definiciji particije, vidimo da T klase ekvivalencije ~cine particiju.
D Ta particija, odnosno skup svih klas~a neke RE ~~ na skupu S, naziva se kvocijentni skup od S po ~~: S/~~:={[x]~~;x@S}. S Ono ~sto je zanimljivo je da vrijedi i obrat ~ od bilo koje particije mo~zemo do~ti do relacije ekvivalencije, ~ciji ~te 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.