Wie man transfinite Rekursion formal verwendet, um eine Sequenz für einen Beweis von Zorns Lemma zu konstruieren

Wir können die Berufung auf Hartogs-Zahlen vermeiden, wenn wir stattdessen einen indirekten Beweis führen. Als Bonus wird die transfinite Rekursion etwas sauberer:

Angenommen , (a)$(P,\preceq)$ist eine teilweise geordnete Menge, die die Prämissen von Zorns Lemma erfüllt, (b)$P$kein maximales Element hat und (c)$C$ist eine Wahlfunktion an$P$. Wir suchen dann einen Widerspruch.

Ohne Beschränkung der Allgemeinheit erweitern$C$so dass$C(\varnothing)=42$, egal ob oder nicht$42\in P$.

Wenden Sie die transfinite Rekursion I auf die Klassenfunktion an

$$G(X) = C(\{y\in P\mid \forall z\in \operatorname{Rng}(X)\cap P: z\prec y\})$$ Dies ergibt eine Klassenfunktion $F$so dass für jede Ordnungszahl $\alpha$, $$F(\alpha) = C(\{y\in P \mid \forall \beta<\alpha : F(\beta)\in P \to F(\beta)\prec y\})$$

Lemma. Für alle$\alpha$das hält es$F(\alpha)\in P$Und$\forall \beta : F(\beta)\prec F(\alpha)$.

Nachweisen. Durch transfinite Induktion an$\alpha$. Das sagt uns die Induktionshypothese$\{F(\beta)\mid \beta<\alpha\}$ist eine Kette drin$P$(Beachten Sie, dass es dank Replacement auf jeden Fall ein Set ist). Die Zorn-Prämisse sagt uns, dass diese Kette eine Obergrenze hat; da es kein maximales Element gibt, hat es sogar eine strikte Obergrenze. Mit anderen Worten,

$$\{y\in P \mid \forall \beta<\alpha : F(\beta)\in P \to F(\beta)\prec y\},$$ die Menge aller strengen oberen Schranken ist also nicht leer $F(\alpha)$ist in $P$und ist größer als alle $F(\beta)$S.

Das sagt uns das Lemma$F$ist eine ordnungserhaltende Funktion von ON bis$P$. Seit$F$bewahrt die Ordnung, es ist insbesondere injektiv . Daher die Formel

$$H(x)=\alpha \iff F(\alpha)=x \lor (\alpha=117 \land \forall\beta:F(\beta)\ne x)$$ ist funktionstüchtig und wendet Ersatz an $P$Und $H$sagt uns, dass ON eine Menge ist. Das Burali-Forti-Paradoxon liefert nun unseren gewünschten Widerspruch.

---

Beachten Sie, dass wir nie wirklich brauchten$C(\varnothing)=42$ außer um das sicherzustellen$G$war eine Klassenfunktion , also konnten wir das Rekursionstheorem darauf anwenden.

Die Beweisstruktur ist hier typisch: Auf die Definition durch transfinite Rekursion folgt unmittelbar eine transfinite Induktion , die nützliche Fakten aus der Rekursionsformel extrahiert. Dieser zweistufige Ansatz ist oft notwendig, um die allgemeine Rekursionsmaschinerie zu verwenden, da wir definieren müssen$G$in einer defensiven Weise, so dass wir beweisen können, dass es Sinn macht und funktioniert, ohne von seinem Argument abzuhängen, das durch Rekursion erzeugt wird. Dieses defensive Gerüst – dh überschneidend$\operatorname{Rng}(X)$mit$P$So$z\prec y$Sinn macht, und dafür sorgen$C(\{x\in P\mid \cdots\})$bedeutet immer etwas , auch wenn die Bedingung am Ende alles wegfiltert – wird dann durch das Lemma weggeräumt, sobald die rekursive Magie ihre Arbeit erledigt hat und wir die Eingabe kennen$G$kommt von einer wohlerzogenen Rekursion.

---

Als zusätzliche Anmerkung könnte man argumentieren, dass dies „moralisch“ kein indirekter Beweis ist. Ich ziehe es vor, darüber nachzudenken, dass ich nur (a) und (c) annehmen und dann in der Mitte des Beweises des Lemmas sagen möchte

... diese Kette hat eine Obergrenze. Wenn diese Obergrenze ein maximales Element ist, dann sind wir fertig ; sonst gibt es etwas Größeres, das ist also eine strenge Obergrenze ...

Zu behaupten, dass „wir mit dem gesamten Lemma von Zorn fertig sind“, wenn wir uns mitten in einem inneren Induktionsschritt befanden, ist jedoch nicht wirklich in höflicher Gesellschaft getan. Indem wir den gesamten Beweis als indirekten Beweis formulieren, können wir dieser Intuition trotzdem auf einfache, aber formal akzeptable Weise folgen.

Der Teil des Beweises nach dem Lemma ist dann nur ein Argument, dass wir schließlich eine der „Wir sind fertig“-Bedingungen treffen müssen , weil ein ewiges Fortsetzen absurde Konsequenzen hätte.

Lassen$C$sei eine Auswahlfunktion an$P.$Wir können Ihre zweite transfinite Rekursionsvariation verwenden, um eine Ordnungsfolge zu definieren$F:\mathbf{Ord}\to P$folgendermaßen:

1. $F(0)= C(P)$
2. Wenn$F(\alpha)$ist maximal drin$P$lassen$F(\alpha+1) = F(\alpha).$Ansonsten das Set$A=\{x\in P : x > F(\alpha)\}$ist nichtleer und nehmen$F(\alpha+1) = C(A).$
3. Für eine Grenzordnungszahl$\lambda,$das können wir per Induktion sehen$F''(\lambda)$ist eine Kette. Die Annahme, dass jede Kette eine Obergrenze in hat$P$bedeutet den Satz $$B=\{x\in P:\mbox{x is an upper bound for $F''(\lambda)$}\}$$ ist nicht leer. Lassen$F(\lambda) = C(B).$

Das zu machen$G$'s Gesamtfunktionen, definieren Sie sie einfach willkürlich für alle Fälle, in denen sie durch das Obige nicht gut definiert sind (z. B. für Dinge, die keine Elemente / Teilmengen von sind$P$oder wenn die Sätze$A$oder$B$sind leer.). Induktion zeigt, dass diese Fälle nie auftauchen.

Hier kommt Hartog ins Spiel. Wir wissen, dass es eine Ordnungszahl gibt$\alpha^*$das spritzt nicht hinein$P.$Also für einige$\beta<\gamma < \alpha^*,$wir haben$F(\beta)=F(\gamma).$Wenn$F(\beta)$waren also nicht maximal$F(\beta+1)> F(\beta)$also dadurch, dass$F$nimmt zu,$F(\gamma)>F(\beta),$widerspricht der Tatsache, dass$F(\gamma)=F(\beta).$Daher$F(\beta)$ist maximal drin$P$.

Ja, dieses Thema hat mich als Student lange Zeit verblüfft. Tatsächlich länger, als ich zugeben möchte.

Lassen Sie uns zuerst das Problem mit dem Satz von Hartogs angehen. Sie müssen es in jedem Fall anwenden. Die Idee ist, dass Sie etwas rekursiv konstruieren, und dieses Etwas ist notwendigerweise eine injektive Funktion. Sie möchten wissen, dass sich der Prozess irgendwann stabilisiert, und der Satz von Hartogs besagt, dass er bei einer Ordnungszahl anhalten muss, sonst hätten wir eine Injektion von der richtigen Klasse aller Ordnungszahlen in unsere Menge erhalten.

Jetzt. Wie macht man das? Arbeiten wir rückwärts.

Das Ziel ist es, eine wohlgeordnete Kette zu konstruieren, die eine Obergrenze hat, die ein maximales Element ist. So$G_i$, oder$G$sollten Ihnen eine etwas längere Kette liefern, wenn sie in der Teilreihenfolge eine Kette erhalten. Wenn sie es nicht tun, ist es uns egal.

Warum ist es uns egal? Denn wir werden per Induktion beweisen, dass unsere rekursive Anwendung der Funktion immer eine Kette ergibt. Alles andere ist also egal.

Jetzt verwenden wir die Auswahlfunktion.

1. Für$x$eine Teilmenge der Teilordnung,$C(x)$ist eine Funktion, die eine obere Grenze für wählt$x$, die außerhalb liegt$x$. Wenn keine solche Obergrenze existiert, dann$x$liegt nicht im Bereich von$C$. Hier wenden wir das Auswahlaxiom an.

2. Wenn$x$ist eine ordnungserhaltende Einbettung aus einer Ordnungszahl$\alpha$in die partielle Ordnung mit einem begrenzten Bild, definieren$G(x)$Ist$C(x)$. Nämlich eine Obergrenze, zu der wir hinzufügen können$x$.

3. Wenn$x$ist etwas anderes,$G(x)=\varnothing$.

Wenden Sie nun den Satz über die transfinite Rekursion an. Wir erhalten eine Funktion, die eine obere Schranke nach der anderen anheftet, und wir müssen – durch Induktion – beweisen, dass dies immer eine Kette ist, und dass sie unterschiedlich sind, wenn sie nicht stabilisiert sind. Nach dem Satz von Hartogs gibt es also einen Punkt, an dem wir uns stabilisiert haben müssen, und dies gibt uns das gewünschte Ergebnis.