# How can I prove this proposition from Peano Axioms?

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.

• 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. Jan 2, 2015 at 15:49

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

@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++$.

• Yes it would be great. How can we prove from here that there doesn't exist any natural number between $0$ and $0{++}$?
– user170039
Jan 2, 2015 at 15:07
• If $n\ne0$ why do we must have $b{++}=n$? Note that this is the problem to be proved.
– user170039
Jan 2, 2015 at 15:16
• @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? Jan 2, 2015 at 15:21
• 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. Jan 2, 2015 at 15:21
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.