Proof of the equality of the difference of two sets iff sets are equal (direct vs. indirect)

Question

I have a problem with the following (really) basic result:
$$A\backslash B=B\backslash A \Longleftrightarrow A=B$$

More specifically, I am able to prove it only by contradiction (in particular in the necessary condition - for the sufficient condition I get a contradiction following the steps of a direct proof).

So my problem is, can we actually prove it without using contradiction?
Moreover (and this is probably a very dumb question, so I apologize), is there a general way to know if a given result that we know is true can be proven only by contradiction or there exist a direct proof of it?

Looking forward to any feedback!

Answer 1

Suppose that $A\setminus B=B\setminus A$. Since $B\setminus A\subseteq B$, this implies that $A\setminus B\subseteq B$. But $(A\setminus B)\cap B=\varnothing$, so $A\setminus B=\varnothing$, and it follows immediately that $A\subseteq B$. Similarly, $B\subseteq A$, so $A=B$.

I suspect that you didn’t really use a proof by contradiction, however: more likely you found a proof of the contrapositive and dressed it up as a proof by contradiction. The contrapositive of this implication is that if $A\ne B$, then $A\setminus B\ne B\setminus A$. If $A\ne B$, then without loss of generality there is some $x\in A\setminus B$ that is not in $B\setminus A$. But then $x\in A$ and $x\notin B$, so $A\ne B$. If you began by assuming that $A=B$, this is a proof by contradiction, but that assumption is unnecessary: without it you have a direct proof of the contrapositive of the original implication.

Answer 2

Here is a direct proof:

Take any element $a\in A$. We know that $a\notin B\setminus A=A\setminus B$, so $a\in B$. It follows that $A\subset B$. The reverse containment is similar.

Answer 3

$\Rightarrow$

Let $a \in A$. We want to prove $a\in B$

If $a \in B$ we're done.

If $a\not\in B$ then $a \in A \setminus B$ so $a\in B\setminus A \subseteq B$ so $a\in B$

So $A\subseteq B$

Similarly $B\subseteq A$

So $A=B$

---

$\Leftarrow$

Suppose $A=B$

$A\setminus B = \emptyset = B\setminus A$

Answer 4

Here is the beginning of a proof, using the definition $$x \in A \setminus B \;\equiv\; x \in A \land \lnot(x \in B)$$ Let's just start at the most complex side, the left hand side, and see if we can simplify it at the logic/element level: $$ \begin{align} & A \setminus B \;=\; B \setminus A \\ \equiv & \;\;\;\;\;\text{"extensionality, i.e., two sets are equal iff they have the same elements"} \\ & \langle \forall x :: x \in A \setminus B \;\equiv\; x \in B \setminus A \rangle \\ \equiv & \;\;\;\;\;\text{"definition of $\setminus$, twice"} \\ & \langle \forall x :: x \in A \land \lnot(x \in B) \;\equiv\; x \in B \land \lnot(x \in A) \rangle \\ \equiv & \;\;\;\;\;\text{"negate one side using De Morgan -- to use the Golden Rule (see below)"} \\ & \langle \forall x :: \lnot(x \in A \land \lnot(x \in B) \;\equiv\; \lnot(x \in B) \lor x \in A)) \rangle \\ \end{align} $$ Now apply (what Dijkstra/Gries/etc. call) the Golden Rule, viz. $$P \;\equiv\; Q \;\equiv\; P \land Q \;\equiv\; P \lor Q$$ for every boolean expression $P$ and $Q$.

Answer 5

Here is some another proof. Basically, it uses the fact that $(p \iff q) \iff [(p \wedge q)\vee(\neg p \wedge \neg q)]$. \begin{align} A\setminus B = B \setminus A &\iff [x \in A \setminus B \iff x \in B \setminus A]\\ &\iff [(x \in A \setminus B \wedge x \in B \setminus A) \vee (x \not\in A \setminus B \wedge x \not\in B \setminus A)]\\ &\iff [0 \vee (x \in A \wedge x \in B) \vee (x \not\in A \wedge x \not\in B)]\\ &\iff [x \in A \iff x \in B]\\ &\iff A = B. \end{align}