Proof of existence of unique successor to a positive number

Question

I am studying Terence Tao's Analysis I, 3rd ed., on my own.

I am trying to prove the following lemma:

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

Relevant definitions:

• A positive number is a natural number ($\mathbb{N} = \{0, 1, 2, \dots\}$) that is not equal to $0$.
• $b\mathrm{++}$ denotes the successor of $b$, for $b \in \mathbb{N}$.

Axioms related to natural numbers:

1. $0 \in \mathbb{N}$
2. If $n \in \mathbb{N}$, then $n\mathrm{++} \in \mathbb{N}$
3. We define $1:= 0\mathrm{++}$, $2:= (0\mathrm{++})\mathrm{++})$, etc.
4. For each $n \in \mathbb{N}$, $n\mathrm{++} \neq 0$.
5. If $n\mathrm{++} = m\mathrm{++}$, then $n = m$.
6. Let $P(n)$ be a property regarding $n \in \mathbb{N}$. Then suppose both (a) $P(0)$ is true and (b) $P(n)$ is true implies that $P(n\mathrm{++})$ is true for each $n\in \mathbb{N}$. Then $P(n)$ is true for each $n \in \mathbb{N}$.

Please let me know if more information is needed.

---

I'm trying to see if there's anything wrong with my proof below of the Lemma for existence. In particular, I'm confused by the answer here.

Proof. For $a = 0$, the statement is vacuously true.

Suppose for some $k$ positive that there exists a $b \in \mathbb{N}$ such that $b\mathrm{++} = k$. Then, it follows that $(b\mathrm{++})\mathrm{++} = k\mathrm{++}$. Since $b \in \mathbb{N}$, it follows that $c = b\mathrm{++} \in \mathbb{N}$ by an axiom. Hence, there exists a $c \in \mathbb{N}$ such that $c\mathrm{++} = k\mathrm{++}$.

Answer 1

Let $P(a)$ be the claim $$P(a): \forall a \text{ positive } \exists b \in \mathbb{N} \text{ with } b\mathrm{++} = a\text{.}$$ Consider $P(0)$. By definition $0$ is not positive, so the proof is vacuously true.

Suppose $P(0)$ is true. By definition, $1 = 0\mathrm{++}$, and $0 \in \mathbb{N}$, so there is a $b \in \mathbb{N}$ such that $b\mathrm{++} = 1$. Hence $P(1)$ is true.

Now suppose $P(k)$ is true for for some $k$ positive. Then there exists a $b \in \mathbb{N}$ such that $b\mathrm{++} = k$. Then, it follows that $(b\mathrm{++})\mathrm{++} = k\mathrm{++}$. Since $b \in \mathbb{N}$, it follows that $c = b\mathrm{++} \in \mathbb{N}$ by an axiom. Hence, there exists a $c \in \mathbb{N}$ such that $c\mathrm{++} = k\mathrm{++}$.

By induction, existence holds.

Answer 2

We can tidy it up as thus: to prove each natural $n$ is either $0$ or a successor, we note the base step is trivial and the inductive step works because, regardless of the properties of $k$, $k++$ is a successor.

Answer 3

Axiom $5$ says that if there is a $b$ so that $b++ = k$ then $b$ is unique. (If $b++ = k$ and $c++ = k$ then $b++ =c++$ and $b = c$).

SInce you base case was not for a positive natural number but a natural number that if it were positive (but wasn't) the prop would be true, you can't assume that such a natural number $k$ exists in your induction step.

But you can fix it.

In fact... it's trivial.

If $k$ is a natural number (whether positive or not) then if we let $b =k$ then $b++ =k++$ because... $k++ = k++$ (duh!). And this is true whether $k++$ is positive or not. (Although it's not possible for $k++$ to not be positive.)

And by axiom 5 $b=k$ is unique as $b++ =k++ \implies b=k$.

.....

This is actually kind of weird because in doing the induction step we don't need the prior case at all!

=========

Recap:

Base case $k = 0$. If $0$ is positive (it isn't) then our proposition about positive numbers, no matter what it is, vacuuously holds.

Induction step: If $k$ is a natural number and it doesn't matter at all whether our proposition holds for $k$ or not,

then there exists a natural $b = k$ so that $b++ = (k++)$. And by Axiom 5 $b$ is unique.

So $P(k++)$ is always true. (And we don't need $P(k) \implies P(k++)$; we have $P(k++)$ is true. Period. Always.)

And although that feels very flimsy it is actually valid induction.

======

In hindsight I think the point is Principal of induction is (almost) the principal that we can get to all the naturals by counting but even more fundimental.

$k++$ is a successor to $k$ so every natural number is either $0$ or a successor to a natural number.

Base case: True for $0$.

Induction step: Whether true or not for $k$ is true for $k++$ (which is the successor of $k$).

So true for all naturals.

And by Axiom 5. If $b++ = k++$ then $b=k$ and this is number to which the natural number (if it is not $0$) is unique.

The more I repeat it the sounder it feels.

=====

.... Okay.... this is the type of result I like to call "almost an axiom". That $0$ is the base number and that every other natural is a successor that can be "reached" from zero (if we could define what "reach" means) should almost be an axiom. From that we can derive that induction would have to be true, but then we realize that induction actually IS the definition of "can be reached" that we wanted so... induction is the axiom and every natural number is a successor that can be reached from $0$ is a basic proposition.

Induction is merely a formal statement that every natural number can be "reached" by taking a successive string of successors.