What is the pitfall in the inductive “proof” of P(x):= x does not succeed 1?

The following statement of Peano's axioms appears in Fundamentals of Mathematics, Volume 1 Foundations of Mathematics: The Real Number System and Algebra; Edited by H. Behnke, F. Bachmann, K. Fladt, W. Suess and H. Kunle

• I. $$1$$ is a number.
• II. To every number $$a$$ there corresponds a unique number $$a^{\prime},$$ called its successor.
• III. If $$a^{\prime}=b^{\prime},$$ then $$a=b.$$
• IV. $$a^{\prime}\ne1$$ for every number $$a.$$

• V. Let $$A\left(x\right)$$ be a proposition containing the variable $$x.$$ If $$A\left(1\right)$$ holds and if $$A\left(n^{\prime}\right)$$ follows from $$A\left(n\right)$$ for every number $$n,$$ then $$A\left(x\right)$$ holds for every number $$x.$$

Typically an inductive proof of some proposition $$P$$ about the natural numbers proceeds as follows: show $$P\left(1\right)$$; show $$P\left(n\right)\implies{P\left(n^\prime\right)}.$$

I will say that a number succeeds $$1$$ if and only if it is the successor of $$1$$ or it is the successor of a number which succeeds $$1$$. Given the proposition

$$P\left(x\right):=\text{x does not succeed 1},$$

we have $$P\left(1\right)$$ is true. If we assume $$P\left(n\right)$$, then $$P\left(n^\prime\right)$$ follows. It is easy to show, however, that $$P$$ does not satisfy Peano's fifth axiom because $$P\left(1^\prime\right)$$ is not true.

What is it about this particular proposition which requires us to test the special case of $$P\left(1^\prime\right)$$?

Put differently, given the proposition

$$Q\left(x\right):=x=1\lor\text{x succeeds 1},$$

is it sufficient to show $$Q\left(1\right)$$ and $$Q\left(n\right)\implies{Q\left(n^\prime\right)}$$?

• How does $P(n) \implies P(n')$? – gt6989b Apr 4 at 4:10
• Assume $n$ does not succeed $1$. Then $n^\prime$ does not succeed $1$. – Steven Thomas Hatton Apr 4 at 4:14
• @StevenHatton Your comment just restates what gt6989b asked. It doesn't prove it in any way. $1$ doesn't succeed $1$ but $1'$ does, so the implication is clearly false. – Derek Elkins Apr 4 at 5:50

Your definition of "succeeds" says (among other things)

if $$n$$ succeeds $$1$$ then $$n'$$ succeeds $$1$$.

This is not the same as your subsequent claim

if $$n$$ does not succeed $$1$$ then $$n'$$ does not succeed $$1$$.

You have made the converse error.

• That was easily corrected by specifying $n^\prime$ succeeds 1 if and only if $n$ succeeds 1. – Steven Thomas Hatton Apr 4 at 4:36
• Now you are really mixing up the logic. If that is supposed to be true for all $n$, then $1'$ does not succeed $1$ (because $1$ does not succeed $1$). If that's not what you meant, then please be more careful with your definition: $x$ succeeds $1$ means...? – David Apr 4 at 4:51
• The modified proposition is: a number succeeds $1$ if and only if it is the successor of $1$ or it is the successor of a number which succeeds $1$. – Steven Thomas Hatton Apr 4 at 4:56
• OK. So $P(n)$ means: $n\ne1'$ and for all $m$, either $n\ne m'$ or $P(m)$. If you still claim that this implies $P(n')$, please provide a careful and detailed proof. – David Apr 4 at 4:58
• In my original post I prove $\forall_{x}P\left(x\right)$ is not true. My question is why did I need to test the unusual case of $P\left(1^\prime\right)$? – Steven Thomas Hatton Apr 4 at 5:03

Your induction step fails, because "$$n'$$ is not the successor of $$1$$" cannot be derived from $$P(n)$$. As is evidenced by $$1'$$.

• But the question is: what is it about this situation that requires testing the case of $1^\prime$? Usually we just test $n=1$ and the generic $n\mapsto n^\prime$. – Steven Thomas Hatton Apr 4 at 6:12
• @StevenHatton There is nothing special about this situation at all. You do not have the implication $P(n)\implies P(n')$. That's the flaw, nothing else. It's just that we can most easily demonstrate the flaw by pointing out the case where it is relevant. – Arthur Apr 4 at 6:14

Forget about what our propositions are and consider the formulae

$$P\left(x\right):=x=1\lor\lnot S\left(x\right),$$

$$S\left(x\right)\iff S\left(x^{\prime}\right)\text{ for } x\ne 1.$$

The latter is equivalent to

$$\lnot{S}\left(x\right)\iff \lnot{S}\left(x^{\prime}\right)\text{ for } x\ne 1.$$

Now assume

$$n\ne{1}\land{P}\left(n\right).$$

This implies $$\lnot{S}\left(n^\prime\right),$$ which implies $$P\left(n^\prime\right).$$ So the induction argument $$n\ne1 \land P\left(n\right)\implies P\left(n^\prime\right)$$ is valid for this situation. And we clearly have $$P\left(1\right)$$.

The reason this is not a valid inductive proof is that there is a disjunction in $$P$$. The rule for $$P\left(1\right)\mapsto P\left(1^\prime\right)$$ is not the same as that for $$P\left(n\right)\mapsto P\left(n^\prime\right)$$. In a sense we have chosen the wrong base case. At a minimum we must explicitly test the first case not "masked" by $$x=1$$. Using the following meaning of $$S$$, upon testing that case we find the proof fails.

The case $$x=1$$ could have been omitted by the proposition the successor of $$x$$ does not succeed $$1$$. Which fails immediately.

What about the case of

$$Q\left(x\right):=x=1\lor S\left(x\right)?$$

Lets express the proposition $$x$$ succeeds $$1$$ as

$$S\left(x\right):=x=1^{\prime}\lor\left(\exists_{y}x=y^{\prime}\land S\left(y\right)\right).$$

By the above reasoning we have to explicitly test the cases $$1, 1^\prime, 1^{\prime\prime}.$$

• For the inductive case, we need to prove $\forall n.P(n)\Rightarrow P(n')$. You can't add extra constraints on $n$, like $n\neq 1$. If you did want to do that, you'd have to change $P$ to $R(n)\equiv n\neq 1\land P(n)$, but then to apply the rule of induction you need to consider the base case $R(1)$, not $P(1)$, which clearly doesn't hold. since $1\neq 1$ is false. If you want to do an induction that only applies to some suffix of the natural numbers, you can simply do $Q(n)\equiv n < k\lor P(n)$ which you can use to ultimately prove $\forall n\geq k.P(n)$. – Derek Elkins Apr 4 at 18:38