Samengestelde relatie

In de abstracte verzamelingenleer kan met behulp van twee relaties tussen verzamelingen soms een nieuwe relatie worden gevormd, de samengestelde relatie. Als $a$ in een zekere relatie staat tot $b$, en $b$ staat op zijn beurt weer in een relatie met $c$, dan is er 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$ een deelverzameling van het cartesische product $A\times B$, en zij $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 \mathrm{\exists }b\in B:(a,b)\in R\text{ 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 worden samengesteld 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, de symmetrische groep $𝒮(A)$ op $A$.

• Beschouw de reële functies $f:ℝ\to ℝ:x\mapsto x^2$ en $g:ℝ\to ℝ: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.