Prinzip der transfiniten Induktion

Die Ordnungszahlen sind das, was Sie erhalten, wenn Sie die Operationen von „successor“ und „supremum“ auf unbestimmte Zeit wiederholen, ähnlich wie die natürlichen Zahlen das sind, was Sie erhalten, wenn Sie den einzigen Operator „successor“ auf unbestimmte Zeit iterieren.

• Beginnen mit$0$. Durch iterierende Nachfolger erhalten wir die natürlichen Zahlen, die die endlichen Ordnungszahlen sind: $$0, 1, 2, 3, \dots$$
• Jetzt nimm das Supremum. Wir nennen dies Ordinalzahl$\omega$. Durch iterierende Nachfolger erhalten wir eine längere Sequenz: $$0, 1, 2, \dots, \omega, \omega+1, \omega+2, \dots$$
• Das Supremum dieser Folge ist die Ordnungszahl$\omega + \omega$. Wir können dann noch mehr Nachfolger nehmen: $$0, 1, \dots, \omega, \omega+1, \dots, \omega + \omega, \omega + \omega + 1, \dots$$ Das Supremum dieser Folge ist die Ordnungszahl$\omega + \omega + \omega$.

• Wenn Sie so fortfahren, erhalten Sie die folgenden Ordinalzahlen:

  $$\omega,\ \omega+\omega,\ \omega+\omega+\omega,\ \omega + \omega + \omega + \omega, \dots$$ Wir können also ein weiteres Supremum nehmen, um die Ordnungszahl zu erhalten$\omega \cdot \omega$. Ebenso erhalten wir$\omega \cdot \omega \cdot \omega$, und so weiter, das Höchste von allem ist$\omega^{\omega}$. Dann erhalten wir$\omega^{\omega^{\omega}}$und so weiter, das Höchste von allem wird genannt$\varepsilon_0$... usw.

• Fortsetzung noch weiterer Anstieg zu den zählbaren Ordinalzahlen . Aber das selbst ist eine Reihe von Ordnungszahlen, also hat es ein Supremum, genannt$\omega_1$. Dann können wir seine Nachfolger nehmen$\omega_1+1$usw.

• Die Ordnungszahlen sind genau die Dinge, die man erhalten kann, indem man die Folgeoperation iteriert und die Ordnungszahl bestimmt.

Formaler sind die (von Neumann) Ordnungszahlen die Elemente der Klasse$\mathrm{Ord}$, das ist die Schließung von$\varnothing$im Nachfolgebetrieb$x \mapsto x \cup \{ x \}$und willkürliche Vereinigungen eingehen.

Das Prinzip der transfiniten Induktion besagt das im Wesentlichen für eine gegebene Formel$P(x)$, Wenn$P(0)$ist wahr, und die Wahrheit von$P(\alpha)$wird bewahrt, indem man Nachfolger und Suprema nimmt, dann$P(\alpha)$muss für alle Ordinalzahlen gelten$\alpha$. (Die können wir weglassen$P(0)$Fall weil$0 = \sup (\varnothing$).)

Ich glaube, der beste Weg, das Prinzip der transfiniten Induktion ohne Bezugnahme auf Ordnungszahlen zu verstehen, ist der folgende (basierend auf der Diskussion in Folland, 1999, Abschnitt 0.4 ):

Lassen$(X,\succsim)$sei eine nichtleere, wohlgeordnete Menge. Für jede$x\in X$, definieren

In Worten, angenommen, wenn $Y$enthält alle Vorgänger von$x$, dann $Y$enthält$x$selbst auch. Dies bedeutet, dass die Eigenschaft die Teilmenge definiert$Y$wird „nach oben vererbt“, was die intuitive Idee hinter der Induktion ist. Die Behauptung ist, dass, wenn eine solche Eigenschaft induktiv vererbt wird, diese Eigenschaft für alle gelten muss$X$. Dies ist das Prinzip der transfiniten Induktion.

Ein kurzer Beweis: Angenommen, die Prämisse gilt – das will man zeigen$Y=X$. Nehmen Sie das aus Gründen des Widerspruchs an$Y\neq X$. Dann der Satz$X\setminus Y$ist nicht leer, hat also ein kleinstes Element$x_0$nach der wohlordnung$\succsim$. Seit$x_0$minimal ist, hat man das wenn$y\prec x_0$, Dann$y\notin X\setminus Y$, oder$y\in Y$. Deshalb,$S_{x_0}\subseteq Y$. Aufgrund der Prämisse impliziert dies dies$x_0\in Y$. Aber$x_0\in X\setminus Y$. Widerspruch.

Beachten Sie, dass die „normale“ Induktion ein Sonderfall ist, in dem$X=\mathbb N$Und$\succsim$ ist die übliche Reihenfolge der Naturals. Wenn Sie Eigentum nachweisen möchten$P$für alle natürlichen zahlen, dann kannst du einstellen

(Sie fragen sich vielleicht, wo Sie das überprüfen$1\in Y$, was normalerweise der erste Schritt in der gewöhnlichen mathematischen Induktion ist, tritt ins Bild. Das ist ein bisschen subtil, aber da. Beachten Sie, dass$S_1=\varnothing\subseteq Y$, wenn also die Prämisse des Prinzips der transfiniten Induktion wahr wäre, müsste man haben$1\in Y$.)

Eine wohlgeordnete Menge ist eine Menge, die so linear geordnet ist, dass jede nicht leere Teilmenge ein kleinstes Mitglied hat.

Eine Ordnungszahl ist im Wesentlichen ein Ordnungstyp einer solchen Menge, dh zwei solcher Mengen haben genau dann dieselbe Ordnungszahl, wenn zwischen ihnen ein Ordnungsisomorphismus besteht, dh eine Eins-zu-Eins-Entsprechung, die die Ordnung bewahrt.

Das bekannteste Beispiel ist die Menge der endlichen Kardinalzahlen:

Das kann man "ewig" fortsetzen und dann danach bekommen$\omega^2$, Dann$\omega^2+1$, usw.

All dies sind "Ordnungszahlen" oder "Ordnungszahlen".

Und die Menge aller endlichen oder abzählbar unendlichen Ordnungszahlen ist selbst eine Ordnungszahl. Es ist gut geordnet.

Die Menge aller endlichen oder abzählbar unendlichen Ordinalzahlen kann als überabzählbar unendlich gezeigt werden. Es ist die kleinste überabzählbar unendliche wohlgeordnete Menge. Seine Kardinalität wird (von Georg Cantor und allen, die ihm folgen) genannt$\aleph_1$. Die berühmte „Kontinuumshypothese“ besagt, dass keine Kardinalität dazwischen liegt$\aleph_0$Und$2^{\aleph_0}$. Dass keine Kardinalität dazwischen liegt$\aleph_0$Und$\aleph_1$dagegen ist beweisbar. Wenn die Kontinuumshypothese wahr ist, ist das dasselbe wie$2^{\aleph_0} = \aleph_1$. (Wenn das Auswahlaxiom falsch und die Kontinuumshypothese wahr ist, dann$\aleph_1$Und$2^{\aleph_0}$können unvergleichbar sein, also ungleiche Kardinalzahlen, von denen keine größer ist als die andere.)

Lassen Sie uns Ordnungszahlen für einen Moment ignorieren und denken Sie daran, dass eine Wohlordnung eine Gesamtordnung ist$\preceq$auf irgendeinem Satz$A$so dass jede nichtleere Teilmenge$B \subseteq A$hat ein minimales Element in Bezug auf$\preceq$.

Das Induktionsprinzip lässt sich nun wie folgt formulieren:

Lassen$P(a)$eine Eigenschaft sein, die für alle definiert ist$a \in A$. Wenn$P(a)$scheitert bei manchen$a \in A$, dann gibt es eine$\preceq$-minimales Element$a_0 \in A$st$P(a_0)$ist falsch, dh

• $P(a_0)$ist falsch
• für alle$b \prec a_0 \colon \ P(b)$ist wahr

Wenn wir das wann immer zeigen können$P(b)$gilt für alle$b \prec a$es gilt auch für$P(a)$(Beachten Sie, dass dies das impliziert$P(a)$gilt für das Minimum von$A$), dann zeigt das obige, dass es keine geben kann$a \in A$so dass$P(a)$scheitert. So dass$P(a)$muss für alle gelten$a \in A$.

Michael und Clive haben schon einiges über Ordinalzahlen geschrieben, aber bisher wurde eine wichtige Eigenschaft nicht erwähnt: Für jede Wohlordnung$(A, \preceq)$es gibt eine eindeutige Ordnungszahl$\alpha$so dass$(A, \preceq)$Und$(\alpha, \subseteq)$sind ordnungsisomorph. Daher können Ordnungszahlen als "Standardrepräsentanten von Brunnenordnungen" angesehen werden.

(Ich habe die Tatsache unterdrückt, dass die Sammlung aller Ordinalzahlen keine Menge, sondern eine richtige Klasse ist. Tatsächlich funktioniert das Induktionsprinzip auch in diesem Fall aus ziemlich demselben Grund ...)

Ich füge eine zweite Antwort hinzu, weil der folgende Punkt sehr interessant ist:

Bei dieser Art der Induktion ist kein Basisfall erforderlich. Angenommen, Sie können das beweisen, wenn$P$gilt für alle Vorgänger von$\alpha$, Dann$P$gilt für$\alpha$. Darauf kannst du dann schließen$P$gilt für alle Ordnungszahlen$\alpha$.

Der Grund, warum Sie keinen Basisfall benötigen, ist, dass dies vage wahr ist$P$gilt für alle Ordnungszahlen$<0$. Sie haben das bewiesen, wenn$P$gilt für alle Ordinalzahlen kleiner als$0$Dann$P$gilt für$0$, einfach als Spezialfall des Induktionsschrittes.

Als diese Typen diese formalen Systeme erfanden, modellierten sie die Ordnung nach der Hierarchie. Sie stellten sich Ordnung vor wie russische Puppen. Die kleinste Puppe ist die „Kleinste“. "Die Ordnungszahlen" sind ein angebliches Konstrukt, das für ein ursprüngliches universelles Verständnis von "kleiner als" oder "größer als" stehen soll, und es könnte in jeder Art von formaler Theorie postuliert werden, nicht nur in der von Mengen mit "Einschluss". ' als Ordnungszeichen. Die Idee in dieser speziellen Version ist, dass Sie auf ein ZF-Axiom zurückgreifen („es gibt eine Menge, die enthält, was immer wir wollen“), um Mengen so zu klassifizieren, dass sie eine Reihenfolge haben, die auf der Menge an Verschachtelungen basiert, die sie hosten. Die Definition ist einfach rekursiv: "Wenn Sie eine Menge sind, ist Ihre Ordnung um eins größer als die der höchsten Ordnungsmengen, die Sie enthalten." Dies ist nur kohärent mit dem anderen ZF-Axiom, 'Fundament' (jede Kette von Mengenzugehörigkeiten endet an einer Menge, die nichts enthält). Die Ordinalzahlen werden also symmetrisch rekursiv „gebaut“ – Sie beginnen mit der leeren Menge und folgen ihr wiederholt. [Mit Folge meine ich, dass Sie einen Mengenoperator S(x) = {x,{x}} anwenden. Es macht Spaß zu sehen, wie dies funktioniert, um sowohl Kardinalität als auch Ordinalität anzugeben] ist nicht notwendig für Induktion, ob endlich oder darüber hinaus; Wesentlich ist der Grundgedanke der Ordnung, dass eins nach dem anderen kommt. Sie werden nur traditionell als "Standard" betrachtet, und zwar noch dazu neu. Tatsächliche Ordnungen im Universum sind weitaus faszinierender. rekursiv - Sie beginnen mit der leeren Menge und folgen ihr wiederholt. [Mit Folge meine ich, dass Sie einen Mengenoperator S(x) = {x,{x}} anwenden. Es macht Spaß zu sehen, wie dies funktioniert, um sowohl Kardinalität als auch Ordinalität anzugeben] ist nicht notwendig für Induktion, ob endlich oder darüber hinaus; Wesentlich ist der Grundgedanke der Ordnung, dass eins nach dem anderen kommt. Sie werden nur traditionell als "Standard" betrachtet, und zwar noch dazu neu. Tatsächliche Ordnungen im Universum sind weitaus faszinierender. rekursiv - Sie beginnen mit der leeren Menge und folgen ihr wiederholt. [Mit Folge meine ich, dass Sie einen Mengenoperator S(x) = {x,{x}} anwenden. Es macht Spaß zu sehen, wie dies funktioniert, um sowohl Kardinalität als auch Ordinalität anzugeben] ist nicht notwendig für Induktion, ob endlich oder darüber hinaus; Wesentlich ist der Grundgedanke der Ordnung, dass eins nach dem anderen kommt. Sie werden nur traditionell als "Standard" betrachtet, und zwar noch dazu neu. Tatsächliche Ordnungen im Universum sind weitaus faszinierender. ist nicht notwendig für Induktion, ob endlich oder darüber hinaus; Wesentlich ist der Grundgedanke der Ordnung, dass eins nach dem anderen kommt. Sie werden nur traditionell als "Standard" betrachtet, und zwar noch dazu neu. Tatsächliche Ordnungen im Universum sind weitaus faszinierender. ist nicht notwendig für Induktion, ob endlich oder darüber hinaus; Wesentlich ist der Grundgedanke der Ordnung, dass eins nach dem anderen kommt. Sie werden nur traditionell als "Standard" betrachtet, und zwar noch dazu neu. Tatsächliche Ordnungen im Universum sind weitaus faszinierender.

Ein seltsamer technischer Punkt ist, dass, obwohl Kardinalität und Ordinalität für endliche Mengen identisch sein sollen (auf der Grundlage der Vorstellung, dass jede endliche Menge „von Hand“ gut geordnet werden kann), die Theoretiker entschieden haben, dass Sie immer noch unendliche Mengen einfügen könnten Mengen, so dass beispielsweise die Nachfolgemenge der Naturals eine höhere Ordnung als die Naturals (aus obiger Definition) hat, ihre Kardinalität aber mit der der Naturals identisch ist. Ich stimme ihnen nicht ganz zu, aber sie sagen, das sei Mathematik, nicht Philosophie. (Ich war mir dessen nie sicher.) Aus diesem Grund besteht die Idee, die die transfinite Induktion so besonders macht, darin, dass sie die Grenze der zählbaren Kardinalität „durchbrechen“ kann (die kreisförmig eine auf natürlichen Zahlen basierende Induktion „stoppen“ muss, wenn wir die Kardinalität auf die Bijektion stützen und beachten, was Galileo über unendliche Korrespondenzen entdeckt hat). Daher 'trans.' Jedes "Prinzip" der transfiniten Induktion kann nur einfach eine Aussage über eine Erweiterung des Standardprinzips "Eine gute Wendung verdient eine andere" sein, eine Wiederholung von Cantors Glauben an unendliche transfinite Kardinalitäten (ebenfalls verkörpert in einem ZF-Axiom aufgrund von Cantor und ein Lehrsatz von ihm). Vielleicht könnte man sagen: "Alle guten Wendungen verdienen eine weitere." Mir ist das alles ein wenig zu metaphysisch. Man sollte sich daran erinnern, dass Cantor an eine absolut höchste Unendlichkeit glaubte, die für den menschlichen Verstand unzugänglich ist und die er mit dem katholischen Gott identifizierte. Die ZF-Axiome wären also aus Cantors metaphysischer Sicht eigentlich nicht absolut wahr (da es keine Ordnung über Gott geben würde. S). Witziger Punkt. Ich persönlich kann ein solches Prinzip nicht anwenden, aber wenn es wirklich jemand kann, ist das großartig. Es scheint eine implizite Vorstellung zu geben, dass es eine Unendlichkeit jenseits der Unendlichkeit gibt, aber Sie konnten es nicht wissen, denn das ist die Sache mit der Unendlichkeit: Sie kommen nie dorthin. Wie kannst du gehenvon irgendwo her, wo du nicht hinkommst ? Das endliche Universum reicht völlig aus, um mich zu befriedigen. Ich werde jedoch sagen, dass es ein interessantes Kapitel der abstrakten Mechanik ist.