Bijectie

Een bijectie tussen twee verzamelingen ${\displaystyle X}$  en ${\displaystyle Y}$ , niet noodzakelijk verschillend, is een functie of afbeelding:

${\displaystyle f\colon X\to Y}$ 

die injectief is en surjectief is. Daarbij is ${\displaystyle f}$ 

• injectief als uit ${\displaystyle f(x_{1})=f(x_{2})}$  volgt dat ${\displaystyle x_{1}=x_{2}}$  en
• surjectief als er voor alle ${\displaystyle y\in Y}$  een ${\displaystyle x\in X}$  is met ${\displaystyle y=f(x)}$ .

Als ${\displaystyle X}$  en ${\displaystyle Y}$  eindige verzamelingen zijn is het makkelijk in te zien dat het bestaan van een bijectie betekent dat beide verzamelingen hetzelfde aantal elementen hebben. Algemeen zegt men dat als er een bijectie tussen twee (eindige of oneindige) verzamelingen bestaat, deze verzamelingen dezelfde kardinaliteit hebben. Georg Cantor was de eerste die verzamelingen op deze manier met elkaar vergeleek. Twee verzamelingen waartussen een bijectie bestaat, worden gelijkmachtig genoemd.

Zo worden de verzamelingen ${\displaystyle \{1,2,3\}}$  en ${\displaystyle \{4,8,12\}}$  gelijkmachtig genoemd, omdat de afbeelding ${\displaystyle f:\{1,2,3\}\rightarrow \{4,8,12\}}$  met ${\displaystyle f(x)=4\,x}$ , bijectief is.

Ook zijn de verzameling van de natuurlijke getallen en de verzameling van de gehele getallen gelijkmachtig, want het is mogelijk een bijectie tussen beiden te vinden. Neem de volgende afbeelding van ${\displaystyle \mathbb {N} }$  naar ${\displaystyle \mathbb {Z} }$ :

• 0 wordt op 0 afgebeeld
• een even natuurlijk getal wordt op zijn helft afgebeeld: bijvoorbeeld: 4 wordt afgebeeld op 2
• bij een oneven natuurlijk getal wordt eerst 1 opgeteld, en wordt dit resultaat gedeeld door -2: bijvoorbeeld: 5 wordt afgebeeld op -3

Meer algemeen:

${\displaystyle 2n\mapsto n\ }$  en ${\displaystyle \ 2n+1\mapsto -n-1}$ 

Dit is een bijectie want elk natuurlijk getal heeft een eenduidig beeld, en elk geheel getal wordt precies een keer bereikt. De verzameling van rationale getallen ${\displaystyle \mathbb {Q} }$  is wel gelijkmachtig met deze twee, maar de verzameling van reële getallen ${\displaystyle \mathbb {R} }$  is niet gelijkmachtig met de drie vorige, maar wel met ${\displaystyle \mathbb {R} ^{n}}$  voor elke gehele waarde van ${\displaystyle n}$  groter dan 0.

Als er tussen twee verzamelingen beide kanten op een injectie is, bestaat er volgens de stelling van Cantor-Bernstein-Schröder een bijectie tussen de twee verzamelingen. Die zijn in dat geval dus gelijkmachtig.

${\displaystyle A=\{1,2,3\},\quad B=\{-7,3,10\}}$ 

${\displaystyle f:A\to B}$ , met ${\displaystyle f(1)=-7,\ f(2)=3,\ f(3)=10}$ 

Geen enkel element uit ${\displaystyle B}$  wordt door ${\displaystyle f}$  aan 2 elementen uit ${\displaystyle A}$  gekoppeld, dus is ${\displaystyle f}$  injectief en ${\displaystyle f}$  laat geen enkel element uit ${\displaystyle B}$  over, dus is ${\displaystyle f}$  surjectief. Dat betekent samen dat ${\displaystyle f}$  bijectief is.

${\displaystyle A=[2,3],\quad B=[2,4]}$ 

${\displaystyle f:A\to B}$ , met ${\displaystyle f(x)=2x-2}$ 

Deze functie ${\displaystyle f}$  is ook een bijectie. Een andere bijectieve afbeelding tussen deze verzamelingen ${\displaystyle A}$  en ${\displaystyle B}$  is:

${\displaystyle g(x)=x^{2}-3x+4}$ 

${\displaystyle A=\{1,2,3\},\quad B=\{-7,3,10\}}$ 

${\displaystyle f\colon A\to B}$ , met ${\displaystyle f(1)=3,\ f(2)=3,\ f(3)=10}$ 

${\displaystyle f}$  is geen bijectie, enerzijds omdat -7 niet gekoppeld wordt, dus niet surjectief is, en anderzijds omdat 3 aan zowel 1 als 2 gekoppeld wordt, dus niet injectief is.

${\displaystyle A=[-1,1],\quad B=[0,1]}$ 

${\displaystyle f\colon A\to B}$ , met ${\displaystyle f(x)=x^{2}}$ 

Dit is geen bijectie. Het is wel zo dat elk element van ${\displaystyle B}$  gekoppeld wordt aan een element van ${\displaystyle A}$ , maar sommige elementen van ${\displaystyle B}$  worden aan twee verschillende elementen van ${\displaystyle A}$  gekoppeld. Zo is bijvoorbeeld ${\displaystyle f(-1)=f(1)=1}$ .

${\displaystyle A=[0,1],\quad B=[0,2]}$ 

${\displaystyle f\colon A\to B}$ , met ${\displaystyle f(x)=x+1}$ 

Dit is geen bijectie, want ${\displaystyle f}$  is niet surjectief omdat niet alle elementen uit ${\displaystyle B}$  worden gekoppeld aan een element uit ${\displaystyle A}$ . Het element 0 in ${\displaystyle B}$  bijvoorbeeld is van geen enkel element uit ${\displaystyle A}$  het beeld. De functie ${\displaystyle f}$  is wel injectief, want geen twee elementen uit ${\displaystyle A}$  worden gekoppeld aan hetzelfde element van ${\displaystyle B}$ .