Elementary set theory problem: proof of equivalence

Question

Let $A, B, C$ be arbitrary sets. Prove that: $$(A\backslash B)\backslash C = A\backslash(B\backslash C) \Longleftrightarrow A\cap C = \emptyset$$

The left hand side of the equivalence:

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

is defined by the following logical expression

$\begin{align} x\in (A\backslash B)\land x\notin C &\Leftrightarrow x\in A \land \lnot(x\in B \land x\notin C)\\ &\Leftrightarrow x\in A\land (x\notin B \lor x\in C)\\ &\Leftrightarrow (x\in A \land x\notin B)\lor(x\in A \land x\in C)\\ &\Leftrightarrow x\in(A\backslash B)\lor x\in (A\cap C) \end{align}$

So I could rewrite the LHS as the following equivalence:

$x\in (A\backslash B)\land x\notin C \Leftrightarrow x\in(A\backslash B)\lor x\in (A\cap C)$

The right hand side of the equivalence:

$A\cap C = \emptyset$

is analogically defined by the expression:

$x\in A \Rightarrow x\notin C$

The whole problem, rewritten: So the whole problem narrows down to proving: $$\Big(x\in (A\backslash B)\land x\notin C \Leftrightarrow x\in(A\backslash B)\lor x\in (A\cap C) \Big)\stackrel{?}{\equiv} \Big(x\in A \Rightarrow x\notin C \Big)$$

Best further approach: My question is generally: What would be the best and most comprehensive further approach as of this point?

• rigorous proof based on boolean algebra with the given result and equivalent transformations;
• splitting the proof into two directions: "$\Longrightarrow$" and "$\Longleftarrow$"
• proof by contradiction (using terms like "suppose", "for an arbitrary" etc.)
• other options?

I know these are all the same, but I'd love to keep going "the rigorous" way with equivalent transformations in the logical expressions. What would your advice be? Thanks in advance!

P.S. I'm also open for corrections of my notation (especially the $\equiv$ symbol, am I using that right?)

Answer 1

I would not approach the problem that way at all: that kind of formal logical computation is in general unnecessarily hard to read and tends to obscure what is going on. It has an important place in formal logic, but it is generally a poor choice for communicating an argument in everyday mathematics, and it really isn’t any more rigorous than a careful verbal argument. See this answer for a little more on the subject.

Here is a straightforward argument written in a reasonably friendly style.

Suppose first that $A\cap C\ne\varnothing$, and let $x\in A\cap C$. Then $x\in C$ implies that $x\notin(A\setminus B)\setminus C$, but $x\in C$ also implies that $x\notin B\setminus C$, and $x\in A$ then implies that $x\in A\setminus(B\setminus C)$. Thus, $A\cap C\ne\varnothing$ implies that

$$(A\setminus B)\setminus C\ne A\setminus(B\setminus C)\,.$$

If, on the other hand, $A\cap C=\varnothing$, then $(A\setminus B)\cap C=\varnothing$, and therefore $(A\setminus B)\setminus C=A\setminus B$. Thus, we want to show that $A\setminus(B\setminus C)=A\setminus B$ as well. Clearly $B\setminus C\subseteq B$, so $A\setminus(B\setminus C)\supseteq A\setminus B$. Suppose that $x\in A\setminus(B\setminus C)$. Then $x\in A$, and $x\notin B\setminus C$, i.e., either $x\notin B$, or $x\in B\cap C$. Now $x$ cannot be in $B\cap C$, because then $x$ would be in $A\cap C$, which is empty. Thus, $x\notin B$, so $x\in A\setminus B$, and we’ve shown that $A\setminus(B\setminus C)\subseteq A\setminus B$. It follows that $A\cap C=\varnothing$ implies that

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

Answer 2

Here is my "rigorous" computational way, although I can agree is by far not optimal or that intuitive...

Let's define logical variables $a \equiv x \in A, b\equiv x\in B, c\equiv x\in C$. Then we start from the LHS and want to arrive at the RHS.

We have $$\begin{align} &(a\land \overline{b}\land\overline{c}) \Leftrightarrow a\land(\overline{b}\lor c)\\ \equiv&\lnot\left[(a\land\overline{b}\land\overline{c})\lor\left(a\land(\overline{b}\lor c)\right)\right]\lor\left[(a\land\overline{b}\land\overline{c})\land\left(a\land(\overline{b}\lor c)\right)\right] &L\Leftrightarrow R \equiv \lnot(L\lor R)\lor(L\land R)\\ \equiv&\lnot\left[a\land(\overline{b} \lor c)\right]\lor\left[a\land \overline{b}\land\overline{c}\right] &(a_1\land a_2...\land a_n)\lor a_i \equiv a_i\\ \equiv&\lnot\left[a\land(\overline{b} \lor c)\right]\lor\lnot\left[\overline{a}\lor b\lor c\right] & (a_1\land a_2\land ...\land a_n) \equiv \lnot(a_1\lor a_2\lor ... \lor a_n)\\ \equiv&\lnot\left[a\land(\overline{b}\lor c)\land\left(\overline{a}\lor b\lor c\right)\right] & \text{de Morgan's law, same as above}\\ \equiv&\lnot\left[a\land(\overline{b}\lor c)\land\left(b\lor c\right)\right] &\text{distributive laws}\\ \equiv&\lnot\left[a\land c\right] &(\overline{b}\lor c)\land(b\lor c) \equiv c\\ \equiv&\overline{a}\lor\overline{c}\\ \equiv&a \Rightarrow \overline{c} \end{align}$$

Thus the equivalence is proven. I don't know, I really find it satisfying working that way! I've maybe just skipped too much between the second and the third row, but all the transformations all really just distributive laws and absorption laws at play.