I would appreciate it if I could get some feedback on my attempt to proof De Morgan's Law. That is, if it is correct or if there is a better way to do this proof. I am self-studying probability theory from Grimmett and Stirzaker's book Probability and Random Processes and am going through the exercises. Thanks in advance.

Let ${A_i : i \in I}$ be a collection of sets.

$(\cup_{i} A_{i})^c = (A_1 \cup A_2 \cup A_3 \cup A_4 \ldots)^c$ $= (A_1 \cup A_2)^c \cup (A_3 \cup A_4)^c \cup \dots$ $= (A_{1}^c \cap A_{2}^c) \cup (A_{3}^c \cap A_{4}^c)\ldots$ $=(A_{1}^c \cap A_{2}^c \cap A_{3}^c \cap A_{4}^c \ldots)$ $=\cap_{i} A_{i}^c$

  • $\begingroup$ How'd you prove that $$\left(A_1\cup A_2\cup B\right)^c=(A_1\cup A_2)^c\cup B^c\;\;??$$ $\endgroup$ – DonAntonio Feb 2 '14 at 13:31
  • $\begingroup$ It's not correct. Your second equality is invalid. Prove by showing each side is a subset of the other. (In one direction: "Let $x$ be an element of the LHS. Do stuff using the definitions... So $x$ is an element of the RHS") $\endgroup$ – David Mitra Feb 2 '14 at 13:31

Perhaps simpler by definition:

$$x\in\left(\bigcup_i A_i\right)^c\iff x\notin\bigcup_i Ai\iff\;\forall\,i\;,\;x\notin A_i\iff$$

$$\iff \;\forall\,i\,,\;x\in A_i^c\iff x\in\bigcap_i A_i^c$$

  • $\begingroup$ I follow the reasoning here up to the last "iff". Please can you expand on that. $\endgroup$ – M.K. Feb 2 '14 at 14:02
  • 1
    $\begingroup$ @IftikharKhan, an element belongs to the intersection of some sets iff it belongs to each one of them (=to all of them)... $\endgroup$ – DonAntonio Feb 2 '14 at 14:04
  • $\begingroup$ Got it! This is a really nice proof. $\endgroup$ – M.K. Feb 2 '14 at 14:06
  • $\begingroup$ I am really bad with these types of questions (I come from an applied maths background). What is the best way to improve one's ability in this area in your opinion? $\endgroup$ – M.K. Feb 2 '14 at 14:08
  • $\begingroup$ Get the heck out of applied mathematics at once! Just kidding: try to follow 1-2 books on the subject (set theory, discrete mathematics) that appeal to you and do exercises there... $\endgroup$ – DonAntonio Feb 2 '14 at 14:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.