Kardinaliteit

In de verzamelingenleer, een deelgebied van de wiskunde, is de kardinaliteit van een verzameling een algemene vorm om het aantal elementen in die verzameling mee aan te duiden. Deze maat is ook voor oneindige verzamelingen van toepassing. Een verzameling is eindig, aftelbaar oneindig of overaftelbaar. De kardinaliteit van een eindige verzameling is het aantal elementen van die verzameling. Alle aftelbaar oneindige verzamelingen hebben dezelfde kardinaliteit, maar er bestaan overaftelbare verzamelingen van verschillende kardinaliteiten.

De kardinaliteit van een verzameling ${\displaystyle A}$ wordt aangeduid met ${\displaystyle |A|}$, zoals bij de notatie voor de absolute waarde. De betekenis is afhankelijk van de context. Soms wordt ook wel de notatie ${\displaystyle \#A}$ gebruikt.

Er zijn twee manieren om het begrip kardinaliteit te benaderen. In de ene benadering vergelijkt men verzamelingen rechtstreeks door gebruik te maken van bijecties en injecties, in de andere maakt men gebruik van kardinaalgetallen. Twee verzamelingen hebben dezelfde kardinaliteit als ze een-op-een op elkaar kunnen worden afgebeeld, dat wil zeggen dat er een bijectie tussen de beide verzamelingen kan worden gegeven. Deze verzamelingen worden dan gelijkmachtig genoemd.

Men kan de volgende drie gevallen onderscheiden:

• ${\displaystyle |A|=|B|}$

Twee verzamelingen ${\displaystyle A}$ en ${\displaystyle B}$ hebben dezelfde kardinaliteit als er een bijectie tussen ${\displaystyle A}$ en ${\displaystyle B}$ bestaat.

Galileo heeft al opgemerkt dat de verzameling ${\displaystyle E=\{2,4,6,\ldots \}}$ van even natuurlijke getallen dezelfde kardinaliteit heeft als de verzameling ${\displaystyle \mathbb {N} }$ van natuurlijke getallen zelf, aangezien de functie ${\displaystyle f(n)=2n+2}$ een bijectie is van ${\displaystyle \mathbb {N} }$ naar ${\displaystyle E}$.

• ${\displaystyle |A|>|B|}$

${\displaystyle A}$ heeft een kardinaliteit die strikt groter is dan de kardinaliteit van ${\displaystyle B}$ als er een injectie van ${\displaystyle B}$ naar ${\displaystyle A}$ bestaat, maar geen bijectie.

De verzameling ${\displaystyle \mathbb {R} }$ van alle reële getallen heeft bijvoorbeeld een kardinaliteit die strikt groter is dan de kardinaliteit van de verzameling ${\displaystyle \mathbb {N} }$ van alle natuurlijke getallen, omdat de identieke afbeelding ${\displaystyle I:\mathbb {N} \to \mathbb {R} }$ injectief is en het met het diagonaalbewijs van Cantor kan worden aangetoond dat er geen bijectieve functie van ${\displaystyle \mathbb {N} }$ naar ${\displaystyle \mathbb {R} }$ bestaat.

• ${\displaystyle |A|\geq |B|}$

${\displaystyle A}$ heeft een kardinaliteit groter dan of gelijk aan de kardinaliteit van ${\displaystyle B}$ als er een injectie van ${\displaystyle B}$ naar ${\displaystyle A}$ bestaat.

Zie Kardinaalgetal voor het hoofdartikel over dit onderwerp.

De relatie dat twee verzamelingen dezelfde kardinaliteit hebben wordt gelijkmachtigheid genoemd. Gelijkmachtigheid is een equivalentierelatie op de klasse van alle verzamelingen. De equivalentieklasse van een verzameling ${\displaystyle A}$ bestaat onder deze relatie uit al die verzamelingen die dezelfde kardinaliteit als ${\displaystyle A}$ hebben. Er zijn twee manieren om de kardinaliteit van een verzameling te definiëren:

1. De kardinaliteit van een verzameling ${\displaystyle A}$ wordt gedefinieerd als haar equivalentieklasse onder gelijkmachtigheid.
2. Er wordt voor elke equivalentieklasse een representatieve verzameling aangewezen.

De kardinaliteiten van de oneindige verzamelingen worden aangeduid door

${\displaystyle \aleph _{0}<\aleph _{1}<\aleph _{2}<\ldots }$

Voor ieder ordinaalgetal ${\displaystyle \alpha }$ is ${\displaystyle \aleph _{\alpha +1}}$ het kleinste kardinaalgetal groter dan ${\displaystyle \aleph _{\alpha }}$. Als het keuzeaxioma wordt aangenomen, worden op deze manier alle kardinaalgetallen opgesomd.

De kardinaliteit van een eindige verzameling is het aantal elementen in de verzameling. Omgekeerd geldt ook, dat als de kardinaliteit van een verzameling een natuurlijk getal is, die verzameling eindig is. Twee eindige verzamelingen hebben dezelfde kardinaliteit als ze hetzelfde aantal elementen hebben.

Een verzameling met een enkel element wordt een singleton of eenpuntsverzameling genoemd.

Een oneindige verzameling heeft altijd een hogere kardinaliteit dan een eindige. Dat wil zeggen, we kunnen elk element van de eindige verzameling op een verschillend element van de oneindige verzameling afbeelden, maar omgekeerd kan dat niet. De kleinste oneindige kardinaliteit is die van de natuurlijke getallen en die wordt ${\displaystyle \aleph _{0}}$ (alef-nul) genoemd. Verzamelingen met deze kardinaliteit heten aftelbaar oneindig. Het diagonaalbewijs van Cantor toont aan dat er een verzameling met een hogere kardinaliteit bestaat. Verzamelingen met een hogere kardinaliteit worden met alef-getallen aangegeven: ${\displaystyle \aleph _{0},\,\aleph _{1},\,\aleph _{2},\,\ldots ,\,\aleph _{\omega },\ \ldots }$.

Zie Kardinaliteit van het continuüm voor het hoofdartikel over dit onderwerp.

Een van Cantors belangrijkste resultaten was dat de kardinaliteit van het continuüm (c of ${\displaystyle {\mathfrak {c}}}$) groter is dan de kardinaliteit ${\displaystyle \aleph _{0}}$ van de natuurlijke getallen. Dat wil zeggen dat er meer reële getallen ${\displaystyle \mathbb {R} }$ dan natuurlijke getallen ${\displaystyle \mathbb {N} }$ bestaan. Cantor toonde dit met zijn diagonaalbewijs aan:

${\displaystyle {\mathfrak {c}}=2^{\aleph _{0}}>\aleph _{0}}$

De continuümhypothese stelt dat er geen kardinaalgetal bestaat tussen de kardinaliteit van de reële getallen en de kardinaliteit van de natuurlijke getallen. De continuümhypothese kan binnen de algemeen aanvaarde Zermelo-Fraenkel-verzamelingenleer, ten minste indien deze axiomatische verzamelingenleer consistent is, noch worden bewezen noch worden verworpen.

Het kan wel worden bewezen dat de kardinaliteit van de machtsverzameling van ${\displaystyle \mathbb {N} }$ gelijk is aan de kardinaliteit van ${\displaystyle \mathbb {R} }$ en dat de kardinaliteit van de machtsverzameling van een verzameling ${\displaystyle V}$ altijd groter is dan de kardinaliteit van ${\displaystyle V}$ zelf.

In de informatica heeft kardinaliteit betrekking op relaties tussen tabellen of associaties tussen klassen en objecten. Dan is dit het aantal keer dat die voorkomen. Dat kan met een getal of een interval worden vastgelegd.