2
$\begingroup$

$A$ and $B$ are any sets, prove that $A \smallsetminus (A \smallsetminus B) = A \cap B.$ This formula makes sense when represented on a Venn diagram, but I am having trouble with proving it mathematically.

I have tried letting $x$ be an element of $A$ and continue from there, but it doesn't seem to work out as a valid proof anyways.

Could anyone please point me in the right direction?

Many thanks.

$\endgroup$
  • $\begingroup$ Please show us your work: starting with $x \in A\setminus(A\setminus B)$, or the other way around, starting with $x \in (A\cap B)$. Please don't claim you tried ABC, unless you also show us you effort using ABC. Would you like to get an answer that says only: "Yup, that's right, start by letting $x \in A\setminus (A\setminus B)$... $\endgroup$ – Namaste Jan 27 '18 at 18:42
5
$\begingroup$

Let $x \in A \setminus (A \setminus B).$

Then $x$ is an element such that $x \in A$ and $x \notin A \setminus B$. But if $x \notin A\setminus B$, with some additional work, we realize this implies that $x \in A$ and $ x \in B$. So $x \in A \cap B$.

Vice-versa: let $x \in A \cap B$ so $x \in A$ and $x \in B$. This implies that $x \notin A \setminus B$. But given that $x \in A$ and $x \notin A \setminus B$ this implies that $x \in A \setminus (A \setminus B)$.

$\endgroup$
  • $\begingroup$ I would like this answer if you hadn't skipped from "$x \in A$ and $x \notin A\setminus B$, but if $x\in A \setminus B$" to "we realize that $x \in A$ and $x\in B$." I added the words ("with some additional work") in between them. I would like this answer more if you explained that $x \in A$ and $x \notin (A\setminus B)$, then $x \in A$ and, it is not the case that ($x \in A$ and $x \notin B$.) By Demorgans, we get that $(x \in A \land \lnot x\in A),$ or $(x \in A \land x\in B)$. The first disjunct is always false (no element can be in a set, and not be in a set. $\endgroup$ – Namaste Jan 27 '18 at 19:13
  • $\begingroup$ ...That leaves us to conclude, that "we realize this implies that $x\in A$ and $x\in B$. $\endgroup$ – Namaste Jan 27 '18 at 19:13
4
$\begingroup$

Notice that \begin{eqnarray*} x\in A\setminus(A\setminus B) &\Leftrightarrow& (x\in A)\wedge \neg(x\in A\setminus B)\\ &\Leftrightarrow & (x\in A)\wedge \neg((x\in A)\wedge \neg (x\in B))\\ &\Leftrightarrow & (x\in A)\wedge ((x\notin A)\lor(x\in B))\\ &\Leftrightarrow & ((x\in A)\wedge (x\notin A))\lor ((x\in A)\wedge(x\in B))\\ &\Leftrightarrow & (x\in A)\wedge (x\in B)\\ &\Leftrightarrow & x\in A\cap B. \end{eqnarray*}

$\endgroup$
  • 1
    $\begingroup$ Yes, when in doubt go back to the logic $\endgroup$ – Tom Collinge Jan 27 '18 at 18:28
  • 1
    $\begingroup$ I like this, because the equivalence makes the proof bi-directional, and doesn't skip important steps between $x \in A) \land $\lnot (x \in A\setminus B$ and its equivalent, $x\in A \land x \in B$ Those are likely the steps on which the asker got tripped up, I suspect. Nice answer. $\endgroup$ – Namaste Jan 27 '18 at 18:51
  • $\begingroup$ I like this, because the equivalence makes the proof bi-directional, and doesn't skip important steps between $x \in A \land \lnot (x \in A\setminus B$ and its equivalent, $x\in A \land x \in B.$ Those are likely the steps on which the asker got tripped up, I suspect. Nice answer. $\endgroup$ – Namaste Jan 27 '18 at 19:01
  • $\begingroup$ @amWhy: Thanks. Indeed, often mistakes are made in these basic logical steps. I've seen many people making mistakes using the notation $x\notin B$. I think it's safer to write $\neg(x\in B)$, indeed, if $B$ is a more complicated expression, we still now how to negate the logical expression appearing inside the brackets. This basic logical way of thinking is user friendly and not very prone to errors. $\endgroup$ – Mathematician 42 Jan 27 '18 at 20:43
3
$\begingroup$

Did you know that

$$A \smallsetminus B = A \cap \overline{B} \;\;?$$

$\begin{align} A \smallsetminus (A \smallsetminus B) &= A \smallsetminus (A \cap \overline{B}) \\ \\ &= A \cap \overline{ (A \cap \overline{B})}\\ \\ &= A \cap (\overline{A} \cup B)\\ \\ &= (A \cap \overline{A} )\cup (A \cap B) \\ \\ &= A \cap B \end{align}$

$\endgroup$
  • 1
    $\begingroup$ cmon, why this get downvoted, it is correct. hmm, maybe you want to precise that $\bar B=B^{\complement}$ and not the closure in this context. $\endgroup$ – zwim Jan 27 '18 at 18:55
  • $\begingroup$ @zwim: Not sure why this got downvoted, however this proof assumes knowledge about standard set operations which you should be able to prove directly as well. You might end up running in circles and not proving anything. $\endgroup$ – Mathematician 42 Jan 27 '18 at 18:58
0
$\begingroup$

Let $x\in A\cap B$.
Then $x\in A$ and $x\in B$.
Then $x\not \in A\setminus B$,
so $x\in A\setminus (A\setminus B)$.

Conversely, if $x\in A\setminus (A\setminus B)$,
then $x\in A$ and $x\not \in (A\setminus B)$.
So $x\in A$ and $x\in B$.
That is $x\in A\cap B$...

$\endgroup$
  • $\begingroup$ ditto of @Skills. $\endgroup$ – Namaste Jan 27 '18 at 18:36

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.