5
$\begingroup$

I'm going through the book Proofs and Fundamentals by Ethan Bloch, and in the chapter of Set Operations there is an exercise (Exercise 3.3.9) that asks you to do the following:

Let $A$ and $B$ be sets. Prove that $(A\cup B)-A = B-(A\cap B)$.

I know that to prove this you just need to show that the right hand side of the equation is a subset of the left side and vice versa.

I began trying to prove it by choosing an arbitrary element $x$ of $(A\cup B)-A$.

$x \in (A\cup B)-A$, which is the same as

$x \in A \cup B $ and $x \notin A$, which is the same as

$x \in A $ or $x \in B $, and $x \notin A$, which I think means

$x \in B $.

I have some intuition on how to proceed but I don't know how to do it formally.

Any corrections and tips and/or complete proofs are welcome.

$\endgroup$
2
  • 4
    $\begingroup$ Use Venn diagrams, and everything will become clear and evident. See this image $\endgroup$
    – Crostul
    Apr 5 '16 at 13:56
  • 1
    $\begingroup$ Your last line is incorrect, because $x$ cannot belong to $A$. So $x\in B$ is necessary but not sufficient. $\endgroup$
    – almagest
    Apr 5 '16 at 13:58
3
$\begingroup$

Your last step should be

$(x\in A \;or\; x\in B) \;and\; (x\notin A)$

Use Distributive law now

$(x\in A \;and\; x\notin A)\;or\;( x\in B \;and\; (x\notin A))$

$\Rightarrow x\in B \;and\; (x\notin A)$

$\Rightarrow x\in B-A$

$\Rightarrow x\in B-(A\cap B)$

This shows $((A\cup B)-A )\subset (B-(A\cap B))$

Now let $x \in (B-(A\cap B)$

$\Rightarrow x\in B \;and \;x\notin (A\cap B)$

$\Rightarrow x\in B \;and\; (x\notin A\; or\; x\notin B)$

$\Rightarrow (x\in B \;and\;x\notin A) \; or\;(x\in B \; and \; x\notin B)$

$\Rightarrow (x\in B \;and\;x\notin A)$

$\Rightarrow x\in B-A$

Also, $B-A \subset (A\cup B)-A$

This completes the proof.

$\endgroup$
1
  • 2
    $\begingroup$ This shows left side is subset of right side. However the same argument can be done coming from the right side going to the left side. Combining both, leads to left and right side are equal. $\endgroup$
    – Imago
    Apr 5 '16 at 14:06
3
$\begingroup$

Suppose $x \in (A \cup B) - A$. Then $(x \in A \text{ or } x \in B)$ and $x \notin A$. This simplifies to $x \in B$ and $x \notin A$. Since $A \cap B \subset A$ (do you see why this is true?), it follows that $x \notin A \cap B$. Hence $x \in B$ and $x\notin A \cap B$, so $x \in B - (A \cap B)$.

$\endgroup$
2
$\begingroup$

A quicker way to notice the solution is the following:

$A \subseteq (A \cup B)$, so $(A \cup B)-A=(A \cup B)- \underbrace{A \cap (A \cup B)}_\text{ distribute}=(A \cup B-A)-A \cap B=B-A \cap B$.


Another idea is the following. We can use your proof, but in the last line you state

"($x \in A$ or $x \in B$) and $x \notin A$.

But let's use the logically equivalent statement:

($x \in A$ and $ x \notin A$) or ($x \in B$ and $x \notin A$).

The first option is a contradiction, so use the second.

then $x \in B-A \subseteq B-A \cap B$.

But now you only have one direction of the proof.


We show the opposite inclusion:

We want: $B-(A\cap B) \subseteq (A \cup B)-A$.

$x \in B-(A \cap B) \implies (x \in B) \land(x \notin A \cap B) \implies (x \in B) \land (x \notin A \lor x \notin B) \implies$_______

hint: you have two cases now, one of them is a contradiction.

$\endgroup$
1
$\begingroup$

Using three properties $A-B=A\cap\bar{B}, B\cap\bar{B}=\emptyset, \overline{A\cup B}=\bar{A}\cap\bar{B}$, where $\bar{B}$ is the complement of $B$, then you have $$ LHS=A\cup B-A=(A\cup B)\cap\bar{B}=(A\cap\bar{B})\cup (B\cap\bar{B})=A\cap\bar{B} $$ and $$ RHS=B-A\cap B=A\cap(\overline{A\cap B})=A\cap(\bar{A}\cup\bar{B})=(A\cap\bar{A})\cup(A\cap\bar{B})=A\cap\bar{B} $$ from which you can obtain $$ A\cup B-A=B-A\cap B.$$

$\endgroup$
0
$\begingroup$

To prove that two sets are equal, the most basic tool is extensionality: they are equal iff they have the same elements.$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\op}[1]{\\ #1 \quad & \quad \unicode{x201c}} \newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \phantom{\unicode{x201c}} } \newcommand{\hint}[1]{\mbox{#1} \unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\ref}[1]{\text{(#1)}} \newcommand{\then}{\Rightarrow} \newcommand{\when}{\Leftarrow} \newcommand{\true}{\text{true}} \newcommand{\false}{\text{false}} $ In other words, the original statement is equivalent to $$ \tag{0} \langle \forall x :: x \in (A \cup B) - A \;\equiv\; x \in B - (A \cap B) \rangle $$

To prove this, let's simplify both sides of this equivalence in turn, by expanding the definitions and then using the laws of logic. For the left hand side, $$\calc x \in (A \cup B) - A \op=\hint{expand the definitions of $\;-\;$ and $\;\cup\;$} (x \in A \lor x \in B) \;\land\; x \not\in A \op=\hint{distribute $\;\land\;$ over $\;\lor\;$ -- to bring both occurrences of $\;x \in A\;$ together} (x \in A \land x \not\in A) \;\lor\; (x \in B \land x \not\in A) \op=\hint{simplify} \false \;\lor\; (x \in B \land x \not\in A) \op=\hint{simplify} x \in B \land x \not\in A \tag{*} \endcalc$$

Do the same thing with the right hand side of $\ref{0}$, get the same result $\ref{*}$, and conclude that $\ref{0}$ is true. That concludes the proof of the original statement.

$\endgroup$

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.