I have been trying to figure out the proof for this for the past 3 hours since our teacher hasn't covered it and gave it on the homework. Any help, hints, and clues are appreciated!
If the following statement is true, prove it. If it is false give a counterexample showing
it is false.
For all sets A, B inside universal set U, A^c × B^c = (A × B)^c
(The "c"s in the question are complements (complement of A x complement of B…)
Best Answer
It is worth pointing out that when talking about a universal set $U$ which contains $A$, that $A^c$ is in reference to $U\setminus A$. Meanwhile, when talking about complements of $A\times B$, it only makes sense in this context to be referring to $A\times B$'s complement with respect to the universal set $U\times U$.
Finishing my proposed counterexample from the comments...
Letting $A = B = \{1\}$ and $U=\{1,2\}$, we have:
$A^c\times B^c = (U\setminus A)\times (U\setminus B) = (\{1,2\}\setminus \{1\})\times (\{1,2\}\setminus \{1\}) = \{2\}\times \{2\} = \{(2,2)\}$
On the other hand $(A\times B)^c = (U\times U)\setminus (A\times B) = (\{1,2\}\times \{1,2\})\setminus (\{1\}\times \{1\})$
$ = \{(1,1),(1,2),(2,1),(2,2)\}\setminus \{(1,1)\} = \{(1,2),(2,1),(2,2)\}$
These are clearly not the same set in this case.
Indeed, most examples you try will be such that the sets are different. Looking at the sizes of the sets involved... letting the universal set be finite and be of size $n$, letting $A$ be of size $a$, and letting $B$ be of size $b$, we have:
$|A^c\times B^c| = |A^c|\times |B^c| = (n-a)\times (n-b) = n^2-an-bn+ab$
Meanwhile, $|(A\times B)^c| = n^2 - |A\times B| = n^2 - |A|\times |B| = n^2-ab$
If these happened to be equal to each other, then that would imply $2ab = an+bn$, which does not happen very often... An example of where it would happen is if the universal set had only one element such as $U=\{1\}$. Conversely, so long as $2ab$ is not equal to $an+bn$, then we know for certain that $A^c\times B^c$ could not equal $(A\times B)^c$