Kardinaalgetal

Alef-0, het kleinste oneindige kardinaalgetal

In de wiskunde is een kardinaalgetal (kort kardinaal), of machtigheid, een veralgemening van een natuurlijk getal die gebruikt wordt om de kardinaliteit (grootte) van een verzameling weer te geven. De kardinaliteit van een eindige verzameling is een natuurlijk getal, namelijk het aantal elementen in de verzameling. De transfiniete kardinaalgetallen beschrijven de groottes van oneindige verzamelingen.

Twee verzamelingen met dezelfde kardinaliteit, eindig of oneindig, heten gelijkmachtig.

Geschiedenis

De notie van kardinaliteit, zoals deze nu wordt begrepen, werd in de jaren 1874-1884 opgesteld door Georg Cantor, de initiator van de verzamelingenleer. Cantor voerde het begrip kardinaliteit eerst in als een instrument om eindige verzamelingen te vergelijken; weliswaar zijn bijvoorbeeld de verzamelingen {1,2,3} en {2,3,4} niet gelijk, maar beide verzamelingen delen wel dezelfde kardinaliteit, drie.

Cantor noemde het kardinaalgetal dat de grootte van de verzameling natuurlijke getallen aangeeft ${\displaystyle \aleph _{0}}$, Alef-nul. Hij bewees dat elke onbegrensde deelverzameling van ${\displaystyle \mathbb {N} }$ dezelfde kardinaliteit heeft als ${\displaystyle \mathbb {N} }$ zelf. Op het eerste gezicht is dit in strijd met de intuïtie. Hij heeft ook bewezen dat de verzameling van alle geordende paren van de natuurlijke getallen aftelbaar is (hetgeen impliceert dat ook de verzameling van alle rationale getallen aftelbaar is). Later bewees Cantor dat ook de verzameling van alle algebraïsche getallen aftelbaar is. Elk algebraïsch getal ${\displaystyle z}$ kan worden gecodeerd als een eindige rij van gehele getallen, de coëfficiënten in de polynomen waarvan deze algebraïsche getallen de oplossing zijn, namelijk de geordende n-tupel ${\displaystyle (a_{0},a_{1},\ldots ,a_{n}),\;a_{i}\in \mathbb {Z} ,}$ samen met een paar van rationale getallen ${\displaystyle (b_{0},b_{1})}$ dusdanig dat ${\displaystyle z}$ de unieke wortel is van de veelterm met coëfficiënten ${\displaystyle (a_{0},a_{1},\ldots ,a_{n})}$, die liggen in het interval ${\displaystyle (b_{0},b_{1})}$.

In zijn artikel uit 1874 bewees Cantor, dat er hogere orde kardinaalgetallen bestaan, door aan te tonen dat de verzameling van de reële getallen een kardinaliteit groter dan die van de verzameling natuurlijke getallen heeft.[1] Zijn originele bewijs maakt gebruikt van een complexe redenering met behulp van geneste intervallen, maar in een artikel uit 1891 bewees hij hetzelfde resultaat door gebruik te maken van zijn ingenieuze diagonaalbewijs. Dit nieuwe kardinaalgetal werd door Cantor, ${\displaystyle c}$, de kardinaliteit van het continuüm genoemd.

Cantor ontwikkelde ook een groot deel van de algemene theorie van de kardinaalgetallen; hij bewees dat er een kleinste transfiniet kardinaalgetal (${\displaystyle \aleph _{0}}$, alef-nul) bestaat en dat er voor elk kardinaalgetal een volgend groter kardinaalgetal ${\displaystyle (\aleph _{1},\aleph _{2},\aleph _{3},\ldots )}$ bestaat.

Inleiding

Twee eindige verzamelingen hebben evenveel elementen als die elementen een-eenduidig aan elkaar gekoppeld kunnen worden, dus als er een bijectie tussen deze twee verzamelingen bestaat. Dit is in overeenstemming met het intuïtieve begrip van grootte van een verzameling. Ook twee oneindige verzamelingen hebben hetzelfde kardinaalgetal als er een bijectie tussen deze twee verzamelingen bestaat. In dit geval is het gedrag complexer. Niet alle oneindige verzamelingen hebben dezelfde kardinaliteit. Een fundamentele stelling, die als eerste werd geponeerd door Georg Cantor, laat zien dat oneindige verzamelingen verschillende kardinaliteiten kunnen hebben. De verzameling van de reële getallen en de verzameling van de natuurlijke getallen hebben bijvoorbeeld niet hetzelfde kardinaalgetal. Dat valt niet af te leiden uit het feit dat de natuurlijke getallen een echte deelverzameling van de reële getallen zijn. De even natuurlijke getallen vormen een echte deelverzameling van alle natuurlijke getallen, maar toch zijn beide verzamelingen gelijkmachtig, bevatten "evenveel" elementen. Hoewel tussen elke twee rationale getallen een reëel getal ligt en tussen elke twee reële getallen een rationaal getal, zijn de rationale getallen aftelbaar, dus gelijkmachtig met de natuurlijke getallen.

Behalve de opeenvolging van de natuurlijke getallen, is er ook een verdergaande opeenvolging van de transfiniete kardinaalgetallen:

${\displaystyle 0,1,2,3,\ldots ;\aleph _{0},\aleph _{1},\aleph _{2},\ldots ,\aleph _{\alpha },\ldots }$

Deze rij begint met de natuurlijke getallen (eindige kardinalen), gevolgd door de alef-getallen (oneindige kardinalen van welgeordende verzamelingen). De alef-getallen worden geïndexeerd door ordinaalgetallen. Onder de aanname van het keuzeaxioma, maakt elk kardinaalgetal deel uit van deze transfiniete opeenvolging. Als men het keuzeaxioma verwerpt ligt de situatie ingewikkelder, met additionele oneindige kardinalen die geen alef-getallen zijn.

Kardinaliteit wordt als een onderdeel van de verzamelingenleer bestudeerd vanwege het belang van het onderwerp. Daarnaast is kardinaliteit ook een hulpmiddel dat in verschillende deelgebieden van de wiskunde, zoals de combinatoriek, de abstracte algebra en wiskundige analyse, wordt gebruikt.

Definitie

Uitgaande van het keuzeaxioma is de kardinaliteit van een verzameling ${\displaystyle X}$ formeel gesproken het kleinste ordinaalgetal α, zodanig dat er een bijectie tussen ${\displaystyle X}$ en α bestaat. Deze definitie staat bekend als de von Neumann-kardinaaltoewijzing. Als het keuzeaxioma niet wordt geaccepteerd, moet men iets anders doen. De oudste definitie van de kardinaliteit van een verzameling ${\displaystyle X}$ (impliciet in Cantor en expliciet in Frege en de Principia Mathematica) is: de verzameling van alle verzamelingen die gelijkmachtig zijn met ${\displaystyle X}$; deze definitie gaat echter niet op in ZFC of andere daaraan gerelateerde systemen uit de axiomatische verzamelingenleer, omdat deze collectie te groot is om een verzameling te zijn, maar de definitie gaat wel op in de typentheorie, de New Foundations en daaraan gerelateerde systemen. Als we ons uit deze klasse echter beperken tot die klassen, die gelijkmachtig zijn met ${\displaystyle X}$ en die de kleinste rang hebben, dan werkt de definitie wel: de reden is dat de collectie van objecten met enige gegeven rang een verzameling is).

Formeel is de volgorde onder kardinaalgetallen als volgt gedefinieerd: ${\displaystyle |X|\leq |Y|}$ betekent dat er een injectieve functie van ${\displaystyle X}$ naar ${\displaystyle Y}$ bestaat. De Stelling van Cantor-Bernstein-Schröder stelt dat als ${\displaystyle |X|\leq |Y|}$ en ${\displaystyle |Y|\leq |X|}$ dat dan ${\displaystyle |X|=|Y|}$ geldt. Het keuzeaxioma is gelijkwaardig aan de uitspraak dat gegeven twee verzamelingen ${\displaystyle X}$ en ${\displaystyle Y}$, ofwel moet gelden dat ${\displaystyle |X|\leq |Y|}$ ofwel dat ${\displaystyle |Y|\leq |X|}$.

Een verzameling ${\displaystyle X}$ noemt men Dedekind-oneindig, indien er een strikte deelverzameling ${\displaystyle Y}$ van ${\displaystyle X}$ bestaat, waarvoor ${\displaystyle |Y|=|X|}$, en Dedekind-eindig, indien er niet zo'n deelverzameling bestaat. De eindige kardinalen zijn gewoon de natuurlijke getallen, dat wil zeggen dat een verzameling ${\displaystyle X}$ dan en slechts dan eindig is als ${\displaystyle |X|=n}$ voor een natuurlijk getal ${\displaystyle n}$. Elke andere verzameling is oneindig. Uitgaande van het keuzeaxioma kan worden bewezen dat de Dedekind-begrippen overeenkomen met de standaardbegrippen. Het kan ook worden bewezen dat het kardinaalgetal ${\displaystyle \aleph _{0}}$[2] het kleinste oneindige kardinaalgetal is. Dat wil zeggen dat elke oneindige verzameling een deelverzameling van kardinaliteit ${\displaystyle \aleph _{0}}$ heeft. De eerstvolgende grotere kardinaal wordt aangegeven door ${\displaystyle \aleph _{1}}$ en zo verder. Voor elk ordinaalgetal α bestaat er een kardinaalgetal ${\displaystyle \aleph _{\alpha },}$ en deze lijst put alle oneindige kardinaalgetallen uit.

Kardinaalrekenkunde

Op kardinaalgetallen zijn rekenkundige operaties gedefinieerd, die generalisaties zijn van de normale operaties voor natuurlijke getallen. Het kan worden aangetoond dat deze operaties voor eindige kardinaalgetallen samenvallen met de gebruikelijke operaties voor de natuurlijke getallen. Bovendien hebben deze operaties veel eigenschappen met de gewone rekenkunde gemeen.

De continuümhypothese

De continuümhypothese (CH) stelt dat er strikt genomen geen kardinalen liggen tussen ${\displaystyle \aleph _{0}}$ en ${\displaystyle 2^{\aleph _{0}}}$. Laatstgenoemde kardinaalgetal wordt vaak aangeduid door ${\displaystyle {\mathfrak {c}}}$; het is de kardinaliteit van het continuüm (de verzameling van reële getallen). In het geval ${\displaystyle 2^{\aleph _{0}}=\aleph _{1}}$ stelt de algemene continuümhypothese (GCH) dat voor elke oneindige verzameling ${\displaystyle X}$, er strikt genomen geen kardinaalgetallen liggen tussen ${\displaystyle |X|}$ en ${\displaystyle 2^{|X|}}$.

De continuümhypothese is onafhankelijk van de gebruikelijke axioma's uit de verzamelingenleer, de Zermelo-Fraenkel-axioma's samen met het keuzeaxioma (ZFC).

Voetnoten

1. Historische nota's bij hoofdstuk 1 van Jech, Thomas, "Set Theory," Third Millennium Edition, gecorrigeerde 4de druk, Springer 2006.
2. Het alef-getal (${\displaystyle \aleph }$), waar 'Alef' voor de eerste letter uit het Hebreeuws alfabet staat, vertegenwoordigt de verzameling van natuurlijke getallen.