# Thread: Elementary Set Theory Question

1. ## Elementary Set Theory Question

Hi guys!

I just worked on another simple set theory proof, and have come out with what seems like it might work alright, but while I was writing this I kind of felt like I was making some statements that perhaps needed to be more better justified. For example, in the second sentence of the proof, it kind of feels like I just pulled that out of thin air without justification.

$\displaystyle \text{\underline{Theorem}:}$ If $\displaystyle A\subseteq B$, then $\displaystyle \bar{A}= A$\$\displaystyle B \cup \bar{B}$
$\displaystyle \text{\underline{Proof}:}$ To show the left to right containment, let $\displaystyle x \in \bar{A}$. Then $\displaystyle x\notin A$. Note that there are two cases for $\displaystyle B$, either $\displaystyle x \in B$ or $\displaystyle x \notin B$. If $\displaystyle x \in B$, then we have $\displaystyle x \in B$ and $\displaystyle x \notin A$, which implies that $\displaystyle x \in B$\$\displaystyle A$. If $\displaystyle x \notin B$, then $\displaystyle x \in \bar{B}$, and so $\displaystyle x \in B$\$\displaystyle A$ $\displaystyle \cup $$\displaystyle \bar{B}. Therefore, \displaystyle \bar{A} \subseteq B\\displaystyle A \cup \bar{B}. To show the reverse containment, let \displaystyle x \in A\\displaystyle B \cup \bar{B}. Then \displaystyle x \in B\\displaystyle A or \displaystyle x \in \bar{B}. So we have two cases to consider. Suppose \displaystyle x\in B\\displaystyle A. Then \displaystyle x \in B and \displaystyle x \notin A. Since \displaystyle x \notin A, \displaystyle x \in \bar{A}. Suppose \displaystyle x \in \bar{B}. Then \displaystyle x \notin B. Note that by hypothesis \displaystyle A \subseteq B, and thus \displaystyle x \notin B clearly implies \displaystyle x \notin A. And so \displaystyle x \in \bar{A}.. Since in either case \displaystyle x \in \bar{A}, we can conlude that \displaystyle B\\displaystyle A \cup \bar{B} \subseteq \bar{A}. Since we've shown both containments hold true, we can conlude that \displaystyle \bar{A}= B\\displaystyle A \cup \bar{B}. Thanks for taking your time to read this, James 2. Originally Posted by james121515 Hi guys! I just worked on another simple set theory proof, and have come out with what seems like it might work alright, but while I was writing this I kind of felt like I was making some statements that perhaps needed to be more better justified. For example, in the second sentence of the proof, it kind of feels like I just pulled that out of thin air without justification. \displaystyle \text{\underline{Theorem}:} If \displaystyle A\subseteq B, then \displaystyle \bar{A}= A\\displaystyle B \cup \bar{B} \displaystyle \text{\underline{Proof}:} To show the left to right containment, let \displaystyle x \in \bar{A}. Then \displaystyle x\notin A. Note that there are two cases for \displaystyle B, either \displaystyle x \in B or \displaystyle x \notin B. If \displaystyle x \in B, then we have \displaystyle x \in B and \displaystyle x \notin A, which implies that \displaystyle x \in B\\displaystyle A. If \displaystyle x \notin B, then \displaystyle x \in \bar{B}, and so \displaystyle x \in B\\displaystyle A \displaystyle \cup$$\displaystyle \bar{B}$. Therefore, $\displaystyle \bar{A} \subseteq B$\$\displaystyle A \cup \bar{B}$. To show the reverse containment, let $\displaystyle x \in A$\$\displaystyle B \cup \bar{B}$. Then $\displaystyle x \in B$\$\displaystyle A$ or $\displaystyle x \in \bar{B}.$ So we have two cases to consider. Suppose $\displaystyle x\in B$\$\displaystyle A$. Then $\displaystyle x \in B$ and $\displaystyle x \notin A$. Since $\displaystyle x \notin A$, $\displaystyle x \in \bar{A}$. Suppose $\displaystyle x \in \bar{B}$. Then $\displaystyle x \notin B$. Note that by hypothesis $\displaystyle A \subseteq B$, and thus $\displaystyle x \notin B$ clearly implies $\displaystyle x \notin A$. And so $\displaystyle x \in \bar{A}.$. Since in either case $\displaystyle x \in \bar{A}$, we can conlude that $\displaystyle B$\$\displaystyle A \cup \bar{B} \subseteq \bar{A}$. Since we've shown both containments hold true, we can conlude that $\displaystyle \bar{A}= B$\$\displaystyle A \cup \bar{B}$.

James
I would phrase your proof a little better

"Let $\displaystyle x\in A'$, then $\displaystyle x\notin A$. If $\displaystyle x\in B'$ we are done, so assume that $\displaystyle x\notin B'$. Clearly then, we have that $\displaystyle x\in B$, but since $\displaystyle x\notin A$ it follows that $\displaystyle x\in B-A$. We may therefore conclude that $\displaystyle x\in B'$ or $\displaystyle x\in B-A$ and thus $\displaystyle x\in \left[\left(B-A\right)\cup B'\right]$. Conversely, suppose that $\displaystyle x\in\left[\left(B-A\right)\cup B'\right]$. Then, $\displaystyle x\in \left(B-A\right)$ or $\displaystyle x\in B'$ so that $\displaystyle x\in \left(B\cap A'\right)$ or $\displaystyle x\in B'$. This leads us to conclude that $\displaystyle x\in B\text{ and }x\in A'$ or $\displaystyle x\in B'$, Using the distributive properties of conjunction (and) and disjunction (or) we may therefore conclude that $\displaystyle \left(x\in B'\text{ or }x\in B\right)\text{ and } \left(x\in A'\text{ or }x\in B'\right)\Leftrightarrow x\in\left[U\cup \left(A'\cup B'\right)\right]$ and since $\displaystyle A\subseteq B\implies B'\subseteq A'$ we see that the above implies $\displaystyle x\in A'$."

Alternatively, you may just use the algebra of sets.

$\displaystyle \left(B-A\right)\cup B'=\left(B\cap A'\right)\cup B'=\left(B\cup B'\right)\cap \left(A'\cup B'\right)$$\displaystyle =U\cap\left(A'\cup B'\right)=A'\cup B'=\left(A\cap B\right)'=A'$

3. Hi Drexel,
Thank you for your response. So for the first containment (left to right) ours proofs seem to follow the same logic. Would you say my left to right is satisfactory? As for the right to left part, I don't understand what you did there. The only way that made sense was to do it by cases. Clearly we have $\displaystyle x \in [A-B]$ or $\displaystyle x\in B'$, so what made sense at least in my mind was to show that in either case, $\displaystyle x \in A'$. Also, I notice you said that $\displaystyle A \subseteq B \implies B'\subseteq A'$. Would this be something that would normally requrie a proof within the proof itself?

james

4. Originally Posted by james121515
As for the right to left part, I don't understand what you did there.
Let $\displaystyle x\in\left[\left(B-A\right)\cup B'\right]$

1. Then $\displaystyle x\in \left(B-A\right)\text{ or }x\in B'$ (I think you got that)

2. Since $\displaystyle x\in\left(B-A\right)\Leftrightarrow x\in\left(B\cap A'\right)$ we know that $\displaystyle x\in B\text{ and }x\in A'$ (this is just using the definition of intersection)

3. So now what we really have is that $\displaystyle \left(x\in B\text{ and }x\in A'\right)\text{ or } x\in B'$ now using the distributive laws of language (in this case the statement $\displaystyle \left(P\text{ and }Q\right)\text{ or }S$ is the same thign as $\displaystyle \left(P\text{ or }S\right)\text{ and }\left(P\text{ or }Q\right)$) we see that $\displaystyle \left(x\in B\text{ or }x\in B'\right)\text{ and }\left(x\in A'\text{ or }x\in B'\right)$

4. This last thing tells us precisely that $\displaystyle x\in\left[\left(B\cup B'\right)\cap\left(A'\cup B'\right)\right]$. But, $\displaystyle B\cup B'=U$ (the universal set) and $\displaystyle U$ intersected with anything is itself. So $\displaystyle x\in\left[U\cap\left(A'\cup B'\right)\right]\Leftrightarrow x\in\left(A'\cup B'\right)$

5. You may have to prove this (let $\displaystyle x\in B'$ then $\displaystyle x\notin B$ and since $\displaystyle x\in A\implies x\in B$ we may conclude that $\displaystyle x\notin A$ so that $\displaystyle x\in A'$) but $\displaystyle A\subseteq B\implies B'\subseteq A'$ so we may finally conclude that $\displaystyle x\in\left(A'\cup B'\right)\Leftrightarrow x\in A'$

This finishes it (I bulletined it so you could better understand it.)

5. Hello everyone
Originally Posted by james121515
...
$\displaystyle \text{\underline{Theorem}:}$ If $\displaystyle A\subseteq B$, then $\displaystyle \bar{A}= A$\$\displaystyle B \cup \bar{B}$
...
$\displaystyle \text{\underline{Theorem}:}$ If $\displaystyle A\subseteq B$, then $\displaystyle \bar{A}= (B$\$\displaystyle A) \cup \bar{B}$