7
$\begingroup$

I have proved this using Venn diagram but when I am trying to prove this using the rule that "If $ A \subset B \text{ and } B \subset A $ then $ A = B $", I am having some problems with my understanding of the same,here is how I did so far:

Let $x \in A \cap (B-C) \Rightarrow x \in A \text{ and } x \in (B-C) \Rightarrow x \in A \text{ and } (x \in B \text{ and } x \notin C) $

How to proceed next? Since if I am do something like this: $ x \in A \text{ and } x \in B \text{ and } x \in A \text{ and } x \notin C $, it's not giving the correct results, what exactly I am missing here?

4 Answers 4

8

Hint: $x \notin C \Rightarrow x \notin D \cap C$ for any set $D$.

  • 0
    That's sufficient for me :)2010-11-10
5

Here is a different style of proof, viz. an equational and calculational one.

The idea is to start at the most complex side, translate from set theory to logic by working at the element level, then expanding the definitions, and see where there leads you.

In other words, for all $\;x\;$ we calculate: \begin{align} & x \in (A \cap B) - (A \cap C) \\ \equiv & \;\;\;\;\;\text{"expand definition of $\;-\;$, and of $\;\cap\;$ (twice)"} \\ & x \in A \land x \in B \land \lnot(x \in A \land x \in C) \\ \equiv & \;\;\;\;\;\text{"DeMorgan"} \\ & x \in A \land x \in B \land (x \not\in A \lor x \not\in C) \\ \equiv & \;\;\;\;\;\text{"use leftmost conjunct $\;x \in A\;$ in the rightmost conjunct"} \\ & x \in A \land x \in B \land (\textrm{false} \lor x \not\in C) \\ \equiv & \;\;\;\;\;\text{"simplify"} \\ & x \in A \land x \in B \land x \not\in C \\ \equiv & \;\;\;\;\;\text{"reintroduce $\;-\;$ and $\;\cap\;$"} \\ & x \in A \cap (B - C) \\ \end{align}

3

Simplyfing the notation of @Marnix answer:

$$ A \cap (B - C) \\ = A \cap B \cap C' \text{ (definition of set complement)}\\ = A \cap B \cap (A' \cup C') \text{ (trick, } A \cap B \cap A' = \emptyset\text{)}\\ = A \cap B \cap (A \cap C)' \text{ (complement of intersection of sets in braces)}\\ = (A \cap B) \cap (A \cap C)' \text{ (assoc.)}\\ = (A \cap B) - (A \cap C) \text{ (definition of set complement)}\\ $$

The key is introducing a good disjoint set (with $A \cap B$) for union with C'.

  • 0
    I'm not sure why this would be "simplifying" my answer. I mean, it might be simpler to do this at the set level, instead of at the element/logic level, depending on your familiarity with set algebra vs. with the laws of logic. (Although the "trick" is better known at the logic level). But this answer also turns the calculation on its head, starting with the simplest side and introducing complexity. That is not simpler. On the contrary, this makes it necessary to use a 'complexifying' step (the "trick" step), which is a "rabbit pulled out of a hat" making the proof less clear.2015-10-01
  • 0
    Hi @Marnix! It was a bit odd to read your comment years after posting, but then I think you've a point. But as I said in my answer, I tried to simplify :) the notation of your answer, using sets. As I see, your answer also has a trick point in which the reader has to understand how a left value is carried to the expression inside brackets. I think both answers are good.2015-10-01
1

It is possible to continue your solution$$\begin{align} A\cap(B-C) & = \{x\space|\space x\in A\space\land(x\in B\space\land x\notin C)\} \\ & = \{x\space|\space (x\in A\space\land x\in B)\space\land x\notin C\} \\ & = \{x\space|\space (x\in A\space\land x\in B)\space\land (x\notin A\lor x\notin C)\} \\ & = \{x\space|\space (x\in A\space\land x\in B)\space\land \neg(x\in A\land x\in C)\} \\ & = (A\cap B)-(A\cap C) \end{align}$$