Relatie (wiskunde)

Uit Wikipedia, de vrije encyclopedie

In de wiskunde en logica is een relatie de abstractie van wat in het algemeen een verband of betrekking tussen dingen, objecten, aangeeft. Een relatie toont het verband dat tussen twee (of meer) verzamelingen bestaat, door aan te geven welke elementen van de betrokken verzamelingen bij de relatie betrokken zijn, en hoe deze elementen zich tot elkaar verhouden. Daarmee is een relatie eenvoudig gedefinieerd als een verzameling van koppels of n-tupels.

[bewerk] Definitie

In formele zin wordt een relatie gedefinieerd als een verzameling van tupels, rijtjes van elementen, ieder uit een van de verzamelingen waarop de relatie gedefinieerd is. De relatie is dus een deelverzameling van het Cartesisch product van de betrokken verzamelingen.

[bewerk] Voorbeeld 1

De relatie "vrouw van", tussen de verzamelingen vrouwen (V) en mannen (M), is een deelverzameling van de paren V × M, en wel:

"vrouw van" = $\{(v,m) \in V \times M \mid v\ en\ m\ zijn\ gehuwd\}$

Het is gebruikelijk om "v is vrouw van m" te schrijven in plaats van (v,m) ∈ "vrouw van".

[bewerk] Voorbeeld 2

De relatie < ("kleiner dan") tussen reële getallen is een deelverzameling van de paren R × R, en wel:

"<" = $\{(x,y) \in R \times R \mid x < y\}$ .

Het is gebruikelijk om "x < y" te schrijven in plaats van "(x,y) ∈ <".

[bewerk] Voorbeeld 3

Een ander voorbeeld is de relatie "gelijkheid" op de verzameling {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Formeel kunnen we deze relatie (laten we hem R noemen) als volgt beschrijven:

$R = \{(0,0), (1,1), (2,2), (3,3), (4,4), (5,5), (6,6), (7,7), (8,8), (9,9)\}_{}^{}$

We zien dat:

$R \subset \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\} \times \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$

In het paar (0,0) hoort de eerste 0 bij de "linker" verzameling, de andere 0 bij de "rechter". Elementen van paren in de verzameling horen tot de gelijkheidsrelatie, paren die er niet in zitten niet. Zo is 2 gelijk aan 2, 3 niet gelijk aan 4.

In het algemeen kan een relatie tussen twee of meer verzamelingen gedefinieerd worden -- deze verzamelingen hoeven niet alle verschillend te zijn (zoals een relatie tussen twee "dezelfde" verzamelingen). Een relatie tussen twee verzamelingen wordt een binaire relatie genoemd. In zo'n binaire relatie heet de "linker" verzameling het domein, de "rechter" verzameling het bereik van de relatie.

Meestal hebben relaties namen of symbolen om de relatie aan te duiden. Een aantal zeer bekende relatoren (namen van relaties) zijn $<, \leq, =, \equiv, \geq, >, \Rightarrow \mbox{ en } \Leftarrow$ . Het voorbeeld boven zouden we wellicht $= 10$ kunnen noemen.

Bij binaire relaties wordt de relator vaak gebruikt in een infix-notatie.

[bewerk] Bijzondere soorten binaire relaties

[bewerk] Functionele relaties

Een bijzonder soort binaire relaties ontstaat als met ieder beginpunt van een koppel ten hoogste één eindpunt wordt verbonden. We spreken dan van een (partiële) functie. Als de relatie f met ieder element van een verzameling A precies één element van een verzameling B in verband brengt, dan heet f een afbeelding van A naar B. Bijzondere soorten afbeeldingen zijn nog injecties, surjecties en bijecties.

De hierna volgende eigenschappen slaan op binaire relaties tussen een verzameling en zichzelf:

$R\subset V\times V$

[bewerk] Reflexiviteit

R heet reflexief als ieder element van V met zichzelf gekoppeld is:

$\forall v \in V: vRv$

R heet irreflexief als geen enkel element van V met zichzelf gekoppeld is:

$\forall v\in V: \neg vRv$

[bewerk] Symmetrie

R heet symmetrisch als met ieder koppel (x,y) van R ook het omgekeerde koppel (y,x) tot R behoort:

$\forall v,w \in V: vRw \Rightarrow wRv$

[bewerk] Transitiviteit

R heet transitief als met iedere twee koppels waarbij het beginpunt van het tweede koppel samenvalt met het eindpunt van het eerste koppel, ook het samengestelde koppel tot R behoort:

$\forall v,w,z \in V: vRw \wedge wRz \Rightarrow vRz$

[bewerk] Equivalentie

De relatie R is een equivalentierelatie als ze reflexief, symmetrisch en transitief is.

[bewerk] Antisymmetrie

R is antisymmetrisch als geen enkel koppel samen met zijn omgekeerde tot R behoort, met eventuele uitzondering van identieke koppels:

$\forall v,w \in V: vRw \wedge wRv \Rightarrow w = v$

[bewerk] Connex

R heet connex als ze elk paar elementen van V in minstens één zin verbindt:

$\forall x,y\in V:xRy\lor yRx$

[bewerk] Orde

De relatie R is een orderelatie of partiële orde als ze reflexief, antisymmetrisch en transitief is.

Een totale orde is een partiële orde die ook nog connex is.

Een strikte orde is antireflexief, antisymmetrisch en transitief.

[bewerk] Samenstelling van relaties

Als we een relatie hebben tussen verzamelingen $A$ en $B$ , en nog een tweede relatie tussen $B$ en een derde verzameling $C$ , dan kunnen we de samengestelde relatie tussen $A$ en $C$ definiëren door na te gaan welke eindpunten van koppels van de eerste relatie tevens beginpunten van koppels van de tweede relatie zijn.