For all sets $A$ and $B$, ( $A \cap B = A \cup B \implies A = B$ )

Question

Prove: For all sets $A$ and $B$, ( $A \cap B = A \cup B \implies A = B$ )

In the upcoming proof, we make use of the next lemma.

Lemma: For all sets $A$ and $B$, $A = B$ iff $A - B = B - A$.

Proof: Let $A$ and $B$ be arbitrary sets and let $S = A \cap B$ and $T = A \cup B$. If $S = T$, then $S$ and $T$ have got the same elements. Thus, by simplification law, Towe can state that

$\forall x \in A \cup B \, ( x \in A \cap B ) \tag 1 \label 1$

To prove $A = B$ we might as well harness our lemma and establish that $A - B = A - B$, which we can be verified through the axiom of extension by showing that $\forall y \in A - B \,( y \in B - A )$ and $\forall y^* \in B - A \, (y^* \in A - B )$. So, let

$y \in A - B \tag 2 \label 2$

and let $y^* \in B - A \tag 3 \label 3$

From \eqref{2} we rest assured that $y\in A$ and $y\not\in B$. Furthermore, by \eqref{1} we know that

$y \in A \land y \in B \tag 4 \label 4$

Nonetheless \eqref{4} is an antilogy since from \eqref{2} we deduced, inter alia, that $y\not\in B$. Notice thus far we are trying to prove that \eqref{3} and $F$ implies $y \in B - A $ and $y^* \in A - B$. Therefore, it’s vacuously true that

$A = B$

Q.E.D

I believe I could've done this proof more easily by using the contrapositive method, but my question is, is this proof right?

Answer 1

Your proof is correct up to $y \notin B.$ Note that $y \in A \setminus B \implies y \in A \cup B =A\cap B \implies y \in B,$ which is a contradiction. This implies $A\setminus B=\emptyset$ and similarly $B\setminus A =\emptyset.$ Therefore $A \setminus B=B\setminus A.$ Moreover, the use of "vacuously true" in the end is also incorrect.

Alternatively, the statement can be proved in a much simpler way as follows:

$$A\subseteq A \cup B = A \cap B \subseteq B.$$ Similarly $B\subseteq A$ and hence $A=B.$

Answer 2

As others have already noted, it is indeed much simpler to prove this by contrapositive. But you asked if your proof is correct, which is a perfectly reasonable question that I would like to answer.

There is a gap in your logic.

You have set out to prove:

$$ \forall y (y\in A-B \rightarrow y \in B-A)\textrm{ and } \forall y^* (y^*\in B-A\rightarrow y^*\in A-B) $$

You fixed arbitrary elements $y$ and $y^*$ and assumed $y\in A-B$ and $y^*\in B-A$. Then you derived a contradiction from the assumption $y\in A-B$ and then said that from this false premise you can conclude anything, such as $y^*\in A-B$. Note that you did all of this without ever using the assumption $y^*\in B-A$. So, in symbols, what you really proved is

$$ \forall y\big(y\in A-B\rightarrow (y\in B-A \textrm{ and }\forall y^*[y^*\in A-B])\big) $$

But this is not logically equivalent to proving the two statements above.

In other words, the two statements you set out to prove are separate. Thus you need to prove the second statement: $$ \forall y^* (y^*\in B-A\rightarrow y^*\in A-B) $$ on its own, and not under a running assumption that there is some $y\in A-B$ (which is only relevant in proving the first statement). To put it simply, the falsity $F$ you obtained is only applicable in proving $\forall y(y\in A-B\rightarrow y\in B)$ (since it was generated in the process of that proof). Thus to prove the second statement $\forall y^* (y^*\in B-A\rightarrow y^*\in A-B)$ you need to start with a clean slate. Of course the proof of the second claim is equally straightforward and you can obtain a similar contradiction.

These two statements are similar enough that you could employ a "without loss of generality". For example, you want to prove $A-B\subseteq B-A$ and $B-A\subseteq A-B$. Since $A$ and $B$ are interchangeable in this situation, you could say without loss of generality it is enough to prove one inclusion.

The main conclusion here is that if you want to prove two separate statements, then you should not try to prove them simultaneously, as you have done here, since it increases the risk of such oversights.

A final comment is that usually when one writes "Proof" after the statement of a lemma, it gives the impression that you are about to prove the lemma just stated. So it's good practice to reiterate the statement you are actually about to prove (which is a good idea here since the statement doesn't appear in the body of the question, only the title).

Other options would be:

Theorem. blah blah

We will use this lemma.

Lemma: blah blah

We now prove the theorem.

Proof. blah blah

OR

Theorem. blah blah

We will use this lemma.

Lemma. blah blah

Proof of the Theorem. blah blah