How do you prove this proposition from set theory, where $\overline X$ denotes the complement of $X$?


My gut feeling tells me to apply De Morgan Law but I don't know how to go about this. Thank you!

  • $\begingroup$ Does the overline denote complement or closure? $\endgroup$ – mxnoqwerty Oct 8 '18 at 0:13
  • $\begingroup$ @mrnoqwerty - I rather suspect complement $\endgroup$ – Henry Oct 8 '18 at 0:14
  • $\begingroup$ It denotes complement. $\endgroup$ – James Warthington Oct 8 '18 at 0:15
  • 1
    $\begingroup$ This is not true. The left-hand side is the entire universe. $\endgroup$ – David Peterson Oct 8 '18 at 0:25

This is false if your space is $\{0\}$ and $A=B=\emptyset$. Because $\overline{A}=\overline{B}=\{0\}$, the left hand side becomes $\overline{\{0\}}\cup\overline{\emptyset}=\emptyset\cup\{0\}=\{0\}$ which is not $A$.

What is true, is that $\overline{\overline{A}\cup\overline{B}}\cup\overline{\overline{A}\cup B}=A$.

Proof in words:

If we have $\overline{V\cup W}$, this is everything not in $V\cup W$, so everything neither in $V$ nor $W$. Hence $\overline{V\cup W}=\overline{V}\cap\overline{W}$. So we get $\overline{\overline{A}\cup\overline{B}}\cup\overline{\overline{A}\cup B}=(A\cap B)\cup(A\cap\overline{B})=A\cap(B\cup\overline{B})=A$.


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.