Page 76 - Echte wiskunde

64 P.W. Hemker Het begrip ‘binaire relatie’ kunnen we als volgt formaliseren9. We gaan uit van het Cartesisch
product V × V , dat is dus de verzameling van paren
{(u, v) | u ∈ V, v ∈ V } ,
Als we de relatie aangeven met R, dan is dus soms uRv waar en soms onwaar. De relatie R is dan ook volledig gekarakteriseerd door de deelverzameling van V × V waarvoor uRv waar is:
R = {(u, v) | u ∈ V, v ∈ V, uRv is waar} ⊂ V × V . Het is duidelijk dat uit uRv niet vRu hoeft te volgen.
Equivalentierelatie
Een binaire relatie R op V heet een equivalentierelatie als R aan de volgende eisen voldoet:
E1. ∀v∈V [vRv] , d.i. R is reflexief
E2. ∀u,v∈V [uRv ⇒ vRu], d.i. R is symmetrisch E3. ∀u,v,w∈V [uRv ∧ vRw ⇒ uRw], d.i. R is transitief.
We merken op dat de voorbeelden 1, 3 en 5 hierboven equivalentierelaties vormen (als men bij 5 tenminste twee samenvallende lijnen ook nog evenwijdig noemt). In voorbeeld 2: < is niet reflexief en niet symmetrisch, en ≤ is wel reflexief maar niet symmetrisch. In voorbeeld 4 is de relatie niet transitief.
Equivalentieklassen
Zij ∼ een equivalentierelatie op V . Is v een element van V , dan heet de verzameling {u | u ∈ V ∧ u ∼ v}
de equivalentieklasse van v. Uit E1, E2, E3 volgt dat equivalente elementen dezelfde equivalen- tieklasse hebben. Een deelverzameling van V heet een equivalentieklasse als het de equivalentie- klasse van een zekere v ∈ V is. Verder is gemakkelijk in te zien: De equivalentieklassen zijn twee aan twee disjunct en de vereniging van alle equivalentieklassen is V zelf.
Met de relatie ∼ correspondeert dus een z.g. klassenindeling van V , en wel zo, dat
u ∼ v ⇔ u en v liggen in dezelfde klasse. (2.4)
Gaat men omgekeerd uit van een klassenindeling van V , dan kan men een binaire relatie ∼ maken door (2.4) als definitie van ∼ te beschouwen. Laat zien, dat ∼ dan weer aan de drie eisen voor een equivalentierelatie voldoet.
Definitie door abstractie
Het komt in de wiskunde zeer vaak voor, dat men nieuwe begrippen vormt door in een bekende verzameling een equivalentie-relatie te beschouwen en vervolgens over de equivalentieklassen te gaan spreken. De equivalentieklassen zijn dan de nieuwe objecten. Een vertrouwd voorbeeld is de definitie van “aantal”. Men vormt daartoe een equivalentierelatie, waarbij “drie paarden”, “drie appels”, “drie centen”, ··· alle onderling equivalent zijn. De equivalentieklasse duidt men aan met het woord “drie”. Het aantal “drie” heet dan gedefinieerd door abstractie10.
9Formaliseren: op een precieze manier in een formule uitdrukken.
10abstractie, dwz “aftrekking”. Wat er afgetrokken is, zijn de woorden “paarden”, “appels”, “centen”, ···.