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$

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.

Tao Analysis I - 3.5.9

Exercise 3.5.9

Suppose that $I$ and $J$ are two sets, and for all $\alpha \in I$ let $A_{\alpha}$ be a set, and for all $\beta \in J$ let $B_{\beta}$ be a set. Show that

$$(\bigcup_{\alpha \in I} A_{\alpha}) \cap (\bigcup_{\beta \in J} B_{\beta}) = \bigcup_{(\alpha,\beta) \in I \times J} (A_{\alpha} \cap B_{\beta})$$

What happens if one interchanges all the union and intersection symbols here?

Solution Strategy

For this solution I wanted to develop the proof using only a chain of equivalences $\iff$, rather than the more verbose approach of proving one direction $\implies$, and the other direction $\impliedby$.

This math stack exchange answer helped clarify this approach, which is still unfamiliar to me (link). 

In addition this wikipedia article on manipulating prenex normal form is useful (link).

Solution Part One

Let's start with the LHS.

$$x \in (\bigcup_{\alpha \in I} A_{\alpha}) \cap (\bigcup_{\beta \in J} B_{\beta}) \iff x \in (\bigcup_{\alpha \in I} A_{\alpha}) \land x \in (\bigcup_{\beta \in J} B_{\beta})$$

Using the definition of the union of sets, this means both of the following are true:

• $x$ is an element of at least one $A_{\alpha}$
• $x$ is an element of at least one $B_{\beta}$

For the next step we have to take care with the use of the $\exists$ existential quantifier.

$$x \in (\bigcup_{\alpha \in I} A_{\alpha}) \cap (\bigcup_{\beta \in J} B_{\beta}) \iff (\exists \alpha\in I) \; [x \in A_{\alpha}] \land (\exists \beta\in J) \; [x \in B_{\beta}]$$

This is essentially writing out what we have written in the bullet points.

If there exists an $\alpha \in I$ and a $\beta \in J$ which meet certain conditions,  then there exists an $(\alpha, \beta) \in I \times J$ where the same conditions are met. That is,

$$\begin{align}x \in (\bigcup_{\alpha \in I} A_{\alpha}) \cap (\bigcup_{\beta \in J} B_{\beta}) & \iff (\exists \alpha\in I) \; [x \in A_{\alpha}] \land (\exists \beta\in J) \; [x \in B_{\beta}] \\ \\ & \iff (\exists (\alpha, \beta) \in I\times J ) \; [x\in A_{\alpha} \land x \in B_{\beta}] \\ \\ & \iff (\exists (\alpha, \beta) \in I\times J ) \; [x\in A_{\alpha}\cap B_{\beta}] \\ \\ & \iff x \in \bigcup_{(\alpha,\beta) \in I \times J} (A_{\alpha} \cap B_{\beta})  \end{align}$$

Thus, we have shown

$$(\bigcup_{\alpha \in I} A_{\alpha}) \cap (\bigcup_{\beta \in J} B_{\beta}) = \bigcup_{(\alpha,\beta) \in I \times J} (A_{\alpha} \cap B_{\beta}) \; \square$$

Solution Part Two

Now consider what happens if we interchange the union and intersection symbols. We have a new proposal to show:

$$(\bigcap_{\alpha \in I} A_{\alpha}) \cup (\bigcap_{\beta \in J} B_{\beta}) = \bigcap_{(\alpha,\beta) \in I \times J} (A_{\alpha} \cup B_{\beta})$$

The proof is almost the same, so we'll only write down the essence of it.

Let's start with the LHS.

$$(\bigcap_{\alpha \in I} A_{\alpha}) \cup (\bigcap_{\beta \in J} B_{\beta}) \iff x \in (\bigcap_{\alpha \in I} A_{\alpha}) \lor x \in (\bigcap_{\beta \in J} B_{\beta})$$

Using the definition of the intersection of sets, this means either or both of the following are true:

• $x$ is an element of every $A_{\alpha}$
• $x$ is an element of every $B_{\beta}$

For the next step we have to take care with the use of the $\forall$ "for all" quantifier.

$$x \in (\bigcap_{\alpha \in I} A_{\alpha}) \cup (\bigcap_{\beta \in J} B_{\beta}) \iff (\forall \alpha\in I) \; [x \in A_{\alpha}] \lor (\forall \beta\in J) \; [x \in B_{\beta}]$$

We continue in a similar manner to the above,

$$\begin{align}x \in (\bigcap_{\alpha \in I} A_{\alpha}) \cup (\bigcap_{\beta \in J} B_{\beta}) & \iff (\forall \alpha\in I) \; [x \in A_{\alpha}] \lor (\forall \beta\in J) \; [x \in B_{\beta}] \\ \\ & \iff (\forall (\alpha, \beta) \in I\times J ) \; [x\in A_{\alpha} \lor x \in B_{\beta}] \\ \\ & \iff (\forall (\alpha, \beta) \in I\times J ) \; [x\in A_{\alpha}\cup B_{\beta}] \\ \\ & \iff x \in \bigcap_{(\alpha,\beta) \in I \times J} (A_{\alpha} \cup B_{\beta})  \end{align}$$

Thus, we have shown

$$(\bigcup_{\alpha \in I} A_{\alpha}) \cup (\bigcup_{\beta \in J} B_{\beta}) = \bigcap_{(\alpha,\beta) \in I \times J} (A_{\alpha} \cup B_{\beta}) \; \square$$

Tao Analysis I - 3.5.8

Exercise 3.5.8

Let $X_1, \ldots , X_n$ be sets. Show that the Cartesian product $\prod_{i=1}^{n} X_i$ is empty if and only if at least one of the $X_i$ is empty.

Let's remind ourselves of Definition 3.5.6 for Cartesian products. 

If $(X_i)_{1 \leq i \leq n}$ is an ordered $n$-tuple of sets, we define their Cartesian product as

$$\prod_{1 \leq i \leq n} X_i := \{ (x_i)_{1 \leq i \leq n}: x_i \in X_i \text{ for all } 1 \leq i \leq n \}$$

We need to how both of the following:

• $\prod_{i=1}^{n} X_i = \emptyset \implies \exists X_i = \emptyset$
• $\exists X_i = \emptyset \implies \prod_{i=1}^{n} X_i = \emptyset$

Let's start with the second statement as it is easier to prove. If at least one $X_i$ is empty, let's call it $X_j$ then there is no $x_j= \in X_i$. This means the $n-$tuple $(x_i)_{1 \leq i \leq n}$ can't be formed with $n$ components. Thus the cartesian product, a set, is empty.

Now let's consider the first statement. The cartesian product is empty only if the $n$-tuples can't be formed with $n$ components. This only happens if one of the $X_i$ is empty. 

By proving both statements, we have shown the Cartesian product $\prod_{i=1}^{n} X_i$ is empty if and only if at least one of the $X_i$ is empty. $\square$

Tao Analysis I - 3.5.7

Exercise 3.5.7

Let $X$, $Y$ be sets, and let $\pi_{X \times Y \to X}:X \times Y \to X$ and $\pi_{X \times Y \to Y}:X \times Y \to Y$ be the maps $\pi_{X \times Y \to X} (x, y) := x$ and $\pi_{X \times Y \to Y}(x, y) := y$; these maps are known as the co-ordinate functions on $X × Y$. Show that for any functions $f : Z \to X$ and $g : Z \to Y$, there exists a unique function $h:Z \to X \times Y$ such that $\pi_{X \times Y \to X} \circ h= f$ and $\pi_{X \times Y \to Y} \circ h=g$. (Compare this to the last part of Exercise 3.3.8, and to Exercise 3.1.7.) This function $h$ is known as the pairing of $f$ and $g$ and is denoted $h = (f, g)$.

Exploration

Lt's illustrate some of these new ideas with a small example.

Consider $X=\{x_1, x_2\}$ and $Y=\{y_1\}$. The cartesian product is therefore $X \times Y = \{(x_1, y_1), (x_2, y_1)\}$.

The function $\pi_{X \times Y \to X}:X \times Y \to X$ maps from the cartesian product, the set of ordered $n$-tuples, to the codomain which is the set X. An example of the mapping $\pi_{X \times Y \to X} (x, y) := x$ is

$$\pi_{X \times Y \to X}(x_2, y_1) = x_2$$

The map essentially extracts the "first coordinate" from the pair in the ordered 2-tuple.

Similarly, an example of the mapping for the other function, $\pi_{X \times Y \to Y}(x, y) := y$, is

$$\pi_{X \times Y \to Y}(x_2, y_1) := y_1$$

This extracts the "second coordinate" from the ordered 2-tuple.

Let's draw a picture to illustrate the described functions $f : Z \to X$, $g: Z \to Y$, and $h : Z \to X \times Y$.

Our aim is to show that for any $f$ and $g$, the function $h$ exists and is unique, given the constraints $\pi_{X \times Y \to X} \circ h= f$ and $\pi_{X \times Y \to Y} \circ h=g$.

Solution Part One

For exercises that ask us to prove a set exists, we typically construct the set from the axioms of set theory. However, to show a function exists is a little different as Tao discusses in his book. He writes, in Remark 3.3.2, that the existence of functions could have been made axiomatic, but they aren't because they can be constructed using ordered triple (domain, codomain, graph/mapping) and the operations of axiomatic set theory.

For our purposes, to show a function exists, we need to make clear its domain and codomain, and then ensure the mapping is well-defined, it conforms to the requirement that each element of the domain maps to only one element of the codomain, the "vertical line test".

It is suggested there might exist a function $h:Z \to X \times Y$ such that the following two conditions are met:

$$\forall z \in Z \; [ \pi_{X \times Y \to X} ( h(z) ) = f(z) ]$$

$$\forall z \in Z \; [ \pi_{X \times Y \to Y} ( h(z) ) = g(z) ]$$

Let's assume such a function does exist. What form does it take?

We know that for all $z \in Z$, $h(z)$ takes the form of an ordered pair $(h_1(z), h_2(z))$ where $h_1(z) \in X$ and $h_2(z) \in Y$. That is, $h_1:Z \to X$ and $h_2:Z \to Y$.

What is $h_1(z)$ and $h_2(z)$?

We use the two conditions to answer this:

$$ \pi_{X \times Y \to X}(h(z)) = h_1(z) = f(z)$$

$$ \pi_{X \times Y \to Y}(h(z)) = h_2(z) = g(z)$$

So we have

$$h(z) = (f(z), g(z))$$

We have shown that if there exists a function $h:z \to X \times Y$ that conforms to the two conditions above, then it must be of the unique form $h(z) = (f(z), g(z))$. 

To show existence, we use the definition of the function we derived $h(z)=(f(z), g(z))$ and show it conforms to any required constrains, and is well-behaved as a function:

• the domain of $h$ is $Z$
• the codomain of $h$ is $X \times Y$
• the first condition is met, $\pi_{X \times Y \to X} ( h(z) ) = \pi_{X \times Y \to X} (f(z), g(z))= f(z)$
• the second condition is met, $\pi_{X \times Y \to Y} ( h(z) ) = \pi_{X \times Y \to Y} (f(z), g(z))= g(z)$
• $h(z)=(f(z), g(z))$ is unique to $z$ because both $f$ and $g$ are well-defined functions, where $f(z)$ is unique to $z$, $g(z)$ is unique to $z$, and so $h(z)=(f(z), g(z))$ is also unique to $z$.

This solution was helped by this answer (link).

Solution Part Two

We are asked to compare this result with last part of Exercise 3.3.8, and to Exercise 3.1.7.

Drawing pictures is the easiest way to show the similarities between the sets and functions in these exercises.

In the following we can see there is a duality between the existence of a unique function that maps to $X \times Y$ in the first instance, and maps from $X \cup Y$ in the second.

And in the following we can see similar duality regarding intersection and union where the function is replaced by a predicate "is a subset of".

Apparently this nudge by Tao relates to category theory, something beyond this book, but discussed here (link).

Tao Analysis I - 3.5.6

Exercise 3.5.6

Let $A$, $B$, $C$, $D$ be non-empty sets. Show that $A \times B \subseteq C \times D$ if and only if $A \subseteq C$ and $B \subseteq D$, and that $A \times B = C \times D$ if and only if $A = C$ and $B = D$. 

What happens if some or all of the hypotheses that the $A$, $B$, $C$, $D$ are non-empty are removed?

Show $A \times B \subseteq C \times D \iff A \subseteq C$ and $B \subseteq D$

To show $A \times B \subseteq C \times D$ if and only if $A \subseteq C$ and $B \subseteq D$ we need to prove the following two statements:

• $A \times B \subseteq C \times D \implies A \subseteq C \land B \subseteq D$
• $A \subseteq C \land B \subseteq D \implies A \times B \subseteq C \times D$

Let's start with the second statement as it easier to prove.

$$A \subseteq C \land B \subseteq D \implies A \times B \subseteq C \times D$$

We need to show - is a statement I was advised by a mathematician friend to get into the habit of writing - $(\forall a\in A, b \in B) \; [(a,b) \in C \times D]$.

Given $A$ and $B$ are assumed non-empty, we can always pick an element $a \in A$ and $b \in B$ to form a tuple $(a,b)$.

By assumption, $A \subseteq C$ and $B \subseteq D$, and so we can deduce $a \in C$ and $b \in D$. So the tuple $(a,b)$ is in $C \times D$ by definition of cartesian products. Thus we have shown $A \subseteq C \land B \subseteq D \implies A \times B \subseteq C \times D$.

Now let's consider the first statement.

$$A \times B \subseteq C \times D \implies A \subseteq C \land B \subseteq D$$

We need to show $(\forall a \in A)\;[a \in C]$ and $(\forall b \in B)\;[b \in D]$.

Since $A$ and $B$ are assumed non-empty, we can always pick an arbitrary $a \in A$ and $b \in B$ to form a tuple $(a,b)$.

By definition of cartesian products, $(a,b) \in A \times B$. By hypothesis $A \times B \subseteq B \times D$, and so $(a,b) \in C \times D$. 

Again, by definition of cartesian products, this means $a \in C \land b \in D$. Thus we have shown $A \times B \subseteq C \times D \implies A \subseteq C \land B \subseteq D$.

By showing both statements, we have shown $A \times B \subseteq C \times D \iff A \subseteq C$ and $B \subseteq D$. $\square$.

Show $A \times B = C \times D \iff A = C$ and $B = D$

To show $A \times B = C \times D$ if and only if $A = C$ and $B = D$ we need to prove the following two statements:

• $A \times B = C \times D \implies A = C \land B = D$
• $A = C \land B = D \implies A \times B = C \times D$

Again, let's start with the second statement as it is easier to prove.

$$A = C \land B = D \implies A \times B = C \times D$$

We need to show $(\forall a \in A, b \in B) \; [(a,b) \in C \times D]$ and $(\forall c \in C, d \in D) \; [(c,d) \in A \times B]$.

Since $A$ and $B$ are assumed non-empty, we can always pick an arbitrary $a \in A$ and $b \in B$ to form a tuple $(a,b)$. By definition of cartesian products, $(a,b) \in A \times B$. By hypothesis, $A = C$ and $B = D$, and so we can deduce $a \in C$ and $b \in D$. And so $(a,b) \in C \times D$ by definition of cartesian products. This gives us $ A \times B \subseteq C \times D$.

To show $A \times B = C \times D$, we also need to show $C \times D \subseteq A \times D$.

Since $C$ and $D$ are assumed non-empty, we can always pick an arbitrary $c \in C$ and $d \in D$ to form a tuple $(c,d)$. The same argument as for $(a,b)$ gives us $C \times D \subseteq A \times D$.

So we have shown $A = C \land B = D \implies A \times B = C \times D$.

Now consider the first statement.

$$A \times B = C \times D \implies A = C \land B = D$$

We need to show $(\forall a \in A)[a \in C]$, $(\forall b \in B)[b \in D]$, $(\forall c \in C)[c \in A]$, and $(\forall d \in D)[d \in B]$.

Since $A$ and $B$ are assumed non-empty, we can always pick an arbitrary $a \in A$ and $b \in B$ to form a tuple $(a,b)$. By definition of cartesian products $(a,b) \in A \times B$. By hypothesis $A \times B = C \times D$, and so $(a,b) \in C \times D$. By definition of cartesian products, we deduce $a \in C$ and $b \in D$.

We have shown $(\forall a \in A)[a \in C]$ and $(\forall b \in B)[b \in D]$. We still need to show $(\forall c \in C)[c \in A]$, and $(\forall d \in D)[d \in B]$.

Since $C$ and $D$ are assumed non-empty, we can always pick an arbitrary $c \in C$ and $d \in D$ to form a tuple $(c,d)$. A symmetric argument to that for $(a,b)$ gives us $c \in A$ and $d \in B$.

So we have shown $A \times B = C \times D \implies A = C \land B = D$.

By showing both statements, we have proven $A \times B = C \times D \implies A = C \land B = D$. $\square$

Removing The Non-Empty Set Assumptions

Consider the first proposal:

$$A \times B \subseteq C \times D \iff A \subseteq C \land B \subseteq D$$

If only $A=\emptyset$, then $A \times B = \emptyset$, which is a subset of any set, not just $C \times D$. There is therefore no relationship between $B$, $C$, and $D$ required to make the LHS true. The proposal is therefore not always true.

Because $B$ is symmetric to $A$, if only $B=\emptyset$, the proposal also fails.

However, if both $A=\emptyset$ and $B=\emptyset$, then the proposal holds.

Now consider the second proposal:

$$A \times B = C \times D \iff A = C \land B = D$$

If only $A=\emptyset$, then $A=C=\emptyset$, and the statement becomes $\emptyset = \emptyset \iff \emptyset = \emptyset \land B = D$. The LHS is true regardless of any relationship between $B$ and $D$, so the proposal is not always true. By symmetry, this applies to $B=\emptyset$ too.

If only both $A=B=\emptyset$, then $A=C=\emptyset$ and $B=D=\emptyset$, and the statement becomes $\emptyset = \emptyset \iff \emptyset = \emptyset \land \emptyset = \emptyset$, which is fine. By symmetry, this applies to $C=D$ too.

If however, only $A=C=\emptyset$ then the statement becomes $\emptyset = \emptyset \iff \emptyset = \emptyset \land B=D$. The LHS can be true regardless of $B$ and $D$, and so the proposal is not always true.

By symmetry, this applies to $B=D$ too.

If all $A=B=C=D=\emptyset$ then the proposal holds.

Note - we can intuitively think of $\emptyset \times A$ as multiplying by zero, and this "losing information" about $A$.

Tao Analysis I - 3.5.5

Exercise 3.5.5

Let $A$, $B$, $C$, $D$ be sets. Show that $(A \times B) \cap (C \times D)=(A \cap C) \times (B \cap D)$.

Is it true that $(A  \times  B)  \cup  (C  \times  D) = (A  \cup  C)  \times  (B  \cup  D)$?

Is it true that $(A  \times  B) \setminus (C  \times  D) = (A \setminus C)  \times  (B \setminus D)$?

Let's draw a picture to help clarify our thinking.

We can see visually that:

• $(A \times B) \cap (C \times D)=(A \cap C) \times (B \cap D)$.
• $(A  \cup  C)  \times  (B  \cup  D)$ contains $(c,b)$ where $c \in C, b \in B$, but $(A  \times  B)  \cup  (C  \times  D)$ does not.
• $(A  \times  B) \setminus (C  \times  D)$ contains $(a,e)$ where $a \in A, e \in B \cap D$, but $(A \setminus C)  \times  (B \setminus D)$ does not.

Show $(A \times B) \cap (C \times D)=(A \cap C) \times (B \cap D)$

Let's write out what $(A \times B) \cap (C \times D)$ means,

$$ (x,y) \in (A \times B) \cap (C \times D) \iff (x,y) \in \{(a,b): a \in A, b \in B \} \land (x,y) \in \{(c,d): c \in C, d \in D \}$$

We can see that $x$ must be in both $A$ and $C$, and $y$ must be in both $B$ and $D$.

Therefore, the RHS is equivalent to

$$(x,y) \in \{(s,t): s \in A \cap C, t \in B \cap D\}$$

Thus we have shown $(A \times B) \cap (C \times D)=(A \cap C) \times (B \cap D)$. $\square$

Is it true that $(A  \times  B)  \cup  (C  \times  D) = (A  \cup  C)  \times  (B  \cup  D)$?

Let's write out what $(A  \times  B)  \cup  (C  \times  D)$ means,

$$ (x,y) \in (A  \times  B)  \cup  (C  \times  D) \iff (x,y) \in \{(a,b): a \in A, b \in B\} \lor (x,y) \in \{(c,d): c \in D, d \in D\}$$

Here we need to be careful about what this means. It means that

$$ (x \in A \land y \in B) \lor (x \in C \land y \in D) $$

Note in particular that $(c, b): c \in C, b \in B$ is not compatible with this, and is therefore not in the set $(A  \times  B)  \cup  (C  \times  D)$. 

Let's consider the other set, $(A  \cup  C)  \times  (B  \cup  D)$. This means

$$ (x,y) \in (A  \cup  C)  \times  (B  \cup  D) \iff (x,y) \in \{(a,b): a \in A \lor C, b \in B \lor D\}$$

This time, the ordered pair $(c, b): c \in C, b \in B$  is in this set.

Therefore the two are not equivalent, $(A  \times  B)  \cup  (C  \times  D) \neq (A  \cup  C)  \times  (B  \cup  D)$. $\square$

A counter-example can illustrate this. Consider $A=\{1\}, B=\{2\}, C=\{3\}, D=\{4\}$. 

Then  $(A  \times  B)  \cup  (C  \times  D) = \{(1,2), (3,4)\}$, and $(A  \cup  C)  \times  (B  \cup  D) = \{(1,2), (1,4), (3,2), (3,4)\}$, a different set. The latter contains $(3,2)$, the former does not.

Is it true that $(A  \times  B) \setminus (C  \times  D) = (A \setminus C)  \times  (B \setminus D)$?

Let's write out what $(A  \times  B) \setminus (C  \times  D)$ means,

$$(x,y) \in (A  \times  B) \setminus (C  \times  D) \iff (x,y) \in \{ (a,b): a \in A, b \in B \} \land (x,y) \notin \{(c,d): c \in C, d \in D\}$$

Again, with some care, we establish what this means. (revision on negating statements)

$$ (x \in A \land y \in B) \land (x \notin C \lor y \notin D)$$

Consider the ordered pair $(a,e): a \in A, e \in B \cap D$. This satisfies the above condition, so is a member of the set $(A  \times  B) \setminus (C  \times  D)$

Now let's consider the other set, $(A \setminus C)  \times  (B \setminus D)$. This means

$$ (x,y) \in (A \setminus C)  \times  (B \setminus D) \iff (x,y) \in \{(a,b): a \in A \land a \notin C, b \in B \land b \notin D\} $$

That is, $x \in A \land x \notin C \land y \in B \land  y \notin D$.

The ordered pair $(a,e): a \in A, e \in B \cap D$ is not in this set.

Therefore the two are not equivalent, $(A  \times  B) \setminus (C  \times  D) \neq (A \setminus C)  \times  (B \setminus D)$. $\square$

Again, a counter-example will illustrate this. Consider $A=\{1\}, B=\{2,3\}, C=\{4\}, D=\{3,5\}$. 

Then, $(A  \times  B) \setminus (C  \times  D) = \{(1,2), (1,3)\}$, and $(A \setminus C)  \times  (B \setminus D) = \{(1,2)\}$, a different set. The former contains $\{1,3\}$, the latter does not.

Tao Analysis I - 3.5.4

Exercise 3.5.4

Let $A$, $B$, $C$ be sets. Show that $A \times (B \cup C)=(A \times B) \cup (A \times C)$, that $A \times (B \cap C)=(A \times B) \cap (A \times C)$, and that $A \times (B \setminus C)=(A \times B) \setminus (A \times C)$.

Show $A \times (B \cup C)=(A \times B) \cup (A \times C)$

Let's write out what $A \times (B \cup C)$ means,

$$(a,d) \in A \times (B \cup C) \iff (a,d) \in \{ (x,y) : x \in A,  y \in B \cup C\}$$

The RHS is equivalent to

$$(a,d) \in \{ (x,y) : x \in A,  y \in B\} \lor (a,d) \in \{ (x,y) : x \in A,  y \in C\}$$

Which is equivalent to

$$(a,d) \in A \times (B \cup C) \iff (a,d) \in (A \times B) \cup (A \times C)$$

Thus, we have shown $A \times (B \cup C)=(A \times B) \cup (A \times C)$. $\square$

Show $A \times (B \cap C)=(A \times B) \cap (A \times C)$

Let's write out what $A \times (B \cap C)$ means

$$(a,d) \in A \times (B \cap C) \iff (a,d) \in \{ (x,y) : x \in A,  y \in B \cap C\}$$

The RHS is equivalent to

$$(a,d) \in \{ (x,y) : x \in A,  y \in B\} \land (a,d) \in \{ (x,y) : x \in A,  y \in C\}$$

Which is equivalent to

$$(a,d) \in A \times (B \cap C) \iff (a,d) \in (A \times B) \cap (A \times C)$$

Thus, we have shown $A \times (B \cap C)=(A \times B) \cap (A \times C)$. $\square$

Show $A \times (B \setminus C)=(A \times B) \setminus (A \times C)$

Let's write out what $A \times (B \setminus C)$ means

$$(a,d) \in A \times (B \setminus C) \iff (a,d) \in \{ (x,y) : x \in A,  y \in B \setminus C\}$$

The RHS is equivalent to

$$(a,d) \in \{ (x,y) : x \in A,  y \in B\} \land (a,d) \notin \{ (x,y) : x \in A,  y \in C\}$$

Which is equivalent to

$$(a,d) \in A \times (B \setminus C) \iff (a,d) \in (A \times B) \setminus (A \times C)$$

Thus, we have shown $A \times (B \setminus C)=(A \times B) \setminus (A \times C)$. $\square$

Tao Analysis I - 3.5.3

Exercise 3.5.3

Show that the definitions of equality for ordered pair and ordered $n$-tuple are consistent with the reflexivity, symmetry, and transitivity axioms, in the sense that if these axioms are assumed to hold for the individual components $x$, $y$ of an ordered pair $(x, y)$, then they hold for the ordered pair itself.

The approach is the same for both ordered pair and $n-tuple$ but for clarity we'll do the special easier case of an ordered pair first, then do the more general $n$-tuple.

Ordered Pair

Two ordered pairs $(x,y)$ and $(x',y')$ are equal if and only if $x=x'$ and $y=y'$, by Definition 3.5.1.

Let's consider reflexivity, $A=B \implies B=A$. So let's assume $(x,y)=(x',y')$. This means $x=x'$ and $y=y'$. Since reflexivity holds for $x, y, x', y'$, we can say $x'=x$ and $y'=y$, which is equivalent to $(x',y')=(x,y)$. Thus we have shown reflexivity, $(x,y)=(x',y') \implies (x',y')=(x,y)$. $\square$

Now let's consider symmetry, $(x,y)=(x,y)$. This is true because we know the components obey the equivalence property $x=x$ and $y=y$, which means the ordered pair is equal to itself by definition 3.5.1. $\square$

Finally, consider transitivity, $A=B \land B=C \implies A=C$. Let's start with $(x,y)=(x',y')$ and $(x',y')=(x'',y'')$. Using definition 3.5.1, we know that $x=x', y=y'$ and also $x'=x'', y'=y''$. Since these individual components obey the equivalence property of transitivity, we can say $x=x'', y=y''$. By definition 3.5.1 this tells us $(x,y)=(x'',y'')$. We have shown ordered pairs obey transitivity, $(x,y)=(x',y')$ and $(x',y')=(x'',y'')$ implies $(x,y)=(x'',y'')$. $\square$

n-Tuples

Definition 3.5.6 generalises equality of ordered pairs to n-tuples:

Two ordered $n$-tuples $(x_i)_{1 \leq i \leq n}$ and $(y_i)_{1 \leq i \leq n}$ are said to be equal iff $x_i = y_i$ for all $1 \leq i \leq n$.

Let's consider reflexivity, $A=B \implies B=A$. Given two equal n-tuples, $(x_i)_{1 \leq i \leq n} = (y_i)_{1 \leq i \leq n}$, we know by the above definition 3.5.1 that $x_i = y_i$ for all $1 \leq i \leq n$. Since these individual components $x_i$ and $y_i$ obey reflexivity, we can say $y_i = x_i$ for all $1 \leq i \leq n$. This is equivalent to $(y_i)_{1 \leq i \leq n} = (x_i)_{1 \leq i \leq n}$, thus we have shown reflexivity. $\square$

Let's now consider symmetry, $(x_i)_{1 \leq i \leq n}=(x_i)_{1 \leq i \leq n}$. For this to be true we must have $x_i = x_i$ for all $1 \leq i \leq n$. This is indeed the case as the individual components $x_i$ obey symmetry. This we have shown symmetry. $\square$

Finally, consider transitivity, $A=B \land B=C \implies A=C$. Let's start with $(x_i)_{1 \leq i \leq n} = (y_i)_{1 \leq i \leq n}$, and $(y_i)_{1 \leq i \leq n} = (z_i)_{1 \leq i \leq n}$. This tells us $x_i = y_i$ for all $1 \leq i \leq n$, and $y_i = z_i$ for all $1 \leq i \leq n$. Since these individual elements obey transitivity, we have $x_i = z_i$ for all $1 \leq i \leq n$. This is equivalent to $(x_i)_{1 \leq i \leq n} = (z_i)_{1 \leq i \leq n}$. Thus, we have shown transitivity. $\square$.

Tao Analysis I - 3.5.2

Exercise 3.5.2

Suppose we define an ordered $n$-tuple to be a surjective function $x : \{i \in \mathbb{N} : 1 \leq i \leq n\} \to X$ whose codomain is some arbitrary set $X$ (so different ordered n-tuples are allowed to have different ranges); we then write $x_i$ for $x(i)$ and also write $x$ as $(x_i)_{1 \leq i \leq n}$. Using this definition, verify that we have $(x_i)_{1 \leq i \leq n} = (y_i)_{1 \leq i \leq n}$ if and only if $x_i = y_i$ for all $1 \leq i \leq n$. 

Also, show that if $(X_i)_{1 \leq i \leq n}$ are an ordered n-tuple of sets, then the Cartesian product, as defined in Definition 3.5.6, is indeed a set. (Hint: use Exercise 3.4.7 and the axiom of specification.)

Let's remind ourselves of Definition 3.5.6 (Ordered $n$-tuple and $n$-fold Cartesian product):

Let $n$ be a natural number. An ordered $n$-tuple $(x_i)_{1 \leq i \leq n}$ (also denoted $(x_1, \ldots , x_n)$) is a collection of objects $x_i$ , one for every natural number $i$ between 1 and $n$; we refer to $x_i$ as the $i^{th}$ component of the ordered $n$-tuple.

Two ordered $n$-tuples $(x_i )_{1 \leq i \leq n}$ and $(y_i )_{1 \leq i \leq n}$ are said to be equal iff $x_i = y_i$ for all $1 \leq i \leq n$.

If $(X_i)_{1 \leq i \leq n}$ is an ordered $n$-tuple of sets, we define their Cartesian product $\prod_{1 \leq i \leq n}X_i$ (also denoted $\prod_{i=1}^{n}X_i$ or $X_1 \times  \ldots \times X_n$) by

$$ \prod_{1 \leq i \leq n} X_i := \{ (x_i)_{1 \leq i \leq n} : x_i \in X_i \text{ for all } 1 \leq i \leq n \} $$

Exploration

The terminology here is quite dense and confusing, so let's illustrate it with small examples to help clarify our thinking.

Let's start with the idea of an n-tuple as a function. The following shows a function which maps from a domain $\{1,2,3\}$ to a codomain $\{a,b,c\}$. 

Specifically, the function maps 1 to $a$, 2 to $b$, and 3 to $c$. 

To fully describe this function, we can list the output values as an ordered n-tuple, $(a,b,c)$. 

However, to do this we also need to know which elements of the domain these output values correspond to, and for this we need to order the domain too. We can do this simply as $i \in \mathbb{N}: 1 \leq i \leq 3$, which gives 1, then 2, then 3, in that order.

To illustrate the notation, we can write $f_i$ for $f(i)$, that is $f_2$ for $f(2)$. We can also write simply $f$ for $(f_i)_{1 \leq i \leq 3}$.

Part One

We need to show that $(x_i)_{1 \leq i \leq n} = (y_i)_{1 \leq i \leq n}$ if and only if $x_i = y_i$ for all $1 \leq i \leq n$. To do this we need to show both:

• $(x_i)_{1 \leq i \leq n} = (y_i)_{1 \leq i \leq n} \implies x_i = y_i$ for all $1 \leq i \leq n$
• $x_i = y_i$ for all $1 \leq i \leq n \implies (x_i)_{1 \leq i \leq n} = (y_i)_{1 \leq i \leq n}$

The first statement assumes the two functions $x$ and $y$ are equal. Functions are equal if they have the same domain, codomain, and also map the same inputs to the same outputs. This last requirement can be written as $x(i) = y(i)$ for all $1 \leq i \leq n$, which is what we needed to show.

The second statement assumes the two functions map the same inputs to the same outputs, $x(i)=y(i)$. The domain is the same because it is defined for both as $i\in \mathbb{N}: 1 \leq i \leq n$. The range is the same because $x(i) = y(i)$ for all $1 \leq i \leq n$. Since the function is surjective, the range is also the domain. Thus we have demonstrated the three requirements for the functions to be equal, $(x_i)_{1 \leq i \leq n} = (y_i)_{1 \leq i \leq n}$.

Having shown both implications, we have proved that $(x_i)_{1 \leq i \leq n} = (y_i)_{1 \leq i \leq n}$ if and only if $x_i = y_i$ for all $1 \leq i \leq n$. $\square$

Part Two - Exploration

I found this quote difficult so I began with an example illustration of some of the objects involved in the exercise.

An ordered $n$-tuple of sets, is a tuple with sets as elements. For example, a 2-tuple $(X_1, X_2)$, where $X_1$ and $X_2$ are sets, not primitive objects like natural numbers. 

To illustrate, the cartesian product of those sets, let's fill in the content of those sets. For example, $X_1=\{a,b\}$, and $X_2=\{c\}$. The cartesian product is a set of 2-tuples, as per definition 3.5.6, which here is

$$\prod_{1 \leq i \leq 2} X_i = \{(a,c), (b,c)\}$$

It is worth being clear that the cartesian product is a set of ordered $n$-tuples.

Let's think about how we might construct the cartesian product:

• we can form the union of the original sets, $\bigcup {X_1, X_2} = \{a,b,c\}$
• each element of the cartesian product is a 2-tuple $(x_1, x_2)$ where $x_1 \in X_1, x_2 \in X_2$
• that 2-tuple is a partial function from the domain $\{1,2\}$ to the codomain $\{a,b,c\}$
• the collection of all such partial functions is a set by exercise 3.4.7
• we can select from that set, using the axiom of specification, just those partial functions that meet our needs: have a domain $\{1,2\}$, have codomain $\{a,b,c\}$, map $i$ to $x_i \in X_i$, and are surjective, which gives us the set $\{(a,c), (b,c)\}$
• the resulting set is the desired cartesian product

Part Two -  Solution

The exercise hints at using the axiom of specification, which can only be applied to one set. This suggests we need to form a single set from the $n$ sets $X_i$, where $1 \leq i \leq n$.

Let's begin with the union of those sets,

$$Y = \bigcup_{1 \leq i \leq n} X_i$$

Thus, any element of any $X_i$ is a member of $Y$. And so this set $Y$ is useful because we can use its elements to build the cartesian product's tuples.

Now, consider a partial function from $\{1 \leq i \leq n\} \to Y$. This is a function which maps from a subset of the domain $\{1 \leq i \leq n\}$ to a subset of the codomain $Y$. The collection of all such partial functions is a set, a result proved in Exercise 3.4.7. Let's call this set $F$.

Some, but not all, elements of this set $F$ are functions, $n$-tuples, that are the elements of the cartesian product. We can select them using the Axiom of Specification to form the set $C$, using a statement $S$.

$$C = \{f \in F: S(f) \text{ is true}\} $$

here the statement $S(f)$ is

$$\begin{align}S(f) \; : \; & \operatorname{dom} f = \{1 \leq i \leq n\} \\ & \land \operatorname{codomain} f = Y \\ & \land f(i) \in X_i \\ & \land f \text { is surjective} \end{align}$$

That is, the statement $S(f)$ is true is the function $f \in F$ has a domain \{1 \leq i \leq n\}, has a codomain $Y=\bigcup X_i$, maps as $f(i) \in X_i$, and is surjective.

The resulting set $C$ contains only the elements of the cartesian product $\prod_{1 \leq i \leq n} X_i$, as per Definition 3.5.6.

We have shown the cartesian product is a set by constructing it using the axioms, as above. $\square$

Tao Analysis I - 3.5.1

Exercise 3.5.1

(i) Suppose we define the ordered pair $(x, y)$ for any objects $x$ and $y$ by the formula $(x, y) := \{\{x\}, \{x, y\}\}$. Show that such a definition (known as the Kuratowski definition of an ordered pair) indeed obeys the property (3.5).

(ii) Suppose we instead define an ordered pair using the alternate definition $(x, y) := \{x, \{x, y\}\}$. Show that this definition (known as the short definition of an ordered pair) also verifies (3.5) and is thus also an acceptable definition of ordered pair. (Warning: this is tricky; one needs the axiom of regularity, and in particular Exercise 3.2.2.)

(iii) Show that regardless of the definition of ordered pair, the Cartesian product $X \times Y$ of any two sets $X,Y$ is again a set. (Hint: first use the axiom of replacement to show that for any $x \in X$, that $\{(x, y) : y ∈ Y\}$ is a set, and then apply the axiom of union.)

Let's remind ourselves of property (3.5):

Two ordered pairs $(x, y)$ and $(x′, y′)$ are considered equal if and only if both their components match, i.e.,

$$(x,y)=(x',y') \iff (x=x' \land y=y')$$

Part (i)

Let's consider two ordered pairs, $(x,y)$ and $(a,b)$. Let's write these in the form of the Kuratowski definition.

$$ (x,y) := \{ \{x\}, \{x, y\} \} $$

$$ (a,b) := \{ \{a\}, \{a, b\} \} $$

For the two ordered pairs to be equal, the two sets, $\{ \{x\}, \{x, y\} \}$ and $\{ \{a\}, \{a, b\} \}$, must be equal. Two sets are equal if every member of one is also a member of the other.

This means the following four statements must be true:

• $\{x\} \in \{ \{a\}, \{a, b\} \}$
• $\{x,y\} \in \{ \{a\}, \{a, b\} \}$
• $\{a\} \in \{ \{x\}, \{x, y\} \}$
• $\{a, b\} \in \{ \{x\}, \{x, y\} \}$

Each of these statements implies the following, listed in corresponding order:

• $(x = a) \lor (x = a = b)$
• $(x = a \land y = b) \lor (x = b \land y = a)$
• $(a = x) \lor (a = x = y)$
• $(a = x \land b = y) \lor (a = y \land b = x)$

These make use of the fact that a set with two (distinct) elements can't equal a singleton set. That is, $\{x\} \neq \{a,b\}$, unless $a=b$, in which case $\{a,b\}=\{a\}=\{b\}$, a singleton set.

These last four statements are only all true if:

$$(x = a) \land (y = b)$$

This is because the first and third statements set $x=a$ in all cases. Then the second and fourth statements set $b=y$, or the case where $x=y=a=b$.

This shows the Kuratowski definition of an ordered pair obeys property 3.5. $\square$

Part (ii)

We take a similar approach to the above. 

Before we do, let's remind ourselves of the result of Exercise 3.2.2:

• If $A$ is a set, then $A \notin A$. 
• If $A$ and $B$ are sets, then either $A \notin B$ or $B \notin A$, or both.

Let's consider two ordered pairs, $(x,y)$ and $(a,b)$. Let's write these in the form of the "short" definition.

$$ (x,y) := \{ x, \{x, y\} \} $$

$$ (a,b) := \{ a, \{a, b\} \} $$

For the two ordered pairs to be equal, the two sets, $\{ x, \{x, y\} \}$ and $\{ a, \{a, b\} \}$, must be equal. Two sets are equal if every member of one is also a member of the other.

This means the following four statements must be true:

• $x \in \{ a, \{a, b\} \}$
• $\{x,y\} \in \{ a, \{a, b\} \}$
• $a \in \{ x, \{x, y\} \}$
• $\{a, b\} \in \{ x, \{x, y\} \}$

Each of these statements implies the following, listed in corresponding order:

• $(x = a) \lor (x = \{a, b\})$
• $(x = a \land y = b) \lor (a = \{x, y\})$
• $(a = x) \lor (a = \{x, y\})$
• $(a = x \land b = y)  \lor (x = \{a,b\})$

This requires more work to resolve. We start with two cases, $x=a$ suggested by the first and third statements,  or $x \neq a$.

case $x=a$

The first statement then suggests $x = a = \{a, b\}$. However, this is ruled out by the axiom of regularity. If $x=a$ is a fundamental object, then it cannot be a set $\{a,b\}$. If $x=a$ is a set, then it cannot be a member of $\{a,b\}$ by the axiom of regularity.

Similarly,  the second statement suggests $a=\{x,y\}$, which is ruled out by the axiom of regularity, following a similar argument as above. This leaves $x=a \land y=b$. That is, $y=b$.

The third statement suggests $a=\{x,y\}$, also ruled out by the axiom of regularity.

The fourth statement suggests $x=\{a,b\}$, which is ruled out by the axiom of regularity, leaving $b=y$.

So the case $x=a$ leaves only $b=y$.

case $x \neq a$

Since $x \neq a$, all four statements tell us the following two statements must be true:

• $a = \{x, y\}$
• $x = \{a, b\}$

This is ruled out by the axiom of regularity in the second form presented above: if $A$ and $B$ are sets, then either $A \notin B$ or $B \notin A$, or both. So $x$ must not be an element of $\{x, y\}$, $a$ must not be an element of $\{a,b\}$

So the case $x \neq a$ is ruled out.

Considering both cases leaves us with

$$(x = a) \land (y = b)$$

This shows the "short" definition of an ordered pair obeys property 3.5. $\square$

Part (iii)

For any two sets, $X$ and $Y$, we want to show that the cartesian product $X \times Y$ is also a set.

Fix an $x' \in X$ and apply the Axiom of Replacement to Y as follows. Consider the statement $P$:

$$ P(\;y, (x'y)\;) : (x',y) \text{ is an ordered pair with } y \in Y $$

This statement $P$ is true if $(x', y)$ is an ordered pair with $y \in Y$. For every $y \in Y$ it is true for at most one ordered pair $(x', y)$, therefore it is suitable for use by the Axiom of Replacement. This gives us a new set $S$ of ordered pairs:

$$ S_{x'} = \{ (x', y) : y \in Y\} $$

Remember, $x'$ is fixed.

Now we need to iterate over $x \in X$ and we can do this using the Axiom of Union, which defines the following set:

$$T = \bigcup_{x \in X} S_x = \{ (x, y) : x \in X, y \in Y\}$$

This set $T$ contains all the combinations of $x \in X$ and $y \in Y$ in the form of ordered pairs $(x,y)$. 

This is the Cartesian product $X \times Y$, and is a set by the axioms of construction we used. $\square$

Update to Part (iii)

This discussion (link) has clarified an important point and is worth discussing here.

The axiom of union is quite intuitive, which is good, but does risk us overlooking some details.

The detail I had glossed over is that the union $\bigcup S$ requires $S$ to be a set (of sets). Ensuring that $S$ is a set is something I had glossed over, so the following approach is a little more rigorous.

Step 1:

• Fix an $x' \in X$ and use the axiom of replacement on $Y$. Use the statement $$P(x', (x', y)): (x',y) \text{ is an ordered pair for } y \in Y$$ which is true for at most one ordered pair $(x', y)$ for each $y \in Y$. This gives us a set $S_{x'}=\{(x', y): y \in Y\}$. That is, the set exists due to the axiom of replacement.

Step 2:

• Now use the axiom of replacement again, this time on $Y$. Use the statement $$Q(x, S{_x}): S_{x} \text{ is the set of ordered pairs } \{(x,y): y \in Y\} \text{ for } x \in X)$$ which is true for at most one $S_x$ for each $x \in X$. This gives us a set of sets $S = \{S_x : x \in X\}$. Again, this set exists due to the axiom of replacement.

Step 3:

• Now we know $S$ exists, we can use the axion of union, $\bigcup S = \{(x,y): (x,y) \in S_x\}$. This is equivalent to $\bigcup S = \{(x,y): x \in X, y \in Y\} = X \times Y$, as required.

Tao Analysis I - 3.4.11

Exercise 3.4.11

Let $X$ be a set, let $I$ be an on-empty set, and for all $\alpha \in I$ let $A_\alpha$ be a subset of $X$.

Show that

$$ X \setminus \bigcup_{\alpha \in I}A_\alpha = \bigcap_{\alpha \in I}( X \setminus A_\alpha) $$

and

$$ X \setminus \bigcap_{\alpha \in I}A_\alpha = \bigcup_{\alpha \in I}( X \setminus A_\alpha) $$

Part One

Let's start by considering $\bigcup_{\alpha \in I}A_\alpha$. By definition we have

$$ x \in \bigcup_{\alpha \in I}A_\alpha \iff (x \in A_\alpha \text{ for some } \alpha \in I)  $$

If $x$ is not in $\bigcup_{\alpha \in I}A_\alpha$, then we have

$$ x \notin \bigcup_{\alpha \in I}A_\alpha \iff (x \notin A_\alpha \text{ for all } \alpha \in I)  $$

Note the quantifier changes from "for some" to "for all" when negated.

So,  $x \in X \setminus \bigcup_{\alpha \in I}A_\alpha $ means

$$(x \in X) \land (x \notin \bigcup_{\alpha \in I}A_\alpha )$$

That is,

$$(x \in X) \land (x \notin A_\alpha \text{ for all } \alpha \in I) $$

That means $x \in X$ and also $x \notin A_\alpha$ for each and every $A_\alpha$. This is equivalent to

$$x \in \bigcap_{\alpha \in I} (X \setminus A_\alpha ) $$

We have shown,

$$X \setminus \bigcup_{\alpha \in I}A_\alpha = \bigcap_{\alpha \in I}( X \setminus A_\alpha) \; \square$$

Part Two

The approach is similar to Part One.

Let's start by considering $\bigcap_{\alpha \in I}A_\alpha$. By definition we have

$$ x \in \bigcap_{\alpha \in I}A_\alpha \iff (x \in A_\alpha \text{ for all } \alpha \in I)  $$

If $x$ is not in $\bigcap_{\alpha \in I}A_\alpha$, then we have

$$ x \notin \bigcap_{\alpha \in I}A_\alpha \iff (x \notin A_\alpha \text{ for some } \alpha \in I)  $$

Note the quantifier changes from "for all" to "for some" when negated. It might be easier to read "for some" as "at least one" in this example.

So,  $x \in X \setminus \bigcap_{\alpha \in I}A_\alpha $ means

$$(x \in X) \land (x \notin \bigcap_{\alpha \in I}A_\alpha )$$

That is,

$$(x \in X) \land (x \notin A_\alpha \text{ for some } \alpha \in I) $$

That means $x \in X$ and also $x \notin A_\alpha$ for some $A_\alpha$. This is equivalent to

$$x \in \bigcup_{\alpha \in I} (X \setminus A_\alpha ) $$

We have shown,

$$ X \setminus \bigcap_{\alpha \in I}A_\alpha = \bigcup_{\alpha \in I}( X \setminus A_\alpha) \; \square$$

Tao Analysis I - 3.4.10

Exercise 3.4.10

Suppose that $I$ and $J$ are two sets, and for all $\alpha \in I \cup J$ let $A_\alpha$ be a set. Show that

$$ \left( \bigcup_{\alpha \in I} A_\alpha \right) \cup \left( \bigcup_{\alpha \in J} A_\alpha \right)  = \bigcup_{\alpha \in I \cup J} A_\alpha $$

If $I$ and $I$ are non-empty, show that

$$ \left( \bigcap_{\alpha \in I} A_\alpha \right) \cap \left( \bigcap_{\alpha \in J} A_\alpha \right)  = \bigcap_{\alpha \in I \cup J} A_\alpha $$

Union of Unions

Let's first consider the set $ \left( \bigcup_{\alpha \in I} A_\alpha \right)$. By definition (3.2), we have

$$ x \in \left( \bigcup_{\alpha \in I} A_\alpha \right) \iff x \in A_\alpha \text{ for some } \alpha \in I $$

Similarly, 

$$ x \in \left( \bigcup_{\alpha \in J} A_\alpha \right) \iff x \in A_\alpha \text{ for some } \alpha \in J $$

Now, by definition of pairwise union, if $x \in X \cup Y \iff (x \in Y) \lor (x \in Y)$. So we have,

$$ x \in  \left( \bigcup_{\alpha \in I} A_\alpha \right) \cup \left( \bigcup_{\alpha \in J} A_\alpha \right) \iff (x \in A_\alpha \text{ for some } \alpha \in I) \lor (x \in A_\alpha \text{ for some } \alpha \in J) $$

The two membership conditions are combined in disjunction.

The RHS is equivalent to $(x \in A_\alpha \text{ for some } \alpha \in I \lor J)$. This is the definition of $\bigcup_{\alpha \in I \cup J} A_\alpha$.

Thus, we have shown

$$ \left( \bigcup_{\alpha \in I} A_\alpha \right) \cup \left( \bigcup_{\alpha \in J} A_\alpha \right)  = \bigcup_{\alpha \in I \cup J} A_\alpha \; \square $$

Intersection of Intersections

Let's consider the set $\left( \bigcap_{\alpha \in I} A_\alpha \right)$. By definition (3.4), we have

$$ x \in  \left( \bigcap_{\alpha \in I} A_\alpha \right) \iff x \in A_\alpha \text{ for all } \alpha \in I  $$

Similarly,

$$ x \in  \left( \bigcap_{\alpha \in J} A_\alpha \right) \iff x \in A_\alpha \text{ for all } \alpha \in J  $$

Now, by definition of pairwise intersection, $x \in X \cap Y \iff (x \in Y) \land (x \in Y)$. So we have,

$$ x \in  \left( \bigcap_{\alpha \in I} A_\alpha \right) \cap \left( \bigcap_{\alpha \in J} A_\alpha \right) \iff (x \in A_\alpha \text{ for all } \alpha \in I) \land (x \in A_\alpha \text{ for all } \alpha \in J) $$

The two membership conditions are combined in conjunction.

The RHS is equivalent to $(x \in A_\alpha \text{ for all } \alpha \in I \land J)$. This is the definition of $\bigcup_{\alpha \in I \cap J} A_\alpha$.

Thus, we have shown

$$ \left( \bigcap_{\alpha \in I} A_\alpha \right) \cap \left( \bigcap_{\alpha \in J} A_\alpha \right)  = \bigcap_{\alpha \in I \cup J} A_\alpha \; \square $$

Tao Analysis I - 3.4.9

Exercise 3.4.9

Show that if $\beta$ and $\beta'$ are two elements of a set $I$, and to each $\alpha \in I$ we assign a set $A_{\alpha}$, then

$$ \{ x \in A_{\beta} : x \in A_{\alpha} \text{ for all } \alpha \in I \} = \{ x \in A_{\beta'} : x \in A_{\alpha} \text{ for all } \alpha \in I \} $$

and so the definition of $\bigcap_{\alpha \in I} A_{\alpha}$ defined in (3.3) does not depend on $\beta$.

Also explain why (3.4) is true.

Let's remind ourselves what the more general definition of intersection (3.3) says:

Given any non-empty set $I$ , and given an assignment of a set $A_{\alpha}$ to each $\alpha \in I$, we can define the intersection $\bigcap_{\alpha \in I}A_{\alpha}$ by first choosing some element $\beta$ of $I$ (which we can do since $I$ is non-empty), and setting

$$ \bigcap_{\alpha \in I} A_{\alpha} := \{ x \in A_{\beta} : x \in A_{\alpha} \text{ for all } \alpha \in I  \} $$

which is a set by the axiom of specification.

Thoughts

Since the intersection contains only elements which are members of all $A_\alpha$, it doesn't matter which $\beta$ is chosen to select one $A_{\alpha=\beta}$. 

Another way to think about this is that, it is impossible to pick a bad $A_\beta$ because if an element is not in $A_\beta$ then it can't be in the intersection.

Another point worth making is that the definition looks over-complicated. Why can't be as simple as the following?

$$ \bigcap_{\alpha \in I} A_{\alpha} := \{ x : x \in A_{\alpha} \text{ for all } \alpha \in I  \} $$

The reason is that defining sets using logical statements can lead to paradoxes, as Tao introduced earlier. However, defining sets as subsets of known sets guarantees they are sets.

Solution

To show the two sets are equivalent, we need to show an element of one is also an element of the other.

If $x \in \{ x \in A_{\beta} : x \in A_{\alpha} \text{ for all } \alpha \in I  \}$ then it must conform to the membership condition $x \in A_{\alpha} \text{ for all } \alpha \in I$.

Since $A_{\beta'}$ is one of the $A_\alpha$, then $x \in A_{\beta'}$. 

So we have $x \in A_{\beta'}$, and also $x \in A_{\alpha} \text{ for all } \alpha \in I$. This is equivalent to  $x \in \{ x \in A_{\beta'} : x \in A_{\alpha} \text{ for all } \alpha \in I  \}$. This is the definition of the second set.

By a symmetric argument, if $x$ is a member of the second set, it is also a member of the first.

Thus we have shown the two sets are equivalent. $\square$.

Now let's consider why (3.4) is true. Let's restate (3.4):

$$ y \in \bigcap_{\alpha \in I} A_\alpha \iff ( y \in A_\alpha \text{ for all } \alpha \in I ) $$

Let's show this in the usual manner, that each statement implies the other.

If  $y \in \bigcap_{\alpha \in I} A_\alpha$, then by definition (3.3) of the intersection of a family of sets, we have $y \in  \{ x \in A_{\beta} : x \in A_{\alpha} \text{ for all } \alpha \in I  \}$. This means $y$ must conform to the membership condition $y \in A_{\alpha} \text{ for all } \alpha \in I $. We have shown

$$y \in \bigcap_{\alpha \in I} A_\alpha \implies y \in A_{\alpha} \text{ for all } \alpha \in I $$

Now the converse, if $y \in A_{\alpha} \text{ for all } \alpha \in I$ is true then the membership condition $\{ y \in A_{\beta} : y \in A_{\alpha} \text{ for all } \alpha \in I  \}$ for the intersection is met, noting that $A_\beta$ is one of the $A_\alpha$. Thus we have shown

$$ y \in A_{\alpha} \text{ for all } \alpha \in I \implies y \in \bigcap_{\alpha \in I} A_\alpha $$

By showing both implications, we have shown that (3.4) is true. $\square$

Tao Analysis I - 3.4.8

Exercise 3.4.8

Show that Axiom 3.5 can be deduced from Axiom 3.1, Axiom 3.4, and Axiom 3.12.

Let's remind ourselves of these axioms.

Axiom 3.5 (Pairwise union). Given any two sets $A$, $B$, there exists a set $A \cup B$, called the union of $A$ and $B$, which consists of all the elements which belong to $A$ or $B$ or both. In other words, for any object $x$,

$$ x \in A \cup B \iff (x \in A \lor x \in B)$$

Axiom 3.1 (Sets are objects). If $A$ is a set, then $A$ is also an object. In particular, given two sets $A$ and $B$, it is meaningful to ask whether $A$ is also an element of $B$.

Axiom 3.4 (Singleton sets and pair sets). If $a$ is an object, then there exists a set $\{a\}$ whose only element is $a$, i.e., for every object $y$, we have $y \in \{a\}$ if and only if $y = a$; we refer to $\{a\}$ as the singleton set whose element is $a$. Furthermore, if $a$ and $b$ are objects, then there exists a set $\{a, b\}$ whose only elements are $a$ and $b$; i.e., for every object $y$, we have $y \in \{a, b\}$ if and only if $y = a$ or $y = b$; we refer to this set as the pair set formed by $a$ and $b$.

Axiom 3.12 (Union). Let $A$ be a set, all of whose elements are themselves sets. Then there exists a set $\bigcup A$ whose elements are precisely those objects which are elements of the elements of $A$, thus for all objects $x$

$$x \in \bigcup A \iff (x \in S \text{ for some } S \in A)$$

Thoughts

The Axiom of Union 3.12 is a generalisation of Axiom of Pairwise Union 3.5. 

This suggests we should apply the given constraints to Axiom 3.12 to yield 3.5.

Solution

Consider two sets, $A$ and $B$. 

Axiom 3.1 tells us these sets are objects. As such they can be considered elements of other sets.

Axiom 3.4 for pair sets tells us that two objects A and B, then there exists a s set $C = \{A, B\}$ whose only elements are $A$ and $B$. In our case, $A$ and $B$ are also sets themselves.

Axion 3.12 tells us that there exists a set $\bigcup C$ whose elements are precisely those objects which are elements of the elements of $C$. That is,  the elements of $\bigcup C$ are the elements of $A$ or $B$, or both.

$$ x \in \bigcup \{A,B\} \iff (x \in A \lor x \in B)$$

This is the definition of a pairwise set of $A$ and $B$, this Axiom 3.5 follows from Axions 3.1, 3.4 and 3.12. $\square$