] >
Een verzameling is eindig als hij gelijkmachtig is met voor een natuurlijk getal . Verzamelingen die gelijkmachtig zijn met heten aftelbaar. De verzamelingen , , en zijn aftelbaar. Zie ook de opgaven ??, ??, ?? van hoofdstuk 3, opgave ?? van hoofdstuk 5, opgave ?? van hoofdstuk 6 en opgave ?? van hoofdstuk 7.
We zullen van diverse verzamelingen zien dat ze overaftelbaar zijn. Dat doen we met een methode bedacht door Cantor. Die methode maakt ook duidelijk dat twee overaftelbare verzamelingen niet gelijkmachtig hoeven te zijn.
We beginnen met de verzameling , de verzameling van rijen in .
Bewijs. Laat gegeven zijn een afbeelding . Bij iedere hebben we een rij . Beschouw de rij in gedefinieerd door . Dan voor iedere in het bijzonder .
De rij is verschillend van alle rijen : zij , dan is de rij verschillend van de rij , want de -de term van is , terwijl de -de term van is .
Voor iedere geldt dus dat hij niet surjectief is. Er is dus geen bijectieve afbeelding . □
We maken het wat concreter (en minder exact). Geven we met bijvoorbeeld (het begin van) een rij in aan en hebben we bij iedere een rij, dan hebben we dus een rij van rijen:
We kunnen daar de diagonaal uit halen. Dat is de rij met op plaats het cijfer dat op plaats in de -de rij staat:
In deze rij vervangen we iedere door een en iedere door een :
Deze rij komt in de rij van rijen niet voor: voor iedere geldt dat hij verschilt van het -de rij, want op de -de plaats in die rij staat iets anders.
Dit type redenering staat bekend als het diagonaalargument van Cantor.
Bewijs. In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □
We gebruiken de notatie voor met . Uit het bewijs van Gevolg 15.64 blijkt dat bijvoorbeeld ook de deelverzameling overaftelbaar is. In feite is deze verzameling gelijkmachtig met :
Bewijs. We schrijven en definiëren een afbeelding door
We bewijzen dat bijectief is. Zij . Is er een unieke met ? Zo’n is de oplossing van de kwadratische vergelijking . De discriminant is . De oplossingen zijn . Precies één daarvan is een element van . □
De rationale getallen vormen een aftelbare deelverzameling van . Een gevolg daarvan is dat de irrationale getallen een overaftelbare deelverzameling van vormen. Immers, als die verzameling ook aftelbaar was, dan was als vereniging van twee aftelbare verzamelingen, het ook. Maar hoe zit het met de deelverzameling van de algebraïsche getallen?
Bewijs. In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □
We gaan verzamelingen naar grootte ordenen.
De volgende stelling van Cantor, Schröder en Bernstein stelt ons in staat om in veel gevallen snel in te zien dat verzamelingen gelijkmachtig zijn.
Bewijs. We nemen aan dat . Laten en injectieve afbeeldingen zijn. We definiëren een transformatie van :
Deze transformatie is injectief: als , dan of en dus , want en zijn injectief. Noem een opvolger van als . We zeggen dan ook dat een voorganger is van . Voor iedere is er dus een unieke opvolger en hoogstens één voorganger omdat injectief is. Laat de deelverzameling zijn van van elementen die geen voorganger hebben en de deelverzameling van van elementen die geen voorganger hebben. We definiëren een afbeelding :
Deze is bijectief. De inverse is gedefinieerd door:
Deze verzamelingen zijn dus allemaal gelijkmachtig.
We hebben en . De verzameling is gelijkmachtig met , zie Propositie 3.46. Dus hebben we . De methode van Cantor laat zich eenvoudig generaliseren tot .:
Bewijs. De afbeelding is injectief. Laat een afbeelding zijn. We tonen aan dat niet surjectief is door te laten zien dat de verzameling geen beeld van een element van is.
Stel voor een . We kijken naar het element .
Stel . Dan en dus , want . Tegenspraak.
Dus . Maar dan niet , ofwel . Dus , want . Tegenspraak.
Er is dus geen met . Dus is niet surjectief. □
Dus . Deze verzamelingen zijn onderling niet gelijkmachtig. Dit volgt direct uit:
Bewijs. In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □
We hebben de standaardverzamelingen die we gebruiken om het aantal elementen van een eindige verzameling mee aan te geven: als . Voor de aftelbare verzamelingen is als standaardverzameling te gebruiken. Daarbij hoort een nieuw ‘getal’: . Dus: als . ( is aleph, de eerste letter van het Hebreeuwse alfabet.)
Er zijn manieren om in de verzamelingsleer aan te geven wat de standaardverzamelingen zijn. We gaan daar hier niet op in. Deze standaardverzamelingen corresponderen met zogeheten cardinaalgetallen. Cardinaalgetallen kunnen worden geordend met behulp van : . Reflexiviteit en transitiviteit van zijn wel duidelijk. De antisymmetrie volgt uit de stelling van Cantor, Schröder en Bernstein. Met behulp van het keuzeaxioma kan men aantonen dat voor verzamelingen en geldt of . Ook kan men aantonen dat er bij ieder cardinaalgetal er een kleinste cardinaalgetal is dat groter is, de opvolger van het cardinaalgetal. De opvolger van noemt men , etc.
Cantor noteerde het cardinaalgetal van als . Is ? Ofwel: is er een cardinaalgetal dat groter dan is en kleiner dan ? De continuümhypothese zegt dat zo’n cardinaalgetal er niet is. In 1940 toonde Kurt Gödel aan dat met de gangbare axioma’s voor de verzamelingsleer de continuümhypothese niet te weerleggen is. In 1963 toonde Paul Cohen aan dat uit deze axioma’s de continuümhypothese ook niet af te leiden is.
Voor cardinaalgetallen kunnen bewerkingen gedefinieerd worden door bewerkingen met verzamelingen:
Pas wel op met schrapwetten, tegengestelden, inversen e.d. We hebben bijvoorbeeld gezien dat: