Samengestelde relatie

In de abstracte verzamelingenleer kan met behulp van twee relaties tussen verzamelingen soms een nieuwe relatie gevormd worden, de samengestelde relatie. Als namelijk ${\displaystyle a}$ in een zekere relatie staat tot ${\displaystyle b}$, en ${\displaystyle b}$ staat op zijn beurt weer in een relatie met ${\displaystyle c}$, dan is er dus een relatie tussen ${\displaystyle a}$ en ${\displaystyle c}$, die de samengestelde relatie heet.

Definitie

Zij ${\displaystyle R}$ een relatie tussen de twee verzamelingen ${\displaystyle A}$ en ${\displaystyle B}$, dus ${\displaystyle R}$ is een deelverzameling van het cartesisch product ${\displaystyle A\times B}$, en ${\displaystyle S}$ een relatie tussen ${\displaystyle B}$ en ${\displaystyle C}$, dus:

${\displaystyle R\subset A\times B,\ S\subset B\times C}$

De samengestelde relatie van ${\displaystyle R}$ en ${\displaystyle S}$ is gedefinieerd als

${\displaystyle S\circ R=\{(a,c)\in A\times C\mid \exists b\in B:(a,b)\in R{\hbox{ en }}(b,c)\in S\}}$

De notatie ${\displaystyle S\circ R}$ wordt soms gelezen als "${\displaystyle S}$ (komt) na ${\displaystyle R}$".

De definitie van de functiecompositie of de samengestelde afbeelding komt daarmee overeen. Als ${\displaystyle f}$ een functie of afbeelding is van ${\displaystyle A}$ naar ${\displaystyle B}$, en ${\displaystyle g}$ van ${\displaystyle B}$ naar ${\displaystyle C}$, dan is ${\displaystyle g\circ f}$ een functie of afbeelding van ${\displaystyle A}$ naar ${\displaystyle C}$, die de functiecompositie of samengestelde afbeelding van ${\displaystyle f}$ en ${\displaystyle g}$ wordt genoemd.

Voorbeelden

• De relatie 'kind van' kan met zichzelf samengesteld worden tot de relatie 'kleinkind van'. Als ${\displaystyle a}$ een kind is van ${\displaystyle b}$, en ${\displaystyle b}$ is een kind van ${\displaystyle c}$, dan is ${\displaystyle a}$ een kleinkind van ${\displaystyle c}$.

• Beschouw de volgende twee relaties tussen de natuurlijke getallen ${\displaystyle \mathbb {N} }$ en zichzelf:

${\displaystyle R=\{(0,0),(1,2),(2,4)\}}$

${\displaystyle S=\{(0,5),(0,10),(4,2),(4,4)\}}$

Dan is hun samengestelde relatie

${\displaystyle S\circ R=\{(0,5),(0,10),(2,2),(2,4)\}}$

In dit geval heeft ook ${\displaystyle R\circ S}$ zin, en

${\displaystyle R\circ S=\{(4,4)\}}$

• Als ${\displaystyle f}$ en ${\displaystyle g}$ permutaties zijn van een gegeven verzameling ${\displaystyle A}$ met een bepaald aantal elementen, dan is ${\displaystyle g\circ f}$ dat ook. De verzameling van alle mogelijke permutaties van ${\displaystyle A}$ vormt met de bewerking ${\displaystyle \circ }$ een groep, genoteerd ${\displaystyle {\mathcal {S}}(A)}$ en genaamd de symmetrische groep op ${\displaystyle A}$.

• Beschouw de reële functies ${\displaystyle f:\mathbb {R} \to \mathbb {R} :x\mapsto x^{2}}$ en ${\displaystyle g:\mathbb {R} \to \mathbb {R} :x\mapsto x-1}$. Dan bestaan zowel ${\displaystyle g\circ f}$ als ${\displaystyle f\circ g}$, en

${\displaystyle (g\circ f)(x)=g(f(x))=x^{2}-1}$

${\displaystyle (f\circ g)(x)=f(g(x))=(x-1)^{2}}$

Transitiviteit

Een relatie ${\displaystyle R\subset A\times A}$ op een verzameling ${\displaystyle A}$ is transitief als ${\displaystyle R\circ R}$ een deel is van ${\displaystyle R}$ zelf.