# how can you use a counter example to prove that the complement of a cartesian product is not its constituents

So how do you prove with an example that

$$(A\times B)^c \not\subset A^c\times B^c$$

Let's say I define the Universal set to be $\{1, 2, 3, 4\}$, $A = \{2,4\}$, $B = \{3,4\}$, $A^c = \{1,3\}$, and $B^c = \{1,2\}$.

You are basically done. Just compute the cartesian products and observe that they are not equal:

\begin{align*} (A\times B)^c &= \{(2,3),(2,4),(4,3),(4,4)\}^C \\ &= \{(1,1),(1,2),(1,3),(1,4),(2,1),(2,2),(3,1),(3,2),(3,3),(3,4),(4,1),(4,2)\} \end{align*} and $$A^c\times B^c=\{(1,1),(1,2),(3,1),(3,2)\}.$$

One thing to note is that it is assumed the universal set to which the complement $(A\times B)^c$ is taken is $\{1,2,3,4\}\times\{1,2,3,4\}$.

Also, it just so happened that $A^c\times B^c\subseteq (A\times B)^c$. Is this true in general? It is! To see this, suppose $(x,y)\in A^c\times B^c$. Then $x\in A^c$ and $y\in B^c$, so we cannot have $(x,y)\in A\times B$. Hence $(x,y)\in (A\times B)^c$.

• but isn't {(1,1), (1,2), (3,1), (2,3)} in (AxB) complement so doesn't that make A complement x B complement a subset of (AxB) complement? Sep 13, 2017 at 2:29
• @user510 In the particular example, they are subsets. To verify if that is a general fact, one has to prove it. See the end of my answer where I do just that. Sep 13, 2017 at 2:31
• But I want to show a counterexample that will give me the result to be false and not a a general solution. So do I have to pick other values for A and B? Sep 13, 2017 at 2:48
• No, since you've found an example where the equality does not hold, you've shown that this equality is not generally true (otherwise it would have to hold in your example). Sep 13, 2017 at 2:50
• nvm i got it thank you Sep 13, 2017 at 20:16

I've included a proof by picture below, for a less formal approach that gives the main idea:

• i get they are not equal, I want an counterexample that shows that fact though Sep 13, 2017 at 2:50
• You've found one, as @JohnGriffin showed. Sep 13, 2017 at 2:52
• but that example is showing that they are subsets. Can you explain me how its not showing that Sep 13, 2017 at 3:03
• @user510 Why do you keep talking about subsets when the question is about equality? $X$ being a subset of $Y$ is not an obstacle to proving that $X \ne Y$, not in the slightest. Sep 13, 2017 at 3:23