2

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?

Rolazaro Azeveires
  • 653
user2793618
  • 49

2 Answers2

1

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

copper.hat
  • 172,524
  • 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
  • 1
    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
  • 1
    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
0

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

tom
  • 25