# Proofs with Induction Imply Proofs Without Induction?

Assume we can prove $\forall x P(x)$ in first order Peano Arithmetic (PA) using induction and modus ponens. Does this mean we can prove $\forall x P(x)$ from the other axioms of PA without using induction?

Given the induction axiom $(P(0) \land \forall x(P(x) \rightarrow P(Sx))) \rightarrow \forall x P(x)$ we must first prove $P(0) \land \forall x(P(x) \rightarrow P(Sx))$ using the other axioms of PA before we can deduce $\forall x P(x)$. This can be converted to $P(0) \land \forall x( \neg P(x) \lor P(Sx))$. We better not be able to prove $\exists x \neg P(x)$ from the other axioms so this reduces to $P(0) \land \forall x P(Sx)$. It seems reasonable if we can prove $P(0) \land \forall x P(Sx)$ from the other axioms without using induction we can prove $\forall x P(x)$ without induction.

To say that any proof that can be done using induction can be done without induction is to say that the induction axiom is redundant; i.e. that the rest of the Peano Axioms can provide a proof of the induction axiom. Natural Number arithmetic without the induction axiom is known as Robinson arithmetic (truthfully, a few other axioms are added, such as the fact that every number is either zero or the successor of some natural number, which is a theorem in Peano Arithmetic), and it is significantly weaker than Peano arithmetic.

Some examples of ways in which Robinson arithmetic is weaker include the non-commutativity of multiplication and addition. (i.e. commutativity is not provable)

The part:

"This can be converted to $P(0) \land \forall x( \neg P(x) \lor P(Sx))$."

is correct.

The part:

"We better not be able to prove $\exists x \neg P(x)$ from the other axioms so this reduces to $P(0) \land \forall x P(Sx)$."

is not. In general $\forall x(A(x)\lor B(x))$ is not equivalent to $\forall x A(x) \lor \forall x B(x)$.

This shows that your argument is not correct. One can also show that what it argues for is not true: It is easy to construct models of the rest of the axioms of first-order PA in which a sentence easily proved in first-order PA is false.

The details depend on the exact formulation of first-order PA. For the version you linked to, note that the non-negative reals (or non-negative rationals, or non-negative numbers of the form $\frac{n}{2}$) with the usual interpretation of successor, addition, and multiplication form a model of the rest of the axioms if we throw the induction scheme away. The sentence $\exists x(x+x=S0)$ is true in all these models, but easily refutable in first-order PA.

• Let $P(x) = (x+x \neq S0)$. Clearly, $\forall x P(x)$ is independent of the other axioms of PA. How is it possible we can prove $P(0) \land \forall x (\neg P(x) \lor P(Sx))$ from the other axioms without using induction? – Russell Easterly Nov 21 '13 at 0:40
• The answer above did not say it can be proved without induction. But it can be proved. – André Nicolas Nov 21 '13 at 0:45