Samengestelde relatie

In de abstracte verzamelingenleer kan met behulp van twee relaties tussen verzamelingen soms een nieuwe relatie gevormd worden, de samengestelde relatie.

Definitie

Zij $R$ een relatie tussen 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$:

$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$".

Voorbeeld

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)\}$

Verband met transitiviteit

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

Samengestelde afbeelding

Zie Functiecompositie voor het hoofdartikel over dit onderwerp.

Als $f$ een afbeelding is van $A$ naar $B$, en $g$ is een afbeelding van $B$ naar $C$, dan is $g\circ f$ een afbeelding van $A$ naar $C$, die de samengestelde afbeelding of de compositie van $f$ en $g$ wordt genoemd.

Voorbeeld

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}$

Permutatiegroep

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

Zie ook

• Functiecompositie