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 $a$ in een zekere relatie staat tot $b$, en $b$ staat op zijn beurt weer in een relatie met $c$, dan is er dus een relatie tussen $a$ en $c$, die de samengestelde relatie heet.

Definitie

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

$R\subset A\times B,\ S\subset B\times C$

De samengestelde relatie van $R$ en $S$ is gedefinieerd als

$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 $S\circ R$ wordt soms gelezen als "$S$ (komt) na $R$".

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

Voorbeelden

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

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

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

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

Dan is hun samengestelde relatie

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

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

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

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

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

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

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

Transitiviteit

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