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$