Ellie Benjamin

2022-07-10

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?
$\left(A×B{\right)}^{C}=\left({A}^{C}×{B}^{C}\right)\cup \left({A}^{C}×B\right)\cup \left(A×{B}^{C}\right)$
I wanted to do it like this:
$A×B=\left\{\left(a,b\right)\in A×B|a\in A\wedge b\in B\right\}$
Taking complement, $\overline{A×B}=\left\{\left(a,b\right)\notin A×B|a\notin A\vee b\notin B\right\}$
Because $\left(a,b\right)\notin A×B$ prevents me from going anywhere, I chose to do:
Let $A×B\subseteq X×Y$
Then, $A×B=\left\{\left(a,b\right)\in X×Y|a\in A\wedge b\in B\right\}$ and $\overline{A×B}=\left\{\left(a,b\right)\in X×Y|a\notin A\vee b\notin B\right\}$
But I'm unsure about the correctness of what I did from here.
$\overline{A×B}=\left\{\left(a,b\right)\in X×Y|\left(a\notin A\wedge b\notin B\right)\vee \left(a\notin A\wedge b\in B\right)\vee \left(a\in A\wedge b\notin B\right)\right\}$
Therefore, $\overline{A×B}=\left\{\left(a,b\right)\in X×Y|\left(a\notin A\wedge b\notin B\right)\right\}\cup \left\{\left(a,b\right)\in X×Y|\left(a\notin A\wedge b\in B\right)\right\}\cup \left\{\left(a,b\right)\in X×Y|\left(a\in A\wedge b\notin B\right)\right\}$ which gives
We know $A×B\subseteq A×B$.
Hence, $\overline{A×B}=\left(\overline{A}×\overline{B}\right)\cup \left(\overline{A}×B\right)\cup \left(A×\overline{B}\right)$.
"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

talhekh

Step 1
Regarding the query in the title of the Q: Suppose $x\in A$ and $y\in A$ with $x\ne y.$. Let $B=C=\left\{x\right\}.$. Then $B×C=\left\{\left(x,x\right)\right\}.$.
Step 2
Now the complement $X=\left(A×A\right)\setminus \left(B×C\right)$ is not the Cartesian product $D×E$ for any D, E.
Because if $X=D×E$ then $\left(x,y\right)\in X\phantom{\rule{thickmathspace}{0ex}}⟹\phantom{\rule{thickmathspace}{0ex}}x\in D$ and also $\left(y,x\right)\in X\phantom{\rule{thickmathspace}{0ex}}⟹\phantom{\rule{thickmathspace}{0ex}}x\in E.$. Hence $\left(x\in D\wedge x\in E\right),$, so $\left(x,x\right)\in D×E=X,$, which is absurd.

Callum Dudley

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\vee 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.
Step 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 \left(b\notin B\vee b\in B\right)$, this is just $\varphi \wedge \mathrm{\top }$, which is equivalent to $\varphi$
4. Distribute to get $\left(a\notin A\wedge b\notin B\right)\vee \left(a\notin A\wedge b\in B\right)$
5. Finally, disjoin the last disjunct and convert into the desired form
Step 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\vee 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

Do you have a similar question?