# Disproving If $S\subseteq A\times B$ then $\exists C,D (C\subseteq A \wedge D\subseteq B\wedge S=C\times D)$

Prove/disprove:

Let $A,B,S$ be sets such that $S\subseteq A\times B$ then $\exists C,D (C\subseteq A \wedge D\subseteq B\wedge S=C\times D)$

For example, take $S=\{(1,1),(2,2)\}, A\times B=\{1,2,3\}\times\{1,2\}$ so there is no subset $C,D$ of $A,B$ such that $S=C\times D$.

My attempt to disprove this:

Let $S\subseteq A\times B$ such that $S=\{(a_0,b_0\},(a_1,b_1)\}$ such that $a_0\neq a_1, b_0\neq b_1$ So $C\cup D$ must have at least two elements, suppose $C\cup D =\{b_0,a_1\}$ so $C\times D$ could never be $\{(a_0,b_0\},(a_1,b_1)\}$.

• The example you mention is enough allready as a proof that it is not true in general. – drhab Feb 7 '15 at 13:01
• @drhab isn't it necessary to show that there are no subsets in general? i.e. to show that for all subsets $C,D$ we have $S\neq C\times D$? – shinzou Feb 7 '15 at 13:02
• No. And also you cannot prove that. Starting with subsets $C\subseteq A$ and $D\subseteq B$ you can define $S:=C\times D\subseteq A\times B$. It is enough to find a counterexample (as you did). That shows that the statement is not true in general. – drhab Feb 7 '15 at 13:08
• To add something to what drhab is saying, for the given example, you still need to prove that it is false that $\exists C,D (C\subseteq A \wedge D\subseteq B(S=C\times D))$. – Git Gud Feb 7 '15 at 13:09
• Also, by the way, if you want to prove something in general you need to be sure to be general -- but when you're giving a counterexample it is okay to be concrete. So for your counterexample you can just set $S=\{(1,1),(2,2)\}$ and $A=B=\{1,2\}$, for example. You still need to argue that no combination of $C$ and $D$ would work, but you don't need to clutter the argument with assumptions that $1\ne 2$, because that is just true. – Henning Makholm Feb 7 '15 at 13:18

## 1 Answer

You're correct in giving a counterexample, and the counterexample is correct. But you do need to show the example is correct.

So following your example $A = \{1,2,3\}, B = \{1,2\}$, and $S = \{(1,1), (2,2)\}$.

Suppose there exists $C \subseteq A, D \subseteq B$ such that $C \times D = S$.

This means, as $(1,1) \in S$ that $1 \in C, 1 \in D$. Also, as $(2,2) \in S$ we know that $2 \in C, 2 \in D$. But then $(1,2) \in C \times D$, while $(1,2) \notin S$. Contradiction. So no such $C$ and $D$ can exist.