1
$\begingroup$

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)\}$.

$\endgroup$
  • $\begingroup$ The example you mention is enough allready as a proof that it is not true in general. $\endgroup$ – drhab Feb 7 '15 at 13:01
  • $\begingroup$ @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$? $\endgroup$ – shinzou Feb 7 '15 at 13:02
  • 1
    $\begingroup$ 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. $\endgroup$ – drhab Feb 7 '15 at 13:08
  • $\begingroup$ 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))$. $\endgroup$ – Git Gud Feb 7 '15 at 13:09
  • 1
    $\begingroup$ 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. $\endgroup$ – Henning Makholm Feb 7 '15 at 13:18
1
$\begingroup$

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.

$\endgroup$

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.