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$
  • $\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$
  • $\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$ – user 170039 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$ – user 170039 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

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