User:IssaRice/Conjunction of subset statements versus Cartesian product subset statement

This is an exercise from Tao's Analysis I (exercise 3.5.6) and from Munkres's Topology (exercise 1.1.2(k)–(l)). It is an exercise that makes apparent some of the subtleties of the basic logic used in math.

The exercise is to consider the sets $A,B,C,D$ and the two statements:

1. $A\subseteq C$ and $B\subseteq D$; and
2. $A\times B\subseteq C\times D$;

and to ask whether one implies the other (or whether the two statements are equivalent).

Relationship between the statements

In general, (1) implies (2). In other words, if $A\subseteq C$ and $B\subseteq D$, then $A\times B\subseteq C\times D$.

If $A$ and $B$ are nonempty sets, then (1) and (2) are logically equivalent. In other words, $A\subseteq C$ and $B\subseteq D$ if and only if $A\times B\subseteq C\times D$.

If $A$ and $B$ are both empty, then (1) and (2) are logically equivalent; in fact, they are both true.

Each statement written out in first-order logic

1. $\forall x(x\in A\implies x\in C)\wedge \forall y(y\in B\implies y\in D)$
2. $\forall x\forall y((x\in A\wedge y\in B)\implies (x\in C\wedge y\in D))$

Erroneous general proof

Here is an erroneous general proof that (2) implies (1).

"Proof". Suppose $A\times B\subseteq C\times D$. We want to show that $A\subseteq C$ and $B\subseteq D$. Let $x\in A$ and $y\in B$. Then $(x,y)\in A\times B$. Since $A\times B\subseteq C\times D$ by assumption, this means $(x,y)\in C\times D$. Thus $x\in C$ and $y\in D$. Since $x$ and $y$ were arbitrary, this shows that $A\subseteq C$ and $B\subseteq D$ as desired. $\Box$

Exercise. Identify the error(s) in the proof. Specifically, state the first incorrect step.

Expand to see solution:

We want to show two things, $A\subseteq C$ and $B\subseteq D$. To simplify things, let's just focus on showing $A\subseteq C$. How did we go about this? We let $x\in A$ and $y\in B$, and eventually showed that $x\in C$. While the reasoning until here is valid, the problem is that this does not allow us to conclude that $A\subseteq C$, which is $\forall x(x\in A\implies x\in C)$. What we have instead shown is $\forall x\forall y(x\in A\land y\in B\implies x\in C)$. But there is no way to show that this is equivalent to what we actually want.

But if $B$ is non-empty, then instead of saying "let $y\in B$" we can instead at the very beginning of the proof say, "since $B$ is non-empty, there exists some $y_{0}\in B$". Then we can go through the rest of the proof to conclude $\forall x(x\in A\implies x\in C)$, which is what we wanted to show. This argument also shows that in order to prove $A\subseteq C$, it is the non-emptiness of $B$ specifically that we needed.

Now going back to the erroneous proof, what we showed overall was $\forall x\forall y((x\in A\land y\in B)\implies (x\in C\land y\in D))$. But this is just the statement that $A\times B\subseteq C\times D$, so we didn't actually prove anything new!

Counterexample

Here is a counterexample that shows that in general, (2) does not imply (1). Let $A:=\{1\}$, $B:=\emptyset$, $C:=\emptyset$, and $D:=\{1\}$. Then

$$A\times B=\{1\}\times \emptyset =\emptyset \subseteq \emptyset =\emptyset \times \{1\}=C\times D$$

but

$$A=\{1\}\not \subseteq \emptyset =C$$

Thus (2) is true but (1) is false.