1
$\begingroup$

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?)

$\endgroup$
2
$\begingroup$

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)\,.$$

$\endgroup$
7
  • $\begingroup$ What I generally mean to avoid by formal logical computation is splitting up my proof in various cases. Plus, I think you've shown the inverse direction only, I mean, only one sided implication. Proving the other direction requires additional writing. I find general algebraic computations much more straightforward, although I can also see your point. Also, a little question: shouldn't it be: ...,i.e., either $x\notin B$, or $x \in C$ . Where did $B\cap C$ come from, I couldn't really understand. $\endgroup$ – D. Petrov Nov 24 '20 at 21:21
  • $\begingroup$ @D.Petrov: No, I showed both directions: the right to left direction directly, and the left to right direction, which I did first, by proving the contrapositive. And no, it should be as I wrote it: if $x\notin B\setminus C$, either $x$ is not in $B$, or $x$ is in $B$ but is also in $C$. $\endgroup$ – Brian M. Scott Nov 24 '20 at 21:33
  • $\begingroup$ Oh, I see, because $x$ can't be in A, not in B, and in C, because $A\cap C$ is empty by assumption. Well, for me, it still depends. I tend to really get confused when it's all so prosaic and word-intensive. I agree with your argument, but I guess I just really find formal transformations more readable. $\endgroup$ – D. Petrov Nov 24 '20 at 21:38
  • 1
    $\begingroup$ @D.Petrov: I strongly suspect that you’re in a minority in that respect, but perhaps more to the point, in my experience most mathematics is written in a more discursive style, albeit a rather concise one, so it’s probably worth your while to try to become more comfortable with it. $\endgroup$ – Brian M. Scott Nov 24 '20 at 21:42
  • 1
    $\begingroup$ @D.Petrov: If you leave a comment here when you’ve done so, I’ll try to make time to take a look. $\endgroup$ – Brian M. Scott Nov 24 '20 at 21:50
2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ Took me a little while to wade through it and supply some of the intermediate steps early on, but yes, that works. $\endgroup$ – Brian M. Scott Nov 24 '20 at 23:57

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.