] > Overaftelbare verzamelingen [volgende][vorige][inhoud]                        (versie: 23 augustus 2011)

15.8  Overaftelbare verzamelingen

Een verzameling is eindig als hij gelijkmachtig is met n¯ voor een natuurlijk getal n. Verzamelingen die gelijkmachtig zijn met heten aftelbaar. De verzamelingen × , , 0() en zijn aftelbaar. Zie ook de opgaven ??, ??, ?? van hoofdstuk 3, opgave ?? van hoofdstuk 5, opgave ?? van hoofdstuk 6 en opgave ?? van hoofdstuk 7.

15.62 Definitie. Een oneindige niet-aftelbare verzameling noemen we overaftelbaar.

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 ({0,1}), de verzameling van rijen in {0,1}.

15.63 Stelling. De verzameling ({0,1}) is overaftelbaar.

Bewijs.   Laat gegeven zijn een afbeelding f : ({0,1}). Bij iedere m hebben we een rij f(m) = (f(m)n). Beschouw de rij (an) in {0,1} gedefinieerd door an = 1 f(n)n. Dan voor iedere n in het bijzonder anf(n)n.

De rij (an) is verschillend van alle rijen f(m): zij m , dan is de rij (an) verschillend van de rij f(m), want de m-de term van (an) is 1 f(m)m, terwijl de m-de term van f(m) is f(m)m.

Voor iedere f : ({0,1}) geldt dus dat hij niet surjectief is. Er is dus geen bijectieve afbeelding f : ({0,1}). □

We maken het wat concreter (en minder exact). Geven we met bijvoorbeeld 1010001011100100100011110001 (het begin van) een rij in {0,1} aan en hebben we bij iedere n een rij, dan hebben we dus een rij van rijen:

1010001011100100100011110001 0101111001010001111111000101 1001101010101001010000011111 0101011010101010000101101011 0101010100100101010101010100 1001010101010001010010100001 1111000000000000000111111111 1010100000011111111110001010 0000001100000000110000000100 1100111001001010111001010011

We kunnen daar de diagonaal uit halen. Dat is de rij met op plaats n het cijfer dat op plaats n in de n-de rij staat:

1101011110

In deze rij vervangen we iedere 1 door een 0 en iedere 0 door een 1:

0010100001

Deze rij komt in de rij van rijen niet voor: voor iedere n geldt dat hij verschilt van het n-de rij, want op de n-de plaats in die rij staat iets anders.

Dit type redenering staat bekend als het diagonaalargument van Cantor.

15.64 Gevolg. De verzameling is overaftelbaar.

Bewijs.  In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □

We gebruiken de notatie I(a,b) = {x a < x < b} voor a,b met a < b. Uit het bewijs van Gevolg 15.64 blijkt dat bijvoorbeeld ook de deelverzameling I(1,1) overaftelbaar is. In feite is deze verzameling gelijkmachtig met :

15.65 Propositie. {x 1 < x < 1}

Bewijs.   We schrijven I = {x 1 < x < 1} en definiëren een afbeelding f : I door

f(x) = x 1 x2 (voor alle x I).

We bewijzen dat f bijectief is. Zij a . Is er een unieke x I met f(x) = a? Zo’n x is de oplossing van de kwadratische vergelijking ax2 + x a = 0. De discriminant is 1 + 4a2 > 0. De oplossingen zijn x = 1±1+4a2 2a . Precies één daarvan is een element van I. □

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?

15.66 Propositie. De deelverzameling van bestaande uit de algebraïsche getallen is aftelbaar.

Bewijs.  In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □

15.67 Gevolg. De deelverzameling van bestaande uit de transcendente getallen is overaftelbaar.

We gaan verzamelingen naar grootte ordenen.

15.68 Definitie. Laten A en B verzamelingen zijn. We definiëren

A B er is een injectieve afbeelding van A naar B.

en

A B A B en er is geen surjectieve afbeelding A B.

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.

15.69 Stelling (Cantor, Schröder, Bernstein). Laten A en B verzamelingen zijn met A B en B A. Dan A B.

Bewijs.   We nemen aan dat A B = . Laten f : A B en g: B A injectieve afbeeldingen zijn. We definiëren een transformatie F van A B:

F(x) = f(x) als x A g(x)  als x B.

Deze transformatie F is injectief: als F(x) = F(y), dan x,y A of x,y B en dus x = y, want f en g zijn injectief. Noem x A B een opvolger van y als F(y) = x. We zeggen dan ook dat y een voorganger is van x. Voor iedere x A B is er dus een unieke opvolger en hoogstens één voorganger omdat F injectief is. Laat A0 de deelverzameling zijn van A van elementen die geen voorganger hebben en B0 de deelverzameling van B van elementen die geen voorganger hebben. We definiëren een afbeelding h: A B:

h(a) =  de voorganger van a, als a in het verloop van een element van B0;  de opvolger van a,  anders.

Deze h is bijectief. De inverse is k: B A gedefinieerd door:

k(b) =  de opvolger van b,  als b in het verloop van een element van B0;  de voorganger van b, anders.

15.70 Voorbeelden.

  1. {x 0 x 1} I(0,1). Een injectieve afbeelding van {x 0 x 1} naar I is bijvoorbeeld x1 2x + 1 4.
  2. Dat × is rechtstreeks in te zien door een bijectie te geven. Het volgt ook uit het bestaan van injecties × en × :
    × ,n(n,0) en × ,(m,n)2m3n.

  3. Uit Gevolg 15.64 en Propositie 15.65 volgt dat ({0,1}) I(1,1) . De afbeelding I(0,1) ({0,1}) die aan een reëel getal z’n binaire ontwikkeling toevoegt, is injectief. Ook geldt I(0,1) I(1,1): beeld x af op 2x 1. Dus:
    I(1,1) I(0,1) ({0,1}) I(1,1) .

    Deze verzamelingen zijn dus allemaal gelijkmachtig.

  4. We laten zien dat × . Omdat ({0,1}), kunnen we ook aantonen dat ({0,1}) ×({0,1}) ({0,1}). De volgende afbeelding is een bijectie:
    ((an),(bn))(cn) metcn = an 2  als n even bn+1 2  als n oneven.

We hebben ({0,1}) en . De verzameling ({0,1}) = {0,1} is gelijkmachtig met P(), zie Propositie 3.46. Dus hebben we P(). De methode van Cantor laat zich eenvoudig generaliseren tot A P(A).:

15.71 Stelling. Zij A een verzameling. Dan A P(A).

Bewijs.   De afbeelding A P(A),a{a} is injectief. Laat f : A P(A) een afbeelding zijn. We tonen aan dat f niet surjectief is door te laten zien dat de verzameling U = {x Axf(x)} geen beeld van een element van A is.

Stel U = f(a) voor een a A. We kijken naar het element a.

Stel a U. Dan af(a) en dus aU, want U = f(a). Tegenspraak.

Dus aU. Maar dan niet af(a), ofwel a f(a). Dus a U, want f(a) = U. Tegenspraak.

Er is dus geen a A met U = f(a). Dus is f niet surjectief. □

Dus P() P(P()) P(P(P())) . Deze verzamelingen zijn onderling niet gelijkmachtig. Dit volgt direct uit:

15.72 Lemma. Laten A, B en C verzamelingen zijn met A B C. Dan A C.

Bewijs.  In: ”Getallen”, Epsilon deel 65, uitgegeven door Epsilon-Uitgaven. □

We hebben de standaardverzamelingen n¯ die we gebruiken om het aantal elementen van een eindige verzameling mee aan te geven: #(A) = n als A n¯. Voor de aftelbare verzamelingen is als standaardverzameling te gebruiken. Daarbij hoort een nieuw ‘getal’: 0. Dus: #(A) = 0 als A . ( 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 : #(A) #(B)A B. 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 A en B geldt A B of B A. 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 0 noemt men 1, etc.

Cantor noteerde het cardinaalgetal van als c. Is c = 1? Ofwel: is er een cardinaalgetal dat groter dan 0 is en kleiner dan c? 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:

Optellen:
#(A) + #(B) = #(A B) als A en B disjunct. Het optellen is associatief en commutatief. Is een van de cardinaalgetallen oneindig, dan is de som de grootste van de twee.
Vermenigvuldigen:
#(A) #(B) = #(A × B). Het vermenigvuldigen is associatief en commutatief. Ook is het distributief over optellen. Is een van de cardinaalgetallen oneindig en zijn beide niet 0, dan is het product de grootste van de twee.
Machtsverheffen:
#(A)#(B) = #(AB). De gebruikelijke rekenregels gelden ook hier: ab+c = abac, abc = (ab)c, (ab)c = acbc.

Pas wel op met schrapwetten, tegengestelden, inversen e.d. We hebben bijvoorbeeld gezien dat:

[volgende][vorige][inhoud