1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Extending De Morgan to infinite number of sets

  1. Jun 30, 2010 #1
    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.

    1. The problem statement, all variables and given/known data
    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.

    2. Relevant 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?

    3. 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.
    Last edited: Jun 30, 2010
  2. jcsd
  3. Jun 30, 2010 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
    Last edited: Jun 30, 2010
  4. Jul 1, 2010 #3
    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.
  5. Jul 1, 2010 #4
    Thanks a lot!

    Seems keeping things simple works here. It's really interesting to have to think about these kinds of problems though.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook