Articles

9.3: Cantor’s Theorem and Its Consequences

Fähigkeiten zur Entwicklung

  • Erklären Sie den Satz von Cantor

Nachdem Cantor gezeigt hatte, dass es zwei Arten von Unendlichkeit gibt (zählbar und unzählbar), war die folgende Frage natürlich: „Haben alle unzählbaren Mengen die gleiche Kardinalität?“

So wie nicht alle „Nicht-Hunde“ Katzen sind, gibt es off-hand keinen Grund zu der Annahme, dass alle unzählbaren Sets gleich groß sein sollten. Das Erstellen unzähliger Sets unterschiedlicher Größe ist jedoch nicht so einfach, wie es sich anhört.

Was ist zum Beispiel mit dem Liniensegment, das durch das Intervall \(\) dargestellt wird, und dem Quadrat, das durch die Menge \( × = \{(x,y)|0 ≤ x,y ≤ 1\}\) . Sicherlich muss das zweidimensionale Quadrat eine größere unendliche Menge sein als das eindimensionale Liniensegment. Bemerkenswerterweise zeigte Cantor, dass diese beiden Sätze die gleiche Kardinalität hatten. In seiner Korrespondenz von 1877 über dieses Ergebnis mit seinem Freund und Mathematikerkollegen Richard Dedekind bemerkte sogar Cantor: „Ich sehe es, aber ich glaube es nicht!“

 abb. 9.3.1.png

Abbildung \(\pageIndex{1}\): Richard Dedekind

Das Folgende gibt die ursprüngliche Idee von Cantors Beweis. Cantor entwickelte die folgende Funktion \(f : × → \). Zuerst stellen wir die Koordinaten eines beliebigen Punktes \((x,y) ∈ ×\) durch ihre Dezimaldarstellungen \(x = 0 .a_1a_2a_3 …\) und \(y = 0.b_1b_2b_3….\) Sogar abschließende Dezimalstellen können so geschrieben werden, wie wir \(0.5 = 0.5000 ….\) Wir können dann \(f(x,y)\) definieren durch

\

Diese relativ einfache Idee hat einige technische Schwierigkeiten im Zusammenhang mit dem folgenden Ergebnis.

Übung \(\pageIndex{1}\)

Betrachten Sie die Sequenz \((0.9,0.99,0.999,…)\). Bestimmen Sie, dass diese Sequenz konvergiert und tatsächlich zu \(1\) konvergiert. Dies deutet darauf hin, dass \(0.999… = 1\).

In ähnlicher Weise haben wir \(0.04999… = 0.05000…\) usw. Um die Dezimaldarstellung einer reellen Zahl in \(\) eindeutig zu machen, müssen wir eine konsistente Wahl treffen, eine abschließende Dezimalzahl als eine zu schreiben, die in einer unendlichen Folge von Nullen oder einer unendlichen Folge von Neunen endet . Egal, welche Wahl wir treffen, wir könnten diese Funktion niemals aufheben. Beispiel: \(109/1100 = 0,09909090…\) hätte als Vorabbild \((0.0999…,0.9000…)\), was eine Mischung der beiden Konventionen wäre.

Cantor war in der Lage, diese Technik zu überwinden, um eine Eins-zu-Eins-Entsprechung zu demonstrieren, aber stattdessen werden wir feststellen, dass die Funktion in beiden Konventionen eins-zu-eins ist, so dass die Menge \(×\) ist die gleiche Kardinalität wie eine (unzählbare) Teilmenge von \(\mathbb{R}\). Die Tatsache, dass dies die gleiche Kardinalität wie \(\mathbb{R}\) ist etwas, worauf wir zurückkommen werden. Aber zuerst werden wir versuchen, eine unzählbare Menge zu konstruieren, die nicht die gleiche Kardinalität wie \(\mathbb{R}\) . Um dieses Problem anzugehen, bewies Cantor 1891 Folgendes.

Satz \(\pageIndex{1}\): Satz von Cantor

Sei \(S\) eine beliebige Menge. Dann gibt es keine Eins-zu-Eins-Entsprechung zwischen \(S\) und \(P(S)\), der Menge aller Teilmengen von \(S\).

Da \(S\) mit einer Teilmenge von \(P(S) (a → \{a\})\) eins zu eins korrespondiert werden kann, besagt dies, dass \(P(S)\) mindestens so groß ist wie \(S\). Im endlichen Fall ist \(/P(S) |\) streng größer als \(|S|\), wie das folgende Problem zeigt. Es zeigt auch, warum \(P (S) \) die Potenzmenge von \ (S\) genannt wird.

Übung \(\pageIndex{2}\)

Beweisen: Wenn \(|S/ = n\), dann \(|P(S)| = 2n\)

Hinweis

Sei \(S = a_1, a_2, …, and\). Betrachten Sie die folgende Entsprechung zwischen den Elementen von \(P(S)\) und der Menge \(T\) aller \(n\)-Tupel von yes (\(Y\)) oder no (\(N\)):

\

Wie viele Elemente sind in \(T\)?

Übung \(\pageIndex{3}\)

Beweisen Sie den Satz von Cantor.

Hint

Angenommen, es gibt eine Eins-zu-Eins-Entsprechung \(f : S → P(S)\). Betrachten Sie \(A = \{x ∈ S|x \nicht {∈} f(x)\}\). Da \(f\) ono ist, gibt es \(a ∈ A\) , so dass \(A = f(a)\) . Ist \(a ∈ A\) oder ist \(a \nicht {∈} A\)?

Tatsächlich stellt sich heraus, dass \(\mathbb{R}\) und \(P(\mathbb{N})\) die gleiche Kardinalität haben. Dies kann auf Umwegen mit einigen der obigen Ideen aus Übung \(\pageIndex{2}\) gesehen werden. Insbesondere sei \(T\) die Menge aller Sequenzen von Nullen oder Einsen (Sie können \ (Y\) oder \ (N\) verwenden, wenn Sie dies bevorzugen). Dann ist es einfach zu sehen, dass \ (T\) und \(P(\mathbb{N})\) die gleiche Kardinalität haben.

Wenn wir \((0,1]\)betrachten, das die gleiche Kardinalität wie \(\mathbb{R}\) hat, dann können wir sehen, dass dies auch die gleiche Kardinalität wie \(T\) hat. Wenn wir uns die Zahlen binär vorstellen, kann jede reelle Zahl in \(\) als \(\sum_{j=1}^{\infty } \frac{a_j}{2^j} = (a_1, a_2, \cdots )\) wobei \(a_j ∈ \{0,1\}\) . Wir müssen die Tatsache berücksichtigen, dass binäre Darstellungen wie \(0.0111…\) und \(0.1000…\) die gleiche reelle Zahl darstellen (sagen wir, dass keine Darstellungen in einer unendlichen Reihe von Nullen enden), dann können wir sehen, dass \(\) die gleiche Kardinalität hat wie \(T – U\), wobei \(U\) ist die Menge aller Sequenzen, die in einer unendlichen Reihe von Nullen enden. Es stellt sich heraus, dass \(U\) selbst eine zählbare Menge ist.

Übung \(\pageIndex{4}\)

Sei \(U_n = \{(a_1, a_2, a_3,…) / a_j ∈ \{0,1\}\) und \(a_{n+1} = a_{n+2} = ··· = 0\}\). Zeigen Sie, dass \(U_n\) für jedes \ (n\) endlich ist, und schließen Sie daraus, dass \ (U \) zählbar unendlich ist.

Die folgenden zwei Probleme zeigen, dass das Löschen einer zählbaren Menge aus einer unzählbaren Menge ihre Kardinalität nicht ändert.

Übung \(\pageIndex{5}\)

Sei \(S\) eine unendliche Menge. Beweisen Sie, dass \(S\) eine zählbar unendliche Teilmenge enthält.

Übung \(\pageIndex{6}\)

Angenommen, \(X\) ist eine unzählbare Menge und \(Y ⊂ X\) ist zählbar unendlich. Beweisen Sie, dass \ (X\) und \(X – Y\) die gleiche Kardinalität haben.

Hinweis

Sei \(Y = Y_0\). Wenn \(X – Y_0\) eine unendliche Menge ist, enthält sie nach dem vorherigen Problem eine zählbar unendliche Menge \(Y_1 \). Wenn \(X – (Y_0 ∪ Y_1)\) unendlich ist, enthält es auch eine unendliche Menge \(Y_2\). Wenn \(X – (Y_0 ∪ Y_1 ∪ Y_2)\) eine unendliche Menge ist, enthält sie eine unendliche Menge \(Y_3 \) usw. Für \(n = 1,2,3,…,\) sei \(f_n : Y_{n-1} → Y_n\) eine Eins-zu-Eins-Entsprechung und definiere \(f : X → X – Y\) durch

\

Zeigen Sie, dass \(f\) eins zu eins und eins ist.

Die obigen Probleme besagen, dass \(R \), \(T – U\), \(T\) und \(P(N)\) alle die gleiche Kardinalität haben.

Wie bereits erwähnt, hatte Cantors Arbeit an unendlichen Mengen einen tiefgreifenden Einfluss auf die Mathematik zu Beginn des zwanzigsten Jahrhunderts. Zum Beispiel entwickelte der bedeutende Logiker Bertrand Russell bei der Untersuchung des Beweises von Cantors Theorem 1901 sein berühmtes Paradoxon. Vor dieser Zeit wurde ein Set naiv als eine Sammlung von Objekten betrachtet. Durch die Arbeit von Cantor und anderen wurden Sets zu einem zentralen Studienobjekt in der Mathematik, da viele mathematische Konzepte in Bezug auf Sets neu formuliert wurden. Die Idee war, dass die Mengenlehre ein verbindendes Thema der Mathematik sein sollte. Dieses Paradoxon stellte die mathematische Welt auf den Kopf.

Russells Paradoxon

Betrachten Sie die Menge aller Mengen, die keine Elemente ihrer selbst sind. Wir nennen diese Menge \(D\) und fragen: „Ist \(D ∈ D\)?“ Symbolisch ist dieses Set

\

Wenn \(D ∈ D\), dann per Definition \(D \nicht {∈} D\). Wenn D 6∈ D, dann per Definition, \(D ∈ D\).

Wenn Sie auf den Beweis von Cantors Theorem zurückblicken, war dies im Grunde die Idee, die uns den Widerspruch gab. Es war skandalös, einen solchen Widerspruch auf der grundlegendsten Ebene der Mathematik auftreten zu lassen. Es zwang eine Reihe von Mathematikern und Logikern, die Axiome, mit denen Mengen konstruiert werden konnten, sorgfältig zu entwickeln. Um ehrlich zu sein, Die meisten Mathematiker nähern sich der Mengenlehre immer noch von einem naiven Standpunkt aus, da die Mengen, mit denen wir uns normalerweise befassen, unter die Kategorie der sogenannten „normalen Mengen“ fallen.“ Tatsächlich wird ein solcher Ansatz offiziell als naive Mengenlehre bezeichnet (im Gegensatz zur axiomatischen Mengenlehre). Versuche, Mengenlehre und Logik auf eine solide Grundlage zu stellen, führten jedoch zum modernen Studium der symbolischen Logik und schließlich zum Entwurf der Computerlogik.

Ein anderer Ort, an dem Kantors Werk einen tiefgreifenden Einfluss auf die moderne Logik hatte, stammt von etwas, auf das wir bereits hingewiesen haben. Wir haben zuvor gezeigt, dass das Einheitsquadrat \(×\) die gleiche Kardinalität hat wie eine unzählbare Teilmenge von \(\mathbb{R}\). Tatsächlich zeigte Cantor, dass das Einheitsquadrat die gleiche Kardinalität wie \ (\ mathbb{R}\) selbst hatte, und wurde 1878 verschoben, um Folgendes voranzutreiben.

Vermutung (Die Kontinuumshypothese)

Jede unzählbare Teilmenge von \(\mathbb{R}\) hat dieselbe Kardinalität wie \(\mathbb{R}\).

Cantor war nicht in der Lage zu beweisen oder zu widerlegen diese Vermutung (zusammen mit jedem anderen Mathematiker). Tatsächlich war das Beweisen oder Widerlegen dieser Vermutung, die als Kontinuumshypothese bezeichnet wurde, eines von Hilberts berühmten \ (23 \) Problemen, die Mathematikern auf dem Internationalen Mathematikerkongress 1900 als Herausforderung vorgestellt wurden.

Da \(\mathbb{R}\) die gleiche Kardinalität wie \(P(N)\) hat, wurde die Kontinuumshypothese auf die verallgemeinert:

Vermutung (Die verallgemeinerte Kontinuumshypothese)

Bei einer unendlichen Menge \(S\) gibt es keine unendliche Menge, deren Kardinalität streng zwischen der von \ (S\) und ihrer Potenzmenge \(P (S) \) liegt.

Bemühungen, dies zu beweisen oder zu widerlegen, waren vergeblich und mit gutem Grund. 1940 zeigte der Logiker Kurt Gödel, dass die Kontinuumshypothese nicht aus den Zermelo-Fraenkel-Axiomen der Mengenlehre 1 widerlegt werden konnte. 1963 zeigte Paul Cohen, dass die Kontinuumshypothese nicht mit den Zermelo-Fraenkel-Axiomen bewiesen werden konnte. Mit anderen Worten, die Zermelo-Fraenkel-Axiome enthalten nicht genügend Informationen, um die Wahrheit der Hypothese zu bestimmen.

Wir sind bereit zu wetten, dass Ihr Kopf an diesem Punkt ein wenig vor Unsicherheit schwimmt. Wenn ja, dann wissen Sie, dass dies die gleichen Gefühle sind, die die mathematische Gemeinschaft in der Mitte des zwanzigsten Jahrhunderts erlebt hat. In der Vergangenheit wurde Mathematik als Modell logischer Gewissheit angesehen. Es ist beunruhigend festzustellen, dass es Aussagen gibt, die „unentscheidbar“ sind.“ Tatsächlich bewies Gödel 1931, dass ein konsistentes endliches Axiomensystem, das die Axiome der Arithmetik enthielt, immer unentscheidbare Aussagen enthalten würde, die mit diesen Axiomen weder wahr noch falsch bewiesen werden konnten. Mathematisches Wissen wäre immer unvollständig.

Abb. 9.3.2.png

Abbildung \(\pageIndex{2}\): Kurt Gödel

Wenn wir also versuchen, die Grundlagen der Infinitesimalrechnung auf festen Boden zu stellen, sind wir an einem Punkt angelangt, an dem wir niemals mathematische Gewissheit erlangen können. Bedeutet das, dass wir unsere Hände hochlegen und eine Niederlage einräumen sollten? Sollten wir vor Angst gelähmt sein, etwas zu versuchen? Gewiss nicht! Wie bereits erwähnt, machen die meisten Mathematiker einen pragmatischen Ansatz: Verwenden Sie ihre Mathematik, um Probleme zu lösen, auf die sie stoßen. In der Tat sind es in der Regel die Probleme, die die Mathematik motivieren. Es ist wahr, dass Mathematiker Chancen eingehen, die sich nicht immer auszahlen, aber sie gehen diese Chancen immer noch ein, oft mit Erfolg. Selbst wenn die Erfolge zu mehr Fragen führen, wie sie es normalerweise tun, führt die Beantwortung dieser Fragen in der Regel zu einem tieferen Verständnis. Zumindest bedeutet unser unvollständiges Verständnis, dass wir immer mehr Fragen zu beantworten und mehr Probleme zu lösen haben.

Was könnte ein Mathematiker sonst noch verlangen?