1. ## Prove By Subsets

Hello all,

I am currently working on proving these statements $\displaystyle \overline{A \cap B \cap C}$ and $\displaystyle \overline{A}\cup \overline{B} \cup \overline{C}$, by means of subsets (I've heard that is is also referred to as, "proof by double inclusion."). I am having trouble with these sort of problems, so I'd certainly appreciate the help.

Here is my work:

Suppose that $\displaystyle x \in \overline{A \cap B \cap C}$; for $\displaystyle x$ to be in the set, $\displaystyle x$ can't be in $\displaystyle A \cap B \cap C$. This means that $\displaystyle x \notin A \wedge x \notin B \wedge x \notin C$; however, by this fact, $\displaystyle x$ can be in $\displaystyle \overline{A}$, $\displaystyle \overline{B}$, or $\displaystyle \overline{C}$. Thus, when $\displaystyle x \in $$\displaystyle \overline{A \cap B \cap C}, \displaystyle x is also in \displaystyle \overline{A}\cup \overline{B} \cup \overline{C}, meaning that \displaystyle \overline{A \cap B \cap C} \subseteq \overline{A}\cup \overline{B} \cup \overline{C} I have not commenced the second part, yet, because I feel as though there is something wrong with this, and I feel like I might have left out steps and explanations. 2. ## Re: Prove By Subsets Originally Posted by Bashyboy I am currently working on proving these statements \displaystyle \overline{A \cap B \cap C} and \displaystyle \overline{A}\cup \overline{B} \cup \overline{C}, by means of subsets (I've heard that is is also referred to as, "proof by double inclusion."). I am having trouble with these sort of problems, so I'd certainly appreciate the help. Here is my work: Suppose that \displaystyle x \in \overline{A \cap B \cap C}; for \displaystyle x to be in the set, \displaystyle x can't be in \displaystyle A \cap B \cap C. This means that \displaystyle x \notin A \wedge x \notin B \wedge x \notin C; however, by this fact, \displaystyle x can be in \displaystyle \overline{A}, \displaystyle \overline{B}, or \displaystyle \overline{C}. Thus, when \displaystyle x \in$$\displaystyle \overline{A \cap B \cap C}$, $\displaystyle x$ is also in $\displaystyle \overline{A}\cup \overline{B} \cup \overline{C}$, meaning that $\displaystyle \overline{A \cap B \cap C} \subseteq \overline{A}\cup \overline{B} \cup \overline{C}$

I have not commenced the second part, yet, because I feel as though there is something wrong with this, and I feel like I might have left out steps and explanations.
This is usually done by using induction.

What you have is not correct.

$\displaystyle x \in \overline {A \cap B \cap C} \to x \notin A \vee x \notin B \vee x \notin C$

3. ## Re: Prove By Subsets

Originally Posted by Plato
This is usually done by using induction.

What you have is not correct.

$\displaystyle x \in \overline {A \cap B \cap C} \to x \notin A \vee x \notin B \vee x \notin C$
I haven't learned about induction yet. Where did I write in my proof that $\displaystyle x \in \overline {A \cap B \cap C} \to x \notin A \vee x \notin B \vee x \notin C$? Isn't this what I am trying to prove?

4. ## Re: Prove By Subsets

Originally Posted by Bashyboy
I haven't learned about induction yet. Where did I write in my proof that $\displaystyle x \in \overline {A \cap B \cap C} \to x \notin A \vee x \notin B \vee x \notin C$? Isn't this what I am trying to prove?
I did not say you wrote that.

In fact you wrote is:
$\displaystyle x \in \overline{A \cap B \cap C}$; for $\displaystyle x$ to be in the set, $\displaystyle x$ can't be in $\displaystyle A \cap B \cap C$. This means that $\displaystyle x \notin A \wedge x \notin B \wedge x \notin C$.
That is FALSE.

What I posted is TRUE.

5. ## Re: Prove By Subsets

Oh, so the use of the disjunction means that x can't be in any of the three sets?

6. ## Re: Prove By Subsets

Originally Posted by Bashyboy
Oh, so the use of the disjunction means that x can't be in any of the three sets?
No again. It means that x is not in at least one of the three sets.

7. ## Re: Prove By Subsets

Okay, Plato, is this better:

Suppose that $\displaystyle x \in \overline{A \cap B \cap C}$, then $\displaystyle x$ can't be an element of $\displaystyle A \cap B \cap C$; in order for $\displaystyle x$ to not be in $\displaystyle A \cap B \cap C$, then it must be the case that $\displaystyle x \notin A \vee x \notin B \vee x \notin C$, that is, it must be the case that x is not in at least one of the three sets. If $\displaystyle x$ is not in at least in one of those sets, then $\displaystyle x \in A \vee x \in B \in C$, that is, it is at least in of the three sets $\displaystyle \overline {A}$, $\displaystyle \overline{B}$, or $\displaystyle \overline{C}$. By the definition of the union, the set $\displaystyle \overline{A} \cup \overline{B} \cup \overline{C}$ will possess the element $\displaystyle x$, because at least one of the three sets has $\displaystyle x$.

Would this show that the statement is a subset of the other?

8. ## Re: Prove By Subsets

And to prove that $\displaystyle \overline{A} \cup \overline{B} \cup \overline{C} \subseteq (\overline{A \cap B \cap C})$, would this be sufficient:

Suppose that $\displaystyle x \in \overline{A} \cup \overline{B} \cup \overline{C}$. For $\displaystyle x$ to be in the set, $\displaystyle x$ has to be in at least one of the three sets, meaning $\displaystyle x$ can't be in$\displaystyle A \cap B \cap C$, because if this were so, $\displaystyle x$ would have to then be in all three sets, falsifying our original assumption. Moreover, if $\displaystyle x$ is not in $\displaystyle A \cap B \cap C$, we can say that $\displaystyle x \in \overline{(A \cap B \cap C)}$.

9. ## Re: Prove By Subsets

Originally Posted by Bashyboy
If $\displaystyle x$ is not in at least in one of those sets, then $\displaystyle x \in A \vee x \in B \in C$
This formula should be $\displaystyle x\in\overline{A}\lor x\in\overline{B}\lor x\in\overline{C}$.

10. ## Re: Prove By Subsets

Oh yes, you are right. I forgot to type the lines in. But the rest of the proof is correct?

11. ## Re: Prove By Subsets

Originally Posted by Bashyboy
Oh yes, you are right. I forgot to type the lines in. But the rest of the proof is correct?
Yes, though the style may be somewhat improved.

Originally Posted by Bashyboy
And to prove that $\displaystyle \overline{A} \cup \overline{B} \cup \overline{C} \subseteq (\overline{A \cap B \cap C})$, would this be sufficient:

Suppose that $\displaystyle x \in \overline{A} \cup \overline{B} \cup \overline{C}$. For $\displaystyle x$ to be in the set, $\displaystyle x$ has to be in at least one of the three sets, meaning $\displaystyle x$ can't be in$\displaystyle A \cap B \cap C$, because if this were so, $\displaystyle x$ would have to then be in all three sets, falsifying our original assumption. Moreover, if $\displaystyle x$ is not in $\displaystyle A \cap B \cap C$, we can say that $\displaystyle x \in \overline{(A \cap B \cap C)}$.
This is correct, though since the fact is so simple, it is difficult to say whether this explanation is not enough, adequate, or too much. I would write, "...$\displaystyle x$ has to be in at least one of the three sets. If $\displaystyle x\in\overline{A}$, then $\displaystyle x\notin A$ and therefore $\displaystyle x\notin A\cap B\cap C$, and similarly for $\displaystyle x\in\overline{B}$ and $\displaystyle x\in\overline{C}$. In all three cases, we have $\displaystyle x\notin A\cap B\cap C$, i.e., $\displaystyle x\overline{A\cap B\cap C}$."

12. ## Re: Prove By Subsets

Oh, I see. Thank you both so very much for the help.