Proof of "Induction proof method"

Question

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$."

Answer 1

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 .

Answer 2

The Principle of Mathematical Induction boils down to a fact known about the natural (counting) numbers for thousands of years:

Every natural number but the "first" (1 or 0), can be reached by a process of repeated succession starting at the "first" number.

More formally, induction can be shown to hold on any set $N$ (possibly finite) with $x_0\in N$ and function $S: N \to N$ such that:

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

My formal proof using a form of natural deduction is here. Yes, it does use some very basic set theory, but only an axiom schema for arbitrary subsets (equivalent of specification in ZFC).

Also on this topic, see my blog postings:

• Daddy, where do numbers come from?
• What is a number again?