nLab Cantor's teorem
Sammendrag
Georg Cantor viste mange teoremer, men Den som vanligvis kalles Cantors teorem er Den første nontrivialteoremet Til Cantors nye settteori: at Noen uendeligheter er større enn andre; spesielt genererer et uendelig kardinaltall (eller uendelig sett) en større ved å ta kraftsettet.
(teoremet gjelder for alle sett, ikke bare uendelige, selv om det er ganske åpenbart for begrensede sett.)
Kantors teorem må ikke forveksles med Cantorâ €Schroederâ €Bernstein Teorem (se kardinaltall), som er forskjellig (men relatert, da det er viktig å rettferdiggjøre kantors Tolkning av hans teorem).
Historie
før Cantor hadde folk en tendens til å tenke på uendelig (om de trodde på det eller ikke) som et absolutt konsept: alle uendeligheter er likeverdige. Det hadde blitt lagt merke Til (Av Galileo, for eksempel) at Det er mulig å gi et uendelig sett en selvinjeksjon som ikke er en surjection; for eksempel, inkluderingen av de jevne heltallene i heltallene ved dobling. Dermed er her to uendeligheter â € “uendelig ee av like heltall og uendelig nn av alle heltallâ €” som faktisk er ekvivalente, selv om det ved første øyekast ser ut til at ee er MINDRE.
Cantor viste at en slik ekvivalens mislykkes med de reelle tallene RR: ingen kart FRA NN TIL RR kan være surjektiv(SLIK AT RR er utallige). Hans første argument var ad hoc, men han generaliserte dette med diagonalargumentet for å vise at ingen kart fra et SETT SS Til dets kraftsett ð ￮”s\mathcal{p}S Kunne være surjektive. (Dette dekket uncountability AV RR, Siden Cantor fant en bijection mellom RR og ð ￮ ‘ “n \ mathcal {p} n,som vi nå kan betrakte Som en forekomst Av cantorâ €Schrã ¶ Derâ €bernstein teorem.) Siden det er et åpenbart injektivkart (singleton-kartet) FRA SS til ð ￮”s\mathcal{p}S, Konkluderte Cantor at kardinaliteten til den ene er strengt mindre enn kardinaliteten til den andre.
Cantors argument, som hele hans settteori, var kontroversielt på den tiden. De Som, Som Kronecker, trodde at all matematikk skulle være endelig matematikk, betraktet det meningsløst. Enda mer moderate tidlige konstruktivister, Som Brouwer Og Weyl, fant at det hadde lite poeng. (Spesielt sier det ingenting direkte om RR, siden bijeksjonen mellom RR og ð ￮”n\mathcal {p} N Ikke er konstruktivt gyldig, selv om cantors opprinnelige bevis på at rr er utallige, kan gjøres til arbeid.)
versjonene av teoremet som er angitt nedenfor er imidlertid konstruktivt gyldige, Og Teoremet er til og med predikativt gyldig (så lenge man har funksjonssett); moderne konstruktivister aksepterer generelt disse som teoremer. (Tolkningen er imidlertid ikke så klar.) De er faktisk teoremer i det indre språket til noen topos(og Teorem er et teorem i noen Î \ Pi-pretopos).
Uttalelser og bevis
Teorem
(Lawvers versjon.)
Gitt sett SS OG VV, anta at det er en surjection FRA SS til funksjonssettet sâ †vs \ til v (også skrevet v SV^S). Deretter har hvert kart n: Vâ †Vn\colon v \ til v et fast punkt; det vil si n (x) = xn (x) = x for noen x:Vx\colon V.
(dette generaliserer Til Lawvere ‘ s fixed point theorem.)
Bevis
La f:Sâ †(Sâ †V)F\colon s \til (s \til v) Være en hvilken som helst funksjon, og vurder funksjonen g: sâ † ‘ Vg \ Colon S\til V gitt Av
Det er, hvis man bruker currying å tolke ff som en funksjon fra SÃSS \ganger S til V., så gg er definert ved hjelp av diagonale kart Î S\Delta_S som
anta nå at ff er surjektiv. Da må det være noe element a:Sa\colon S slik at f(a)=gf(a) = g. Men så
så g(a)g(a) er et fast punkt på nn.
Tilstedeværelsen av diagonalkartet Î S\Delta_S her forklarer hvorfor dette beviset kalles diagonalargumentet. (Denne forklaringen er anakronistisk, men moralsk korrekt.) Lawvere@ bevis forklarer også (faktisk generaliserer) Yyâ € Eller fast-punkt kombinator i untyped lambda-kalkulus, hvor y(n)y(n) er et fast-punkt for enhver term nn.
det følger umiddelbart (selv konstruktivt) at HVIS VV har en selvkartlegging uten fast punkt, kan ikke noe kart FRA SS Til Sâ †vs \ til v være en surjeksjon. Faktisk har vi noe litt sterkere enn (men klassisk ekvivalent med) feilen i ff til å være en surjection: det eksisterer faktisk et element gg Av Sâ †vs \ til v Som ikke er lik noen verdi i ff-området. (HVIS VV har et apartness-forhold, kan du få et enda sterkere resultat for en tilsvarende sterkere hypotese på nn, men det gjelder ikke versjonene nedenfor.)
Teorem
(Cantors versjon.)
Gitt et SETT SS, er det ingen surjection FRA SS til strømsettet ð ￮”S\mathcal {p} S.
Bevis
La VV være settet av sannhetsverdier, og la n: Vâ †vn\colon v \å v Re negasjon. Siden nn ikke har noe fast punkt, bruk Teorem .
Merk at selv om negasjon ikke har alle sine vanlige egenskaper i konstruktiv matematikk, er p=Â = \neg{p} fortsatt umulig.
den neste versjonen er klassisk ekvivalent med den forrige versjonen (i hvert fall hvis du sjekker at ð ￮”s\mathcal{p} s er bebodd), men ikke konstruktivt ekvivalent. (Faktisk, i motsetning Til Teorem , har det tilsynelatende ingen konstruktiv analog når ð ￮”s\mathcal{p}s er erstattet av v SV^s.) Dette Argumentet er fra proposisjon 2.8.8 av taylors praktiske Grunnlag (Selv om jeg ikke vet om det virkelig oppsto der).
Teorem
(Taylors versjon.)
Gitt et SETT SS, er det ingen injeksjon fra ð ￮ ‘ “s\mathcal{p}S til ss.
Bevis
La jeg:ð ￮ ‘”Sâ †’ Si \ Colon \ mathcal{p}S \til s være noen funksjon. Definer f: Sâ †ð ￮ ” sf \ Colon s \ til \ mathcal {p}S Som Følger:
hvis ii er en injeksjon, er ff en tilbaketrekking av ii og dermed en surjeksjon, som er umulig Ved Teorem .
Selvfølgelig beviste Cantor Også Teorem, men hans bevis var ikke konstruktivt.
vi kan kombinere Teoremer og inn i følgende enda mer generelle uttalelse, hentet Fra D4.1.8 Av Johnstone ‘ S Elephant.
Teorem
(Johnstones versjon.)
Gitt et SETT SS, kan dets strømsett ð ￮”s\mathcal{p}S ikke uttrykkes som en subquotient av ss.
Bevis
Anta at vi hadde et sett BB, en injeksjon jeg:BâªSi\kolon B \hookrightarrow S og en surjection f:Bâð”Sf\kolon B \til \mathcal{P}S. Deretter preimage funksjon i *:ð”Sâð”Bi^*\kolon\mathcal{P}S \til \mathcal{P}B ville være en surjection (fordi jeg *∃ i=1 ð”Bi^\ast \exists_i = 1_{\mathcal{P}B}), som ville bildet funksjonen f ∃:ð”Bâð”ð”S\exists_f\kolon \mathcal{P}B \til \mathcal{P}\mathcal{P}S (fordi ∃ ff *=1 ð”ð”S\exists_f f^\ast = 1_{\mathcal{P}\mathcal{P}S}). Dermed ville deres sammensetning være en surjection ð ￮ ‘ “Sâ † ‘” ④ ” s \ mathcal {p} s \ Til \ Mathcal {p} \ mathcal {p} s, Som er Umulig ved teorem .
Tolkning
Merk at DET finnes en injeksjon FRA SS TIL ð ￮ ‘ “s\mathcal {p} s, gitt av singleton-kartet. Så i aritmetikken til kardinaltall har vi
men siden det ikke er noen slik surjection, er det absolutt ingen bijection, og vi har
så vi konkluderer med at
det vil si at hvert sett er strengt mindre i kardinalitet enn strømsettet.
denne tolkningen er avhengig av et godt forhold mellom â ‰ ¤\leq og == i klassen av kardinaltall; spesielt er cantorâ €Schroederâ €Bernstein Teorem At  ‰ ¤\leq er antisymmetrisk. I konstruktiv matematikk mangler dette forholdet, og det er ganske mulig for to sett å hver være strengt mindre enn hverandre i den forstand ovenfor. Takket Være Teoremet er dette ikke mulig for et sett og dets kraftsett, men det betyr at tolkningen av <\lt som relativ størrelse er problematisk â €faktisk nesten like problematisk som ideen om at det er færre like heltall enn heltall!
Paul Taylor har hevdet At Den essensielle verdien Av Cantors Teorem er lemma, implisitt I Cantors bevis, At Bill Lawvere isolert Som Teorem . Siden Hovedfortolkningen av Teoremet kun er meningsfull i en bestemt settteoretisk kontekst (spesielt en Der Cantorâ €Schroederâ €Bernstein-Teoremet holder), kan det ikke overleve en â € revolusjonâ € ™ som omstyrter forrangen til den konteksten. Men Lawvere ‘ s lemma vil overleve, siden det â € gjør jobbenâ € ™ mens cantors Teorem â € tar kredittkort. (Se Taylor 2009 nedenfor for videre diskusjon av hryvnias lemmas Som gjør arbeidet og teoremer Som tar credit5.)
i posets
kan et teorem som Er Analogt Med Cantorâ € ™ s teorem for sett formuleres for andre kartesiske lukkede kategorier. Spesielt kan man spørre om Det Er mulig Å ha en surjection Xâ †2 xx \til 2 ^ x Mellom posets, hvor basen 22 ikke er den diskrete poset {0,1}\{0, 1\} men heller rekkefølgen {0â ‰ ¤ 1} \ {0\leq 1\}.
svaret er at det ikke finnes en slik surjeksjon f: Xâ †2 Xf: X \til 2^X, men dette følger ikke av en enkel anvendelse Av Lawvereinois s fastpunktsteorem, hvor man forsøker å utelukke en slik ff ved å påkalle eksistensen av et kart 2â †22 \ til 2 som ikke har et fast punkt (det er ikke noe slikt poset kart 2â †22 \til 2!). Vi kan heller ikke appellere til noe grovt kardinalitetsargument; for EKSEMPEL, HVIS XX er ordinal Ï ‰omega, Så er 2 x2 ^ X ordren âš ¥ âš ” ï ‰ op \ botSqcup \ omega ^{op} (fritt støter på et bunnelement âš ¥\bot til ï ‰ op\omega^{op}), som har samme kardinalitet. Så noen andre bevis må søkes.
Å Bevise At Det Ikke er noen surjection Xâ †2 xx \til 2^x Er en morsom øvelse. En angrepslinje (som internaliserer til noen topos) finner du her.
- Lawvere ‘ s fast punkt teorem
