Tao Analysis I - 3.5.13

Exercise 3.5.13

The purpose of this exercise is to show that there is essentially only one version of the natural number system in set theory (cf. the discussion in Remark 2.1.12). Suppose we have a set $N'$ of “alternative natural numbers”, an “alternative zero” $0'$ , and an “alternative increment operation” which takes any alternative natural number $n' \in N'$ and returns another alternative natural number $n'++' \in N'$, such that the Peano axioms (Axioms2.1-2.5) all hold with the natural numbers, zero, and increment replaced by their alternative counterparts. 

Show that there exists a bijection $f : N \to N'$ from the natural numbers to the alternative natural numbers such that $f (0) = 0'$ , and such that for any $n \in N$ and $n' \in N'$, we have $f(n)=n'$ if and only if $f(n++)=n'++'$. (Hint: use Exercise 3.5.12)

Discussion

The overall aim is to show that two number systems, $N$ and $N'$, if they both obey the same Peano Axioms, are equivalent. To do this we need to demonstrate there exists a bijection from one to the other. To show bijectivity, we need to show both injectivity and surjectivity.

Let's remind ourselves of the Peano Axioms:

• Axiom 2.1 0 is a natural number.
• Axiom 2.2 If $n$ is a natural number, then $n++$ is a natural number.
• Axiom 2.3 0 is not the successor of any natural number.
• Axiom 2.4 Different numbers have different successors.
• Axiom 2.5 Principle of mathematical induction. If $P(n)$ is true, and $P(n)$ implies $P(n++)$ then $P(n)$ is true for all natural numbers.

Solution

Exercise 3.5.12 tells us there exists a function

$$f:N \to N' \text{ where } \begin{cases} f(0) = 0' \\ \\ f(n++) = g(n, f(n)) \; , \forall n \in N \end{cases}$$

where $g:N\times N' \to N'$ is a well-defined function. Let's define $g$ as follows:

$$g(n,n') = n'++'$$

This $g$ passes the vertical line test due to Peano Axiom 2.4.

Our function $f$ is thus defined as:

$$f:N \to N' \text{ where } \begin{cases} f(0) = 0' \\ \\ f(n++) = f(n)++'  \; , \forall n \in N \end{cases}$$

Let's show $f$ is surjective by induction. We can use induction as Peano Axiom 2.5 holds for $N'$.

Consider the statement

$$S(k') : \exists k \in N \text{ such that } f(k) = k' \in N'$$

The base case $S(0)$ is true because $f$ is defined such that $f(0)=0'$.

For the inductive hypothesis, assume $S(k')$ is true. We need to show $S(k'++')$ is true. 

Consider $f(k++)$, which by definition of $f$ is $f(k++)=f(k)++'$. By the inductive hypothesis, $f(k) = k'$. This gives us $f(k++)=k'++'$, and so $S(k'++')$ is true.

By induction we have shown $f$ is surjective.

Let's show $f$ is injective by induction. We can use induction as Peano Axiom 2.5 holds for $N$.

Consider the statement

$$P(k) : f(a)=f(b) \implies a=b, \quad \text{ for } a,b \in \{0, \ldots , k\}$$

The base case $P(0)$ is true because we have a singleton domain $\{0\}$ and so $a=b$ trivially.

For the inductive hypothesis, assume $P(k)$ is true. We need to show $P(k++)$ is true.

Consider $f(k++)=f(b)$ where $b \in \{0, \ldots , k++\}$. By definition of $f$, we have

$$f(k++)=f(k)++'$$

Similarly, 

$$f(b)=f(c)++'$$

where $c++=b$. 

Therefore, $f(k)++'=f(c)++'$. By axiom 2.4, $f(k)=f(c)$, and by the inductive hypothesis $k=c$, because both $k$ and $c$ are in $\{0, \ldots, k\}$, and so $k++=b$. Thus $P(k++)$ is true.

By induction we have shown $f$ is injective.

We have shown there exists a function $f$ which is a bijection between $N$ and $N'$, thus showing two natural number systems are equivalent if they both conform to the Peano Axioms. $\square$

Finally we need to confirm that $f(n)=n' \iff f(n++)=n'++'$. We do this by proving both

• $f(n)=n' \implies f(n++)=n'++'$
• $f(n++)=n'++' \implies f(n)=n'$

Consider $f(n++)=n'++'$. By definition of $f$ we know $f(n++)=f(n)++'$. By Axiom 2.4 this means $f(n)=n'$. So $f(n++)=n'++' \implies f(n)=n'$.

Now consider $f(n)=n'$. Again by Axiom 2.4, this gives us $f(n)++'=n'++'$. By the definition of $f$, this means $f(n++)=n'++'$.

Thus, $f(n)=n' \iff f(n++)=n'++'$. $\square$