Nachweis der „Induktionssicherungsmethode“

Question

Ich habe also verschiedene logische Aussagen mit der Induktionsmethode bewiesen (wie strukturelle Induktion, starke Induktion, schwache Induktion usw.). Ich habe mich gefragt, ob es einen Beweis für diese "Induktionsbeweismethode" gibt. Bisher bin ich dazu gekommen,

Induktion $\rightarrow$ Gut bestellender Auftraggeber $\rightarrow$ Axiom der Wahl $\rightarrow$ ZFC $\rightarrow$ Logiktheorie erster Ordnung

Jetzt frage ich mich also, ob es eine Möglichkeit gibt, diese Beweismethode nur mit Logik und ohne Mengenlehre zu beweisen (oder gleichwertig zu zeigen). Weisen Sie auch darauf hin, ob meine Argumentation fehlerhaft ist

Bearbeiten : Es scheint, als würde strukturelle Induktion keine Induktion über Zahlen jeglicher Art durchführen, sondern über Strukturen. Ich kann also keine Peanos-Axiome verwenden, um sie zu formulieren. Ich brauche ZFC. Aber ZFC ist nur eine Art Logik erster Ordnung Die strukturelle Induktion beruht also auf dieser speziellen Logik erster Ordnung. Aber es gibt einige allgemeine Theoreme (die wahrscheinlich nicht unbedingt zu ZFC gehören) in Propositional Calculus, die ich mit struktureller Induktion beweisen muss. Aber strukturelle Induktion kann nurIch bin verwirrt. Auf einfachere Weise: Der folgende allgemeine Satz, den ich am Ende meiner Frage zeigen werde, liegt außerhalb der Mengenlehre. Und ich brauche strukturelle Induktion, um es zu beweisen. Aber strukturelle Induktion kann nur Dinge innerhalb der Mengenlehre beweisen. Weil die strukturelle Induktion ein Axiom der axiomatischen Mengenlehre ist.

Ich werde nur ein Beispiel für einen dieser allgemeinen Sätze geben .

" Angenommen$A$_$1$ $\equiv$ $A$_$2$. Zeigen Sie das für jede Formel$C$-haltig $A$_$1$ als Teil, wenn wir eines oder mehrere Vorkommen des Teils ersetzen $A$_$1$ durch $A$_$2$ dann ist die resultierende Formel logisch äquivalent zu $C$. ""

Answer 1

Die mathematische Induktion ist eines der Peano-Axiome, an die sich jede Definition der natürlichen Zahlen und der Menge der natürlichen Zahlen in jeder Mengenlehre halten muss.

Nach der Definition natürlicher Zahlen in einer Mengenlehre und nach der Konstruktion der natürlichen Zahlen und der Menge natürlicher Zahlen daraus müssen die Peano-Axiome innerhalb der Mengenlehre bewiesen werden, wobei nur die Mengenlehre und die symbolische Logik verwendet werden. Es findet alles statt$\textit{within}$ eine Mengenlehre, und daher kann man es nicht tun $\textit{outside}$ eine Mengenlehre.

Der Beweis des Induktionsschemas reduziert sich auf ein einfaches satztheoretisches Argument; Dies kann natürlich je nach den Grundlagen der verwendeten Mengenlehre unterschiedlich sein. In Quines New Foundations (NF) gilt das Induktionsschema beispielsweise im Allgemeinen nicht - wie zu erwarten ist, gilt es nur für geschichtete Formeln oder allgemeiner für Formeln$\phi$ für welche $\{x|\phi\}$ existiert.

Siehe meine Dissertation über NF in https://eprints.illc.uva.nl/574/1/X-1989-02.text.pdf .

Answer 2

Das Prinzip der mathematischen Induktion läuft auf eine Tatsache hinaus, die über die natürlichen (Zähl-) Zahlen seit Tausenden von Jahren bekannt ist:

Jede natürliche Zahl außer der "ersten" (1 oder 0) kann durch einen Vorgang wiederholter Abfolge ab der "ersten" Zahl erreicht werden.

Formal kann gezeigt werden, dass die Induktion an jedem Satz anhält$N$ (möglicherweise endlich) mit $x_0\in N$ und Funktion $S: N \to N$ so dass:

$~~~~~~N = \{ x_0,~ S(x_0), ~S(S(x_0)), ~\cdots ~\} $

Mein formaler Beweis mit einer Form des natürlichen Abzugs ist hier . Ja, es wird eine sehr grundlegende Mengenlehre verwendet, aber nur ein Axiomschema für beliebige Teilmengen (entspricht der Spezifikation in ZFC).

Siehe auch zu diesem Thema meine Blog-Beiträge:

• Papa, woher kommen Zahlen?
• Was ist wieder eine Nummer?