4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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)

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Russell Easterly Nov 21 '13 at 0:40
  • $\begingroup$ The answer above did not say it can be proved without induction. But it can be proved. $\endgroup$ – André Nicolas Nov 21 '13 at 0:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.