2
$\begingroup$

I would like to construct a formal proof of the following:

$(A\setminus C)\setminus(B\setminus C) = (A\setminus B)\setminus C$

Let $a∈A$ be an arbitrary element, we will show that $a\in A \cap \overline B \cap \overline C$.

For LHS, since $a\in A$, we have that $a\in (A \cap \overline C) \cap (\overline B \cap \overline C)$. This is equivalent to $a\in (A \cap \overline B) \cap \overline C$.

For RHS, since $a\in A$, we have that $a\in (A \cap \overline B) \cap \overline C$

$\therefore lhs \equiv rhs$ and this concludes the proof

I would be grateful for any feed back on this element chasing proof. Is it flawed or where should improvements be made?

Thanks

4 Answers 4

2

My favorite version of element chasing is to start at the most complex side, expand the definitions to get to the element/logic level, then simplify, and finally go back to the set level.

In this case, for every $\;x\;$, \begin{align} & x \in (A \setminus C) \setminus (B \setminus C) \\ \equiv & \;\;\;\;\;\text{"definition of $\;\setminus\;$"} \\ & x \in A \setminus C \;\land\; \lnot (x \in B \setminus C) \\ \equiv & \;\;\;\;\;\text{"definition of $\;\setminus\;$, twice"} \\ & x \in A \;\land\; \lnot (x \in C) \;\land\; \lnot (x \in B \land \lnot (x \in C)) \\ \equiv & \;\;\;\;\;\text{"logic: simplify by using $\;\lnot (x \in C)\;$ on other side of $\;\land\;$"} \\ & x \in A \;\land\; \lnot (x \in C) \;\land\; \lnot (x \in B \land \text{true}) \\ \equiv & \;\;\;\;\;\text{"logic: simplify; rearrange -- to better match the other side"} \\ & x \in A \;\land\; \lnot (x \in B) \;\land\; \lnot (x \in C) \\ \equiv & \;\;\;\;\;\text{"definition of $\;\setminus\;$"} \\ & x \in A \setminus B \;\land\; \lnot (x \in C) \\ \equiv & \;\;\;\;\;\text{"definition of $\;\setminus\;$"} \\ & x \in (A \setminus B) \setminus C \\ \end{align} By set extensionality, this proves the original statement.

  • 0
    @user394691 I'm using the rule that if $\;P \Rightarrow (Q \equiv R)\;$, then $\;P \land Q \;\equiv\; P \land R\;$, and I tried to make that clear by using the hint: "$\text{logic: simplify by using $\;P\;$ on other side of $\;\land\;$}$". (Here, $\;P\;$ is $\;\lnot(x \in C)\;$, $\;Q\;$ is $\;\lnot(x \in B \land \lnot(x \in C))\;$, and $\;R\;$ is $\;\lnot(x \in B \land \text{true})\;$.)2017-08-24
3

$\rm\begin{eqnarray} {\bf Hint}\quad (A\backslash C)\backslash (B\backslash C) &\:=\: &\rm A\cap C'\cap\, (B\cap C')'\\ &=&\rm A\cap C'\cap (B'\cup C)\\ &=&\rm A\cap (C'\cap B'\cup C'\cap C) \\ &=&\rm (A\cap B')\cap C'\\ &=&\rm (A\backslash B)\backslash C \end{eqnarray} $

2

$(A-C)=A\cap C'$ and $(B-C)=B\cap C'$ then $(A-C)-(B-C)=(A\cap C')\cap(B\cap C')'=\\(A\cap C')\cap(B'\cup C)=(A\cap C'\cap B')\cup(A\cap C'\cap C)$ but $(A\cap C'\cap C)=\emptyset$ so $(A-B)-(B-C)=(A\cap C'\cap B')=A\cap(B\cup C)'=A-(B\cup C)$ or $(A-B)-(B-C)=(A\cap B'\cap C')=(A\cap B')\cap C'=(A-B)- C$

2

You’re in trouble already in the first line of your argument:

Let $a\in A$ be an arbitrary element, we well show that $a\in A\cap\overline B\cap\overline C$.

You can’t show this, because it’s not necessarily true that an arbitrary element of $A$ belongs to $\overline B\cap\overline C$. It also isn’t what you want to show. At this point you’re trying to show that $(A\setminus C)\setminus(B\setminus C)\subseteq(A\setminus B)\setminus C\;,\tag{1}$ so you should be starting with an arbitrary $a\in(A\setminus C)\setminus(B\setminus C)$, like this:

Let $a\in(A\setminus C)\setminus(B\setminus C)$ be arbitrary. Then $a\in A\setminus C$, and $a\notin B\setminus C$. Since $a\in A\setminus C$, $a\in A$ and $a\notin C$. Since $a\notin B\setminus C$, either $a\notin B$, or $a\in C$. But we know that $a\notin C$, so it must be the case that $a\notin B$. Putting the pieces together, we see that $a\in A$ and $a\notin B$, so $a\in A\setminus B$, and moreover $a\notin C$, so $a\in(A\setminus B)\setminus C$. This proves $(1)$.

To complete the proof you must show that

$(A\setminus B)\setminus C\subseteq(A\setminus C)\setminus(B\setminus C)\tag{2}\;,$

so this time you should start with an arbitrary element of $(A\setminus B)\setminus C$:

Let $a\in(A\setminus B)\setminus C$ be arbitrary. Then $a\in A\setminus B$, and $a\notin C$. Since $a\in A\setminus B$, $a\in A$, and $a\notin B$. We now know that $a\in A$ and $a\notin C$, so $a\in A\setminus C$. We also know that $a\notin B$, so $a\notin B\setminus C$, and therefore $a\in(A\setminus C)\setminus(B\setminus C)$. This proves $(2)$, and $(1)$ and $(2)$ together yield the desired result that $(A\setminus C)\setminus(B\setminus C)=(A\setminus B)\setminus C$.

There’s nothing tricky about any of this: it’s all just using the definition of set difference. It’s an example of what I call a follow-your-nose proof: you do the most straightforward, natural thing at each step, and it works.

  • 0
    @bosra: You’re very welcome.2012-11-18