# Proving that $\lnot(A \cup B) = \lnot A \cap \lnot B$

I'm working on proving the case above thusly:

Note: I should point out that i'm using the $\lnot$ symbol in place of the complement bar that should go over the letters, as i can't seem to get that formatted on this site.

In the first case of $\lnot(A \cup B)$, we know that for every item $x, x \in \lnot (A \cup B)$, which is to say >$x \notin A \cup B$.

From this, we know that $x \notin A$ and $x \notin B$. By the definition of complements, we can conclude that $x\in \lnot A$ and $x \in \lnot B$. As such, $x \in \lnot A \cap \lnot B$, which proves that $\lnot (A \cup B) \subseteq \lnot A \cap \lnot B$.

In the second case of $\lnot A \cap \lnot B$, we know that for every item $x, x \in \lnot A \cap \lnot B$, which is to say that $x \notin A \cap B$.

From this, we can conclude that $x \notin A$ or $x \notin B$. As such, its clear that $x \in \notin A$ or $x \in \lnot B$. Further, from the definition of a union, we can conclude that $x \in \lnot (A \cup B)$, which proves that $\lnot A \cap \lnot B \subseteq \lnot (A \cup B)$.

As such, we have proven that $\lnot (A \cup B) = \lnot A \cap \lnot B$ by proving that $\lnot (A \cup B) \subseteq \lnot A \cap \lnot B$ and that $\lnot A \cap \lnot B \subseteq \lnot (A \cup B)$.

According to my instructor, the part where i say "in the second case" is where i start to go wrong, however i don't really see what i'm doing incorrectly even after having reviewed the textbook and searched around these forums.

help?

-
You get $\overline{A}$ with \overline{A}. –  Brian M. Scott Dec 9 '12 at 21:29

Your strategy is right. You want to prove that (i) any element of the left-hand set is an element of the right-hand set and (ii) any element of the right-hand set is an element of the left-hand set.

Task (i) was carried out successfully, though I would not call it the first case.

Task (ii) was (at least) not written out correctly. We do not know something about every item, but we do know that any element $x$ of $\lnot A \cap \lnot B$ is simultaneously an element of $\lnot A$ and $\lnot B$. You say "which is to say $x\not\in A\cap B$." The "which is to say" is wrong, at least if by "which is to say" you mean that the two assertions are equivalent.

Then you say that $x\not\in A$ or $x\notin B$. True, but not helpful. From this you cannot conclude that $x\in \lnot(A\cup B)$. For we can have the "or if $x\not\in A$ but $x\in B$.

The correct way to proceed is to say that since $x\in \lnot A \cap \lnot B$, we have $x\not\in A$ and $x\not\in B$. (The crucial difference is that in what you wrote, you used or.) From this it follows that $x\not\in A\cup B$, and therefore $x$ is an element of the left-hand set.

-

Your problem is not saying $x \in ¬A \cap ¬B \implies x \in ¬(A \cap B)$. This is not true.

-

$x \in \neg A \cap \neg B$ means that $x \notin A$ AND $x \notin B$, whereas you said OR. This implies that $x \notin A \cap B$ but is not equivalent to it.

-
Would this make more sense then: In the second case of ¬A ∩ ¬B, we know that for every item x, x ∈ ¬A ∩ ¬B, which is to say that ¬(x ∈ (A ∩ B)). From this, we can conclude that ¬(x ∈ A) or ¬(x ∈ B). As such, its clear that x ∈ ¬A or x ∈ ¬B. Further, from the definition of a union, we can conclude that x ∈ ¬(A ∪ B), which proves that ¬A ∩ ¬B ⊆ ¬(A ∪ B). –  James Barnard Dec 9 '12 at 20:12
@JamesBarnard That looks good to me. For consistency, I suggest that you use the same notation for both halves of your proof. That is either stick with using $\not\in$ in the second half or change the first half to use $\neg ( blah )$. –  Code-Guru Dec 9 '12 at 20:16
No, it is wrong when you say "which is to say that" since the implication is one way whereas "which is to say that" sort of means that the implication is both ways. What I would say is "Which implies that" or "which means that". Other than that, it looks fine, although I agree with Code-Guru's notational advice. –  Tom Oldfield Dec 9 '12 at 20:21