# Proof verification for the equivalence of two sets.

I have constructed two identical draft proofs for the following question using implications and words. Can you please verify whether they are logically correct. Should I have used De Morgan's Laws?

Exercise:

Suppose that $$C,D$$ are subsets of a set $$X$$. Prove that $$(X\setminus C){\,}\cap{\,}D =D\setminus C.$$

Proof 1:

Suppose that $$x\in{(X\setminus C){\,}\cap{\,}D}$$. Then $$x\in{(X\setminus C)}$$ and $$x\in{D}$$. Then ($$x\in{X}$$ and $$x\notin{C}$$) and $$x\in{D}$$. Then ($$x\in{X}$$ and $$x\in{D}$$) and ($$x\in{D}$$ and $$x\notin {C}$$). Then $$x\in(X \cap D) \cap (D \setminus C)$$. Thus, $$x\in(D \setminus C)$$. So, $$(X \setminus C) {\,} \cap D \subseteq (D \setminus C)$$.

Conversely, suppose that $$x\in (D\setminus C)$$. Then $$(x\in{D}$$ and $$x\notin{C})$$. Then $$(x\in X$$ and $$x\in{D}$$) and $$x\notin{C}$$. Then $$(x\in{X}$$ and $$x\notin{C})$$ and $$x\in{D}$$. Thus $$x\in(X\setminus {C})\cap{D}$$. So, $$(D\setminus{C}) \subseteq{(X\setminus{C}})\cap{D}$$.

Since $$(X \setminus C) {\,} \cap D \subseteq (D \setminus C)$$ and $$(D\setminus{C}) \subseteq{(X\setminus{C}})\cap{D}$$, we have that $$(X \setminus C) {\,} \cap D = (D \setminus C)\\$$.

Proof 2:

Suppose that $$x\in{(X\setminus C){\,}\cap{\,}D}$$. Then,

\begin{align} &\implies x\in{(X\setminus C)}{\,}{\,}\text{and}{\,}D \\ &\implies(x\in{X} {\,}\text{and} {\,}x\notin{C}) {\,}\text{and}{\,} x\in{D} \\ &\implies (x\in{X} {\,}\text{and}{\,} x\in{D}) {\,}\text{and} {\,}(x\in{D} {\,}\text{and}{\,} x\notin {C})\\ &\implies x\in(X \cap D) \cap (D \setminus C)\\ &\implies x\in(D \setminus C).\\ \\ \text{Thus}, (X \setminus C) {\,} \cap D \subseteq (D \setminus C).\\ \\ \end{align}

Conversely, suppose $$x\in (D\setminus C)$$. Then,

\begin{align} &\implies (x\in{D} {\,}\text{and}{\,} x\notin{C}) \\ &\implies (x\in X {\,}\text{and}{\,} x\in{D}){\,}\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})\cap{D}. \\ \\ \text{Thus,}{\,}(D\setminus{C}) \subseteq{(X\setminus{C}})\cap{D}. \end{align} Since $$(X \setminus C) {\,} \cap D \subseteq (D \setminus C)$$ and $$(D\setminus{C}) \subseteq{(X\setminus{C}})\cap{D}$$, we have that $$(X \setminus C) {\,} \cap D = (D \setminus C)$$.

Your logic all seems to follow fine. My main nitpick would be to more clearly indicate when the assumption $$C,D \subseteq X$$ is used.

With respect to whether you should have used De Morgan's law, I don't think they would have made anything easier. I'm not even sure if they would have any use here. In any event your method of proof is how I would've done things at any rate.

• Thanks. Can you please let me know where you would indicate in the proof what you have suggested. :) – user503154 Jan 15 at 2:25
• The main point that it came to mind was when you went from $$(x\in{D} {\,}\text{and}{\,} x\notin{C})$$ to $$(x\in X {\,}\text{and}{\,} x\in{D}){\,}\text{and}{\,} x\notin{C}$$ It took me a bit to realize that this followed because $D \subseteq X$. I didn't really have any other problems following the proof other than that, so that'd probably be the main point to apply it. – Eevee Trainer Jan 15 at 2:31

Perhaps more briefly:

For any sets $$A,B$$ we define $$A\cap B$$ by $$\forall x\,(\;x\in A\cap B\iff (x\in A\land x\in B)\;).$$ And we define $$A\setminus B$$ by $$\;\forall x \,(\;x\in A\setminus B \iff (x\in A\land x \not \in B)\;).$$

And we have $$D\subset X\iff \forall x\;(x\in D \iff (x\in D\land x\in X))$$ .

So if $$D\subset X$$ then for all $$x$$ we have $$[x\in D\setminus C]\iff$$ $$\iff [x\in D\land x\not \in C] \iff$$ $$\iff [(x\in D\land x\in X)\land x\not \in C] \iff$$ $$\iff [x\in D \land (x\in X\land x \not \in C)]\iff$$ $$\iff [x\in D\land x\in X\setminus C] \iff$$ $$\iff [ x\in D\cap (X\setminus C)].$$ And it doesn't matter whether or not $$C\subset X.$$