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?

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

  • $\begingroup$ 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)$? $\endgroup$ – user2793618 Aug 19 '18 at 18:56
  • 1
    $\begingroup$ 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$. $\endgroup$ – copper.hat Aug 19 '18 at 19:28
  • $\begingroup$ oh I see thanks! $\endgroup$ – user2793618 Aug 19 '18 at 19:36
  • 1
    $\begingroup$ I had a few typos. in my comment, the worst was the last I should have $x \in A \setminus B$. $\endgroup$ – copper.hat Aug 19 '18 at 19:57

How about trying this by contradiction?

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


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.