I have some exercises to prove different laws of set theory but my study guide does not provide any answers for the exercise. I have completed one of the exercises and just want to make sure I am getting the correct answers.
$$(A\cap B)^c=A^c\cup B^c$$
I have:
Let $P(x) : x\in A$; $Q(y) : y\in B$
(I did this step because this is how the book started each example.)
$$\begin{align*}
(A\cap B)^c&\iff\neg\big(P(x)\land Q(y)\big)\\
&\iff\neg P(x)\lor\neg Q(y)\\
&\iff A^c\cup B^c
\end{align*}$$
Thanks for any help.
Tony
Best Answer
Your first and last $\iff$’s are meaningless, I’m afraid. The statement $P\iff Q$ means that either $P$ and $Q$ are both true, or $P$ and $Q$ are both false. In particular, $P$ and $Q$ have to be statements, things that can be true or false. $(A\cap B)^c$, however, is a set, not a statement: it can no more be true or false than a symphony can be pink.
The statement $\neg\big(P(x)\land Q(y)\big)$ actually says that it is not the case that $x\in A$ and $y\in B$. What are $x$ and $y$? They’ve come out of nowhere. What you want, I think, is to say that an object belongs to $(A\cap B)^c$ if and only if it is not the case that it belongs to $A$ and to $B$:
$$x\in(A\cap B)^c\iff\neg\big(P(x)\land Q(x)\big)\;.$$
Now you can proceed much as you did before, applying one of the logical De Morgan’s laws:
$$\neg\big(P(x)\land Q(x)\big)\iff\neg P(x)\lor\neg Q(x)\;.$$
That step was fine, except that you were working with an expression that wasn’t quite right to begin with. In the last step, however, you have the same problem that you had in the first step: $A^c\cup B^c$ is not a statement, so it makes no sense to connect it to something with $\iff$. What you want here is
$$\neg P(x)\lor\neg Q(x)\iff x\notin A\lor x\notin B\iff x\in A^c\lor x\in B^c\iff x\in A^c\cup B^c\;.$$
And since you have $\iff$ ‘if and only if’ at each step, this argument shows that the elements of $(A\cap B)^c$ are exactly the same as those of $A^c\cup B^c$ and hence that $(A\cap B)^c=A^c\cup B^c$: you’re done at that point.