I`m trying to prove this claim and I need some advice how to continue, $$(A \setminus B) \cup (A \setminus C) = B \Leftrightarrow A=B , C\cap B=\varnothing$$ what I did is: $$(A \setminus B) \cup (A \setminus C) = (A \cap B') \cup (A \cap C') = A \cup (B' \cap C')$$ thanks!
Asked
Active
Viewed 1,227 times
1
-
Did you also mean for the title and the first statement to be the union of $(A\setminus B)$ and $(A \setminus C)$, as in the second statement (your work)? – amWhy Jul 15 '13 at 14:35
-
in one equality you used $\cap$ and in the other you used $\cup$. which is correct? – Jul 15 '13 at 14:35
-
@SamiBenRomdhane Sorry, I fixed that to many edits, my mistake. – Ofir Attia Jul 15 '13 at 14:37
3 Answers
3
Hint for $\implies$ direction:
When using the distributive law, note the equivalence between $(A\cap B') \cup (A\cap C') \iff A\cap (B' \cup C')$:
$$(A/B) \cup (A/C) = \color{blue}{(A \cap B')\cup(A\cap C')} = \color{blue}{\bf A \cap(B'\cup C')}$$
Note that by DeMorgan's $$A \cap(B'\cup C') = A\cap (B \cap C)'$$
Now recall that the premise is $$(A\setminus B) \cup (A\setminus C) = B$$
And now we're at $$\begin{align} (A\setminus B) \cup (A\setminus C) & = B \\ \\ A \cap(B'\cup C') & = B \\ \\ A\cap (B \cap C)' & = B \\ \\ A\setminus (B\cap C) & = B \end{align}$$
Now, what can you conclude about the relationship between $A$ and $B$, and about the intersection $B\cap C\;?$
amWhy
- 209,954
-
-
$A \cup ( B \cap C)' = A \cup ( B' \cup C') = A \cap ( B \cap C) = A \cap \phi = A = B$ ? – Ofir Attia Jul 15 '13 at 14:51
-
Not quite: we have $A$ intersect the complement of $B\cap C$ giving us $A\setminus(B\cap C) = B$. Can you see how this with $B\cap C = \varnothing$ forces $A = B$? – amWhy Jul 15 '13 at 14:57
-
-
And that gives us $A = B$. Make sure you have both directions covered in your $\iff$. The other direction is trivial ;-) – amWhy Jul 15 '13 at 15:01
-
1
One direction is trivial (if $A=B$ and $C\cap B=\emptyset$ is given). For the other direction note $$B=(A\backslash C)\cup (A\backslash B)\subseteq A$$ and $$A\backslash B\subseteq B $$ which together imply $A=B$. Thus your equation simplifies to $$A\backslash C=A$$ and therefore $A\cap C=\emptyset.$
Simon Markett
- 10,636
- 1
- 22
- 32
0
I usually start this type of set proofs by translating the set-level expressions to logic-level expressions using set extensionality and the definitions of the set operators, and then complete the proof on the logic level. That way I don't have to remember all the set-theoretic rules, and can just use ordinary logic.
Let's do that for both sides, and see where that leads us. For the left hand side, \begin{align} & (A \setminus B) \cup (A \setminus C) = B \\ \equiv & \;\;\;\;\;\text{"extensionality"} \\ & \langle \forall x :: x \in (A \setminus B) \cup (A \setminus C) \;\equiv\; x \in B \rangle \\ \equiv & \;\;\;\;\;\text{"expand $\;\cup\;$ and then $\;\setminus\;$ twice using their definitions"} \\ & \langle \forall x :: (x \in A \land x \not\in B) \lor (x \in A \land x \not\in C) \;\equiv\; x \in B \rangle \\ \equiv & \;\;\;\;\;\text{"in the left hand side: factor out $\;x \in A\;$; apply DeMorgan"} \\ (0) \;\; \phantom\equiv & \langle \forall x :: x \in A \land \lnot(x \in B \land x \in C) \;\equiv\; x \in B \rangle \\ \end{align} For the right hand side we similarly get the following $$ (1) \;\; \langle \forall x :: (x \in A \equiv x\in B) \land \lnot(x \in B \land x\in C) \rangle $$ Seeing that the shapes of $(0)$ and $(1)$ have a lot in common, we can complete the proof by proving (for any boolean expressions $\;P\;$, $\;Q\;$, and $\;R\;$) $$ (2) \;\; P \land \lnot(Q \land R) \:\:\equiv\;\; Q \:\:\equiv\:\: (P \equiv Q) \land \lnot(Q \land R) $$ Since $\;\equiv\;$ is associative and symmetric, and the first and last of the three parts look similar, we can bring these parts together by rearranging this to $$ \phantom{(2)} \;\; P \land \lnot(Q \land R) \:\:\equiv\:\: (P \equiv Q) \land \lnot(Q \land R) \:\:\equiv\:\: Q $$ Now we calculate \begin{align} & P \land \lnot(Q \land R) \:\:\equiv\:\: (P \equiv Q) \land \lnot(Q \land R) \\ \equiv & \;\;\;\;\;\text{"factor out common conjunct"} \\ & \lnot(Q \land R) \;\Rightarrow\; (P \;\equiv\; P \equiv Q) \\ \equiv & \;\;\;\;\;\text{"simplify right hand side"} \\ & \lnot(Q \land R) \;\Rightarrow\; Q \\ \equiv & \;\;\;\;\;\text{"use negation of right hand side $\;Q\;$ in left hand side"} \\ & \lnot(\textrm{false} \land R) \;\Rightarrow\; Q \\ \equiv & \;\;\;\;\;\text{"simplify"} \\ & Q \\ \end{align} This proves $(2)$ and completes the proof.
