2
$\begingroup$

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)$.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Thanks. Can you please let me know where you would indicate in the proof what you have suggested. :) $\endgroup$ – user503154 Jan 15 at 2:25
  • 1
    $\begingroup$ 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. $\endgroup$ – Eevee Trainer Jan 15 at 2:31
0
$\begingroup$

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.$

$\endgroup$

Your Answer

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