0
$\begingroup$

Let $X$ be a set and $A\subset X$ and $B\subset X$.

$A\cap B = \emptyset$ iff $A^c\cup B^c = X$

Attempted proof - Suppose $A\cap B = \emptyset$ then $A$ and $B$ are two disjoint sets in $X$. Let $x\in A^c\cup B^c$ then $x\in A^c$ or $x\in B^c$ or both.

Not really sure how to proceed with this one any suggestions is greatly appreciated.

$\endgroup$
  • 1
    $\begingroup$ Look up "De Morgan law". $\endgroup$ – user228113 May 25 '16 at 16:58
2
$\begingroup$

Suppose $A$ and $B$ are disjoint sets in $X$ with complements $A^c$, $B^c$.

You know that each $x \in X$ that isn't in $B$ is in $B^c$. You also know that $a \in A \Rightarrow a \not\in B$ because $A$ and $B$ are disjoint. This implies that $A \subseteq B^c$.

Because $A \cup A^c = X$, $B^c \cup A^c = X $.

For simple set theory, the visualization of sets as groups of points on a two dimensional plot is intuitive.

disjoint sets

If you color in $A$ and $B$, the part of $U$ that isn't colored is the subset of $U$ not in $A$ or $B$. If you color in the complements $A^c$ and $B^c$, then $B^c$ overlaps $A$, the part of the graph which isn't covered by $A^c$. That is essentially a hand-wavy version of the proof I wrote above.

Obviously these kinds of representations are not acceptable proofs, but they can help build intuition and tie together your ability to write proofs with visualization of mathematical properties.

$\endgroup$
5
$\begingroup$

If we assume that

$$A \cap B = \emptyset,$$

Then by the rule of complements,

$$\iff (A \cap B)^c = (\emptyset)^c = X \setminus \emptyset = X$$

$$\iff (A \cap B)^c = A^c \cup B^c = X,$$

by De Morgan's laws.

$\endgroup$
2
$\begingroup$

While it is important to understand "automatic" things like De Morgan's laws, and to be able to apply them in as many situations as possible, it is also important to be able to solve problems like this one "from first principles" to make sure De Morgan's laws and such don't blind us to the real meaning of things.

In this case: Suppose $A \cap B = \emptyset$. We must show $A^C \cup B^C = X$. Equality of two sets means inclusion in both directions. $\subset$ is trivial; there is no reason to take $x \in A^C \cup B^C$. Rather, take $x\in X$. We must show $x \in A^C \cup B^C$. Well, $A \cap B = \emptyset$, so either $x \not \in A$ or $x \not\in B$ (or both), which means $x\in A^C$ or $x\in B^C$ (or both). Which is what we needed to show.

Letting you prove the converse: if $A^C \cup B^C = X$ then $A \cap B = \emptyset$. Start with any $x \in X$. You must show that $x\not\in A$ or $x\not\in B$ (or both). To prove that, use the assumption: $A^C \cup B^C = X$.

$\endgroup$

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.