0
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ How does $P(n) \implies P(n')$? $\endgroup$ – gt6989b Apr 4 at 4:10
  • $\begingroup$ Assume $n$ does not succeed $1$. Then $n^\prime$ does not succeed $1$. $\endgroup$ – Steven Thomas Hatton Apr 4 at 4:14
  • 5
    $\begingroup$ @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. $\endgroup$ – Derek Elkins Apr 4 at 5:50
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That was easily corrected by specifying $n^\prime$ succeeds 1 if and only if $n$ succeeds 1. $\endgroup$ – Steven Thomas Hatton Apr 4 at 4:36
  • $\begingroup$ 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...? $\endgroup$ – David Apr 4 at 4:51
  • $\begingroup$ 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$. $\endgroup$ – Steven Thomas Hatton Apr 4 at 4:56
  • $\begingroup$ 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. $\endgroup$ – David Apr 4 at 4:58
  • $\begingroup$ 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)$? $\endgroup$ – Steven Thomas Hatton Apr 4 at 5:03
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Steven Thomas Hatton Apr 4 at 6:12
  • 3
    $\begingroup$ @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. $\endgroup$ – Arthur Apr 4 at 6:14
0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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)$. $\endgroup$ – Derek Elkins Apr 4 at 18:38

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.