# Prove By Subsets

• Mar 17th 2013, 08:34 AM
Bashyboy
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. • Mar 17th 2013, 09:07 AM Plato Re: Prove By Subsets Quote: 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$
• Mar 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.

$\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?
• Mar 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 $\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.
• Mar 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?
• Mar 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.
• Mar 17th 2013, 11:05 AM
Bashyboy
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?
• Mar 17th 2013, 11:24 AM
Bashyboy
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)}$.
• Mar 17th 2013, 12:09 PM
emakarov
Re: Prove By Subsets
Quote:

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}$.
• Mar 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?
• Mar 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 $\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}$."
• Mar 17th 2013, 12:33 PM
Bashyboy
Re: Prove By Subsets
Oh, I see. Thank you both so very much for the help.