Beweis des Prinzips der Doppelinduktion
Ich arbeite an den Übungen in Hrabacecks und Jecks Einführungsbuch zur Mengenlehre und habe Probleme mit dem Beweis des Doppelinduktionsprinzips. Das Ergebnis wird wie folgt angegeben: wenn fest angegeben$n,m$
$(\forall k)(\forall l)((k<m\vee(k=m\wedge l<n))\Rightarrow P(k,l))\Rightarrow P(m,n)$ (*)
hält dann $P(n,m)$ gilt für alle $n,m$.
Meine Idee ist es zu versuchen und zu zeigen, dass die Eigenschaft $Q(m)=(\forall l)P(m,l)$ gilt für alle Werte von $m$, nehme ich an
$(\forall k)(k<m\Rightarrow(\forall l)P(k,l))$ (($(\forall k)(k<m\Rightarrow Q(k))$)
in einem Versuch zu zeigen, dass dies (zusammen mit (*)) impliziert $Q(m)$ und dann starke Induktion verwenden, um den Beweis abzuschließen.
Ich bin mir wirklich nicht sicher, wohin ich von hier aus gehen soll. Oder besser gesagt, ich komme zu der Antwort, nach der ich suche, aber ich verwende nur einmal eine starke Induktion, was seltsam ist und mich denken lässt, dass ich etwas falsch mache, aber ich kann den Fehler nicht finden. Ich habe einen anderen Beitrag mit einer sehr ähnlichen Frage zu genau derselben Übung gesehen, aber die Antworten dort sind nicht sehr hilfreich.
Antworten
Versuchen wir, den Beweis methodisch durchzugehen. ich werde schreiben$\mathscr{Ens}$um die Sammlung von Axiomen und Schemata der Mengenlehre kurz und bündig zu bezeichnen. Angesichts der Hypothese:$$R\colon \equiv(\forall m)(\forall n)(m, n \in \mathbb{N} \Rightarrow [(\forall k)(\forall l)((k<m \wedge l \in \mathbb{N})\vee (k=m \wedge l<n) \Rightarrow P(k, l)) \Rightarrow P(m, n)]),$$ wir werden feststellen, dass: $$\mathscr{Ens}, R \vdash (\forall m)(\forall n)(m, n \in \mathbb{N} \Rightarrow P(m, n)). \tag{0}$$ Wir haben jedoch in $\mathscr{Ens}$ (Eigentlich genügt es, nur den rein logischen Teil zu betrachten, wobei die Axiome, die Mengen betreffen, außer Acht gelassen werden.) Die Äquivalenz: $$(\forall m)(\forall n)(m, n \in \mathbb{N} \Rightarrow P(m, n)) \Leftrightarrow (\forall m)(m \in \mathbb{N} \Rightarrow (\forall n)(n \in \mathbb{N} \Rightarrow P(m, n))),$$ Um (0) zu beweisen, reicht es aus, Folgendes festzustellen: $$\mathscr{Ens}, R \vdash (\forall m)(m \in \mathbb{N} \Rightarrow Q(m)), \tag{1}$$ wo wir, wie Sie ganz angemessen angegeben haben, Folgendes vorstellen: $$Q(m)\colon \equiv (\forall n)(n \in \mathbb{N} \Rightarrow P(m, n)).$$ Aufgrund des Induktionsprinzips in seiner sogenannten "starken" Form genügt es, um (1) festzustellen, dass: $$\mathscr{Ens}, R \vdash (\forall m)(m \in \mathbb{N} \Rightarrow ((\forall k)(k<m \Rightarrow Q(k))\Rightarrow Q(m))). \tag{1'}$$
Da weder $\mathscr{Ens}$ Noch $R$ enthalten beliebige Buchstaben (Variablen) - mit anderen Worten die Theorie, deren Liste von Axiomen und Schemata gegeben ist durch $\mathscr{Ens}$ zusammen mit $R$hat keine Konstanten - es reicht aus, die dequantifizierte Version von (1 ') zu erstellen:$$\mathscr{Ens}, R \vdash m \in \mathbb{N} \Rightarrow ((\forall k)(k<m \Rightarrow Q(k))\Rightarrow Q(m)), \tag{1''}$$da eine erneute Angabe möglich ist (über Buchstaben, die keine Konstanten sind). Unter Berufung auf das Metatheorem des Abzugs , um zu beweisen (1 ''), reicht es aus, Folgendes festzustellen:$$\mathscr{Ens}, R, m \in \mathbb{N} \vdash (\forall k)(k<m \Rightarrow Q(k))\Rightarrow Q(m), \tag{1'''}$$ und indem Sie dieses Metatheorem erneut anwenden, um es auf Folgendes zu reduzieren: $$\mathscr{Ens}, R, m \in \mathbb{N}, (\forall k)(k<m \Rightarrow Q(k)) \vdash Q(m). \tag{1''''}$$
Um noch einmal auf die starke Form des Induktionsprinzips zurückzugreifen, um zu beweisen (1 '' ''), genügt es zu zeigen, dass: $$\mathscr{Ens}, R, m \in \mathbb{N}, (\forall k)(k<m \Rightarrow Q(k)) \vdash (\forall n)(n \in \mathbb{N} \Rightarrow [(\forall l)(l<n \Rightarrow P(m, l)) \Rightarrow P(m, n)]). \tag{2}$$ Seit dem Brief $n$ wird nicht unter den Konstanten der Theorie gefunden, die durch die Sammlung von beschrieben werden $\mathscr{Ens}, R, m \in \mathbb{N}, (\forall k)(k<m \Rightarrow Q(k))$ - dessen einzige Konstante ist $m$, ein eindeutiger Buchstabe - um zu beweisen, (2) die dequantifizierte Version zu etablieren: $$\mathscr{Ens}, R, m \in \mathbb{N}, (\forall k)(k<m \Rightarrow Q(k)) \vdash n \in \mathbb{N} \Rightarrow [(\forall l)(l<n \Rightarrow P(m, l)) \Rightarrow P(m, n)] \tag{2'}$$wird aus dem gleichen Grund wie oben für die Dequantifizierung / Reantantifizierung über Nichtkonstanten ausreichen. In ähnlicher Weise wird durch erneutes Appellieren an das Metatheorem des Abzugs der Beweis (2 ') erreicht, solange wir Folgendes feststellen:$$\mathscr{Ens}, R, m, n \in \mathbb{N}, (\forall k)(k<m \Rightarrow Q(k)) \vdash (\forall l)(l<n \Rightarrow P(m, l)) \Rightarrow P(m, n), \tag{2''}$$ und eine weitere Anwendung des Metatheorems des Abzugs reduziert unsere Aufgabe auf die Feststellung: $$\mathscr{Ens}, R, m, n \in \mathbb{N}, (\forall k)(k<m \Rightarrow Q(k)), (\forall l)(l<n \Rightarrow P(m, l)) \vdash P(m, n). \tag{2'''}$$
Der Einfachheit halber sei $\mathscr{T}$ bezeichnen die Theorie, deren Liste von Axiomen und Schemata von der Sammlung gegeben wird $\mathscr{Ens}, R, m, n \in \mathbb{N}, (\forall k)(k<m \Rightarrow Q(k)), (\forall l)(l<n \Rightarrow P(m, l))$. Schon seit$R$ ist offensichtlich ableitbar von $\mathscr{T}$können wir auch die dequantifizierte Version ableiten: $$\mathscr{T} \vdash m, n \in \mathbb{N} \Rightarrow [(\forall k)(\forall l)((k<m \wedge l \in \mathbb{N})\vee (k=m \wedge l<n) \Rightarrow P(k, l)) \Rightarrow P(m, n)]. \tag{3}$$ Da weiterhin $m, n \in \mathbb{N}$ ist auch ableitbar von $\mathscr{T}$Wir sammeln, indem wir modus ponens auf (3) anwenden, dass:$$\mathscr{T} \vdash (\forall k)(\forall l)((k<m \wedge l \in \mathbb{N}) \vee (k=m \wedge l<n) \Rightarrow P(k, l)) \Rightarrow P(m, n). \tag{4}$$ Um das zu beweisen $\mathscr{T} \vdash P(m, n)$Es wird aufgrund der Modus-Ponens-Abzugsmethode ausreichen, um festzustellen, dass der Vorgänger der Implikation bei (4) auch aus ableitbar ist $\mathscr{T}$mit anderen Worten: $$\mathscr{T} \vdash (\forall k)(\forall l)((k<m \wedge l \in \mathbb{N}) \vee (k=m \wedge l<n) \Rightarrow P(k, l)). \tag{5}$$ Da die einzigen Konstanten von $\mathscr{T}$ sind $m$ und $n$ - die sich von unterscheiden $k$ und $l$ - Um (5) zu beweisen, reicht es aus, die dequantifizierte Version zu beweisen: $\mathscr{T} \vdash (k<m \wedge l \in \mathbb{N}) \vee (k=m \wedge l<n) \Rightarrow P(k, l), \tag{5'}$aus dem gleichen Grund der Dequantifizierung / Reantantifizierung, den wir bereits mehrfach erwähnt haben. Die Beziehung (5 ') kann wiederum aufgrund der Methode der Disjunktion von Fällen abgeleitet werden, solange wir separat festlegen, dass:$$\mathscr{T} \vdash (k<m \wedge l \in \mathbb{N}) \Rightarrow P(k, l) \tag{6a}$$ beziehungsweise: $$\mathscr{T} \vdash (k=m \wedge l<n) \Rightarrow P(k, l). \tag{6b}$$ Aufgrund des Metatheorems des Abzugs können die Beziehungen (6a) und (6b) wie folgt umformuliert werden: $$\begin{align} \mathscr{T}, k<m \wedge l \in \mathbb{N} &\vdash P(k, l) \tag{6a'}\\ \mathscr{T}, k=m \wedge l<n &\vdash P(k, l). \tag{6b'} \end{align}$$ Wir haben eindeutig: $$\mathscr{T} \vdash (\forall k)(k<m \Rightarrow Q(k)), \tag{7}$$ woher durch Dequantifizierung schließen wir insbesondere, dass: $$\mathscr{T} \vdash k<m \Rightarrow Q(k). \tag{7'}$$ Da jeder Satz einer schwächeren Theorie ein Satz für jede stärkere Theorie bleibt, ist klar, dass: $$\mathscr{T}, k<m \wedge l \in \mathbb{N} \vdash k<m \Rightarrow Q(k). \tag{7''}$$ Es ist auch offensichtlich, dass: $$\mathscr{T}, k<m \wedge l \in \mathbb{N} \vdash k<m, l \in \mathbb{N} \tag{7'''}$$ - da eine Konjunktion immer einen ihrer Begriffe impliziert - woher erhalten wir durch modus ponens in Kombination mit (7 ''): $$\mathscr{T}, k<m \wedge l \in \mathbb{N} \vdash Q(k),$$ was explizit ausgeschrieben ist ist genau: $$\mathscr{T}, k<m \wedge l \in \mathbb{N} \vdash (\forall n)(n \in \mathbb{N} \Rightarrow P(k, n)). \tag{8}$$ Partikularisierung $n$ wie $l$ wir erhalten weiter: $$\mathscr{T}, k<m \wedge l \in \mathbb{N} \vdash l \in \mathbb{N} \Rightarrow P(k, l), \tag{8'}$$und modus ponens in Kombination mit (7 '' ') ergibt genau (6a'). In Bezug auf (6b ') stellen wir zunächst fest, dass per Definition:$$\mathscr{T} \vdash (\forall l)(l<n \Rightarrow P(m, l)),$$ woher durch Entquantifizierung haben wir: $$\mathscr{T} \vdash l<n \Rightarrow P(m, l) \tag{9}.$$ Die gleiche Implikation lässt sich auch aus der stärkeren Theorie ableiten: $$\mathscr{T}, k=m \wedge l<n \vdash l<n \Rightarrow P(m, l), \tag{9’}$$ und wir bemerken, dass wir durch ein Zeichen, das dem im Fall der Beziehung (7 '' ') erläuterten ähnlich ist, in diesem Fall haben: $$\mathscr{T}, k=m \wedge l<n \vdash k=m, l<n. \tag{7’’’’}$$ Wenn wir modus ponens auf (7 '' '') und (9 ') anwenden, sammeln wir: $$\mathscr{T}, k=m \wedge l<n \vdash P(m, l). \tag{9’’}$$ Aufgrund eines der Schemata, die das Gleichheitsverhältnis axiomatisieren, haben wir insbesondere: $$\mathscr{T}, k=m \wedge l<n \vdash k=m \Rightarrow (P(k, l) \Leftrightarrow P(m, l)),$$ woher durch Modus Ponens in Kombination mit (7 '' '') folgt, dass: $$\mathscr{T}, k=m \wedge l<n \vdash P(k, l) \Leftrightarrow P(m, l),$$ was außerdem beinhaltet: $$\mathscr{T}, k=m \wedge l<n \vdash P(m, l) \Rightarrow P(k, l). \tag{9’’’}$$ Eine endgültige Anwendung von Modus Ponens zwischen (9 '') und (9 '' ') legt (6b') fest und schließt unser Argument ab.
Wenn Sie davon ausgehen, dass für eine feste $m$, $n$ du hast $$(\forall k)(\forall l)((k<m\vee(k=m\wedge l<n))\Rightarrow P(k,l))\Rightarrow P(m,n).$$ Nun nimm das an $P(M,N)$ ist für manche falsch $(M,N)$, und nehme $(M,N)$ sein (unter den Werten, für die $P$ ist falsch) derjenige, für den für jeden $M^{\prime}$, $N^{\prime}$ so dass $P(M^{\prime},N^{\prime})$ ist auch falsch $M < M^{\prime}$ oder $M = M^{\prime}$ und $N \leq N^{\prime}$ (dh das lexikographisch erste solche Paar).
Jetzt können Sie einen leichten Widerspruch bekommen (vorausgesetzt, dass $P(1,1)$ ist wahr).
Eine alternative Methode, wenn Sie keinen Widerspruch mögen, nehmen Sie an $P(1,1)$ und dann zeig das $P(m,1)$ ist für alle wahr $m$. Dann für jeden$m$, verwenden $P(m,1)$ zu zeigen, dass $P(m,n)$ ist für alle wahr $n$. Dies scheint wie Ihr versuchter Beweis zu sein. Sie müssen hier zweimal Induktion verwenden, da Sie zeigen müssen, dass, wenn die Aussage wahr ist$m=1$dann ist es für alle wahr $m$.