nLab Cantor' s Theorem
Zusammenfassung
Georg Cantor bewies viele Sätze, aber der gewöhnlich Cantors Theorem genannte ist der erste nichttriviale Satz von Cantors neuer Mengenlehre: Dass einige Unendlichkeiten größer sind als andere; Insbesondere erzeugt jede unendliche Kardinalzahl (oder unendliche Menge) eine größere, indem sie die Potenzmenge nimmt.
(Der Satz gilt für alle Mengen, nicht nur für unendliche, obwohl er für endliche Mengen ziemlich offensichtlich ist.)
Cantors Theorem sollte nicht mit dem Cantorâ Schroederâ Bernstein-Theorem verwechselt werden (siehe Kardinalzahl), das anders ist (aber verwandt ist, da es wichtig ist, Cantors Interpretation seines Theorems zu rechtfertigen).
Geschichte
Vor Cantor neigten die Menschen dazu, die Unendlichkeit (ob sie daran glaubten oder nicht) als absolutes Konzept zu betrachten: Alle Unendlichkeiten sind gleichwertig. Es war bemerkt worden (zum Beispiel von Galileo), dass es möglich ist, einer unendlichen Menge eine Selbstinjektion zu geben, die keine Surjektion ist; zum Beispiel die Einbeziehung der geraden ganzen Zahlen in die ganzen Zahlen durch Verdoppelung. So sind hier zwei Unendlichkeiten â ”die Unendlichkeit EE von geraden ganzen Zahlen und die Unendlichkeit NN aller integersâ , die tatsächlich äquivalent sind, obwohl es auf den ersten Blick scheint, dass EE kleiner ist.
Cantor zeigte, dass eine solche Äquivalenz mit den reellen Zahlen RR fehlschlägt: Keine Karte von NN nach RR kann surjektiv sein (so dass RR unzählbar ist). Sein erstes Argument war ad hoc, aber er verallgemeinerte dies dann mit dem diagonalen Argument, um zu zeigen, dass keine Karte von einer Menge SS zu ihrer Potenzmenge ð”S\mathcal {P} S surjektiv sein könnte. (Dies bedeckte die Unzählbarkeit von RR, da Cantor eine Bijektion zwischen RR und ð”N \ mathcal {P}N fand, die wir jetzt als eine Instanz des Cantorâ Schrö derâ Bernstein-Theorems betrachten können.) Da es eine offensichtliche injektive Karte (die Singleton-Karte) von SS zu ð”S\ mathcal {P}S gibt, kam Cantor zu dem Schluss, dass die Kardinalität der einen streng kleiner ist als die Kardinalität der anderen.
Cantors Argument war, wie seine gesamte Mengenlehre, zu dieser Zeit umstritten. Diejenigen, die wie Kronecker glaubten, dass alle Mathematik endliche Mathematik sein sollte, hielten sie für bedeutungslos. Noch gemäßigtere frühe Konstruktivisten wie Brouwer und Weyl fanden, dass es wenig Sinn hatte. (Insbesondere sagt es nichts direkt über RR aus, da die Bijektion zwischen RR und ð”N \ mathcal {P} N nicht konstruktiv gültig ist, obwohl Cantors ursprünglicher Beweis, dass RR unzählbar ist, zum Funktionieren gebracht werden kann.)
Die unten angegebenen Versionen des Satzes sind jedoch konstruktiv gültig, und der Satz ist sogar prädikativ gültig (solange man Funktionsmengen hat); Moderne Konstruktivisten akzeptieren diese im Allgemeinen als Theoreme. (Die Interpretation ist jedoch nicht so klar.) Sie sind in der Tat Theoreme in der internen Sprache eines Topos (und Theorem ist ein Theorem in jedem Î \Pi-pretopos).
Aussagen und Beweise
Theorem
(Lawvere’s Version.)
Angenommen, es gibt eine Surjektion von SS zu der Funktionsmenge SâVS \bis V (auch geschrieben V SV^S). Dann hat jede Karte n:Vâ Vn\colon V \to V einen festen Punkt; das heißt, n(x) = xn (x) = x für einige x:Vx\colon V.
( Dies verallgemeinert sich auf Lawveres Fixpunktsatz.)
Beweis
Sei f:Sâ(SâV)f\colon S \to (S \to V) eine beliebige Funktion und betrachte die Funktion g:SâVg\colon S \to V gegeben durch
Das heißt, wenn man currying verwendet, um ff als eine Funktion von SãSS \ S zu VV zu interpretieren, dann wird gg unter Verwendung der diagonalen Karte Î S\Delta_S als
Angenommen, ff ist surjektiv. Dann muss es ein Element geben a:Sa\colon S so, dass f(a)=gf(a) = g. Aber dann
also ist g(a)g(a) ein fester Punkt von nn.
Das Vorhandensein der Diagonalkarte Δ S\Delta_S erklärt hier, warum dieser Beweis als Diagonalargument bezeichnet wird. (Diese Erklärung ist anachronistisch, aber moralisch korrekt.) Lawvereâ s Beweis erklärt auch (in der Tat verallgemeinert) die YYâ oder Fixpunkt-Kombinator in untypisierten Lambda-Kalkül, wo Y (n) Y (n) ein Fixpunkt für jeden Begriff nn ist.
Es folgt sofort (sogar konstruktiv), dass, wenn VV eine Selbstkartierung ohne festen Punkt hat, keine Karte von SS nach Sâ VS \nach V eine Surjektion sein kann. Tatsächlich haben wir etwas etwas Stärkeres als (aber klassisch äquivalentes) das Versagen von ff, eine Surjektion zu sein: Es gibt tatsächlich ein Element gg von Sâ VS \bis V , das keinem Wert im Bereich von ff entspricht. (Wenn VV eine Apartness-Relation hat, können Sie für eine entsprechend stärkere Hypothese zu nn ein noch stärkeres Ergebnis erhalten, dies gilt jedoch nicht für die folgenden Versionen.)
Satz
(Kantors Version.)
Bei einer Menge SS gibt es keine Surjektion von SS zur Potenzmenge ð”S\mathcal{P}S.
Beweis
Sei VV die Menge der Wahrheitswerte und sei n:VâVn\colon V \to V Negation. Da nn keinen festen Punkt hat, wenden Sie den Satz an .
Beachten Sie, dass, obwohl Negation nicht alle ihre üblichen Eigenschaften in der konstruktiven Mathematik hat, p=Âpp = \neg{p} immer noch unmöglich ist.
Die nächste Version ist klassisch äquivalent zur vorherigen Version (zumindest wenn Sie überprüfen, ob ð”S\mathcal{P}S bewohnt ist), aber nicht konstruktiv äquivalent. (In der Tat hat es im Gegensatz zum Theorem anscheinend kein konstruktives Analogon, wenn ð”S\mathcal{P}S durch V SV ^ S ersetzt wird.) Dieses Argument stammt aus Satz 2.8.8 von Taylors Practical Foundations (obwohl ich nicht weiß, ob es wirklich dort entstanden ist).
Satz
(Taylors Version.)
Bei einer Menge SS erfolgt keine Injektion von ð”S\mathcal{P}S nach SS.
Beweis
Sei i:ð”Sâ’Si\colon \mathcal{P}S \to S eine beliebige Funktion. Definieren Sie f:Sâð”Sf\colon S \to \mathcal{P}S wie folgt:
Wenn ii eine Injektion ist, dann ist ff eine Retraktion von ii und damit eine Surjektion, was durch den Satz unmöglich ist .
Natürlich bewies Cantor auch Theorem , aber sein Beweis war nicht konstruktiv.
Wir können Theoreme kombinieren und in die folgende noch allgemeinere Aussage, entnommen aus D4.1.8 von Johnstones Elefant.
Satz
(Johnstones Version.)
Bei einer Menge SS kann ihre Potenzmenge ð”S\mathcal{P}S nicht als Subquotient von SS ausgedrückt werden.
Beweis
nehmen wir an, wir hatten eine Reihe BB, eine Injektion i:BâªSi\colon B \hookrightarrow S und eine surjection f:Bâð”Sf\colon B \to \mathcal{P}S. Dann wird das preimage-Funktion, die ich *:ð”Sâð”Bi^*\colon\mathcal{P}S \to \mathcal{P}B wäre eine surjection (weil ich *∃ i=1 ð”Bi^\ast \exists_i = 1_{\mathcal{P}B}), so wäre der Bild-Funktion ∃ f:ð”Bâð”ð”S\exists_f\colon \mathcal{P}B \in \mathcal{P}\mathcal{P}S (weil ∃ ff *=1 ð”ð”S\exists_f f^\ast = 1_{\mathcal{P}\mathcal{P}S}). Somit wäre ihre Zusammensetzung eine Surjektion ð”Sâð”ð”S\mathcal{P} S \ zu \mathcal{P} \mathcal{P} S , was durch den Satz unmöglich ist .
Interpretation
Beachten Sie, dass es eine Injektion von SS nach ð”S\mathcal{P}S gibt, die durch die Singleton-Map gegeben ist. In der Arithmetik der Kardinalzahlen haben wir also
Aber da es keine solche Surjektion gibt, gibt es sicherlich keine Bijektion, und wir haben
Daraus schließen wir, dass
Das heißt, jede Menge ist in der Kardinalität streng kleiner als ihre Potenzmenge.
Diese Interpretation beruht auf einer guten Beziehung zwischen â¤\leq und == auf der Klasse der Kardinalzahlen; insbesondere der Satz von Cantorâ SchroederâBernstein, dass â¤\leq antisymmetrisch ist. In der konstruktiven Mathematik fehlt diese Beziehung, und es ist durchaus möglich, dass zwei Mengen im obigen Sinne jeweils streng kleiner sind. Dank Theorem , ist dies nicht möglich für eine Menge und ihre Macht gesetzt, aber es bedeutet, dass die Interpretation von <\lt als relative Größe problematisch â in der Tat fast so problematisch wie die Idee, dass es weniger ganze Zahlen als ganze Zahlen!
Paul Taylor hat argumentiert, dass der wesentliche Wert von Cantors Theorem das Lemma ist, das in Cantors Beweis implizit enthalten ist, dass Bill Lawvere als Theorem isoliert wurde . Da die Hauptinterpretation des Satzes nur in einem bestimmten mengentheoretischen Kontext sinnvoll ist (insbesondere in einem, in dem der Satz von Cantorâ Schroederâ Bernstein gilt), kann er eine â revolutionâ nicht überleben, die den Vorrang dieses Kontexts stürzt. Aber Lawveres Lemma wird überleben, da es â die workâ tut, während Cantors Theorem â die creditâ nimmt. (Siehe Taylor 2009 unten für eine weitere Diskussion über â Lemmata, die die Arbeit und Theoreme tun, die die creditâ nehmen.)
In posets
Ein Satz analog Cantorâ s Satz für Mengen kann für andere kartesische geschlossene Kategorien formuliert werden. Insbesondere kann man fragen, ob es möglich ist, eine Surjektion Xâ2 XX \ bis 2 ^ X zwischen Posets zu haben, wobei die Basis 22 nicht die diskrete Poset ist {0,1}\{0, 1\} sondern die Reihenfolge {0â¤1}\{0 \leq 1\}.
Die Antwort ist, es gibt keine solche Surjektion f:Xâ’2 Xf: X \ bis 2 ^ X, aber dies folgt nicht aus einer einfachen Anwendung von Lawvereâ s Fixpunktsatz, wo man versucht, solche ff auszuschließen, indem Existenz einer Karte 2â22 \ bis 2 aufrufen, die keinen festen Punkt hat (es gibt keine solche poset Karte 2â22 \bis 2!). Wir können uns auch nicht auf ein grobes Kardinalitätsargument berufen; Zum Beispiel, wenn XX die Ordinalzahl Ï \ omega ist, dann ist 2 X2 ^ X die Reihenfolge ⊥ âŠÏ op\ bot \sqcup \omega ^{op} (grenzt frei an ein unteres Element ⊥\bot an Ï op\omega ^ {op}), das die gleiche Kardinalität hat. Also muss ein anderer Beweis gesucht werden.
Zu beweisen, dass es keine Surjektion Xâ2 XX \bis 2 ^ X gibt, ist eine amüsante Übung. Eine Angriffslinie (die zu jedem Topos verinnerlicht wird) kann hier gefunden werden.
- Lawveres Fixpunktsatz
