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).