Proofs with Induction Imply Proofs Without Induction?

Question

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.

Answer 1

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)

Answer 2

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.