ekvivalentsusrelatsiooni

Ekvivalentsusrelatsioon on relatsioon, mis on seti A peal refleksiivne, sümmeetriline ja transitiivne. See tähendab, et iga a ∈ A sobitab endaga a ~ a (refleksiivsus), kui a ~ b siis ka b ~ a (sümmeetria), ning kui a ~ b ja b ~ c, siis ka a ~ c (transitiivsus). Relatsiooni märgitakse tavaliselt tildega a ~ b või lihtsalt a ~ b.

Iga ekvivalentsusrelatsioon ~ määratleb ekvivalentsusklasside kogu: [a] = { x ∈ A | x ~ a }. Elementide omavaheline ühteseks kuuluvus defineerib, mida tähistatakse kui sama klassi kuuluvust. Ekvivalentsusklassid on omavahel mitteseotud ja katavad kogu A; iga element kuulub täpselt ühte klassi.

Quotientset A/~ kogub kokku kõik need ekvivalentsusklassid. See on kui A modifitseeritud “klasside tasandil”: iga a korral viitab projektsioon π(a) oma klassile [a]. Ekvivalentsusrelatsioon ja selle klasside jagunemine on seega tihedalt seotud: iga relatsioon ilmneb kui kollektiivne eraldamine, ning iga tunnistatud eraldamine (partition) määrab kindla ekvivalentsusrelatsiooni.

Näited: Z-saal, modulo n ekvivalentsusrelatsioon a ≡ b mod n, kui n jagub (a − b). Sellel relatsioonil on n ekvivalentsusklassi [0], [1], ..., [n−1], vastavalt jääkidele. Teine näide on triviaalne relatsioon a ~ b iff a = b, mis tekitab iga elemendi eraldi klassi.

Seetõttu on ekvivalentsusrelatsioonid ja nende klassid keskne tööriist algebrilises ja kombinatoorses mõtlemises, ühendades relatsioonid ja osad- või jaotabide mõisted.