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.

  • 2
    $\begingroup$ "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. $\endgroup$ – JMoravitz Jul 25 '18 at 22:22
  • $\begingroup$ 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$? $\endgroup$ – user2780519 Jul 25 '18 at 22:37
  • $\begingroup$ 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$..." $\endgroup$ – JMoravitz Jul 25 '18 at 22:40
  • $\begingroup$ Cheers, I always end up missing an edge case or two.. $\endgroup$ – user2780519 Jul 25 '18 at 22:47

If we rewrite the proof, the flaw becomes more apparent:

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.