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