Articles

9.3: Cantors sætning og dens konsekvenser

færdigheder til at udvikle

  • Forklar Cantors sætning

når Cantor viste, at der var to typer uendelighed (tællelig og utallige), var følgende spørgsmål naturligt: “har alle utallige sæt den samme kardinalitet?”

ligesom ikke alle “ikke-hunde” er katte, er der ingen grund til at tro, at alle utallige sæt skal have samme størrelse. Men konstruere utallige sæt af forskellige størrelser er ikke så nemt som det lyder.

for eksempel,hvad med linjesegmentet repræsenteret af intervallet \(\) og firkanten repræsenteret af sættet \ (list = \{(h,y)|0 list h, y list 1\}\). Bestemt den todimensionale firkant skal være et større uendeligt sæt end det endimensionelle linjesegment. Bemærkelsesværdigt viste Cantor, at disse to sæt var den samme kardinalitet. I sin 1877 korrespondance af dette resultat til sin ven og kollega matematiker, Richard Dedekind, selv Cantor bemærkede, ” jeg ser det, men jeg tror ikke på det!”

fig 9.3.1.png

figur \(\Sideindeks{1}\): Richard Dedekind

følgende giver den oprindelige ide om Cantors bevis. Cantor udtænkt følgende funktion \(f: lot\). For det første repræsenterer vi koordinaterne for et hvilket som helst punkt \((H,y) list\) ved deres decimalrepræsentationer \(h = 0.a_1a_2a_3 …\ ) og \(y = 0.b_1b_2b_3….\ ) Selv terminerende decimaler kan skrives på denne måde, som vi kunne skrive \(0,5 = 0,5000….\ ) Vi kan derefter definere \(f (H,y)\) ved

\

denne relativt enkle ide har nogle tekniske vanskeligheder i forbindelse med følgende resultat.

øvelse \(\Sideindeks{1}\)

overvej sekvensen \((0.9,0.99,0.999,…)\). Bestem, at denne sekvens konvergerer, og faktisk konvergerer den til \(1\). Dette tyder på, at \(0.999… = 1\).

Tilsvarende har vi \(0.04999… = 0.05000…\), osv. For at gøre decimalrepræsentationen af et reelt tal i \(\) unikt, skal vi foretage et konsekvent valg af at skrive en afsluttende decimal som en, der ender i en uendelig streng af nuller eller en uendelig streng af ni . Uanset hvilket valg vi foretager, vi kunne aldrig gøre denne funktion på. For eksempel \(109/1100 = 0,09909090…\ ) ville have som sin pre-image \((0.0999…,0.9000…)\) hvilket ville være en blanding af de to konventioner.

Cantor var i stand til at overvinde denne teknikalitet for at demonstrere en en til en korrespondance, men i stedet vil vi bemærke, at funktionen i begge konventioner er en-til-en, så dette siger, at Sættet \ (prist\) er den samme kardinalitet som en (utallige) delmængde af \(\mathbb{R}\). Det faktum, at dette har den samme kardinalitet som \(\mathbb{R}\) er noget, vi vil vende tilbage til. Men først vil vi forsøge at konstruere et utallige sæt, som ikke har samme kardinalitet som \(\mathbb{R}\). For at løse dette problem beviste Cantor følgende i 1891.

Sætning \(\Sideindeks{1}\): Cantors sætning

Lad \(S\) være ethvert sæt. Så er der ingen en-til-en korrespondance mellem \(S\) og \(P(S)\), sættet af alle undergrupper af \(S\).

da \(S\) kan sættes i en-til-en korrespondance med en delmængde af \(P(S) (en lot \{a\})\), Så siger dette, at \(P(S)\) er mindst lige så stor som \(S\). I det endelige tilfælde er \(/P (S)|\) strengt større end \(|S|\) som følgende problem viser. Det viser også, hvorfor \(P(S)\) kaldes strømsættet \(S\).

Øvelse \(\Sideindeks{2}\)

Bevis: Hvis \(/S / = n\), så \(|P(S)| = 2n\)

Hint

Lad \(S = a_1, a_2,…, a_n\). Overvej følgende korrespondance mellem elementerne i \(P (S)\) og Sættet \(T\) af alle \(n\) – tupler af ja (\(Y\)) eller nej (\(N\)):

\

hvor mange elementer er der i \(T\)?

øvelse \(\Sideindeks{3}\)

bevis Cantors sætning.

Hint

Antag for modsigelse, at der er en en-til-en korrespondance \(F : S P(S)\). Overvej \(A = \ {S / S \ ikke {l} f (S)\}\). Da \(f\) er på, så er der \(en lussing a\) sådan at \(a = f(a)\). Er \(a lot A\) eller er \(A \ikke {lot} A\)?

faktisk viser det sig, at \(\mathbb{R}\) og \(P(\mathbb{N})\) har samme kardinalitet. Dette kan ses på en rundkørsel ved hjælp af nogle af ovenstående ideer fra øvelse \(\Sideindeks{2}\). Specifikt lad \(T\) være sættet med alle sekvenser af nuller eller dem (du kan bruge \(Y\) s eller \(N\) s, hvis du foretrækker det). Så er det ligetil at se, at \(T\) og \(P(\mathbb{N})\) har samme kardinalitet.

hvis vi overvejer \((0,1]\), som har samme kardinalitet som \(\mathbb{R}\), så kan vi se, at dette også har samme kardinalitet som \(T\). Specifikt, hvis vi tænker på tallene i binær, så kan hvert reelt tal i \ ( \ ) skrives som \(\sum_{j=1}^{\infty } \frac{a_j}{2^j} = (a_1, a_2, \cdots )\) hvor \(a_j lit \{0,1\}\). Vi skal redegøre for, at binære repræsentationer som \(0.0111…\ ) og \(0.1000…\ ) repræsenterer det samme reelle tal (sig at ingen repræsentationer vil ende i en uendelig streng af nuller), så kan vi se, at \ ( \ ) har samme kardinalitet som \(T – U\), hvor \(U\) er sæt af alle sekvenser, der slutter i en uendelig streng af nuller. Det viser sig, at \(U\) selv er et tælleligt sæt.

øvelse \(\Sideindeks{4}\)

lad \(U_n = \ {(a_1, a_2, a_3,…) / a_j lit \{0,1\}\) og \(a_{n + 1} = a_{n+2} = ··· = 0\}\). Vis, at for hver \(n\) er \(U_n\) endelig, og brug dette til at konkludere, at \(U\) er tælleligt uendelig.

de følgende to problemer viser, at sletning af et tællbart sæt fra et utallige sæt ikke ændrer dets kardinalitet.

øvelse \(\Sideindeks{5}\)

Lad \(S\) være et uendeligt sæt. Bevis at \(S\) indeholder en countably uendelig delmængde.

øvelse \(\Sideindeks{6}\)

Antag, at \(H\) er et utallige sæt, og \(Y L\\) er tælleligt uendelig. Bevis at \(H\) og \(H\) har samme kardinalitet.

Tip

Lad \(Y = Y_0\). Hvis \(y_0\) er et uendeligt sæt, indeholder det ved det forrige problem et uendeligt uendeligt sæt \(Y_1\). På samme måde, hvis \(y_0 (y_0) y_1)\) er uendelig, indeholder den også et uendeligt sæt \(Y_2\). Igen, hvis \(y_0 liter y_1 liter Y_2)\) er et uendeligt sæt, så indeholder det et uendeligt sæt \(Y_3\) osv. For \(n = 1,2,3,…,\) lad \(f_n: y_{n-1} lis Y_n\) være en en-til-en korrespondance og definer \(f : Lis Lis – y\) ved

\

vis at \(f\) er en-til-en og på.

ovenstående problemer siger, at \(R\), \(T – U\), \(T\) og \(P(N)\) alle har samme kardinalitet.

som tidligere nævnt havde Cantors arbejde med uendelige sæt en dybtgående indvirkning på matematik i begyndelsen af det tyvende århundrede. For eksempel ved at undersøge beviset for Cantors sætning udtænkte den fremtrædende logiker Bertrand Russell sit berømte paradoks i 1901. Før dette tidspunkt blev et sæt naivt betragtet som bare en samling objekter. Gennem Cantor og andres arbejde blev Sæt ved at blive et centralt objekt for studier i matematik, da mange matematiske begreber blev omformuleret med hensyn til sæt. Ideen var, at sætteori skulle være et samlende tema for matematik. Dette paradoks satte den matematiske verden på øret.

Russells paradoks

overvej sæt af alle sæt, som ikke er elementer af sig selv. Vi kalder dette sæt \(D\) og spørger, ” Er \(D Lr D\)?”Symbolsk set er dette sæt

\

hvis \(D-ret D\), derefter per definition, \(D \ ikke {- ret} D\). Hvis D 6 liter D, derefter pr.

hvis du ser tilbage på beviset for Cantors sætning, var dette dybest set ideen, der gav os modsætningen. At have en sådan modsigelse på det mest basale niveau af matematik var skandaløst. Det tvang en række matematikere og logikere til omhyggeligt at udtænke de aksiomer, hvormed sæt kunne konstrueres. For at være ærlig, de fleste matematikere nærmer sig stadig sætteori fra et naivt synspunkt, da de sæt, vi typisk beskæftiger os med, falder ind under kategorien af det, vi ville kalde “normale sæt.”Faktisk kaldes en sådan tilgang officielt naiv sætteori (i modsætning til aksiomatisk sætteori). Forsøg på at sætte sætteori og logik på solid fod førte imidlertid til den moderne undersøgelse af symbolsk logik og i sidste ende design af computer (maskine) logik.

et andet sted, hvor Cantors arbejde havde en dybtgående indflydelse i moderne logik, kommer fra noget, vi hentydede til før. Vi viste før, at enhedsfirkanten \ (prist\) havde samme kardinalitet som en utallige delmængde af \(\mathbb{R}\). Faktisk viste Cantor, at enhedens firkant havde samme kardinalitet som \(\mathbb{R}\) selv og blev flyttet til at fremme følgende i 1878.

formodning (kontinuumhypotesen)

hver utallige delmængde af \(\mathbb{R}\) har samme kardinalitet som \(\mathbb{R}\).

Cantor var ude af stand til at bevise eller modbevise denne formodning (sammen med enhver anden matematiker). Faktisk var det at bevise eller modbevise denne formodning, der blev kaldt kontinuumhypotesen, et af Hilberts berømte \(23\) problemer, der blev præsenteret som en udfordring for matematikere på den internationale kongres for matematikere i 1900.

siden \(\mathbb{R}\) har samme kardinalitet som \(P (N)\), blev kontinuumhypotesen generaliseret til:

formodning(den generaliserede Kontinuumhypotese)

givet et uendeligt sæt \(S\) er der intet uendeligt sæt, der har en kardinalitet strengt mellem den af \(S\) og dens strømsæt \(P (S)\).

bestræbelserne på at bevise eller modbevise dette var forgæves og med god grund. I 1940 viste logikeren Kurt g Kurtdel, at kontinuumhypotesen ikke kunne modbevises fra nul-Fraenkel-Aksiomerne i sætteori 1. I 1963 viste Paul Cohen, at kontinuumhypotesen ikke kunne bevises ved hjælp af nul-Fraenkel-Aksiomerne. Med andre ord indeholder Aksiomerne ikke nok information til at bestemme hypotesens sandhed.

vi er villige til at satse på, at dit hoved måske svømmer lidt med usikkerhed. I så fald skal du vide, at dette er de samme følelser, som det matematiske samfund oplevede i midten af det tyvende århundrede. Tidligere blev matematik set som en model for logisk sikkerhed. Det er foruroligende at finde ud af, at der er udsagn, der er “ubeslutsomme.”Faktisk beviste G. Krusdel i 1931, at et konsistent endeligt aksiomsystem, der indeholdt aritmetikens aksiomer, altid ville indeholde ubeslutsomme udsagn, som hverken kunne bevises sande eller falske med disse aksiomer. Matematisk viden vil altid være ufuldstændig.

 fig 9.3.2.png

figur \(\Sideindeks{2}\): Kurt g Kurtdel

så ved at forsøge at sætte grundlaget for calculus på fast grund, er vi kommet til et punkt, hvor vi aldrig kan opnå matematisk sikkerhed. Betyder det, at vi skal kaste vores hænder op og indrømme nederlag? Skal vi være lammet af frygt for at prøve noget? Bestemt ikke! Som vi nævnte før, klarer de fleste matematikere sig godt ved at tage en pragmatisk tilgang: bruge deres matematik til at løse problemer, de støder på. Faktisk er det typisk de problemer, der motiverer matematikken. Det er rigtigt, at matematikere tager chancer, der ikke altid panorerer, men de tager stadig disse chancer, ofte med succes. Selv når succeserne fører til flere spørgsmål, som de typisk gør, at tackle disse spørgsmål fører normalt til en dybere forståelse. I det mindste betyder vores ufuldstændige forståelse, at vi altid vil have flere spørgsmål at besvare, flere problemer at løse.

hvad mere kunne en matematiker bede om?