Proving DeMorgan's Theorem I'm trying to prove that (without using logical equivalencies):
$\overline{A\cap B} = \bar A \cup \bar B$
by proving both sides:
(1) $ x \in \overline{A\cap B} \to x \in \bar A\cup\bar B$
(2) $ x \in \bar A\cup\bar B \to x \in \overline{A\cap B}$
I figured out the 2nd part, but I'm struggling with the first. The only thing I'm confident about now is:
Let $x \in \overline{A\cap B}$. We prove that $x \in \bar A\cup \bar B$. By definition of complement, $x \not\in A\cap B$.
I'm not sure if I should use cases, or if I should prove by contradictions. With the other variation of DeMorgan's, I could assume $x \in A$ and $x \in B$ and they would lead to contradictions with the first assumption, but I can't do that here because it's a $\cap$ instead of a $\cup$.
For reference, here's the proof I was given for the other variation of DeMorgan's:
Prove: $\overline{A \cup B} = \bar A \cap \bar B$
(1) if $x \in \overline{A \cup B}$ then $x \in \bar A \cap \bar B$
(2) if $x \in \bar A \cap \bar B$ then $x \in \overline{A \cup B}$
Proof:
(1)Let $x \in \overline{A \cup B}$. We prove that $x \in \bar A \cap \bar B$. By definition of complement, $x \not\in A \cup B$. Suppose, for contradiction, $x \not\in \bar A$. By definition of complement, $x \in A$, and by definition of union, $x \in A\cup B$, a contradiction. Thus, $x \in \bar A$. Now, suppose for contradiction, $x \not\in \bar B$. By definition of complement, $x \in B$, and by definition of union, $x \in A \cup B$, a contradiction. So, $x \in \bar B$. Therefore, $x \in \bar A$ and $x \in \bar B$, so by definition of intersection, $x \in \bar A \cap \bar B$.
(I'm leaving out the 2nd part, as I've figured out the 2nd part in my problem above)
Any ideas? I'm assuming it has to be of similar complexity.
 A: Let $x\in \overline{A\cap B}$. Then, by definition, $x\notin A\cap B$, thus $x\notin A$ or $x\notin B$. For suppose to the contrary, that $x\in A$ and $x\in B$. Then it is the case that $x\in A\cap B$, hence $x\notin \overline{A\cap B}$, a contradiction to our assumption. So we have $x\in\overline{A}$ or $x\in\overline{B}$; combining these two, we have $x\in\overline{A}\cup \overline{B}$.
A: Yes, you've got $x\notin A\cap B$ correct. If you're allowed to use the variation on DeMorgan's you were given. $A\cap B = \overline{\bar{A}\cup \bar{B}},$ from which $x\notin \overline{\bar{A}\cup \bar{B}},$ so $x\in \bar{A} \cup \bar{B}.$ If you're not, then just prove the other variation and use it :)
A: DeMorgan revolves around two principles 


*

*$\sim \forall x P(x) \iff \exists x \sim P(x)$.

*$\sim \exists x P(x) \iff \forall x \sim P(x)$.


That's all folks!
A: $n \in \overline{A \cap B}$. 
then $n \not \in A \cap B$ 
$n$ may exist in either $A$ or in $B$ but not both.
We can then be certain that $n \in \overline{A}$ or $n \in \overline{B}$. 
Because the element $n$ is contained in either $\overline{A}$ or $\overline{B}$ we can be sure that $\overline{A} \cup \overline{B}$ contains the element $n$.
$n \in \overline{A} \cup \overline{B}$
so $n \not\in A \cup B$ thus $n \not \in A $ or $n \not \in B$
we can then determine $n \not \in A \cap B$.
Finally by the definition of a complement we can state that $n \in \overline{A \cap B}$  which proves our theorem that $\overline{A \cap B}= \bar A \cup \bar B$.
