Tao Analysis I - 2.2.2

Exercise 2.2.2

Prove Lemma 2.2.10. Let $a$ be a positive number. Then there exists exactly one natural number $b$ such that $b++ = a$.

We are required to do two things

• existence - show that there is a solution
• uniqueness - show that there is only one solution
  

Again, the challenge is to get past the obviousness of the statement and try to dispassionately show it is true using the axioms.

Axiom 2.2 says that if $n$ is a natural number, then $n++$ is also a natural number. We should take care to note this is a one-way implication. It doesn't say that if $b++$ is a natural number then so is $b$. Note also that in Tao's book natural numbers include $0$. 

Existence

The book encourages us to use induction.

Let the proposal $P(a)$ state that if $a$ is a positive number, then there exists a natural number $b$ such that $b++ = a$.  That is,

$$ a \in \mathbb{N^+} \implies \exists b \in \mathbb{N} : b++ = a $$

Let's consider the base case $P(1)$. The base case is not $P(0)$ because $a$ must be a positive number which is never $0$, as per Definition 2.2.7.

$$ 1 \in \mathbb{N^+} \implies \exists b \in \mathbb{N} : b++ = 1 $$

Is this true? It is because 1 is indeed a positive number, and there does exist a natural number $b$ such that $b++ = 1$. That $b$ is $0$.

The inductive hypothesis is that $P(a)$ is true,

$$ a \in \mathbb{N^+} \implies \exists b \in \mathbb{N} : b++ = a $$

We need to show that $P(a++)$ is true. I've used $c$ to avoid mixing up variables,

$$ (a++) \in \mathbb{N^+} \implies \exists c \in \mathbb{N} : c++ = (a++) $$

This says that if $(a++)$ is a positive number, then there exists a natural number $c$ such that $c++ = (a++)$.  Is it true?

Well, $(a++)$ is indeed a positive number, because it is not zero, by Axiom 2.3. 

Is there a $c++$ that is $(a++)$? If we set $c=a$ then because $a$ is a natural number, so is $c$, and so is its successor $c++$ by Axiom 2.2.

Note that we didn't actually use $P(a)$ to show $P(a++)$ is true. We showed $P(a++)$ is true directly. This doesn't invalidate the structure of a proof by induction. Strictly speaking, if the consequent of an implication is always true, the implication itself is true.

Summarising, we have shown:

• the base case $P(1)$ is true
• if $P(a)$ is true then $P(a++)$ is true
  

So by induction, the proposal P(a) is true for all positive numbers $a \in \mathbb{N^+}$. 

But we're not finished yet because the proposal $P(a)$ only says that a $b$ exists, not that it is unique.

Uniqueness

Imagine that there are two disctinct natural numbers $b$ and $c$ that satisfy the proposal.

$$\begin{align} b++ &= a \\ c++ &= a \end{align}$$

Axiom 2.4 says different natural numbers have different successors. Here $a$ and $b$ have the same successor, so they must not be different. That is, $a$ must be $b$. So $b$ in the proposal is unique.

Having shown existence and uniqueness, the Lemma 2.2.10 is proven. $\square$