# Proof

• February 4th 2007, 05:26 AM
mauro21pl
Proof
Hi guys
Could anybody help me with the proof
Attachment 1668
Appreipriate it
• February 4th 2007, 12:13 PM
topsquark
Quote:

Originally Posted by mauro21pl
Hi guys
Could anybody help me with the proof
Attachment 1668
Appreipriate it

I don't have my book with me at the moment (and I don't trust myself to do the full proof without it, no matter how elementary), so I won't do the whole thing, but think about this as an induction proof. De Morgan's Law holds for two sets. Can you think of a way to show that if it holds for N sets that it will also hold for N+1? (Given that it holds for 2 sets.)

-Dan

Note: I'm having some thoughts about this for $N \to \infty$. I don't know if you might not run into trouble with that. But as your problem specifies an "n" as an upper index you should be fine for your proof.
• February 4th 2007, 01:11 PM
Plato
There are two basic ways to prove this.
First by DeMorgan quantification rules:
$\begin{array}{rcl}
x \notin \left( {\bigcap\limits_{i = 1}^K {E_i } } \right) & \Leftrightarrow & \left[ {\exists k,1 \le k \le K} \right]\left( {x \notin E_k } \right) \\
& \Leftrightarrow & \left[ {\exists k,1 \le k \le K} \right]\left( {x \in \left( {E_k } \right)'} \right) \\
& \Leftrightarrow & x \in \left( {\bigcup\limits_{i = 1}^K {\left( {E_i } \right)'} } \right) \\
\end{array}.$

The other is by induction.
$\left( {E_1 \cap E_2 } \right)' = \left( {E_1 ' \cup E_2 '} \right).$
Then note $\left( {\bigcap\limits_{i = 1}^{K + 1} {E_i } } \right) = \left( {\bigcap\limits_{i = 1}^K {E_i } } \right) \cap E_{K + 1} .$