Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This problem I am trying to solve is one I alluded to in this thread: Proving By Subsets

I am having difficulty with proof by subsets, so I am aware that I am missing steps; I would certainly appreciate it if someone could help me with this.


Suppose that $x \in \overline{(A \cap B \cap C)}$; for $x$ to be in this set, $x$ can't be in $(A \cap B \cap C)$, that is, $X \notin (A \cap B \cap C)$. This means that $x$ can't be in $A$, $B$, and $C$ ; however, by this fact, $x$ can be in $\overline{A}$, $\overline{B}$, or $\overline{C}$. Thus, when $x \in \overline{(A \cap B \cap C)}$, $x$ is also in $\overline{A} \cup \overline{B} \cup \overline{C}$, further implying that $x \in \overline{(A \cap B \cap C)} \subseteq \overline{A} \cup \overline{B} \cup \overline{C}$

Now, suppose that $x \in \overline{A} \cup \overline{B} \cup \overline{C}$, then $x$ can't be in $A$, $B$, or $C$, which means that $x$ can be in everything else, or, $x$ can be in $\overline{(A \cap B \cap C)}$. This shows that $\overline{A} \cup \overline{B} \cup \overline{C} \subseteq \overline{(A \cap B \cap C)}$


As I said, it just seems as though steps are missing and reasons why I am able to conclude the various things that I do in my proof.

share|improve this question
    
@Mack A better description than proof by subsets would be proof by double inclusion. –  Git Gud Mar 17 '13 at 15:28
    
You second argument is wrong (the second suppose paragraph). It will become clear if you draw a venn diagram. –  Patrick Li Mar 17 '13 at 15:30

3 Answers 3

up vote 2 down vote accepted

Personally, I would write this down as a calculation using set extensionality: given sets $A$, $B$, and $C$, for every $x$ $$ \begin{align*} & x \in \overline{(A \cap B \cap C)} \\ \equiv & \;\;\;\;\; \text{"definition of set complement"} \\ & \lnot (x \in A \cap B \cap C) \\ \equiv & \;\;\;\;\; \text{"definition of $\cap$, twice"} \\ & \lnot (x \in A \land x \in B \land x \in C)) \\ (*) \equiv & \;\;\;\;\; \text{"logic: De Morgan, i.e., distribute $\lnot$ over $\land$"} \\ & \lnot (x \in A) \lor \lnot (x \in B) \lor \lnot (x \in C) \\ \equiv & \;\;\;\;\; \text{"definition of set complement, three times"} \\ & x \in \overline{A} \lor x \in \overline{B} \lor x \in \overline{C} \\ \equiv & \;\;\;\;\; \text{"definition of $\cup$, twice"} \\ & x \in \overline{A} \cup \overline{B} \cup \overline{C} \\ \end{align*} $$

and therefore the given two sets are equal.

Note how this translates set notation to logic notation, does essentially the same transformation in the key step $(*)$, and translates back.

(Yes, I know this is not a proof by subsets / double inclusion-- but in this case I don't see how that technique would lead to a clearer proof.)

share|improve this answer

Now suppose that $x \in \overline{A} \cup \overline{B} \cup \overline{C}$, then $x$ can't be in $A,B$ or $C$, is wrong, you only have $x$ can't be in $A,B$ and $C$.

Because $x \in \overline{A} \cup \overline{B} \cup \overline{C}$ is true iff $$x\in \overline A \vee x\in \overline{B} \vee x\in \overline{C}$$

share|improve this answer

We have $x\in \bar{A}\cup\bar{B}\cup\bar{C}$ then $x\in\bar{A}$ or $x\in\bar{B}$ or $x\in\bar{C}$ then $x\notin A$ or $x\notin B$ or $x\notin C$ which implies $x\notin A\cap B\cap C$

(otherwise, if $x\in A\cap B\cap C$ this will contradicts the fact that $x\in\bar{A}$ or $x\in\bar{B}$ or $x\in\bar{C}$)

which implies that $x\in\overline{A\cap B\cap C}$

Remark: in fact if you proved that $\overline{A\cap B}=\overline{A}\cup \overline{B}$ then you can show using induction that $$\displaystyle\overline{\bigcap_{i=1}^{n}A_i}=\bigcup_{i=1}^{n}\overline{A_i}, $$ for any $ n\in\Bbb N .$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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