So I have been proving various logical statements using induction method (like structural induction , strong induction , weak induction etc ).I was wondering If there is a proof of this "Induction proof method" . So far , I came to this ,
Induction $\rightarrow$ Well ordering principal $\rightarrow$ Axiom of choice $\rightarrow$ ZFC $\rightarrow$ First-order logic theory
So now I wonder , Is there a way to prove (or show equivalence of) this method of proof using just Logic and no Set theory.Also point out if there is a flaw in my reasoning
Edit:It seems like structural induction doesn't do induction over numbers of any kind , it does in on structures .So I can't use peanos axioms to formulate it .I need ZFC .But ZFC is just a kind of first order logic.So structural induction comes from this particular first order logic . But there are some General theorems (which probably don't necessarily belong to ZFC) in Propositional Calculus which I have to prove using structural Induction .But Structural Induction can only be used inside ZFC , not outside of it.I am confused.In a simpler way , The following general theorem I will show at the end of my question is outside of set theory . And I need structural induction to prove it . But structural Induction can only prove things inside set theory. Because Structural Induction is a axiom of Axiomatic set theory.
I will give just a example of one of these general theorem.
"Assume $A$$1$ $\equiv$ $A$$2$ . Show that for any formula $C$-containing $A$$1$ as a part , if we replace one of more occurences of the part $A$$1$ by $A$$2$ , then the resulting formula is logically equivalent to $C$."
Best Answer
Mathematical induction is one of the Peano axioms, to which every definition of the natural numbers and the set of natural numbers, in every set theory, has to abide.
After defining natural numbers in a set theory, and after constructing the natural numbers and the set of natural numbers from this, the Peano axioms need to be proved within the set theory, making only use of set theory and symbolic logic. It all takes place $\textit{within}$ a set theory, and hence one cannot do it $\textit{outside}$ a set theory.
The proof of the induction schema reduces to a simple set-theoretical argument; of course this may differ according to the basics of the set theory used. For example, in Quine's New Foundations (NF) the induction schema does not generally hold - as may be expected, it only holds for stratified formulae, or, more general, for formulae $\phi$ for which $\{x|\phi\}$ exists.
See my dissertation on NF in https://eprints.illc.uva.nl/574/1/X-1989-02.text.pdf .