# Writing this as a formal proof.

The question from Velleman's How to Prove It section 3.1 is as follows:

Suppose $A \setminus B \subseteq C \cap D$ and $x \in A.$ Prove that if $x \notin D$ then $x \in B$

My logical form of the statement is:

$x \in A \land x \in B \rightarrow x \in C \land x \in D$ and $x \subseteq A$

I am unsure of how to properly express this as a proof. There is this one.

But that thread doesn't show a written out proof.

Also, are you allowed to do the contrapositive of a given? Because if I am, then I could apply demorgan's law to it, which would show that $x \notin D \lor x \notin C \rightarrow x \notin A \lor x \notin B$. Obviously from here, we assume that $x \notin D$, and from the contrapositive we see that x doesn't belong in B.

For my thinking above, how would I turn this into a proof if correct?

• If $x\in A\setminus B$ then $x\in A\land x\notin B$ – Teh Rod Aug 19 '18 at 3:54
• You can look at the contrapositive since it is logically equivalent to $p\to q$ – Teh Rod Aug 19 '18 at 4:04
• I presume you mean $x \in A$. – copper.hat Aug 19 '18 at 4:06
• @TehRod so I am allowed to turn the givens into anything equivalent? – user2793618 Aug 19 '18 at 18:53
• @user2793618 yes – Teh Rod Aug 19 '18 at 18:54

Here is one way:

Note that $A \setminus B \subset D$.

$A = (A \cap B) \cup ( A \setminus B)$, this is a disjoint union.

We have $A \subset (A \cap B) \cup D$.

Hence if $x \in A$, we must have $x \in A \cap B$ or $x \in D$.

Since $x \notin D$, we must have $x \in A \cap B \subset B$.

• Thanks for the answer! I more or less follow that you've written but what's the difference between $\subseteq \ and \ \subset$ also what is a disjoint union and why can you do $A = (A \cap B) \cup ( A \setminus B)$? – user2793618 Aug 19 '18 at 18:56
• Some folks use $\subseteq$ to emphasise that it may be equality. A disjoint union means the to sets above that make up $A$ are disjoint. If $x \in A$ then either it is also in $B$ or it is not. That is $x \in A \cap B$ or $x \in A \subset B$. – copper.hat Aug 19 '18 at 19:28
• oh I see thanks! – user2793618 Aug 19 '18 at 19:36
• I had a few typos. in my comment, the worst was the last I should have $x \in A \setminus B$. – copper.hat Aug 19 '18 at 19:57

Suppose $A \setminus B \subseteq C \cap D$ and $x \in A$.
Suppose further that $x \notin D$ and $x \notin B$.
Since $x \in A$ and $x \notin B$,   $x \in A \setminus B$.
Since $A \setminus B \subseteq C \cup D$,   $x \in C \cup D$ ... i.e. $x \in C$ and $x \in D$.
Since we assumed that $x \notin D$, this is a contradiction.
Thus, if $x \notin D$ then $x \in B$.