1
$\begingroup$

The problem is,

Prove that for each positive natural number $a$ there exists a natural number $b$ such that $b{++}=a$.

Using only the followings,

  1. Peano Axioms.

Axiom 2.1

$0$ is a natural number.

Axiom 2.2

If $n$ is a natural number then $n{+}{+}$ is also a natural number. (Here $n{+}{+}$ denotes the successor of $n$ and previously in the book the notational implication has been bijected to the familiar $1, 2\ldots$).

Axiom 2.3

$0$ is not the successor of natural number; i.e. we have $n{+}{+}\neq 0$ for every natural number $n$.

Axiom 2.4

Different natural numbers must have different successors; i.e., if $n, m$ are natural numbers and $n\neq m$, then $n{+}{+}\neq m{+}{+}$.

Axiom 2.5

Let $P(n)$ be any property pertaining to a natural number $n$. Suppose that $P(0)$ is true, and suppose that whenever $P(n)$ is true, $P(n{+}{+})$ is also true. Then $P(n)$ is true for every natural number $n$.

  1. Definition of Addition: Let $m$ be a natural number. We define, $0 + m = m$ and suppose we have inductively defined the addtion $n + m$ then we define, $(n{++})+m=(n+m){++}$. Where $n{++}$ is the successor of $n$.

  2. Commutativity, Associativity and Cancellation Laws of Addition.

  3. Definition of Positivity: A natural number $n$ is said to be positive if $n\neq 0$.

I thought to apply induction on $a$ but I can't figure out how to prove the base case and what value would be apt for $a$ because if we take $a=0{++}$ then we are bound to assume that,

There doesn't exist any natural number between $0$ and $0{++}$.

Which I can't prove. Recently I have asked another question here whose proof also depended on the vital proof of the problem I have given. It will be very nice if someone can give some outline of the argument.

$\endgroup$
1
  • $\begingroup$ Why do you need to prove that there is no natural number "between" $0$ and $0++$? If you apply induction then, by the axiom of induction, you can prove it for all natural numbers, and no other information about them is needed. $\endgroup$ – KSmarts Jan 2 '15 at 15:49
2
$\begingroup$

Use induction on the statement "$n=0$ or there exists a natural number $b$ such that $b++=n$."

Showing this for $n=0$ is obvious. Do you need help on showing the induction step?

ADDED: Here is the induction step (in summary: you can fill in the small gaps).

Assume the statement is true for $n$. There are two cases: $n=0$ or $n \ne 0$.

If $n=0$, then $0++=n++$, and the statement is true for $n++$.

If $n\ne 0$, we must have $b++=n$ for some $b$ (since we assumed the statement is true for $n$). Then $(b++)++=n++$, and again the statement is true for $n++$.

ADDED EVEN LATER:

@Andreas Blass gave a much shorter and better induction step in his comment. Here it is:

Assume the statement is true for $n$ (although we will not use this assumption). Then let $b=n$. We trivially get $b++=n++$, so the statement is true for $n++$.

$\endgroup$
6
  • $\begingroup$ Yes it would be great. How can we prove from here that there doesn't exist any natural number between $0$ and $0{++}$? $\endgroup$ – user170039 Jan 2 '15 at 15:07
  • $\begingroup$ If $n\ne0$ why do we must have $b{++}=n$? Note that this is the problem to be proved. $\endgroup$ – user170039 Jan 2 '15 at 15:16
  • $\begingroup$ @user170039: Does my additional edit answer your second comment? $\endgroup$ – Rory Daulton Jan 2 '15 at 15:18
  • 1
    $\begingroup$ @user170039: We cannot yet prove "there doesn't exist any natural number between $0$ and $0++$" since you have not yet defined the concept "between." Which definition are you using? $\endgroup$ – Rory Daulton Jan 2 '15 at 15:21
  • 1
    $\begingroup$ The induction step can be done much more easily. The statement to be proved, given the induction hypothesis, is "$n++=0$ or there exists $b$ such that $b++=n++$." To prove it, ignore the induction hypothesis (because we don't need it) and notice that $b=n$ works. $\endgroup$ – Andreas Blass Jan 2 '15 at 15:21
1
$\begingroup$

Define the predicate $P(n)$ to be $n=0$ or $\exists m: S(m) = n$, where $S$ denotes the successor function (which you write $++$). Now show this by induction.

$\endgroup$

Your Answer

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