Relacija ekvivalencije

Relacija ekvivalencije R na skupu A je binarna relacija koja je zapravo podskup kartezijevog produkta A x A sa sljedećim svojstvima:

• refleksivnost - svaki element a iz skupa A je u relaciji sam sa sobom, tj. aRa
• simetričnost- neka su a, b elementi iz skupa A, ako je aRb tada je i bRa
• tranzitivnost- neka su a, b, c elementi iz A, ako je aRb i bRc tada je aRc

Svaka relacija ekvivalencije dijeli skup na klase, tj. čini jednu particiju skupa, i svaka particija skupa stvara jednu relaciju ekvivalencije.

Klasa elementa a iz A označava se s [a], i a se naziva reprezentant klase, on nije jedinstven, dapače trivijalno je pokazati da je svejedno koji element uzmemo za reprezentanta klase, naravno iz te klase.

Klasa je skup svih elemenata koju su ekvivalentni po toj relaciji ekvivalencije tj. [a]={b iz A : aRb}

Još je važno naglasiti da za dvije klase [a], [b] iz relacije ekvivalencije R vrijedi ili [a]=[b] ili je [a] u presjeku sa [b] prazan skup, tj. nemaju niti jedan zajednički element.