Extending De Morgan to infinite number of sets

[faklif]

I'm using my summer vacation to try to improve my understanding of real analysis on my own but it seems it's not as easy when not having a teacher at hand so I've a small question.

Homework Statement

The problem concerns extending a De Morgan relation to more than two sets and then, if possible, to infinity.

From [tex]\neg(A_{1} \cap A_{2}) = \neg A_{1} \cup \neg A_{2}[/tex] I've proved using induction that the same kind of relation holds for n sets [tex]\neg(A_{1} \cap A_{2} \cap ... \cap A_{n}) = \neg A_{1} \cup \neg A_{2} \cup ... \cup \neg A_{n}. [/tex]

So now the problem becomes to explain why induction will not work to extend the relation to an infinite number of sets and then to prove the relation in another way if it is true. I've started on the first part of this but I'm not there yet.

Homework Equations

There's a hint that one could possibly look at an earlier problem:
If [tex]A_{1} \supseteq A_{2} \supseteq A_{3} ...[/tex] are all sets containing an infinite number of elements, is the intersection [tex]\cap_{n\in N}A_{n}[/tex] infinite as well?

The Attempt at a Solution

I think the answer to the previous exercise is no. Looking at [tex]A_{n} = [0,1/n][/tex] which contains an infinite number of elements for any n but when taking the intersection only the element 0 remains. This would meen that there is a fundamental difference between the finite and infinite intersections. I'm not really getting anywhere when it comes to giving a clear reason why induction will not work though.

 

[jbunniii]

The De Morgan laws are valid for an infinite (even uncountable) collection of sets. However, proof by induction by its very nature is a tool to prove that an assertion [itex]P(n)[/itex] is true for all (FINITE) positive integer values of [itex]n[/itex]. It cannot prove "[itex]P(\infty)[/itex]", which is essentially what you are trying to do.

I don't know how formal a proof you are looking for, but an argument proving that

[tex]\left(\bigcap_{i \in I} A_i\right)^c = \bigcup_{i \in I} A_i^c[/tex]

is straightforward. (Here, [itex]I[/itex] is an arbitrary index set that can be finite or infinite (countable or uncountable, it makes no difference).)

[tex]x \in \left(\bigcap_{i \in I} A_i\right)^c[/tex]

means precisely that [itex]x[/itex] is not in every [itex]A_i[/itex], so there is some [itex]i \in I[/itex] such that [itex]x \in A_i^c[/itex] and therefore

[tex]x \in \bigcup_{i \in I} A_i^c[/tex]

Thus we have shown that

[tex]\left(\bigcap_{i \in I} A_i\right)^c \subseteq \bigcup_{i \in I} A_i^c[/tex]

The reverse inclusion is similar.

P.S. You are correct that the answer to the hint is "no," and your counterexample is fine. However, I don't see how it has any bearing on proving De Morgan's laws.

 

[Tedjn]

To add onto the excellent answer above, a correct proof for an arbitrary collection of sets is actually just an extension of the proof for two sets. You use the definitions for arbitrary unions and intersections instead of the definitions for unions and intersections of two sets.

 

[faklif]

Thanks a lot!

Seems keeping things simple works here. It's really interesting to have to think about these kinds of problems though.