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$

Tao Analysis I - 3.5.12 (i)

Exercise 3.5.12 (i)

This exercise will establish a rigorous version of Proposition 2.1.16 that avoids circularity (in particular, avoiding the use of any object that required Proposition 2.1.16 to construct).

(i) Let $X$ be a set, let $f : \mathbb{N} \times X \to X$ be a function, and let $c$ be an element of $X$. Show that there exists a function $a : X \to X$ such that

$$a(0) = c$$

and

$$a(n++) = f(n, a(n)) \text{ for all } n \in \mathbb{N}$$

and furthermore that this function is unique. (Hint: first show inductively, by a modification of the proof of Lemma 3.5.11, that for every natural number $N \in \mathbb{N}$, there exists a unique function $a_N:\{n \in \mathbb{N}:n \leq N\} \to X$ such that $a_N(0)=c$ and $a_N(n++)= f(n,a_N(n))$ for all $n \in \mathbb{N}$ such that $n < N$.)

Discussion

I found this exercise tricky because it needs clarity on what we need to do and show. This answer on math stack exchange is helpful on proof strategy (link).

It is also worth pondering on the point of the exercise. It shows that some recursively defined functions can be valid functions. Without proof we can't assume a function defined in terms of itself is a valid function. 

Exploration

To clarify the objects we're dealing with let's write out some examples.

For $N=0$, we have $a_N$ as

$$a_0 : \{0\} \to X \quad \text{ where } \quad a_0(0) = c$$

Note that $a_0$ is a function, defined over the domain $\{0\}$, the subscript zero is not a parameter or input to that function.

Our definition of $a_N$ must conform to the two conditions:

• $a_N(0)=c$
• $a_N(n++)= f(n,a_N(n))$ for all $n \in \mathbb{N}$ such that $n < N$

Our $a_0$ meets the first condition by its own definition.

What about the second condition? The second condition is vacuously true because there are no $n \in \mathbb{N}$ such that $n < N=0$.

For $N=1$, we have $a_N$ as

$$a_1 : \{0, 1\} \to X \quad \text{ where } \quad \begin{cases}a_1(0) &= c \\ \\ a_1(1) &= f(0, a_1(0)) \\ & = f(0, a_0(0)) \end{cases}$$

Here $a_1(0)$ is trivially defined to be $c$, and $a_1(1)$ maps to a unique element of $X$ because $f$ is given as a well-defined function. Thus $a_1$ is also a well-defined function.

For $N=2$, we have $a_N$ as

$$a_2 : \{0, 1,2\} \to X \quad \text{ where } \quad \begin{cases}a_2(0) &= c \\ \\ a_2(1) &= f(0, a_2(0)) \\ & = f(0, a_1(0))  \\ \\ a_2(2) &= f(1, a_2(1)) \\ & = f(1, a_1(1)) \end{cases}$$

Note how we choose to define $a_1(0)=a_0(0)=c$, and $a_2(1)=a_1(1)$ , and in general

$$a_N(n)=a_{N-1}(n)$$

because we want each $a_N$ to be equal to all previous $a_M$ over their shared domain $\{0, \ldots, M\}$, where $M < N, n \leq N$.

So in general we have $a_N$ as

$$a_N : \{0, \ldots, N\} \to X \quad \text{ where } \quad \begin{cases}a_N(0) &= c \\ \\ a_N(n++) &= f(n, a_N(n)) \\ & = f(n, a_{N-1}(n)) \end{cases}$$

where $n < N$.

On the question of uniqueness, each $a_N$ is unique if $f$ is unique, which it is because we are told it is a well-defined function.

Solution

To show that for every natural number $N \in \mathbb{N}$ there exists a unique function $a_N$ as defined in the question, we will use induction on $N$. 

Consider the statement $P(N):$ there is a unique function $a_N:\{n \in \mathbb{N}:n \leq N\} \to X$ which meets the two conditions:

• $a_N(0)=c$
• $a_N(n++)= f(n,a_N(n))$ for all $n \in \mathbb{N}$ such that $n < N$

Base case P(0): We can define a function $a_0 : \{0\} \to X$ where $a_0(0) = c$.

This meets the first condition by definition, and the second condition is vacuously true because there is no $n \in \mathbb{N}$ such that $n<N=0$.

This $a_0:\{0\}\to X$ is also unique. If there were another function $b_0:\{0\}\to X$ which met the same conditions, it would mean $b_0(0)=c$. Since they map every element of the domain, in this case $\{0\}$, to the same $c \in X$, the two functions are equal.

Inductive Hypothesis P(N): We will assume the function $a_N:\{0, \ldots, N\} \to X$ exists, meets the two conditions, and is unique.

Inductive Step P(N++): We need to show $a_{N+1}$ exists, meets the two conditions, and is unique. Let's define it as follows:

$$a_{N+1} : \{0, \ldots, N+1\} \to X \quad \text{ where } \quad \begin{cases}a_{N+1}(0) &= c \\ \\ a_{N+1}(n++) &= f(n, a_{N++}(n)) \\ & = f(n, a_{N}(n)) \end{cases}$$

where $n < N+1$.

By its definition it meets the first condition, $a_{N+1}(0)=c$. The second condition is met because we chose to define $a_{N}$ to equal $a_{N-1}$ over their shared domain $\{0, \ldots, N-1\}$, which gives us $f(n, a_{N++}(n)) = f(n, a_{N}(n))$, which in turn means $a_{N+1}$ exists.

The inductive hypothesis tells us $a_N$ exists and is unique. This means $f(n, a_{N}(n))$ is unique because $f$ is a well-defined function. So if $f(n, a_{N}(n))$  exists and is unique, we have shown $a_{N+1}$ exists and is unique.

Thus, by induction, a unique $a_N$ exists for all $N \in \mathbb{N}$. 

This means there exists a function $a : X \to X$ such that

$$a(0) = c$$

and

$$a(n++) = f(n, a(n)) \text{ for all } n \in \mathbb{N}$$

and furthermore that this function is unique. $\square$

Tao Analysis I 3.5.11

Exercise 3.5.11

Show that Axiom 3.11 can in fact be deduced from Lemma 3.4.10 and the other axioms of set theory, and thus Lemma 3.4.10 can be used as an alternate formulation of the power set axiom. (Hint: for any two sets $X$ and $Y$ , use Lemma 3.4.10 and the axiom of specification to construct the set of all subsets of $X \times Y$ which obey the vertical line test. Then use Exercise 3.5.10 and the axiom of replacement.)

Let's remind ourselves of Axiom 3.11

Axiom 3.11 (Power set axiom). Let $X$ and $Y$ be sets.Then there exists a set, denoted $Y^X$, which consists of all the functions from $X$ to $Y$, thus

$$f \in Y^X \iff f: X \to Y$$

And also remind ourselves of Lemma 3.4.10

Lemma 3.4.10. Let $X$ be a set. Then the set $\{Y: Y \subseteq X\}$ is a set. That is to say, there exists a set $Z$ such that $Y \in Z \iff Y \subseteq X$ for all objects $Y$.

Discussion

Interestingly, most people in my experience, think of the "power set axiom" as that described in Lemma 3.4.10 and not the formulation in Axion 3.11.

Solution

For any two sets $X$ and $Y$ we can form the cartesian product, $X \times Y$ as per Definition 3.5.4.

Now we apply Lemma 3.4.10 to $X \times Y$ to form the set of all subsets of $X \times Y$, which we can call $P(X \times Y)$.

Not every set in $P(X \times Y)$ will obey the vertical line test, so we can use the axiom of specification to filter out those that do, to form a set $Z$

$$Z = \{G \in P(X \times Y): G \text{ obeys the vertical line test}\}$$

The elements $G$ of $Z$ are all the graphs from $X \to Y$ which obey the vertical line test.

We can use the axiom of replacement on $Z$ to replace each element $G$ with an ordered triple $(X, Y, G)$, which we can do because for each $G$ there is a unique $(X, Y, G)$. 

This gives us a set of all the ordered triples $(X, Y, G)$ where $G$ is a graph from $X$ to $Y$ which obeys the vertical line test. Thus, by exercise 3.5.10 part (iii), this is a set of all the functions from $X$ to $Y$. $\square$

Tao Analysis I - 3.5.10

Exercise 3.5.10

If $f:X \to Y$ is a function, define the graph of $f$ to be the subset of $X \times Y$ defined by $\{(x, f(x)) : x \in X\}$.

(i) Show that two functions $f:X \to Y$, $\tilde{f}:X \to Y$ are equal if and only if they have the same graph.

(ii) Conversely, if $G$ is any subset of $X \times Y$ with the property that for each $x \in X$, the set $\{ y \in Y : (x,y) \in G \}$ has exactly one element ($G$ obeys the vertical line test), show that there is exactly one function $f:X \to Y$ whose graph is equal to $G$.

(iii) Suppose we define a function $f$ to be an ordered triple $f = (X, Y, G)$, where $X$, $Y$ are sets, and $G$ is a subset of $X \times Y$ that obeys the vertical line test. We then define the domain of such a triple to be $X$, the codomain to be $Y$, and for every $x \in X$, we define $f(x)$ to be the unique $y \in Y$ such that $(x,y) \in G$. Show that this definition is compatible with Definition 3.3.1 in the sense that every choice of domain $X$, codomain $Y$, and property $P(x,y)$ obeying the vertical line test produces a function as defined here that obeys all the properties required of it in that definition, and is also similarly compatible with Definition 3.3.8.

Exploration

It is worth thinking a little about what the graph is and isn't. The graph is all the mappings from $x \in X$ to $f(x) \in Y$. It is an important and very informative part of the definition of a function, alongside specifying the domain and co-domain. A graph on its own is not technically the same as a function.

Part (i)

We need to show the following two statements:

• Two functions are equal $\implies$ they have the same graph.
• Two functions with the same graph $\implies$ they are equal.

Let's start with the first statement. Consider two functions $f_1: X \to Y$ and $f_2: X \to Y$. If these two functions are equal, they have the same domain, same co-domain and the same mapping between the two. This last requirement is $f_1(x)=f_2(x)$ for every $x \in X$.

The graph of $f_1$ is $\{(x, f_1(x)) : x \in X\}$.

The graph of $f_2$ is $\{(x, f_2(x)) : x \in X\}$. 

Since the two functions are the same, we have $f_1(x)=f_2(x)$ for all $x \in X$, and so the graphs of $f_1$ and $f_2$ are the same.

Let's now consider the second statement. If we have two functions $f_1:X \to Y$ and $f_2:X \to Y$ with the same graph, we have:

$$\{(x, f_1(x)) : x \in X\} =  \{(x, f_2(x)) : x \in X\} $$

This means the two functions map each $x \in X$ to the same element of the co-domain, that is, $f_1(x)=f_2(x)$ for all $x \in X$. We are given that the two function share the same domain, $X$, and also the same co-domain, $Y$. Together, this allows us to say the two functions are equal. 

Having shown both statements, we have proven that two functions $f:X \to Y$, $\tilde{f}:X \to Y$ are equal if and only if they have the same graph. $\square$

Part (ii)

Let's first show the existence of $f:X \to Y$. We can define a function $f$ with the following properties:

• it has a domain $X$
• it has a co-domain $Y$
• it maps each $x \in X$ to a unique $y \in Y$ as $f(x) = y$

We need to show that the mapping is unique, that is, for every $x \in X$ there is only one $y \in Y$, the vertical line test. We are given that for each $x \in X$ the set $\{ y \in Y : (x,y) \in G \}$ has exactly one element, which is equivalent to the vertical line test.

Thus the function $f(x)=y$ exists, and has a graph $\{(x, f(x)): x \in X\}$

Now let's show the function $f:X \to Y$ is unique. Consider two functions $f_1:X \to Y$ and $f_2:X \to Y$ which meet the given criteria, that is, both have a graph equal to $G \subseteq X \times Y$. We have shown in part (i) that two functions which the same graph are equal. Therefore $f_1=f_2$. 

We have shown there is exactly one function $f:X \to Y$ whose graph is equal to $G$. $\square$

Part (iii)

Let's remind ourselves of Definition 3.3.1:

Definition 3.3.1 (Functions). Let $X$, $Y$ be sets, and let $P(x,y)$ be a property pertaining to an object $x \in X$ and an object $y \in Y$, such that for every $x \in X$, there is exactly one $y \in Y$ for which $P(x,y)$ is true (vertical line test). Then we define the function $f: X \to Y$ defined by $P$ on the domain $X$ and codomain $Y$ to be the object, which, given any input $x \in X$, assigns an output $f(x) \in Y$, defined to be the unique object $f(x) \in Y$ for which $P(x,f(x))$ is true. Thus, for any $x \in X$ and $y \in Y$,

$$y = f(x) \iff P(x,y) \text{ is true}$$

Let's also remind ourselves of Definition 3.3.8:

Definition 3.3.8 (Equality of functions). Two functions $f"X \to Y$, $g:X' 'to Y'$ are said to be equal if their domains and codomains agree, and furthermore that $f(x)=g(x)$ for all $x \in X$. 

Let's be clear about what is required of us. We need to show that:

• A function defined with a domain $X$, codomain $Y$ and property $P(x,y)$ as per Definition 3.3.1 produces a function as defined by the ordered triple $(X, Y, G)$. 
• Such a function defined by the ordered triple $(X, Y, G)$ obeys the properties as required by Definition 3.3.1 and 3.3.8.

Let's consider the first objective.

For a given domain $X$ and codomain $Y$, we can form a unique ordered pair $(X, Y)$. Now a function, as per Definition 3.3.1, has a property $P(x,y)$ which for any $x \in X$ is true for exactly one $y \in Y$ (vertical line test). Thus we can form a set $G \subseteq X \times Y$ such that $G$ obeys the vertical line test. To do this we can use the Axiom of Replacement on the set $X$ and replace each $x$ with the ordered pair $(x,y)$ such that $P(x,y)$ is true, which we know is only true for one $y$ for each $x$. Then we can form an ordered triple $(X, Y, G)$ which is unique to the domain $X$, codomain $Y$ and property $P(x,y)$.

Let's now consider the second objective.

The properties of Definition 3.3.1 are met by virtue of how we constructed $(X, Y, G)$. For example, we know $G$ obeys the vertical line test because it is constructed using $P(x,y)$ which by definition must obey the vertical line test.

Definition 3.3.8 states that two functions are the same if they have the same domain, codomain and map elements from the domain to the codomain in the same way. If we have two functions $(X, Y, G)$ and $(X', Y', G')$, these ordered $n$-tuples are only equal if $X=X'$, $Y=Y'$ and $G=G'$. That is, the domains are the same,  the codomains are the same, and the. graphs are the same. We have already shown in part (i) that equal graphs implies equal functions.