# Proving two sets are equal using bi-directional set inclusion

Prove(A∩B)’=A’∪B’.
let x ∈ (A ∩ B)’
∴ (x ∈ A ∩ B)’
∴ (x ∈ A ∧ x ∈ B)’
∴ (x ∈ A)’ ∨ (x ∈ B)’
∴ x ∈ A’ ∨ x ∈ B’
∴ x ∈ A’ ∪ B’
∴ (A ∩ B)’ ⊆ A’ ∪ B’

The above is the solution provided. Sorry if it seems trivial but I don't understand how
∴ (x ∈ A ∧ x ∈ B)’
∴ (x ∈ A)’ ∨ (x ∈ B)’
and not
∴ (x ∈ A)’ ∧ (x ∈ B)’

-
If it is not true that ($2 + 2 = 4$ and I am the pope), then either $2 + 2 \neq 4$, or I am not the pope. But it is not the case that both $2 + 2 \neq 4$ and I am not the pope. en.wikipedia.org/wiki/De_Morgan%27s_laws –  Rahul Oct 21 '10 at 18:29
All that needs to happen to make the statement (A and B) false is for at least one of the parts to be false. This is equivalent to (not A or not B) being true. –  Paul VanKoughnett Oct 21 '10 at 18:38
For future reference, it would be clearer if you distinguished in your notation between set complement and logical negation. The standard symbol for the latter is prefix ¬, so the first 3 lines of your proof would read let x ∈ (A ∩ B)’ ∴ ¬(x ∈ A ∩ B) ∴ ¬(x ∈ A ∧ x ∈ B) –  Stewart Nov 20 '10 at 18:25

This is just one of DeMorgan's Laws. Not (A and B) is equivalent to (Not A) or (Not B), that is that (A and B) is false if either one is false. If you go to (Not A) and (Not B) you need both to be false.

-
Got it thanks. :) Was really confused cause I thought it had something to do with set identities. –  jon2512chua Oct 22 '10 at 14:57