Tao Analysis I - 3.6.3

Exercise 3.6.3

Let $n$ be a natural number, and let $f:\{i \leq i \leq n\} \to \mathbb{N}$ be a function. Show that there exists a natural number $M$ such that $f(i) \leq M$ for all $1 \leq i \leq n$. (Hint: induct on $n$. You may also want to peel at Lemma 5.1.14.). Thus finite subsets of the natural numbers are bounded. Use this to give an alternate proof of Theorem 3.6.12 that does not use Lemma 3.6.9.

Let's remind ourselves of Theorem 3.6.12:

The set of natural numbers $\mathbb{N}$ is infinite.

Solution Part 1

We will use induction on $n$. Consider the statement $P(n)$,

$$P(n): \text{ there exists an } M \in \mathbb{N} \text{ such that for all } i \in \{1 \ldots n\} \text{ we have } f(i) \leq M$$

Consider the base case $P(0)$, which states there exists a natural number $M$ such that $f(i) \leq M$ for $i \in \emptyset$. This is vacuously true.

To avoid any doubt, let's consider $P(1)$ as a base case. It states there exists a natural number $M$ such that $f(i) \leq M$ for $i \in \{1\}$. Since $f$ maps to $\mathbb{N}$, $f(i)$ is a (finite) natural number. We can choose $M=f(1)$, thus identifying an $M$ which satisfies the statement, making $P(1)$ true.

Now let's assume $P(n)$ is true as the inductive hypothesis. We need to show $P(n++)$ is true. Consider $f(n++)$. Again, since $f$ maps to $\mathbb{N}$, we have $f(n++)$ as a finite natural number. We can select $X=f(n++)$ so that $f(n++) \leq X$. By the inductive hypothesis, we know there exists a natural number $Y$ such that $f(i) \leq Y$ for $1 \leq i \leq n$. We can choose the larger of the two, $M=\max(X,Y)$, so that $f(i) \leq M$ for $1 \leq i \leq (n++)$. Thus $P(n++)$ is true.

By induction we have shown there exists a natural number $M$ such that $f(i) \leq M$ for all $1 \leq i \leq n$. That is, finite subsets of the natural numbers, here $\{f(i)\}$, are bounded. $\square$

Solution Part 2

Let's write out what we have just shown: If a subset of the natural numbers $\mathbb{N}$ is finite, then it is bounded.

The contrapositive is: If a subset of the natural numbers is not bounded, then it is not finite.

Consider the set of natural numbers $\mathbb{N}$, which is a subset of $\mathbb{N}$. Let's assume it is finite. That means it must be bounded, as we have shown above. Let's say $M$ is the largest element in that set. This $M$ is a natural number, and by the Peano axioms, has a successor $M+1$ which is also a natural number in $\mathbb{N}$. Therefore $M$ can not be the largest element of the set. We have shown that $\mathbb{N}$ is not bounded. By the above contrapositive statement, it is therefore not finite. $\square$

Tao Analysis I - 3.6.2

Exercise 3.6.2

Show that a set $X$ has cardinality $0$ if and only if $X$ is the empty set.

Let's remind ourselves of the definitions of cardinality.

Def 3.6.1 (Equal cardinality) We say that two sets $X$ and $Y$ have equal cardinality iff there exists a bijection $f : X \to Y$ from $X$ to $Y$.

Def 3.6.5 Let $n$ be a natural number. A set $X$ is said to have cardinality $n$, iff it has equal cardinality with $\{i ∈ N : 1 ≤ i ≤ n\}$. We also say that $X$ has $n$ elements iff it has cardinality $n$.

We need to show both of the following:

• If a set is the empty set then it has cardinality 0.
• If a set has cardinality $0$, it must be the empty set.

Show $X = \emptyset \implies \#X = 0$

We assume $X=\emptyset$. The only set it has a bijection with is the empty set (link). This existence of a bijection is sufficient for Def 3.6.1. By Def 3.6.5 this cardinality is $0$, because the empty set has a bijection with the set $\{i ∈ N : 1 ≤ i ≤ n\}$ with $n=0$.

Thus we have shown $X = \emptyset \implies \#X = 0$.

Show $\#X = 0 \implies X = \emptyset$

If a set $X$ has cardinality $0$, then by Def 3.6.5 it has cardinality equal to to the set $\{i ∈ N : 1 ≤ i ≤ n\}$ where $n=0$. This is the empty set.

Thus we have shown $\#X = 0 \implies X = \emptyset$.

By showing both statements, we have shown that a set $X$ has cardinality $0$ if and only if $X$ is the empty set. $\square$

Tao Analysis I - 3.6.1

Exercise 3.6.1

Prove Proposition 3.6.4. 

Proposition 3.6.4 Let $X$, $Y$, $Z$ be sets. 

• Then $X$ has equal cardinality with $X$ . 
• If $X$ has equal cardinality with $Y$, then $Y$ has equal cardinality with $X$.
• If $X$ has equal cardinality with $Y$ and $Y$ has equal cardinality with $Z$, then $X$ has equal cardinality with $Z$.

Discussion

The first part of the proposition says that cardinality is symmetric. The second says it is reflective. The third says it is transitive. These are the requirements of an equivalence relation.

We will use properties of bijective functions that we have previously established - that they are symmetric, reflexive and transitive (link).

Reflexive

Let's start with Definition 3.6.1, which says two sets $X$ and $Y$ have equal cardinality iff there exists a bijection $f:X \to Y$ from $X$ to $Y$.

We already know that bijections are reflexive, and so $\#X=\#X$. $\square$

Symmetric

We know bijections are symmetric, and so if $\#X=\#Y \implies \#Y=\#X$. $\square$

Transitive

We know bijections are transitive. That is, the composition of two bijections is also a bijection.  And so $(\#X=\#Y) \land (\#Y=\#Z) \implies \#X=\#Z$. $\square$

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$