Tao Analysis I - 3.6.6

Exercise 3.6.6

Let $A$, $B$, $C$ be sets. Show that the sets $(A^B)^C$ and $A^{B \times C}$ have equal cardinality by constructing an explicit bijection between the two sets. Conclude that $(a^b)^c = a^{bc}$ for any natural numbers $a$, $b$, $c$. Use a similar argument to also conclude $a^b \times a^c = a^{b+c}$ .

This stack exchange post helped with this exercise (link), as well as this solution (link).

Let's start with $A^B$. This is a set of all the functions from $B$ to $A$. Let's denote an element of this set $f$. 

$$f \in A^B \text{ where } f:B \to A$$

So $f(b)=a$ where $a \in A$ and $b \in B$.

Now $(A^B)^C$ is the set of all functions from $C$ to $A^B$. Let's denote an element of this set $g$. 

$$g \in (A^B)^C \text{ where } g:C \to A^B$$

So $g(c) = f_c$ where $c \in C$ and $f_c \in A^B$.

Let's now consider $A^{B \times C}$. This is a set of all the functions from $B \times C$ to $A$. Let's denote an element of this set $h$. 

$$h \in A^{B \times C} \text{ where } h:{B \times C} \to A$$

So $h( (b,c) ) = a$ where $a \in A$, and $(b,c)$ is an ordered pair with $b \in B, c \in C$.

We need a bijection, let's call it $\Theta$ which maps $(A^B)^C$ to $A^{B \times C}$. That is

$$\Theta (g) = h$$

Noting that $g$ takes one parameter $c$, and $h$ takes two $(b,c)$, helps suggest a possible mapping.

$$\Theta ( g ) = g(c)(b) := h(b,c)$$

UNSURE

That is, $\Theta$ maps $g(c) \in (A^B)^C$ to $g(c)(b) \in A^{B \times C}$ which we define to be $h(b,c) \in A$.

We now need to show that $\Theta$, as we have defined it, is indeed a bijection. 

Let's show $\Theta$ is surjective. For every $h(b, c) := g(c)(b) \in A^{B \times C}$ there exists a $g(c) \in (A^B)^C$ such that $\Theta( g(c)) = g(c)(b) = h(b, c)$.  UNSURE

Let's now show $\Theta$ is injective. TODO

Tao Analysis I - 3.6.5

Exercise 3.6.5

Let $A$ and $B$ be sets. Show that $A \times B$ and $B \times A$ have equal cardinality by constructing an explicit bijection between the two sets. Then use Proposition 3.6.14 to conclude an alternate proof of Lemma 2.3.2.

Proposition 3.6.14 are the six proposals regarding cardinal arithmetic we saw in the previous exercise.

Let's remind ourselves of Lemma 2.3.2 (Multiplication is commutative): Let $n, m$ be natural numbers. Then $n \times m = m \times n$.

Note that $A$ and $B$ are not specified to be finite. 

A possible bijection $f$ between $A \times B$ and $B \times A$ is one which simply swaps the components of the ordered pair

$$f((a,b)) = (b,a) \text{ for } (a,b) \in A \times B$$

This function is surjective because for every $(b,a) \in B \times A$ there exists an $(a,b) \in A \times B$ such that $f((a,b))=(b,a)$. The function is injective because $f((a,b))=f((a',b'))=(b,a)$ implies $(a,b)=(a',b')$.

Since a bijection exists between $A \times B$ and $B \times A$, the two sets have the same cardinality (even if they are not finite). $\square$

Now, because there is a bijection between $A \times B$ and $B \times A$, the two sets have the same cardinality. 

By Proposition 3.6.14 (e), the cardinality of the set $A \times B$ is $\#A \times \#B$. Similarly the cardinality of the set $B \times A$ is $\#B \times \#A$. Here $\#A$ and $\#B$ are natural numbers, and so requires the sets $A$ and $B$ to be finite.

If we name $m=\#A$ and $n=\#B$, the equality of cardinality gives us $m \times n = n \times m$, proving Lemma 2.3.2. $\square$

Tao Analysis I - 3.6.4

Exercise 3.6.4

Prove Proposition 3.6.14.

Proposition 3.6.14 contains six proposals so let's look at each as we develop solutions to each.

(a) Let $X$ be a finite set, and let $x$ be an object which is not an element of $X$. Then $X \cup \{x\}$ is finite and $\#(X \cup \{x\}) = \#(X) + 1$.

The finite set $X$ has a cardinality of $\#X$, which by Definition 3.6.10 is a natural number. This also means, by Definition 3.6.5, there is a bijection $g:X \to \{1, \ldots, \#X\}$.

Since $x$ is not in $X$, the bijection $g$ doesn't map $x$ to an element of $\{1, \ldots, \#X\}$. We can define a new bijection $h$ which maps just as $g$ for $x' \in X$, and maps $x$ to $\#X +1$, since $\#X+1$ is not in $\{1, \ldots, \#X\}$.

This $h$ is a bijection from $X \cup \{x\}$ to $\{1, \ldots, \#X+1\}$. This means $X \cup \{x\}$ has a cardinality $\#X +1$, and because this is a natural number (successor to $\#X$), it is also a finite set. $\square$

(b) Let $X$ and $Y$ be finite sets. Then $X \cup Y$ is finite and $\#(X \cup Y) \leq \#(X) + \#(Y)$. If in addition $X$ and $Y$ are disjoint (i.e., $X \cap Y = \emptyset$), then $\#(X \cup Y) = \#(X) + \#(Y)$.

There are two cases to consider, $X$ and $Y$ are disjoint, and $X$ and $Y$ are not disjoint.

Let's consider the disjoint case first. 

Since both sets are finite, their cardinalities $\#X$ and $\#Y$ are natural numbers (Definition 3.6.10). This means there exist bijections (Definition 3.6.5) $f: X \to \{1, \ldots, \#X\}$ and $g: Y \to \{\#X+1, \ldots, \#X+\#Y\}$. Since the two sets are disjoint, they share no common elements, and so we can define a new bijection $h: X \cup Y \to \{1, \ldots, \#X+\#Y\}$. Thus, if $X$ and $Y$ are disjoint, then $\#(X+Y)=\#X+\#Y$. $\square$

Now consider the non-disjoint case.

Since both sets are finite, their cardinalities $\#X$ and $\#Y$ are natural numbers. This means there exist bijections $f: X \to \{1, \ldots, \#X\}$ and $g: Y \to \{\#X+1, \ldots, \#X+\#Y\}$. 

Here $X$ and $Y$ do share at least one common element. That means there exists an $x \in X$ that is also in $Y$. Therefore, a bijection $h: X \cup Y \to \{1, \ldots, m\}$ requires $m < \#X + \#Y$.

To see this more clearly, consider $Y'=Y \setminus X$, the set $Y$ without any elements that are also in $X$. Therefore the cardinality of $Y'$ is $\#Y' < \#Y$. We have $(X \cup Y) = (X \cup Y')$ and so $\#(X \cup Y) = \#X + \#Y' < \#X +\#Y$

Thus, in the general case, $\#(X \cup Y) \leq \#(X) + \#(Y)$. $\square$

(c) Let $X$ be a finite set, and let $Y$ be a subset of $X$. Then $Y$ is finite, and $\#(Y) ≤ \#(X)$. If in addition $Y \neq X$ (i.e., $Y$ is a proper subset of $X$), then we have $\#(Y) < \#(X)$.

$X$ is a finite set so it has a natural number cardinality $\#X$, and there is a bijection $f: X \to \{1, \ldots, \#X\}$. 

If $Y$ is a subset of $X$, then it is finite too. We can define a function $g$ with domain $Y \subseteq X$  and which maps as $g(y) = f(y)$ . Since $f$ is a bijection, so is $g$. 

This $g$ is bijective with $g': Y \to \{1, \ldots, \#Y\}$, where $\#Y \leq \#X$ because the domain of $g$ is some or all of $X$. That is, $\#(Y) ≤ \#(X)$. $\square$

In the case $Y$ is a proper subset of $X$, then there is at least one element of $X$ that is not in $Y$. And so the domain of $g$ is not equal to the domain of $f$. This means $g$ is bijective with $g': Y \to \{1, \ldots, \#Y\}$ where now $\#Y < \#X$ because the domain of $g$ is some but not all of $X$. That is, $\#(Y) < \#(X)$. $\square$

(d) If $X$ is a finite set, and $f:X \to Y$ is a function, then $f(X)$ is a finite set with $\#( f (X)) \leq \#(X)$. One has equality $\#( f (X)) = \#(X)$ if and only if $f$ is one-to-one.

The definition of a function $f:X \to Y$ requires it to map each element of $X$ to a single element of $Y$. Furthermore, for each element $y \in f(X)$, there exists an $x \in X$ such that $f(x)=y$. 

There are two cases: there could be a unique $x$ for each $y \in f(X)$, or there could be more than one element of $X$ that maps to $y \in f(X)$.

In the case there is a unique $x$ for each $y \in f(X)$, the function $f$ is one-to-one, a bijection, and so $\#f(X) = \#X$. $\square$

In the case there is more than one element of $X$ that map to the same $y \in f(X)$, the function $f$ is not one-to-one. In this case there is a bijection between $f(X)$ and $\{1, \ldots, m\}$, where $m < \#X$.

Thus in general, $\#f(X) \leq \#X$. $\square$

(e) Let $X$ and $Y$ be finite sets. Then Cartesian product $X \times Y$ is finite and $\#(X × Y) = \#(X) \times \#(Y)$.

Consider $X=\{x_1, x_2, \ldots, x_m\}$ where $m=\#X$, and $Y=\{y_1, y_2, \ldots, y_n\}$ where $n=\#Y$. Since both sets are finite, $m$ and $n$ are natural numbers.

The Cartesian product is the set of ordered pairs, 

$$\begin{align}X \times Y = & \{ (x_1, y_1), (x_1, y_2), \ldots , (x_1, y_n), \\  \\ &  (x_2, y_1), (x_2, y_2), \ldots , (x_2, y_n), \\  \\& \ldots  \\ \\ &   (x_m, y_1), (x_m, y_2), \ldots , (x_m, y_n) \} \end{align}$$

For each of the $m$ elements of $X$ there are $n$ elements of the form $(x_i, y_j)$ in $X \times Y$. All of these elements are unique because each element of $X$ and $Y$ is unique. 

Therefore, there are $m \times n$ elements of $X \times Y$, which is $\#X \times \#Y$. This is a natural number, and so the cartesian product is finite. $\square$

(f) Let $X$ and $Y$ be finite sets. Then the set $Y^X$ (defined in Axiom 3.11) is finite and $\#(Y^X) = \#(Y)^{\#(X)}$.

Let's remind ourselves of Axiom 3.1.1

(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$.

We'll prove this proposition by induction.

Let $P(n)$ be the statement: $\#(Y^X) = \#(Y)^{\#(X)}$ where $n=\#X$.

For the base case $n=1$, we have $X=\{x_1\}$, a singleton set. The power set $Y^X$ is the set of all functions from $X=\{x_1\}$ to $Y$. Since there is only one element of $X$, there are $\#Y$ possible functions from $X$ to $Y$. That is, $\#(Y^X) = \#Y^{\#(X)}=\#Y^1=\#Y$, and so the base case $P(1)$ is true.

Let's now assume $P(n)$ is true, and show $P(n+1)$ is true. The statement $P(n)$ is $\#(Y^X) = \#(Y)^{\#(X)}$ where $n=\#X$. 

If we extend the set $X$ with an element it doesn't currently have $x'$, we have $X'=X \cup \{x'\}$, and $\#X'=n+1$. The addition of one extra element to $X$ means that for each of the existing functions $f \in X \times Y$, there are an additional $\#Y$ new possible functions $f' \in X' \times Y$.

More specifically, each function $f \in X \times Y$ can be extended to map $x'$ to any one of $\#Y$ elements of $Y$.

Thus $\#(Y^{X'}) = \#Y \times \#Y^{\#X} = \#Y^{\#X+1}$, and so $P(n+1)$ is true.

We have shown by induction that $\#(Y^X) = \#(Y)^{\#(X)}$. $\square$

Since $X$ and $Y$ are finite, then $\#X$, $\#Y$ and $\#X+1$ are natural numbers. This means the cardinality of the power set is also a natural number, and so is finite too. $\square$

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$