1
$\begingroup$

Let $C$ and $D$ be subsets of $X$. Prove that $$(X\setminus C)\cap D=D\setminus C$$ My workings: Showing two sets are equal amounts to showing inclusion both ways so I want to show $$(X\setminus C)\cap D\subseteq C$$ and $$(X\setminus C)\cap D\supseteq D\setminus C$$ For the first one I did the following. Let $x\in (X\setminus C)\cap D$, then $x\in(X\setminus C)$ and $x\in D$. This implies that $x\in X$, $x\notin C$ and $x\in D$. Because $D\subseteq X$ this is equivalent to saying $x\in D$, $x\notin C$. Therefore $x\in D\setminus C$. this shows that $(X\setminus C)\cap D\subseteq D\setminus C$.

For the second part I ran into some trouble. This time let $x\in D\setminus C$. Then I thought since $D\subseteq X$ this implies $D\cap X=D$ and we can say $x\in (X\cap D)\setminus C$. I just don't know if this is completely correct to say, and it also doesn't finish the argument.

If anyone could help me out with this last part I would be grateful. Also it is very possible that the arguments in the first are not rigorous enough, if so please feel free to point out where I could improve. Thanks

|cite|improve this question
$\endgroup$
2
$\begingroup$

Your first inclusion looks fine.

For the second, your thought pattern is fine; just need to put it in notation...we simply "commute" the "anded" statements.

$ \begin{align} x \in D \setminus C &\implies x \in D\;\text{ and}\;x \notin C \\ \\ &\implies x \in D \cap X = D\;\text{ and}\;x \notin C \\ \\ & \implies x \in D \text{ and}\; x \in X\;\text{ and}\;x \notin C \\ \\ &\implies x \in X\;\text{ and}\;x\notin C\;\text{ and}\;x \in D \\ \\ & \implies x \in (X\setminus C)\;\text{ and}\;x \in D \\ \\ & \implies x \in (X\setminus C)\cap D \end{align} $

So we've shown that $x \in D\setminus C \implies x\in (X\setminus C)\cap D$

Hence, $\;D\setminus C \subseteq (X\setminus C)\cap D$

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks, so if I were to continue the argument I was working on would the reasoning $x\in (X\cap D)\setminus C$ implies $x\in (X\setminus C)\cap D$ be correct as well because $C,D\subseteq X$? $\endgroup$ – Slugger Feb 11 '13 at 16:55
  • $\begingroup$ Absolutely, because we have "anded" statements x in X and x in D and x not in C...and commute them, validly, getting x in X and x not in C, and x in D. $\endgroup$ – Namaste Feb 11 '13 at 17:00
  • $\begingroup$ Does this make sense now? X is the "superset" containing subsets C and D, as you argued... $\endgroup$ – Namaste Feb 11 '13 at 17:05
  • $\begingroup$ Yes this makes a lot of sense thanks! I have a lot more of these questions I need to do so I might post one or two more if I am having trouble (or is it considered bad manners to upload several similar questions?) $\endgroup$ – Slugger Feb 11 '13 at 17:10
  • $\begingroup$ What do you think of calling Superset, a Mother set? + $\endgroup$ – mrs Feb 11 '13 at 18:15
2
$\begingroup$

$X \setminus C = C^C$.

$X \setminus C \cap D = C^C \cap D = D \setminus C$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Hey thanks for the answer, it is definitely a very nice argument because it is so short and concise. However, my teacher asked us to show inclusion both ways so I am afraid this will not be accepted. Thanks for the answer though, it is nice! $\endgroup$ – Slugger Feb 11 '13 at 16:53
  • $\begingroup$ You can repeat the above twice, once with $=$ replaced by $\subset$ and another time with $=$ replaced by $\supset$. $\endgroup$ – copper.hat Feb 11 '13 at 16:56
1
$\begingroup$

The first direction is well-handled. For the other direction, essentially the same argument works.

You want to prove if $x\in D\setminus C$, then $x$ is in $(X\setminus C)\cap D$. This is immediate, since $x$ is in $D$, in $X$ of course because $D$ is a subset of $X$, but not in $C$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Hey thanks for the feedback. I am not sure if I can see the typo, in the second part I am assuming that $x\in D\setminus C$ and want to show it is therefore in $(X\setminus C)\cap D$. Now because $D=X\cap D$ I argued that $D\setminus C = (X\cap D)\setminus C$. Maybe this is the typo you are referring to, if so, it is actually what I meant. $\endgroup$ – Slugger Feb 11 '13 at 16:51
  • $\begingroup$ I guess I was surprised, since a direct attack works well, and is essentially the same as the forward direction that you handled with no trouble. $\endgroup$ – André Nicolas Feb 11 '13 at 16:56
  • $\begingroup$ Yeah I can understand, this is my first encounter with proving these kinds of things. I find it difficult because the whole statement looks so obvious and a Venn diagram makes it very clear but making it rigorous in a correct manner confuses me still. $\endgroup$ – Slugger Feb 11 '13 at 17:00
  • $\begingroup$ The only question in my mind is whether you are allowed to say that $x\in U\V$ if and only if $x\in U$ and $x\not\in V$. Perhaps you are expected to translate $U\setminus V$ first to $U\cap V^c$. In that case, the version of the answer by copper.hat is the right one to use. $\endgroup$ – André Nicolas Feb 11 '13 at 17:06
0
$\begingroup$

An alternative is to do the following direct calculation:$$ \begin{align*} & (X \setminus C) \cap D = D \setminus C \\ \equiv & \;\;\;\;\;\text{"extensionality"} \\ & \langle \forall x :: x \in (X \setminus C) \cap D \;\equiv\; x \in D \setminus C \rangle \\ \equiv & \;\;\;\;\;\text{"definition of $\cap$; definition of $\setminus$, twice"} \\ & \langle \forall x :: x \in X \land x \notin C \land x \in D \;\equiv\; x \in D \land x \notin C \rangle \\ \equiv & \;\;\;\;\;\text{"logic"} \\ & \langle \forall x :: x \notin C \land x \in D \;\Rightarrow\; x \in X \rangle \\ \equiv & \;\;\;\;\;\text{"$x \in D \Rightarrow x \in X$, since $D \subseteq X$"} \\ & \mathrm{true} \\ \end{align*} $$

This shows that the assumption that $C \subseteq X$ is not necessary for this proof.

|cite|improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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