Bijectie

(Doorverwezen vanaf Bijectief)

In de wiskunde is een bijectie, bijectieve afbeelding of een-op-een-correspondentie een afbeelding of functie, die zowel injectief als surjectief is, dus alle elementen van twee verzamelingen een-op-een aan elkaar koppelt. Bijectief wil dus zeggen dat ieder element uit het domein gekoppeld is aan precies één element uit het codomein en dat omgekeerd ook ieder element van gekoppeld is aan precies één element uit . Een correspondentie is een tweeplaatsige relatie, die zowel links- als rechtsvolledig is.

Bijectie tussen de verzamelingen en Y

Voor elke bijectie van een verzameling op een verzameling bestaat er een inverse functie van naar , die zelf ook een bijectie is.

Een bijectie van een verzameling op zichzelf wordt wel een permutatie genoemd. Bijecties zijn essentieel voor veel deelgebieden binnen de wiskunde, voor onder meer de definities van permutatiegroep, isomorfisme, homeomorfisme en diffeomorfisme. De aanduiding 'bijectieve afbeelding' werd geïntroduceerd door Bourbaki.

Definitie

bewerken

Een bijectie tussen twee verzamelingen   en  , niet noodzakelijk verschillend, is een functie of afbeelding:

 

die injectief is en surjectief is. Daarbij is  

  • injectief als uit   volgt dat   en
  • surjectief als er voor alle   een   is met  .

Gelijkmachtigheid

bewerken

Als   en   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   en   gelijkmachtig genoemd, omdat de afbeelding   met  , 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   naar  :

  • 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:

  en  

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   is wel gelijkmachtig met deze twee, maar de verzameling van reële getallen   is niet gelijkmachtig met de drie vorige, maar wel met   voor elke gehele waarde van   groter dan 0.

Stelling van Cantor-Bernstein-Schröder

bewerken

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.

Voorbeelden en tegenvoorbeelden

bewerken

Voorbeeld 1

bewerken
 
 , met  

Geen enkel element uit   wordt door   aan 2 elementen uit   gekoppeld, dus is   injectief en   laat geen enkel element uit   over, dus is   surjectief. Dat betekent samen dat   bijectief is.

Voorbeeld 2

bewerken
 
 , met  

Deze functie   is ook een bijectie. Een andere bijectieve afbeelding tussen deze verzamelingen   en   is:

 

Tegenvoorbeeld 1

bewerken
 
 , met  

  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.

Tegenvoorbeeld 2

bewerken
 
 , met  

Dit is geen bijectie. Het is wel zo dat elk element van   gekoppeld wordt aan een element van  , maar sommige elementen van   worden aan twee verschillende elementen van   gekoppeld. Zo is bijvoorbeeld  .

Tegenvoorbeeld 3

bewerken
 
 , met  

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