# Which part of this theorem and corresponding proof about relations is incorrect?

I have a theorem and corresponding proof whose correctness I need to verify. The theorem is:

For any sets $A$, $B$, $C$, and $D$: $A$ x $B \subseteq C$ x $D$ $\implies$ $A \subseteq C$ $\land$ $B \subseteq D$

The proof is:

Suppose $A$ x $B \subseteq C$ x $D$. Let $a$ be an arbitrary element of $A$ and let $b$ be an aribtrary element of $B$. Then $(a, b) \in A$ x $B$. So since $A$ x $B \subseteq C$ x $D$, $(a, b) \in C$ x $D$. Therefore $a \in C$ and $b \in D$. Since $a$ and $b$ were arbitrary elements of $A$ and $B$, respectively, this shows that $A \subseteq C$ and $B \subseteq D$.

The above proof is demonstratably wrong with the case where $A = \{1\}$, and $B = C = D = \emptyset$, but I cannot find the flaw in the logic.

Following my own reasoning gives me:

$1)$ Assuming the 'P' of the conditional: $Givens = \{$$A x B \subseteq C x D\}, Goals = \{A \subseteq C, B \subseteq D\} 2) Assuming arbitrary a and b, assuming a \in A and b \in B: Givens = \{$$A$ x $B \subseteq C$ x $D, a \in A, b \in B\}$, $Goals = \{a \in C, b \in D\}$

$3)$ Note that $(a, b) \in A$ x $B \implies (a, b) \in C$ x $D \implies a \in C \land b \in D$

$4)$ Since $a \in A \land b \in B$, we can create an ordered pair, $(a, b)$ such that $(a, b) \in A$ x $B$, which appears to lead to the conclusion noted in $3)$, thus satisfying our goals.

Which is just a rambling version of the original proof.

• "Assuming $a\in A$ and $b\in B$" assumes that you can choose such an $a$ and $b$. In the case that $B$ is empty, of course such a choice is invalid. – JMoravitz Jul 25 '18 at 22:22
• Thank you, so a corrected form of the theorem would be: $A$ x $B \subseteq C$ x $D \land A \neq \emptyset \land B \neq \emptyset ...$ $\implies$ $A \subseteq C$ $\land$ $B \subseteq D$? – user2780519 Jul 25 '18 at 22:37
• Yes, alternatively to keep the statement cleaner you should include the restrictions on $A$ and $B$ when you define the variables: "For any non-empty sets $A,B,C,D$..." – JMoravitz Jul 25 '18 at 22:40
• Cheers, I always end up missing an edge case or two.. – user2780519 Jul 25 '18 at 22:47

Given arbitrary element $a$ of $A$, $a$ we can form an ordered pair $(a,b)$ where $b$ is in $B$. Since $(a,b)$ would then be in $AxB$, it follows that it is $CxD$, and thus $a$ is in $C$. A similar argument shows that $b$ is in $D$.
The flaw is in the "we can form an ordered pair $(a,b)$" part. If B is empty, then we can't form any ordered pairs containing $a$, and thus the proof that $a$ is in $C$ fails.