Equivalentierelatie

Een equivalentierelatie is een binaire relatie op een verzameling die reflexief, symmetrisch en transitief is.

Motivatie

Een equivalentierelatie is een soort verfijning van de gelijkheidsrelatie. We kunnen altijd beslissen of twee elementen van een verzameling gelijk zijn, dus of a = b. Maar soms is het handig om vast te stellen of twee elementen alleen op elkaar lijken, en niet per se gelijk zijn. Oftewel: of ze een bepaalde belangrijke eigenschap gemeen hebben. Twee boeken kunnen we bijvoorbeeld op elkaar vinden lijken als ze hetzelfde genre hebben — of met behulp van equivalentie: twee boeken zijn equivalent als ze hetzelfde genre hebben.

Wat zouden we van zo'n equivalentie verwachten? We nemen een ander voorbeeld. Twee woorden lijken op elkaar / zijn equivalent als ze even lang zijn.

We zouden waarschijnlijk verwachten dat als we de gelijkenis van twee identieke woorden meten, er uitkomt dat ze op elkaar lijken. Voor alle woorden moet dus gelden dat ze op zichzelf lijken / equivalent zijn met zichzelf. In de taal van relaties: een equivalentierelatie moet reflexief zijn.

Als het woord “rivier” op het woord “Sophie” lijkt / equivalent is met “Sophie”, dan verwachten we zeker dat ook het woord “Sophie” equivalent is met het woord “rivier”. Met andere woorden: de volgorde doet er niet toe. In de taal van relaties: een equivalentierelatie moet symmetrisch zijn.

En tot slot: als het woord “dood” lijkt op / equivalent is met het woord “vink” en het woord “vink” equivalent is met het woord “poot”, dan verwachten we dat ook het paar woorden “dood” en “poot” equivalent is. Een equivalentierelatie moet dus ook transitief zijn.

Verder verwachten we niets van een equivalentie.

Voorbeelden

Nog meer voorbeelden van equivalenties:

• In dezelfde stad wonen. Bram woont zeker in dezelfde stad als Bram (reflexiviteit). Als Bram in dezelfde stad woont als Sem, dan woont ook Sem in dezelfde stad als Bram (symmetrie). En als Sem in dezelfde stad woont als Daan, dan woont ook Bram in dezelfde stad als Daan (transitiviteit).
• Liedjes met dezelfde maker. Het liedje “Noordenwind” heeft zeker dezelfde maker als het liedje “Noordenwind” (reflexiviteit). Als de liedjes “Noordenwind” en “Zilvermist” dezelfde maker hebben, dan hebben ook “Zilvermist” en “Noordenwind” dezelfde maker (symmetrie). En als “Zilvermist” en “Kleine golf” dezelfde maker hebben, dan hebben ook “Noordenwind” en “Kleine golf” dezelfde maker (transitiviteit).
• (a, b) ∈ R precies dan als a − b een even getal is; a, b zijn gehele getallen. Reflexiviteit: a − a = 0, nul is een even getal. Symmetrie: noem c = a − b. Dan is b − a = −(a − b) = −c. Als c even is, dan moet ook −c even zijn. Transitiviteit: noem p = a − b en verder q = b − c. We weten dat zowel p als q even getallen zijn. Nu moeten we bewijzen dat a − c een even getal is. In deze vergelijking vullen we voor c in c = b − q: a − (b − q), en dat is gelijk aan a − b + q. Uit de aannames weten we dat a − b een even getal is. Als we bij een even getal nog een even getal q optellen, krijgen we weer een even getal.
• Gelijkheid. Gelijkheid is een equivalentie, en tegelijk de kleinste equivalentie op een willekeurige verzameling M.

Triviale equivalentie

We hebben een niet-lege verzameling M. Wat is de kleinst mogelijke equivalentie R op de verzameling M? De kleinst mogelijke deelverzameling van het cartesisch product M × M is de lege verzameling ∅. Voldoet de lege verzameling aan de voorwaarden van een equivalentie?

Ze is zeker symmetrisch: omdat de relatie R geen elementen heeft, is aan de voorwaarde van symmetrie automatisch en triviaal voldaan. Net zo bij transitiviteit. Het probleem zit bij de reflexiviteit. De definitie zegt dat voor alle elementen x van de verzameling M geldt dat (x, x) ∈ R. Is hieraan voldaan? De verzameling M is niet leeg, dus ze bevat een element, bijvoorbeeld q. Zit het paar (q, q) in de relatie R? Nee. De relatie R is dus niet reflexief.

Wat is de kleinste relatie die reflexief is? De gelijkheidsrelatie. De relatie R moet minstens de paren (x, x) bevatten voor alle elementen van M. Dat is precies de identiteitsrelatie. Is zo'n relatie symmetrisch? Je ziet eenvoudig dat dat zo is. Net zo is gemakkelijk in te zien dat ze ook transitief is. De kleinste equivalentierelatie op een verzameling M is dus de identiteitsrelatie, die we noteren als id_M en die de paren (x, x) bevat voor alle x ∈ M.

Wat is de grootst mogelijke equivalentie op de verzameling M? De grootste deelverzameling is de hele verzameling M × M. Voldoet ze aan de voorwaarden van een equivalentie? Het is waarschijnlijk triviaal in te zien dat dat zo is.

Equivalentieklasse

Elke equivalentie verdeelt de verzameling M in een systeem van disjuncte verzamelingen, die we dan equivalentieklassen noemen.

We nemen de verzameling van alle woorden M en de equivalentie R “even lang zijn”. Dus (a, b) ∈ R precies dan als de woorden a en b even lang zijn. Deze equivalentie verdeelt de verzameling woorden in een aantal kleinere verzamelingen, die altijd woorden van dezelfde lengte bevatten. De afzonderlijke equivalentieklassen kunnen we onderscheiden met een subscript, die tegelijk de lengte van de woorden in die verzameling aangeeft:

• M₁ = {u, o, …}
• M₂ = {ik, je, we, in, op, …}
• M₃ = {een, het, zon, tak, …}
• M₄ = {dood, vink, poot, huis, …}
• …

Let op twee dingen: 1) de afzonderlijke verzamelingen zijn onderling disjunct, ze hebben geen enkel gemeenschappelijk element. 2) alle elementen in elke afzonderlijke verzameling zijn onderling equivalent. Alle woorden in de verzameling M₃ zijn onderling equivalent, omdat alle woorden lengte drie hebben, dus dezelfde lengte, en dat is de voorwaarde van de equivalentie.

Bovendien bepaalt elk element eenduidig zijn equivalentieklasse. Dat noteren we meestal met de notatie M[x], waarbij x ∈ M. Als we M[zon] schrijven, bepalen we daarmee eenduidig de equivalentieklasse die we al M₃ hadden genoemd.

Hoe vinden we eigenlijk de equivalentieklasse als we een x ∈ M kennen? We lopen alle elementen in M langs en kijken welke van die elementen equivalent zijn met het element x. Dat zijn alle elementen die deel uitmaken van de equivalentieklasse M[x].

Voor M[zon] zouden we alle woorden in M langslopen en in M₃ de woorden bewaren die lengte drie hebben.

Definitie en eigenschappen van een equivalentieklasse

We kunnen de equivalentieklasse zo definiëren. We hebben een verzameling M en daarop een gedefinieerde equivalentie R. Dan verstaan we onder de klasse van de partitie die het element x ∈ M bevat:

$$M[x]=\{y\in M;(x,y)\in R\}$$

De definitie zegt dat het alle y zijn die equivalent zijn met het gegeven element x. Omdat een equivalentierelatie reflexief is, komt op deze manier ook het element x zelf erin — want x is equivalent met zichzelf.

Onder de partitie van een equivalentie verstaan we dan de verzameling van alle equivalentieklassen. De partitie van de verzameling van alle woorden zou dus de verzameling {M₁, M₂, M₃, …} zijn.

Basiseigenschappen van equivalentieklassen:

• (a, b) ∈ R precies dan als M[a] = M[b]. Als we twee elementen a, b hebben die equivalent zijn, dan moeten hun equivalentieklassen gelijk zijn.
• Omgekeerd, als (a, b) ∈ R niet geldt, dan ook M[a] ≠ M[b], preciezer M[a] ∩ M[b] = ∅. Als we twee elementen hebben die niet equivalent zijn, dan zijn hun klassen van de partitie disjunct.
• De vereniging van alle equivalentieklassen moet de oorspronkelijke verzameling M geven: M₁ ∪ M₂ ∪ … ∪ M_n = M. (De voorgaande notatie geldt alleen voor een eindig aantal equivalentieklassen, maar in het algemeen kunnen het er oneindig veel zijn.)

Voorbeelden van partities bij een equivalentie

Het eerste voorbeeld, oneven en even getallen:

We nemen een eenvoudige equivalentie R gedefinieerd op de natuurlijke getallen N. (a, b) ∈ R precies dan als zowel a als b oneven is of zowel a als b even is. Voorbeelden van elementen: (1, 7), (13, 9), (4, 6), (8, 136). We bepalen nu de partitie van deze equivalentie in equivalentieklassen.

We beginnen stap voor stap. Waaraan is de klasse N[1] gelijk? We moeten alle getallen vinden die equivalent zijn met het getal een. Volgens de voorwaarde van de equivalentie zijn dat alle oneven getallen, dus N[1] = {1, 3, 5, 7, 9, …}.

Waaraan is de klasse N[2] gelijk? We vinden alle getallen die equivalent zijn met twee. Dat zijn alle even getallen: N[2] = {2, 4, 6, 8, 10, …}.

Nu N[3]. Welke getallen zijn equivalent met drie? Alle oneven getallen. Daarmee krijgen we dus de verzameling N[1], die we een paar alinea's terug hebben bepaald. Net zo voor N[4], daar weer de verzameling van de even getallen.

We zien dat daarna steeds dezelfde verzamelingen zouden terugkomen. Dat zie je ook doordat voor elk ander natuurlijk getal n dat we nemen al geldt dat n ∈ N[1] of n ∈ N[2]. Andere natuurlijke getallen dan oneven en even hebben we niet, dus deze twee verzamelingen vormen de partitie van de equivalentie.

Het is vergelijkbaar met een equivalentie op een verzameling mensen waarbij zowel a als b een man is of zowel a als b een vrouw is. Dan zouden we als partitie de verzameling van de vrouwen en de verzameling van de mannen krijgen.

Het tweede voorbeeld, absolute waarde:

We nemen een equivalentie R op de verzameling van de gehele getallen Z die als volgt is gedefinieerd: (a, b) ∈ R precies dan als |a| = |b|. (Die verticale strepen zijn de absolute waarde.) We gaan weer stap voor stap te werk:

• Z[0] = {0}. Nul staat alleen met nul in relatie.
• Z[1] = {−1, 1}. Een staat in relatie met een en met min een, want |1| = |−1|.
• Z[2] = {−2, 2}. Twee staat in relatie met twee en met min twee.
• Z[3] = {−3, 3}.
• …

Het is waarschijnlijk duidelijk hoe het verdergaat. De hele partitie is dus de verzameling klassen:

$$\{\{a,-a\};a\in {\mathbb{Z}}_0^{+}\}$$

(Dus alle paren a, −a, waarbij a een niet-negatief geheel getal is.) Je ziet dat er oneindig veel klassen zijn.