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

Question

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)}$?

Answer 1

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.

Answer 2

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

Answer 3

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}.$