# How to show that the complement of Cartesian product of two non-empty sets is not the same as the Cartesian product of their complements?

I am having trouble deriving the property of Cartesian product of sets as shown here:

I wanted to do it like this:

$$A \times B = \{ (a, b) \in A\times B \vert a \in A \wedge b\in B\}$$

Taking complement, $$\overline {A \times B} = \{ (a, b) \notin A\times B \vert a \notin A \vee b\notin B\}$$

Because $$(a,b) \notin A \times B$$ prevents me from going anywhere, I chose to do:

Let $$A \times B \subseteq X \times Y$$

Then, $$A \times B = \{ (a, b) \in X\times Y \vert a \in A \wedge b\in B\}$$

and $$\overline {A \times B} = \{ (a, b) \in X\times Y \vert a \notin A \vee b\notin B\}$$

But I'm unsure about the correctness of what I did from here.

$$\overline {A \times B} = \{ (a, b) \in X\times Y \vert (a \notin A \wedge b\notin B) \vee (a\notin A \wedge b\in B) \vee (a\in A \wedge b\notin B)\}$$

Therefore, $$\overline {A \times B} = \{ (a, b) \in X\times Y \vert (a \notin A \wedge b\notin B)\} \cup \{ (a, b) \in X\times Y \vert (a\notin A \wedge b\in B)\} \cup \{ (a, b) \in X\times Y \vert (a\in A \wedge b\notin B)\}$$, which gives

We know $$A\times B \subseteq A \times B$$.

Hence, $$\overline {A \times B} = ( \bar A \times \bar B) \cup (\bar A \times B) \cup (A \times \bar B)$$

Is my logic correct here? Any help would be much appreciated :)

Edit: "derive" instead of "prove" because I don't need to prove the equivalence per se. I'm just trying to see how the LHS can lead to the RHS. I should've been more careful about the wording

Regarding the query in the title of the Q: Suppose $$x\in A$$ and $$y\in A$$ with $$x\ne y.$$ Let $$B=C=\{x\}.$$ Then $$B\times C=\{(x,x)\}.$$

Now the complement $$X=(A\times A)\setminus (B\times C)$$ is not the Cartesian product $$D\times E$$ for $$any$$ $$D, E.$$

Because if $$X=D\times E$$ then $$(x,y)\in X\implies x\in D$$ and also $$(y,x)\in X\implies x\in E.$$ Hence $$(x\in D \land x\in E),$$ so $$(x,x)\in D\times E =X,$$ which is absurd.

To demonstrate that 2 sets equal each other we need to show they're both subsets of each other. To do that, assume one side and derive the other.

Let's start with assuming $$a\notin A\lor b\notin B$$

To derive a conclusion from a disjunction we need to derive said conclusion from each disjunct. This is proof by cases, or disjunction elimination.

Case 1

1. Assume $$a\notin A$$
2. The conclusion contains a conjunction, so we need to add that in. We can only do that if we don't change the meaning of the formula. This is the logic equivalent of adding 0 to an equation.
3. $$a\notin A\wedge (b\notin B\lor b\in B)$$, this is just $$\phi\wedge\top$$, which is equivalent to $$\phi$$
4. Distribute to get $$(a\notin A\wedge b\notin B)\lor(a\notin A\wedge b\in B)$$
5. Finally, disjoin the last disjunct and convert into the desired form

Case 2

• Assume $$b\notin B$$ and follow a similar procedure to Case 1

• From each disjunct we've derived the same conclusion, hence we've derived the conclusion from the disjunction

The details and the other direction I'll leave to you.

Edit:

If you prefer a more semantic approach, assume 1 side is true and the other is false and derive a contradiction. Repeat for the other direction.

Example:

If $$a\notin A\lor b\notin B$$ is false then $$a\in A\wedge b\in B$$. Notice that this isn't true for any disjunct in the formula we're saying is true, hence a contradiction. Again, I'll leave you to fill in the details