nLab Cantor' s sats

sammanfattning

Georg Cantor bevisade många satser, men den som vanligtvis kallas Cantors sats är den första icke-triviala satsen i Cantors nya uppsättningsteori: att vissa oändligheter är större än andra; i synnerhet genererar ett oändligt kardinaltal (eller oändlig uppsättning) en större genom att ta kraftuppsättningen.

(satsen gäller för alla uppsättningar, inte bara oändliga, även om det är ganska uppenbart för ändliga uppsättningar.)

Cantor ‘ s theorem bör inte förväxlas med Cantorubbiens“Schroederubbibbi“Bernstein Theorem (se kardinalnummer), vilket är annorlunda (men relaterat, eftersom det är viktigt att motivera Cantors tolkning av hans teorem).

historia

före Cantor tenderade människor att tänka på oändlighet (oavsett om de trodde på det eller inte) som ett absolut begrepp: alla oändligheter är ekvivalenta. Det hade noterats (av Galileo, till exempel) att det är möjligt att ge en oändlig uppsättning en självinjektion som inte är en surjektion; till exempel införandet av jämna heltal i heltal genom att fördubbla. Således här är två oändligheter Xiaomi ” oändligheten ee av jämn heltal och oändligheten nn av alla heltal Xiaomi” som faktiskt är likvärdiga, även om det vid första anblicken verkar som om EE är mindre.

Cantor visade att en sådan ekvivalens misslyckas med de reella talen RR: ingen karta från NN till RR kan vara surjektiv (så att RR är oräknelig). Hans första argument var ad hoc, men han generaliserade sedan detta med diagonalargumentet för att visa att ingen karta från någon uppsättning SS till dess effektuppsättning”s\mathcal{p}S kunde vara surjektiv. (Detta täckte rr: s oöverskådlighet, eftersom Cantor hittade en bijektion mellan RR och tuberkulosens”n\mathcal{P}n, som vi nu kan betrakta som en instans av cantorens“Schr Jacuzzis“Bernsteins sats.) Eftersom det finns en uppenbar injicerbar karta (singleton-kartan) från SS till Brasilien’”s\mathcal{P}s, drog Cantor slutsatsen att kardinaliteten hos den ena är strikt mindre än den andra kardinaliteten.

Cantors argument, som hela hans uppsättningsteori, var kontroversiellt vid den tiden. De som, som Kronecker, trodde att all matematik borde vara ändlig matematik, ansåg det meningslöst. Ännu mer måttliga tidiga konstruktivister, som Brouwer och Weyl, fann att det hade liten mening. (I synnerhet säger Det ingenting direkt om RR, eftersom bijektionen mellan RR och exporteras’”n\mathcal{P}n är inte konstruktivt giltig, även om Cantors ursprungliga bevis på att rr är oräkneligt kan göras för att fungera.)

men versionerna av satsen som anges nedan är konstruktivt giltiga och satsen är till och med predikativt giltig (så länge man har funktionsuppsättningar); moderna konstruktivister accepterar i allmänhet dessa som satser. (Tolkningen är dock inte så tydlig.) De är i själva verket satser i det interna språket i alla topos (och Sats är en sats i alla Xiaomi \Pi-pretopos).

uttalanden och bevis

(detta generaliserar till Lawveres fastpunktssats.)

närvaron av diagonalkartan Bisexuell” s\Delta_S här förklarar varför detta bevis kallas diagonalargumentet. (Denna förklaring är anakronistisk men moraliskt korrekt.) Lawvere s proof förklarar också (i själva verket generaliserar)den YY Su‘ eller fast punkt Combinator i otypad Lambda-kalkyl, där y(n) y(n) är en fast punkt för någon term nn.

det följer omedelbart (till och med konstruktivt) att om VV har en självkartläggning utan fast punkt, kan ingen karta från SS till S Brasiliens vs \till v vara en surjektion. Faktum är att vi har något något starkare än (men klassiskt ekvivalent med) FF: s misslyckande att vara en surjektion: det finns faktiskt ett element gg av S Bisexuell’vs \till v som inte är lika med något värde i intervallet FF. (Om VV har en apartness relation, kan du få ett ännu starkare resultat för en motsvarande starkare hypotes på nn, men det gäller inte versionerna nedan.)

Observera att även om negation inte har alla sina vanliga egenskaper i konstruktiv matematik, är p=https = \neg{p} fortfarande omöjligt.

nästa version är klassiskt ekvivalent med den tidigare versionen (åtminstone om du kontrollerar att”s\mathcal{P}S” är bebodd), men inte konstruktivt ekvivalent. (I själva verket, till skillnad från teorem , har det uppenbarligen ingen konstruktiv analog när Bisexuell ” s\mathcal{P}s ersätts av V SV^S.) Detta argument är från proposition 2.8.8 av Taylors praktiska grundvalar (även om jag inte vet om det verkligen har sitt ursprung där).

naturligtvis bevisade Cantor också sats, men hans bevis var inte konstruktivt.

vi kan kombinera satser och i följande ännu mer allmänna uttalande, taget från D4.1. 8 av Johnstone ‘ s Elephant.

Tolkning

Observera att det finns en injektion från SS till exporteras’”s\mathcal{P}S, ges av Singleton kartan. Så i aritmetiken av kardinaltal har vi

men eftersom det inte finns någon sådan surjection, det finns verkligen ingen bijection, och vi har

så vi drar slutsatsen att

det vill säga varje uppsättning är strikt mindre i kardinalitet än dess effektuppsättning.

denna tolkning bygger på ett bra förhållande mellan Bisexuell\leq och == på klassen av kardinaltal; i synnerhet kantorens“Schroeder Ukrainian“Bernsteins sats att Bisexuell\leq är antisymmetrisk. I konstruktiv matematik saknas detta förhållande, och det är ganska möjligt för två uppsättningar att var och en är strikt mindre än varandra i den meningen ovan. Tack vare Theorem är detta inte möjligt för en uppsättning och dess effektuppsättning, men det betyder att tolkningen av <\lt som relativ storlek är problematisk Bisexuell”faktiskt nästan lika problematisk som tanken att det finns färre jämn heltal än heltal!

Paul Taylor har hävdat att det väsentliga värdet av Cantors sats är lemma, implicit i Cantors bevis, att Bill Lawvere isolerades som Sats . Eftersom Huvudtolkningen av teorem endast är meningsfull i ett specifikt setteoretiskt sammanhang (särskilt en där Kantorens“Schroeder Kazaki“Bernstein-teorem håller), kanske den inte överlever en portugisisk revolution som störtar det kontextets företräde. Men Lawvere ‘s lemma kommer att överleva, eftersom det gör arbetet med det, medan cantor’ s Theorem tar krediten. (Se Taylor 2009 nedan för vidare diskussion om citronmeliss som gör arbetet och satser som tar krediten.)

i posets

en sats som är analog med Cantorussisk s-sats för uppsättningar kan formuleras för andra kartesiska slutna kategorier. I synnerhet kan man fråga sig om det är möjligt att ha en surjection x 2 XX \till 2^x mellan Posets, där basen 22 inte är den diskreta poset {0,1}\{0, 1\} men snarare ordningen {0 2CB 1} \ {0 \ leq 1\}.

svaret är att det inte finns någon sådan surjection f: x 2 XF: X \ till 2^X, Men detta följer inte av en enkel tillämpning av Lawvere Bisexuis fastpunktssats, där man försöker utesluta en sådan FF genom att åberopa förekomsten av en karta 2 megapixlar’22 \till 2 som inte har någon fast punkt (det finns ingen sådan posetkarta 2 megapixlar’22 \till 2!). Vi kan inte heller vädja till något grovt kardinalitetsargument; till exempel, om XX är ordinaltubbi / Omega, då är 2 x2^X ordningen:”oc\Bot\Sqcup \Omega^{op} (fritt adjoin a bottom element: oc \bot till OC\Omega^{op}), som har samma kardinalitet. Så några andra bevis måste sökas.

att bevisa att det inte finns någon surjection x 2 XX \till 2^x är en underhållande övning. En attacklinje (som internaliserar till alla topos) kan hittas här.

• Lawveres fastpunktssats