Das diagonale Argument von Cantor, auch genannt das diagonalisation Argument, das diagonale Hieb-Argument oder die diagonale Methode, wurde 1891 von Georg Cantor als ein mathematischer Beweis veröffentlicht, dass es unendliche Sätze gibt, die in die isomorphe Ähnlichkeit mit dem unendlichen Satz von natürlichen Zahlen nicht gestellt werden können. Solche Sätze sind jetzt als unzählbare Sätze bekannt, und die Größe von unendlichen Sätzen wird jetzt durch die Theorie von Grundzahlen behandelt, die Cantor begonnen hat.

Das diagonale Argument war nicht der erste Beweis des Kantoren des uncountability der reellen Zahlen; es wurde wirklich viel später veröffentlicht als sein erster Beweis, der 1874 erschienen ist. Jedoch demonstriert es eine starke und allgemeine Technik, die in einer breiten Reihe von Beweisen, auch bekannt als diagonalen Argumenten analog mit dem in diesem Beweis verwendeten Argument seitdem verwendet worden ist. Die berühmtesten Beispiele sind vielleicht das Paradox von Russell, der erste von den Unvollständigkeitslehrsätzen von Gödel und der Antwort von Turing auf Entscheidungsproblem.

Ein unzählbarer Satz

Der ursprüngliche Beweis des Kantoren denkt eine unendliche Folge S von der Form (s, s, s...), wo jedes Element s eine unendliche Folge 1s oder 0s ist. Diese Folge ist zählbar, betreffs jeder natürlichen Zahl n vereinigen wir ein und nur ein Element der Folge. Wir könnten solch eine Folge wie eine numerierte Liste schreiben:

:s = (0, 0, 0, 0, 0, 0, 0...)

:s = (1, 1, 1, 1, 1, 1, 1...)

:s = (0, 1, 0, 1, 0, 1, 0...)

:s = (1, 0, 1, 0, 1, 0, 1...)

:s = (1, 1, 0, 1, 0, 1, 1...)

:s = (0, 0, 1, 1, 0, 1, 1...)

:s = (1, 0, 0, 0, 1, 0, 0...)

:...

Für jede M und n gelassener s, das n Element der M Folge auf der Liste sein. Also, zum Beispiel ist s das erste Element der zweiten Folge.

Es ist möglich, eine Folge s auf solche Art und Weise zu bauen, dass sein erstes Element vom ersten Element der ersten Folge in der Liste verschieden ist, ist sein zweites Element vom zweiten Element der zweiten Folge in der Liste, und im Allgemeinen verschieden, sein n Element ist vom n Element der n Folge in der Liste verschieden. Das heißt, wenn s 1 ist, dann ist s 0, sonst ist s 1. Zum Beispiel:

:s = (0, 0, 0, 0, 0, 0...)

:s = (1, 1, 1, 1, 1, 1...)

:s = (0, 1, 1, 0, 1, 0...)

:s = (1, 0, 1, 1, 0, 1...)

:s = (1, 1, 0, 1, 1, 1...)

:s = (0, 0, 1, 1, 0, 1...)

:s = (1, 0, 0, 0, 1, 0...)

:s = (...)

Die Elemente s, s, s werden hier und so weiter hervorgehoben, den Ursprung des Namens "diagonales Argument" zeigend. Jedes Element in s ist definitionsgemäß vom hervorgehobenen Element in der entsprechenden Säule des Tisches darüber, verschieden. Kurz gesagt, s  s.

Deshalb ist diese neue Folge s von allen Folgen in der Liste verschieden. Das folgt aus der Tatsache, dass, wenn es zu, sagen wir, der 10. Folge in der Liste dann identisch war, wir s = s haben würden. Im Allgemeinen würden wir s = s haben, der, wegen des Aufbaus von s, unmöglich ist. Kurz gesagt, durch seine Definition s wird in der zählbaren Folge S nicht enthalten.

Lassen Sie T ein Satz sein, der aus allen unendlichen Folgen von 0s und 1s besteht. Durch seine Definition muss dieser Satz nicht nur die Folgen enthalten, die in S, sondern auch s eingeschlossen sind, der gerade eine andere Folge von 0s und 1s ist. Jedoch erscheint s nirgends in S. Folglich kann T nicht mit S. zusammenfallen

Weil dieses Argument für jeden zählbaren Satz S von Folgen von 0s und 1s gilt, hieraus folgt dass T keinem solchem Satz gleich sein kann. So ist T unzählbar: Es kann in die isomorphe Ähnlichkeit mit dem Satz von natürlichen Zahlen nicht gelegt werden.

Interpretation

Die Interpretation des Ergebnisses des Kantoren wird von jemandes Ansicht von der Mathematik abhängen. Zu constructivists zeigt das Argument nicht mehr als, dass es keine Bijektion zwischen den natürlichen Zahlen und T gibt. Es schließt die Möglichkeit nicht aus, dass die Letzteren subzählbar sind. Im Zusammenhang der klassischen Mathematik ist das unmöglich, und das diagonale Argument stellt fest, dass, obwohl sowohl Sätze unendlich sind, es wirklich mehr unendliche Folgen von als auch Nullen gibt als, gibt es natürliche Zahlen.

Reelle Zahlen

Der uncountability der reellen Zahlen wurde bereits durch den ersten uncountability Beweis des Kantoren gegründet, aber es folgt auch aus dem obengenannten Ergebnis. Um das zu sehen, werden wir eine isomorphe Ähnlichkeit zwischen dem Satz T unendlicher binärer Schnuren und einer Teilmenge von R (der Satz von reellen Zahlen) bauen. Da T unzählbar ist, muss diese Teilmenge von R unzählbar sein. Folglich ist R unzählbar.

Um diese isomorphe Ähnlichkeit (oder Bijektion) zu bauen, bemerken Sie, dass die Schnur t = 0111 … nach dem binären Punkt in der Binärentwicklung 0.0111 … erscheint. Das deutet an, die Funktion f (t) = 0.t zu definieren, wo t eine Schnur in T ist. Leider, f (1000 …) = 0.1000 … = 1/2 und f (0111 …) = 0.0111 … = 1/4 + 1/8 + 1/16 + … = 1/2. So ist diese Funktion nicht eine Bijektion, da zwei Schnuren einer Zahl — eine Zahl entsprechen, die zwei Binärentwicklungen hat.

Jedoch erzeugt das Ändern dieser Funktion eine Bijektion von T bis den Zwischenraum (0, 1) — d. h. die reellen Zahlen> 0 und Schnur in der Folge b, lassen Sie g (t) die n Zahl in der Folge a sein; lassen Sie sonst g (t) = 0.t.

Eine Bijektion von T bis R zu bauen: Fangen Sie mit der Tangente-Funktionslohe (x) an, der eine Bijektion von ( π/2, π/2) zu R zur Verfügung stellt. Bemerken Sie als nächstes, dass die geradlinige Funktion h (x) = πx - π/2 eine Bijektion von (0, 1) zu ( π/2, π/2) zur Verfügung stellt. Die zerlegbare Funktionslohe (h (x)) = Lohe (πx - π/2) stellt eine Bijektion von (0, 1) zu R zur Verfügung. Setzen Sie diese Funktion mit g (t) zusammen, um Lohe (h (g (t))) = Lohe zu erhalten (πg (t) - π/2), der eine Bijektion von T bis R ist. Das bedeutet, dass T und R denselben cardinality haben — wird dieser cardinality "cardinality des Kontinuums genannt."

Allgemeine Sätze

Eine verallgemeinerte Form des diagonalen Arguments wurde vom Kantoren verwendet, um den Lehrsatz des Kantoren zu beweisen: Für jeden Satz S der Macht-Satz von S, d. h., der Satz aller Teilmengen von S (hier schriftlich als P (S)), ist größer als S selbst. Dieser Beweis geht wie folgt weiter:

Lassen Sie f jede Funktion von S bis P (S) sein. Es genügt, um zu beweisen, dass f surjective nicht sein kann. Das bedeutet, dass ein Mitglied von P (S), d. h., eine Teilmenge von S, nicht im Image von f ist. Denken Sie den Satz:

Für jeden s in S ist entweder s in T oder nicht. Wenn s in T ist, dann definitionsgemäß T ist s nicht in f (s), so ist T f (s) nicht gleich. Andererseits, wenn s nicht in T ist, dann definitionsgemäß T ist s in f (s), so wieder ist T f (s) nicht gleich.

Auf eine mehr ganze Rechnung dieses Beweises, sieh den Lehrsatz des Kantoren.

Folgen

Dieses Ergebnis deutet an, dass der Begriff des Satzes aller Sätze ein inkonsequenter Begriff ist. Wenn S der Satz aller Sätze dann P (S) wären, würde zur gleichen Zeit größer sein als S und eine Teilmenge von S.

Das Paradox von Russell hat uns gezeigt, dass naive Mengenlehre, die auf einem uneingeschränkten Verständnis-Schema gestützt ist, widersprechend ist. Bemerken Sie, dass es eine Ähnlichkeit zwischen dem Aufbau von T und dem Satz im Paradox von Russell gibt. Deshalb je nachdem wie wir das Axiom-Schema des Verständnisses modifizieren, um das Paradox von Russell zu vermeiden, können Argumente wie das Nichtsein von einer Reihe aller Sätze oder können gültig nicht bleiben.

Das diagonale Argument zeigt, dass der Satz von reellen Zahlen "größer" ist als der Satz von natürlichen Zahlen (und deshalb, die ganzen Zahlen und rationals ebenso). Deshalb können wir fragen, ob es einen Satz gibt, dessen cardinality "zwischen" dieser der ganzen Zahlen und diesem der reals ist. Diese Frage führt zur berühmten Kontinuum-Hypothese. Ähnlich führt die Frage dessen, ob dort ein Satz besteht, dessen cardinality zwischen |S und |P (S) | für einen unendlichen S ist, zur verallgemeinerten Kontinuum-Hypothese.

Entsprechungen des diagonalen Arguments werden in der Mathematik weit verwendet, um die Existenz oder das Nichtsein von bestimmten Gegenständen zu beweisen. Zum Beispiel ist der herkömmliche Beweis der Unlösbarkeit des stockenden Problems im Wesentlichen ein diagonales Argument. Außerdem wurde diagonalization ursprünglich verwendet, um die Existenz willkürlich harter Kompliziertheitsklassen zu zeigen, und hat eine Schlüsselrolle in frühen Versuchen gespielt zu beweisen, dass P NP nicht gleichkommt. 2008 wurde diagonalization verwendet, um die Tür" auf dem Dämon von Laplace "zuzuschlagen.

Version für die neuen Fundamente von Quine

Der obengenannte Beweis fehlt für die "Neuen Fundamente von W. V. Quine" Mengenlehre (NF). In NF wird das naive Axiom-Schema des Verständnisses modifiziert, um die Paradoxe durch das Einführen einer Art "lokaler" Typ-Theorie zu vermeiden. In diesem Axiom-Schema,

ist nicht ein Satz — d. h., befriedigt das Axiom-Schema nicht. Andererseits könnten wir versuchen, ein modifiziertes diagonales Argument dadurch zu schaffen, das zu bemerken

ist ein Satz in NF. In welchem Fall, wenn P (S) der Satz von Ein-Element-Teilmengen von S und f ist, eine vorgeschlagene Bijektion von P (S) zu P (S) ist, ist man im Stande, reductio zu verwenden, um dass |P (S) | &lt zu beweisen; |P (S) |.

Der Beweis folgt durch die Tatsache dass, wenn f tatsächlich eine Karte auf P (S) waren), dann konnten wir r in S, solch finden, dass f ({r}) mit dem modifizierten diagonalen Satz oben zusammenfällt. Wir würden dass beschließen, wenn r nicht in f ({r}) ist, dann ist r in f ({r}) und umgekehrt.

Es ist nicht möglich, P (S) in einer isomorphen Beziehung mit S zu stellen, weil die zwei verschiedene Typen haben, und so würde jede so definierte Funktion die tippenden Regeln für das Verständnis-Schema verletzen.

Siehe auch

• Meinungsverschiedenheit über die Theorie des Kantoren

Außenverbindungen

• Der diagonale Beweis des Kantoren an MathPages