equivalentierelaties

Een equivalentierelatie op een verzameling A is een relatie R ⊆ A×A die reflexief, symmetrisch en transitief is. Met aRb wordt aangeduid dat a gerelateerd is aan b. In het bijzonder geldt aRa voor elk a ∈ A.

Voor elk a ∈ A is de equivalentieklasse [a] = { x ∈ A | aRx } de verzameling van alle elementen die met a in relatie staan. Deze klassen zijn onderling disjunct en hun vereniging is A; zij vormen daarmee een partitie van A. De relatie R wordt volledig bepaald door deze partitie, en omgekeerd levert elke partitie van A een equivalentierelatie op: x ~ y als x en y in dezelfde blok van de partitie zitten.

De verzameling van alle equivalentieklassen wordt de quotiëntverzameling A/R (of A/~) genoemd. Het levert vaak een vereenvoudigde structuur op. Voorbeeld: x ≡ y (mod n) op de gehele getallen. [r] bevat dan alle gehele getallen congruent aan r modulo n; er zijn precies n verschillende klassen en de quotiëntverzameling is {0,1,...,n-1}.