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.