# Prove By Subsets

• March 17th 2013, 08:34 AM
Bashyboy
Prove By Subsets
Hello all,

I am currently working on proving these statements $\overline{A \cap B \cap C}$ and $\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 $x \in \overline{A \cap B \cap C}$; for $x$ to be in the set, $x$ can't be in $A \cap B \cap C$. This means that $x \notin A \wedge x \notin B \wedge x \notin 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}$, meaning that $\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.
• March 17th 2013, 09:07 AM
Plato
Re: Prove By Subsets
Quote:

Originally Posted by Bashyboy
I am currently working on proving these statements $\overline{A \cap B \cap C}$ and $\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 $x \in \overline{A \cap B \cap C}$; for $x$ to be in the set, $x$ can't be in $A \cap B \cap C$. This means that $x \notin A \wedge x \notin B \wedge x \notin 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}$, meaning that $\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.

$x \in \overline {A \cap B \cap C} \to x \notin A \vee x \notin B \vee x \notin C$
• March 17th 2013, 09:19 AM
Bashyboy
Re: Prove By Subsets
Quote:

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

What you have is not correct.

$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 $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?
• March 17th 2013, 10:00 AM
Plato
Re: Prove By Subsets
Quote:

Originally Posted by Bashyboy
I haven't learned about induction yet. Where did I write in my proof that $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:
$x \in \overline{A \cap B \cap C}$; for $x$ to be in the set, $x$ can't be in $A \cap B \cap C$. This means that $x \notin A \wedge x \notin B \wedge x \notin C$.
That is FALSE.

What I posted is TRUE.
• March 17th 2013, 10:16 AM
Bashyboy
Re: Prove By Subsets
Oh, so the use of the disjunction means that x can't be in any of the three sets?
• March 17th 2013, 10:23 AM
Plato
Re: Prove By Subsets
Quote:

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.
• March 17th 2013, 11:05 AM
Bashyboy
Re: Prove By Subsets
Okay, Plato, is this better:

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

Would this show that the statement is a subset of the other?
• March 17th 2013, 11:24 AM
Bashyboy
Re: Prove By Subsets
And to prove that $\overline{A} \cup \overline{B} \cup \overline{C} \subseteq (\overline{A \cap B \cap C})$, would this be sufficient:

Suppose that $x \in \overline{A} \cup \overline{B} \cup \overline{C}$. For $x$ to be in the set, $x$ has to be in at least one of the three sets, meaning $x$ can't be in $A \cap B \cap C$, because if this were so, $x$ would have to then be in all three sets, falsifying our original assumption. Moreover, if $x$ is not in $A \cap B \cap C$, we can say that $x \in \overline{(A \cap B \cap C)}$.
• March 17th 2013, 12:09 PM
emakarov
Re: Prove By Subsets
Quote:

Originally Posted by Bashyboy
If $x$ is not in at least in one of those sets, then $x \in A \vee x \in B \in C$

This formula should be $x\in\overline{A}\lor x\in\overline{B}\lor x\in\overline{C}$.
• March 17th 2013, 12:12 PM
Bashyboy
Re: Prove By Subsets
Oh yes, you are right. I forgot to type the lines in. But the rest of the proof is correct?
• March 17th 2013, 12:28 PM
emakarov
Re: Prove By Subsets
Quote:

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.

Quote:

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

Suppose that $x \in \overline{A} \cup \overline{B} \cup \overline{C}$. For $x$ to be in the set, $x$ has to be in at least one of the three sets, meaning $x$ can't be in $A \cap B \cap C$, because if this were so, $x$ would have to then be in all three sets, falsifying our original assumption. Moreover, if $x$ is not in $A \cap B \cap C$, we can say that $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, "... $x$ has to be in at least one of the three sets. If $x\in\overline{A}$, then $x\notin A$ and therefore $x\notin A\cap B\cap C$, and similarly for $x\in\overline{B}$ and $x\in\overline{C}$. In all three cases, we have $x\notin A\cap B\cap C$, i.e., $x\overline{A\cap B\cap C}$."
• March 17th 2013, 12:33 PM
Bashyboy
Re: Prove By Subsets
Oh, I see. Thank you both so very much for the help.