Articles

9.3: Cantors Teorem Og Dens Konsekvenser

Ferdigheter Til Å Utvikle

  • Forklar Cantors teorem

Når Cantor viste at det var to typer uendelig (tellbar og utallige), var følgende spørsmål naturlig: «Har alle utallige sett samme kardinalitet?»

Akkurat som ikke alle «ikke-hunder» er katter, er det ingen grunn til å tro at alle utallige sett skal være like store. Men å bygge utallige sett med forskjellige størrelser er ikke så lett som det høres ut.

hva med for eksempel linjesegmentet som representeres av intervallet \ ( \ ) og kvadratet som representeres av settet \ (× =\{(x,y)|0 ≤ x, y ≤ 1\}\). Absolutt må det todimensjonale torget være et større uendelig sett enn det endimensjonale linjesegmentet. Bemerkelsesverdig Viste Cantor at disse to settene var samme kardinalitet. I sin 1877 korrespondanse av dette resultatet Til Sin venn Og med matematiker, Richard Dedekind, Bemerket Selv Cantor: «jeg ser det, men jeg tror det ikke !»

fig 9.3.1.png

Figur \(\PageIndex{1}\): Richard Dedekind

følgende gir den opprinnelige ideen Om Cantors bevis. Cantor utviklet følgende funksjon \(f:× →\). Først representerer vi koordinatene til et hvilket som helst punkt \((x, y)∈ ×\) ved deres desimalrepresentasjoner \ (x = 0.a_1a_2a_3 …\ ) og \ (y = 0.b_1b_2b_3….\ ) Selv avsluttende desimaler kan skrives på denne måten som vi kunne skrive \(0,5 = 0,5000….\ ) Vi kan da definere \(f (x, y)\) ved

\

Denne relativt enkle ideen har noen tekniske problemer i det relatert til følgende resultat.

Øvelse \(\PageIndex{1}\)

Vurder sekvensen \((0.9,0.99,0.999,…)\). Bestem at denne sekvensen konvergerer og faktisk konvergerer den til \(1\). Dette antyder at \(0.999… = 1\).

på Samme måte har vi \(0.04999… = 0.05000…\), osv. For å gjøre desimalrepresentasjonen av et reelt tall i \ ( \ ) unikt, må vi gjøre et konsekvent valg om å skrive et avsluttende desimal som en som ender i en uendelig streng av nuller eller en uendelig streng av niner . Uansett hvilket valg vi gjør, kunne vi aldri gjøre denne funksjonen på. For eksempel, \(109/1100 = 0,09909090…\ ) ville ha som sin pre-image \((0.0999…,0.9000…)\) som ville være en blanding av de to konvensjonene.

Cantor var i stand til å overvinne denne teknikken for å demonstrere en til en korrespondanse, men i stedet vil vi merke at i begge konvensjoner er funksjonen en-til-en, så dette sier at settet \(×\) er den samme kardinaliteten som noen (utallige) delmengde av \(\mathbb{R}\). Det faktum at dette har samme kardinalitet som \(\mathbb{R}\) er noe vi vil komme tilbake til. Men først vil vi prøve å konstruere et utallige sett som ikke har samme kardinalitet som \(\mathbb{R}\). For å løse dette problemet viste Cantor følgende i 1891.

Teorem \(\PageIndex{1}\): Cantors Teorem

La \(S\) være et sett. Da er det ingen en-til-en korrespondanse mellom \(S\) og\ (P (S)\), settet av alle undergrupper av \(S\).

Siden \(S\) kan settes inn i en-til-en korrespondanse med en delmengde av \(P(S) (a → \{a\})\), så sier dette at \(P (S)\) er minst like stor som \(S\). I det endelige tilfellet er \(/P (S|/\) strengt større enn \(/S/\) som følgende problem viser. Det viser også hvorfor \(P (S)\) kalles strømsettet til \(S\).

Øvelse \(\PageIndex{2}\)

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

Hint

La \(s = a_1, a_2,…, a_n\). Vurder følgende korrespondanse mellom elementene i \(P (S)\) og settet \(T\) av alle \(n\)-tupler av ja (\(Y\)) eller nei (\(N\)):

\

Hvor mange elementer er i \(T\)?

Øvelse \(\PageIndex{3}\)

Bevis Cantors Teorem.

Hint

Anta for motsetning, at det er en en-til-en korrespondanse \(f: S → P (S)\). Vurder \(a = \{x ∈ S /x \ ikke {∈} f (x)\}\). Siden \(f\) er på, så er det \(en ∈ A\) slik det \(a = f (a)\). Er \(en ∈ A\) eller er \(en \ikke {∈A\)?

Faktisk viser det seg at \(\mathbb{R}\) og\(P (\mathbb{N})\) har samme kardinalitet. Dette kan sees i en rundkjøring måte å bruke noen av de ovennevnte ideer Fra Øvelse \(\PageIndex{2}\). Spesifikt, la \(T\) være settet av alle sekvenser av nuller eller enere (du kan bruke \(Y\)s eller \(N\)s, hvis du foretrekker). Da er det greit å se at \(T\) og\(P (\mathbb{N})\) har samme kardinalitet.

hvis vi vurderer \((0,1]\), som har samme kardinalitet som \(\mathbb{R}\), så kan vi se at dette også har samme kardinalitet som \(T\). Spesielt, hvis vi tenker på tallene i binær, kan hvert reelt tall i \ ( \ ) skrives som \(\sum_{j=1}^{\infty } \frac{a_j}{2^j} = (a_1, a_2, \cdots)\) hvor \(a_j ∈ \{0,1\}\). Vi må redegjøre for det faktum at binære representasjoner som \(0.0111…\ ) og \(0.1000…\ ) representerer det samme reelle tallet (si at ingen representasjoner vil ende i en uendelig streng av nuller), så kan vi se at \(\) har samme kardinalitet som \(T – U\), hvor \(U\) er settet av alle sekvenser som slutter i en uendelig streng av nuller. Det viser seg at \(U\) selv er et tellbart sett.

Øvelse \(\PageIndex{4}\)

La \(U_n = \{(a_1, a_2, a_3,…) / a_j ∈ \ {0,1\}\) og \(a_{n + 1} = a_{n+2} = ··· = 0\}\). Vis at for hver \(n\), \(U_n\) er endelig og bruk dette til å konkludere med at \(U\) er countably uendelig.

følgende to problemer viser at sletting av et tellbart sett fra et utallige sett ikke endrer kardinaliteten.

Øvelse \(\PageIndex{5}\)

La \(S\) være et uendelig sett. Bevis at \(S\) inneholder en countably uendelig delmengde.

Øvelse \(\PageIndex{6}\)

Anta At \(X\) er et utallige sett og \ (Y ⊂ X\) er tellbart uendelig. Bevis at \(X\) og\ (X – Y\) har samme kardinalitet.

Hint

La \(Y = Y_0\). Hvis \(X-Y_0\) er et uendelig sett, inneholder det ved det forrige problemet et uendelig sett \(Y_1\). På samme måte hvis \(X – (Y_0 ∪ Y_1)\) er uendelig, inneholder den også et uendelig sett \(Y_2\). Igjen, hvis \(X – (Y_0 ∪ Y_1 ∪ Y_2)\) er et uendelig sett, inneholder det et uendelig sett \(Y_3\), etc. For \(n = 1,2,3,…,\) la \(f_n: y_{n-1} → Y_n\) være en en-til-en korrespondanse og definere \(f : X → X – Y\) etter

\

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

de ovennevnte problemene sier at \(R\), \(T – U\), \(T\) og \(P(N)\) alle har samme kardinalitet.

Som det ble indikert før, Hadde Cantors arbeid på uendelige sett en dyp innvirkning på matematikken i begynnelsen av det tjuende århundre. For eksempel, i å undersøke Beviset På Cantors Teorem, utviklet den eminente logikeren Bertrand Russell sitt berømte paradoks i 1901. Før denne tiden ble et sett naivt tenkt på som bare en samling av objekter. Gjennom Arbeidet Til Cantor og andre, settene ble et sentralt objekt for studier i matematikk som mange matematiske begreper ble omformulert i form av settene. Tanken var at settteori skulle være et samlende tema for matematikk. Dette paradokset satte den matematiske verden på øret.

Russells Paradoks

Vurder settet av alle sett som ikke er elementer av seg selv. Vi kaller dette settet \(D\) og spør, » Er \(D ∈ D\)?»Symbolsk sett er dette settet

\

Hvis \(D ∈ D\), så per definisjon, \(D \ ikke {∈} D\). Hvis D 6∈ D, så per definisjon, \(D ∈ D\).

hvis du ser tilbake på Beviset På Cantors Teorem, var dette i utgangspunktet ideen som ga oss motsigelsen. Å ha en slik motsetning som skjedde på det mest grunnleggende nivået i matematikk var skandaløst. Det tvang en rekke matematikere og logikere til å nøye utarbeide aksiomene som settene kunne bygges på. For å være ærlig, nærmer de fleste matematikere seg settteori fra et naivt synspunkt, da settene vi vanligvis håndterer, faller under kategorien av det vi vil kalle «normale sett.»Faktisk er en slik tilnærming offisielt kalt Naiv Settteori (i motsetning Til Aksiomatisk Settteori). Imidlertid førte forsøk på å sette settteori og logikk på solid grunnlag til den moderne studien av symbolsk logikk og til slutt utformingen av datamaskin (maskin) logikk.

Et annet sted Hvor Cantors arbeid hadde en dyp innflytelse i moderne logikk kommer fra noe vi antydet før. Vi viste før at enhetskvadratet \ ( × \ ) hadde samme kardinalitet som en utallige delmengde av \(\mathbb{R}\). Faktisk Viste Cantor at enhetskvadratet hadde samme kardinalitet som\ (\mathbb{R}\) selv og ble flyttet for å fremme følgende i 1878.

Formodning (Kontinuumhypotesen)

Hver utallige delmengde av \(\mathbb{R}\) har samme kardinalitet som \(\mathbb{R}\).

Cantor var ikke i stand til å bevise eller motbevise denne formodningen (sammen med alle andre matematikere). Faktisk var det å bevise eller motbevise Denne formodningen, som ble kalt Kontinuumhypotesen, En Av Hilberts berømte \(23\) problemer presentert som en utfordring for matematikere på Den Internasjonale Matematikerkongressen i 1900.

siden \(\mathbb{R}\) har samme kardinalitet som \(P (N)\), ble Kontinuumhypotesen generalisert til:

Formodning (Den Generaliserte Kontinuumhypotesen)

Gitt et uendelig sett \(S\), er det ikke noe uendelig sett som har en kardinalitet strengt mellom det av \(S\) og dets kraftsett \(P(S)\).

Forsøk på å bevise eller motbevise dette var forgjeves og med god grunn. I 1940 viste logikeren Kurt Gö at Kontinuumhypotesen ikke kunne motbevises Fra zermelo-Fraenkel-Aksiomene i mengdelære 1. I 1963 viste Paul Cohen at Kontinuumhypotesen ikke kunne bevises ved Hjelp Av Zermelo-Fraenkel-Aksiomene. Med Andre ord inneholder Zermelo-Fraenkel-Aksiomene ikke nok informasjon til å bestemme sannheten i hypotesen.

Vi er villige til å satse på at på dette punktet hodet kan svømme litt med usikkerhet. I så fall vet du at disse er de samme følelsene som det matematiske samfunnet opplevde i midten av det tjuende århundre. Tidligere ble matematikk sett på som en modell av logisk sikkerhet. Det er urovekkende å finne at det er uttalelser som er » undecidable.»Faktisk beviste Gö i 1931 at et konsistent endelig aksiomsystem som inneholdt aritmetikkens aksiomer alltid ville inneholde undecidable uttalelser som verken kunne bevises sanne eller falske med disse aksiomene. Matematisk kunnskap vil alltid være ufullstendig.

 fig 9.3.2.png

Figur \(\PageIndex{2}\): Kurt Gö

så ved å prøve å legge grunnlaget for kalkulator på fast grunn, har vi kommet til et punkt der vi aldri kan oppnå matematisk sikkerhet. Betyr dette at vi skal kaste opp våre hender og innrømme nederlag? Skal vi bli lammet av frykt for å prøve noe? Absolutt ikke! Som vi nevnte tidligere, gjør de fleste matematikere det bra ved å ta en pragmatisk tilnærming: bruke matematikken til å løse problemer de møter. Faktisk er det vanligvis problemene som motiverer matematikken. Det er sant at matematikere ta sjanser som ikke alltid panorere ut, men de fortsatt ta disse sjansene, ofte med suksess. Selv når suksesser føre til flere spørsmål, som de vanligvis gjør, takle disse spørsmålene fører vanligvis til en dypere forståelse. I det minste betyr vår ufullstendige forståelse at vi alltid vil ha flere spørsmål å svare på, flere problemer å løse.

hva annet kan en matematiker be om?