Articles

9.3: Stelling van Cantor en zijn gevolgen

vaardigheden om

  • te ontwikkelen

toen Cantor eenmaal liet zien dat er twee soorten oneindigheid waren( telbaar en ontelbaar), was de volgende vraag natuurlijk: “hebben alle ontelbare verzamelingen dezelfde kardinaliteit?”

net zoals niet alle “niet-Honden” Katten zijn, is er geen reden om aan te nemen dat alle ontelbare sets dezelfde grootte zouden moeten hebben. Maar de bouw ontelbare sets van verschillende maten is niet zo eenvoudig als het klinkt.

bijvoorbeeld, hoe zit het met het lijnsegment vertegenwoordigd door het interval \(\) en het vierkant vertegenwoordigd door de verzameling \( × = \{(x,y)|0 ≤ x,y ≤ 1\}\). Zeker moet het tweedimensionale vierkant een grotere oneindige verzameling zijn dan het eendimensionale lijnsegment. Opmerkelijk genoeg toonde Cantor aan dat deze twee verzamelingen dezelfde kardinaliteit hadden. In zijn correspondentie van 1877 met zijn vriend en collega-wiskundige Richard Dedekind merkte zelfs Cantor op: “Ik zie het, maar ik geloof het niet!”

figuur 9.3.1.PNG

figuur \(\Paginindex{1}\): Richard Dedekind

het volgende geeft het oorspronkelijke idee van het bewijs van Cantor. Cantor bedacht de volgende functie \(f:× →\). Ten eerste representeren we de coördinaten van elk punt \((x,y) ∈ ×\) door hun decimale representaties \(x = 0.a_1a_2a_3 …\ ) en \(y = 0.b_1b_2b_3….\ ) Zelfs afsluitende decimalen kunnen op deze manier worden geschreven omdat we \(0.5 = 0.5000 zouden kunnen schrijven….\ ) We kunnen dan \(f(x,y)\) definiëren door

\

dit relatief eenvoudige idee heeft een aantal technische problemen in verband met het volgende resultaat.

oefening \(\Paginindex{1}\)

overweeg de volgorde \((0.9,0.99,0.999,…)\). Bepaal dat deze reeks convergeert en in feite convergeert naar \(1\). Dit suggereert dat \(0.999… = 1\).

op dezelfde manier hebben we \(0,04999… = 0.05000…\), etc. Om de decimale weergave van een reëel getal in \(\) uniek te maken, moeten we een consistente keuze maken van het schrijven van een eindigende decimaal als een die eindigt in een oneindige reeks nullen of een oneindige reeks negens . Het maakt niet uit welke keuze we maken, we kunnen deze functie nooit maken. Bijvoorbeeld \(109/1100 = 0,09909090…\ ) zou als voorbeeld \((0.0999…,0.9000…)\) wat een mix van de twee conventies zou zijn.

Cantor was in staat om deze techniciteit te overwinnen om een één-op-één correspondentie aan te tonen, maar in plaats daarvan zullen we opmerken dat in beide conventies de functie één-op-één is, dus dit zegt dat de verzameling \(×\) dezelfde kardinaliteit is als een (ontelbare) deelverzameling van \(\mathbb{R}\). Het feit dat dit dezelfde kardinaliteit heeft als \(\mathbb{R}\) is iets waar we op terugkomen. Maar eerst zullen we proberen een ontelbare verzameling te construeren die niet dezelfde kardinaliteit heeft als \(\mathbb{R}\). Om dit probleem aan te pakken, bewees Cantor het volgende in 1891.

Stelling \(\Paginindex{1}\): Stelling van Cantor

zij \(S\) een willekeurige verzameling. Dan is er geen één-op-één correspondentie tussen \(s\) en \(P(S)\), de verzameling van alle deelverzamelingen van \(s\).

omdat \(S\) in één-op-één correspondentie kan worden gezet met een deelverzameling van \(P (S) (A → \{a\})\), dan zegt dit dat \(P(S)\) minstens zo groot is als \(s\). In het eindige geval is \(/P (S)|\) strikt groter dan \(|S|\) zoals het volgende probleem laat zien. Het laat ook zien waarom \(P (S)\) de machtsverzameling van \(S\) wordt genoemd.

Oefening \(\Paginindex{2}\)

Bewijzen: Als \(/S / = n\), dan \(|P(S)| = 2n\)

Hint

laat \(S = a_1, a_2, …, a_n\). Overweeg de volgende overeenkomst tussen de elementen van \(P (S)\) en de verzameling \(T\) van alle\(n\)-tupels van ja (\(Y\)) of nee (\(N\)):

\

hoeveel elementen zitten er in \(T\)?

oefening \(\Paginindex{3}\)

bewijs Cantors stelling.

Hint

ga ervan uit dat er een één-op-één correspondentie is \(f : S → P(S)\). Beschouw \(A = \{x ∈ S / X \ not {∈} f (x)\}\). Omdat \(f\) op is, dan is er \(a ∈ a\) zodanig dat \(A = f (a)\). Is \(a ∈ A\) of is \(a\Niet {∈} a\)?

eigenlijk blijkt dat \(\mathbb{R}\) en\(P (\mathbb{N})\) dezelfde kardinaliteit hebben. Dit is op een omweg te zien aan de hand van enkele van de bovenstaande ideeën uit oefening \(\Paginindex{2}\). Specifiek, laat \(T\) de verzameling zijn van alle reeksen van nullen of enen (je kunt \(Y\)s of \(N\)s gebruiken, als je dat liever hebt). Dan is het duidelijk om te zien dat \(T\) en \(P (\mathbb{N})\) dezelfde kardinaliteit hebben.

als we \((0,1]\) beschouwen, die dezelfde kardinaliteit heeft als \(\mathbb{R}\), dan kunnen we zien dat dit dezelfde kardinaliteit heeft als \(T\). Specifiek, als we denken aan de getallen in binair, dan kan elk reëel getal in \(\) worden geschreven als \(\sum_{j=1}^{\infty } \frac{a_j}{2^j} = (a_1, a_2, \cdots )\) waar \(a_j ∈ \{0,1\}\). We moeten rekening houden met het feit dat binaire representaties zoals \(0.0111…\ ) en \(0.1000…\ ) stelt hetzelfde reële getal voor (stel dat geen representaties eindigen in een oneindige reeks nullen), dan kunnen we zien dat \ ( \ ) dezelfde kardinaliteit heeft als \(T – U\), waarbij \(U\) de verzameling is van alle reeksen die eindigen in een oneindige reeks nullen. Het blijkt dat \(U\) zelf een aftelbare verzameling is.

oefening \(\Paginindex{4}\)

laat \(U_n = \{(a_1, a_2, a_3,…) / a_j ∈ \{0,1\}\) en \(a_{n+1} = a_{n+2} = ··· = 0\}\). Laat zien dat voor elke \(n\) \(U_n\) eindig is en gebruik dit om te concluderen dat \(U\) aftelbaar oneindig is.

de volgende twee problemen tonen aan dat het verwijderen van een aftelbare verzameling uit een ontelbare verzameling de kardinaliteit ervan niet verandert.

oefening \(\Paginindex{5}\)

laat \(S\) een oneindige verzameling zijn. Bewijs dat \(S\) een aftelbaar oneindige deelverzameling bevat.

oefening \(\Paginindex{6}\)

stel dat \(X\) een ontelbare verzameling is en \(Y ⊂ X\) aftelbaar oneindig is. Bewijs dat \(X\) en \(X – Y\) dezelfde kardinaliteit hebben.

Hint

Laat \(Y = Y_0\). Als \(X – Y_0\) een oneindige verzameling is, dan bevat het door het vorige probleem een aftelbaar oneindige verzameling \(Y_1\). Evenzo als \(X – (Y_0 ∪ Y_1)\) oneindig is, bevat het ook een oneindige verzameling \(Y_2\). Nogmaals, als \(X – (Y_0 ∪ Y_1 ∪ Y_2)\) een oneindige verzameling is dan bevat het een oneindige verzameling \(Y_3\), enz. Voor \(n = 1,2,3,…,\) laat \(f_n : Y_{n-1} → Y_n\) een één-op-één correspondentie zijn en definieer \(f : X → X – Y\) door

\

laat zien dat \(f\) één-op-één is en op.

bovenstaande problemen zeggen dat \(R\), \(T – U\), \(T\), en \(P (N)\) allemaal dezelfde kardinaliteit hebben.Zoals eerder werd aangegeven, had Cantors werk over oneindige verzamelingen een diepgaande invloed op de wiskunde in het begin van de twintigste eeuw. Bijvoorbeeld, bij het onderzoeken van het bewijs van de Stelling van Cantor, bedacht de eminente logicus Bertrand Russell zijn beroemde paradox in 1901. Voor die tijd werd een set naïef gezien als een verzameling objecten. Door het werk van Cantor en anderen werden verzamelingen een centraal studieobject in de wiskunde, omdat veel wiskundige concepten werden geherformuleerd in termen van Verzamelingen. Het idee was dat de verzamelingenleer een verenigend thema van de wiskunde moest zijn. Deze paradox zette de wiskundige wereld op zijn oor.

Russell ‘ s Paradox

beschouw de verzameling van alle verzamelingen die geen elementen van zichzelf zijn. We noemen deze verzameling \(D\) en vragen: “Is \(D ∈ D\)?”Symbolisch is deze set

\

als \(D ∈ D\), dan per definitie \(d \not {∈} D\). Als D 6∈ D, dan per definitie \(D ∈ D\).

als je terugkijkt op het bewijs van de Stelling van Cantor, was dit in principe het idee dat ons de tegenstrijdigheid gaf. Het was schandalig om zo ‘ n tegenstrijdigheid op het meest elementaire niveau van de wiskunde te hebben. Het dwong een aantal wiskundigen en logici om zorgvuldig de axioma ‘ s te bedenken waarmee verzamelingen konden worden geconstrueerd. Om eerlijk te zijn benaderen de meeste wiskundigen de verzamelingenleer nog steeds vanuit een naïef standpunt, omdat de Verzamelingen waar we meestal mee te maken hebben, onder de categorie vallen van wat we “normale verzamelingen” zouden noemen.”In feite wordt een dergelijke benadering officieel naïeve verzamelingenleer genoemd (in tegenstelling tot axiomatische verzamelingenleer). Pogingen om de verzamelingenleer en logica op een solide basis te zetten leidden echter tot de moderne studie van de symbolische logica en uiteindelijk tot het ontwerp van de computer (machine) logica.

een andere plaats waar Cantors werk een diepgaande invloed had in de moderne logica komt voort uit iets waar we eerder op gezinspeeld hebben. We toonden eerder aan dat het eenheidsvierkant \ ( × \ ) dezelfde kardinaliteit had als een ontelbare deelverzameling van \(\mathbb{R}\). In feite toonde Cantor aan dat het eenheidsvierkant dezelfde kardinaliteit had als \(\mathbb{R}\) zelf en werd in 1878 verplaatst om het volgende vooruit te gaan.

vermoeden (de continuümhypothese)

elke ontelbare deelverzameling van \(\mathbb{R}\) heeft dezelfde kardinaliteit als \(\mathbb{R}\).

Cantor was niet in staat om dit vermoeden te bewijzen of te weerleggen (samen met elke andere wiskundige). In feite was het bewijzen of weerleggen van dit vermoeden, dat de continuümhypothese werd genoemd, een van Hilberts beroemde \(23\) problemen die tijdens het Internationaal Wiskundecongres in 1900 als een uitdaging voor wiskundigen werden gepresenteerd.

omdat \(\mathbb{R}\) dezelfde kardinaliteit heeft als \(P (N)\), werd de continuümhypothese veralgemeend naar de:

vermoedens(de veralgemeende continuümhypothese)

gegeven een oneindige verzameling \(S\), is er geen oneindige verzameling die strikt een kardinaliteit heeft tussen die van \(s\) en haar machtsverzameling \(P (S)\).

pogingen om dit te bewijzen of te weerleggen waren tevergeefs en met goede reden. In 1940 toonde de logicus Kurt Gödel aan dat de continuümhypothese niet kon worden weerlegd uit de Zermelo-Fraenkel axioma ‘ s van de verzamelingenleer 1. In 1963 toonde Paul Cohen aan dat de continuümhypothese niet kon worden bewezen met behulp van de axioma ‘ s van Zermelo-Fraenkel. Met andere woorden, de axioma ‘ s van Zermelo-Fraenkel bevatten niet genoeg informatie om de waarheid van de hypothese te bepalen.

we zijn bereid om te wedden dat op dit moment je hoofd een beetje zwemt van onzekerheid. Als dat zo is, weet dan dat dit dezelfde gevoelens zijn die de wiskundige gemeenschap in het midden van de twintigste eeuw heeft ervaren. In het verleden werd wiskunde gezien als een model van logische zekerheid. Het is verontrustend om te ontdekken dat er verklaringen zijn die “onbeslist zijn.”In feite bewees Gödel in 1931 dat een consistent eindig axioma-systeem dat de axioma’ s van de rekenkunde bevatte altijd onbeslist uitspraken zou bevatten die noch waar noch onwaar konden worden bewezen met die axioma ‘ s. Wiskundige kennis zou altijd onvolledig zijn.

 fig 9.3.2.PNG

figuur \(\Pagindex{2}\): Kurt Gödel

dus door te proberen de grondslagen van de calculus op vaste grond te leggen, zijn we op een punt gekomen waar we nooit wiskundige zekerheid kunnen verkrijgen. Betekent dit dat we onze handen moeten overgeven en een nederlaag moeten toegeven? Moeten we verlamd zijn van angst om iets te proberen? Zeker niet! Zoals we al eerder vermeldden, doen de meeste wiskundigen het goed door een pragmatische aanpak te kiezen: hun wiskunde gebruiken om problemen op te lossen die ze tegenkomen. In feite zijn het meestal de problemen die de wiskunde motiveren. Het is waar dat wiskundigen risico ’s nemen die niet altijd uitkomen, maar ze nemen die risico’ s nog steeds, vaak met succes. Zelfs als de successen leiden tot meer vragen, zoals ze meestal doen, het aanpakken van die vragen leidt meestal tot een dieper begrip. Op zijn minst betekent ons onvolledige begrip dat we altijd meer vragen moeten beantwoorden, meer problemen moeten oplossen.

wat kan een wiskundige nog meer vragen?