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.