Proof

Printable View

February 4th 2007, 05:26 AM
mauro21pl

1 Attachment(s)

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}<br /> 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) \\ <br /> & \Leftrightarrow & \left[ {\exists k,1 \le k \le K} \right]\left( {x \in \left( {E_k } \right)'} \right) \\ <br /> & \Leftrightarrow & x \in \left( {\bigcup\limits_{i = 1}^K {\left( {E_i } \right)'} } \right) \\ <br /> \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} .$