In the proof for one of De Morgan's Theorems: $A\setminus (B\cup C)=(A\setminus B)\cap (A\setminus C)$ I'm failing to follow one of the steps. If we let $x\in A\setminus (B \cup C)$ then $x\in A$ and $x\notin (B\cup C)$, all of this makes sense to me but they lose me at the next step where they rewrite this as: $x\in A$ and $(x\notin B\mbox{ and } x\notin C)$. I don't understand how they can change it from "or" to "and". I can kind of see whats happening though since if $x\in A$ and $x\notin (B\cup C)$ then I think we have $x\in A$ or $x\in (B\cup C)$.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ For these types of problems, sketching a Venn diagram can help to get an idea of what you are trying to prove and how to prove it. If you have (at least a sketch) of the proof in your head, it will be much easier to follow the one on paper. $\endgroup$– Dan RobertsonOct 21, 2015 at 1:02
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
If $x\notin(B\cup C)$ then $x\notin B \wedge x\notin C$.
If an element is not in the union of the sets, then it is not in either of sets. So it is not in one, and it is not in the other.
"Xavier is not enrolled in Business or Chemistry," said George.
"You mean that Xavier is not in Business," said Jean, "and that Xavier is not in Chemistry either?"
"That is what I said," affirmed George.
answered Oct 21, 2015 at 1:15
$\begingroup$
$\endgroup$
If $x$ is not in the union of $B$ and $C$, that means that the statement "$x\in B\cup C$" is false.
That statement is equivalent to the statement "$x\in B$ OR $x\in C$". The statement $p$ or $q$ is only false if both $p$ and $q$ are false.
Therefore, in order for $x\in B\cup C$ to be false, both the statement $x\in B$ and the statement $x\in C$ must be false.
The logic I described is basically the most famous De Morgan's law, which states that $$(A\cup B)^c = A^c \cap B^c$$
where $A^c$ denotes the complement of $A$.
