# Does mathematical induction presuppose the existence of a completed infinity?

Consider the following statement by Edward Nelson--this from the "Outline" of his 'proof' of the inconsistency of $$PA$$ (which Terry Tao found to contain an error):

"The induction axiom schema of Peano arithmetic $$\mathtt P$$ is usually justified as follows. Assume the basis $$\mathbb A_x(0)$$ and the induction step $$\forall$$x[$$\mathbb A\rightarrow\mathbb A_x$$(Sx)]. For any numeral $$d$$ [a numeral is just a string of the form $$\epsilon$$ (for the 'empty' string), |,||,|||,...--my comment], a special case of the induction step is $$\mathbb A_x$$($$d$$)$$\rightarrow\mathbb A_x$$(S$$d$$). Then we can prove $$\mathbb A_x$$($$d$$), starting with the basis and using detachment (modus ponens) as many times as there are occurrences of S in $$d$$.

This justification leaves much to be desired. The argument applies only to numerals, and shows that there is no need at all to postulate induction for numerals. By an unspoken conflation of the concrete concept of numeral with the formal concept of number, induction is postulated for numbers.

...Induction is justified by the finitary credo: for every number $$x$$ there exists a numeral $$d$$ such that $$x$$ is $$d$$. It is necessary to make this precise. We cannot express it as a formula of arithmetic because 'there exists' in 'there exists a numeral $$d$$ is a metamathematical existence assertion, not an arithmetical formula beginning with $$\exists$$.

The finitary credo can be formulated precisely using the standard model of arithmetic: for every element $$\xi$$ of $$\mathbb N$$ there exists a numeral $$d$$ such that it can be proved that $$d$$ is equal to the name of $$\xi$$, but this brings us into set theory [Extensionality + Infinity in $$ZF$$?--my question and comment]. The finitary credo has an infinitary foundation."

For my part, at least, I interpret the $$\forallx$$ in the induction step according to the number of elements in the universe of discourse--finite, if the universe of discourse is finite, infinite otherwise. If one concerns oneself with the special case of the induction step for the numerals (which he claims is used as the 'justification' for induction) $$\mathbb A_x\rightarrow\mathbb A_x$$(Sx), and proving $$\mathbb A_x$$($$d$$) by "starting with the basis ($$\mathbb A_x(\epsilon)$$) and using detachment (modus ponens) as many times as there are occurrences of S in $$d$$, one has

From $$\mathbb A_x(\epsilon)$$, $$\mathbb A_x(|)$$, $$\mathbb A_x(||)$$,... infer $$\forallx$$ $$\mathbb A_x(x)$$, the $$\omega$$-rule if one presupposes an infinite number of premises (in which case Nelson seems to be correct).

However, in his paper, "The Scope of Goedel's First Incompleteness Theorem", Bern Buldt writes, regarding the $$\omega$$-rule:

"Let $$\mathcal F$$ be a consistent formal system containing $$\mathcal Q$$ [Robinson arithmetic, so let $$\mathcal F$$=$$\mathcal Q$$--my comment] and $$\mathcal F^{\Omega}$$ denote the closure under the $$\omega$$-rule [where $$\Omega$$=$$\omega^2$$--my comment], then a straightforward induction along the arithmetical hierarchy establishes,

Proposition 3.5. $$\mathcal F^{\Omega}$$=$$\mathbf T\mathbf A$$[=True Arithmetic--my comment]."

Buldt also writes the following:

"Let $$\mathcal F_{\alpha}^{\omega}$$ denote a semi-formal system that admits $$\alpha$$ applications of the $$\omega$$-rule ($$\alpha$$ an ordinal number, $$\mathcal F$$ extending, say $$PA$$ [or rather, in this case, $$Q$$--my comment])...

Lemma 3.6. (For all n$$\in$$ $$\mathbb N$$) $$\mathcal F_n^{\omega}$$ is $$\Pi_{2n}$$- and $$\Sigma_{2n}$$-complete.

Proof: The induction basis comes for free ($$\Delta_0$$-completeness). In the induction step remove the two outermost quantifiers and employ the induction hypothesis. $$\exists$$-introduction and the $$\omega$$-rule then prove the result."

Consider now the following (philosophical) argument: Assume Nelson is correct about the finitary credo, i.e. that it cannot be formulated in $$Q$$ and that it is a "metamathematical existence assertion". Svejdar proved, however, that $$Q$$ is interpretable in Grzegorczyk's theory $$TC$$, so I argue that $$TC$$ is a metatheory for $$Q$$ and that the finitary credo can be formulated in $$TC$$. If this holds, then my argument holds also in $$TC$$, and Nelson's "justification" (i.e., the usual justification by the mathematical community) of mathematical induction presupposes the $$\omega$$-rule also holds for $$TC$$. If this is so, then by Buldt's theorem 3.6 one has that $$\mathcal F^{\Omega}$$=TA, where $$\mathcal F$$ is the fragment of $$TC$$ equivalent to $$Q$$. Since the $$\omega$$-rule implies mathematical induction holds, $$TC$$+$$\omega$$-rule interprets $$PA$$ so $$Q^{\Omega}$$=$$PA^{\Omega}$$=TA and by Buldt, $$\Omega_{Q}$$=$$\Omega_{PA}$$=$$\omega^2$$.

Question 1: Is this a valid argument? If not, where are the flaws?

Question 2: Since $$\Omega_{Q}$$=$$\Omega_{PA}$$=$$\omega^2$$ seems an odd result (after all, shouldn't $$\Omega_{PA}$$=$$\epsilon$$?), does it call into question Nelson's belief that the finitary credo has an infinitary foundation?

• In what way? Since $PA$ is equiconsistent with $ZFC$-Infinity, how does $Q$ +"Second-order Induction" allow $ZFC$-Infinity to 'regain' Infinity? Dec 30 '15 at 13:19
• Is $PA^2$ then interpretable in finite $ZF$ where Infinity holds? Dec 30 '15 at 23:00