0
$\begingroup$

Let A and B be subsets of a universe V.

I need to prove the following statement:

(I can't use associativity of symmetric difference)

$A \triangle B = \varnothing \iff A =B$

Here is my proof, could someone please check it and see if it's correct?

$A \triangle B = \varnothing \iff (A - B) \cup (B-A) = \varnothing$

$\iff (A \cap B^c)\cup(B \cap A^c) = \varnothing$

If $(A \cap B^c)$ is equal to a non-empty subset C, then $(A \cap B^c)\cup(B \cap A^c) = C \cup (B \cap A^c) \ne \varnothing$.

If $(B \cap A^c)$ is equal to a non-empty subset C, then $(A \cap B^c)\cup(B \cap A^c) = (A \cap B^c)\cup C \ne \varnothing$.

Therefore we have:

$ (A \cap B^c)\cup(B \cap A^c) = \varnothing \iff (A \cap B^c) = \varnothing \land (B \cap A^c) = \varnothing$ (1)

Let $A = B$, so $A \cap B^c = B \cap A^c = A \cap A^c = B \cap B^c = \varnothing$, which means that:

$ A = B \implies (A \cap B^c) = \varnothing \land (B \cap A^c) = \varnothing$ (2)

Assuming $A \ne B$, at least one of the following conditions holds:

(i). There exists an element x, such that $x \in A$ and $x \notin B$

(ii). There exists an element x, such that $x \notin A$ and $x \in B$

If (i) is true:

$\exists x \in (A \cap B^c) \implies (A \cap B^c) \ne \varnothing$ (3)

If (ii) is true:

$\exists x \in (B \cap A^c) \implies (B \cap A^c) \ne \varnothing$ (4)

By (1),(2),(3), and (4): $A \triangle B = \varnothing \iff A =B$

$\blacksquare$

$\endgroup$
  • 2
    $\begingroup$ You have a slight error in the lines leading up to $(1)$. You treated the case were $(A\cap B^c)\neq \emptyset$ and $(B\cap A^c)=\emptyset$ as well as the case where $(B\cap A^c)\neq \emptyset$ and $(A\cap B^c)=\emptyset$ but you have not yet touched the case where $(A\cap B^c)$ and $(B\cap A^c)$ are simultaneously nonempty. Instead of adding a third case to consider, simply remove the second conditions in each case, i.e. remove the "and $(B\cap A^c)=\emptyset$" from the first line and similarly for the second. $\endgroup$ – JMoravitz Sep 21 '17 at 21:16
  • $\begingroup$ I've edited the proof considering your correction in this comment. Is it correct now? $\endgroup$ – IMK Sep 21 '17 at 21:31
  • 1
    $\begingroup$ Yes, though it might be worth writing as $(A\cap B^c)\cup (B\cap A^c)\supseteq C\supsetneq \emptyset$. There is nothing inherently incorrect about your steps (2) through (4) that I personally noticed, but I found them a bit hard to follow at times in trying to make sure that you were proving both directions of the if and only if. $\endgroup$ – JMoravitz Sep 21 '17 at 21:34
4
$\begingroup$

Apart from the one small mistake I pointed out in the comments above (you did not consider $(A\cap B^c)$ and $(B\cap A^c)$ both being nonempty simultaneously leading up to (1)), your proof is correct but could be cleaned up considerably.

Leading up to (1) you successfully proved that $A\triangle B=\emptyset\iff (A\cap B^c)=(B\cap A^c)=\emptyset$

I would have instead continued by showing $(A\cap B^c)=\emptyset\iff A\subseteq B$.

Let $x\in A$. Then since if $x\notin B$ would imply that $x\in A\cap B^c=\emptyset$, either the assumption that there existed an $x\in A$ at all or the assumption that $x\notin B$ must be incorrect. It follows then that $x\in B$ or that $A=\emptyset$, in either case $A\subseteq B$. Conversely, if $A\cap B^c\neq \emptyset$ then there must be some $x$ for which $x\in A$ and $x\notin B$, which would act as a counterexample to $A$ being a subset of $B$.

The same logic will show $(B\cap A^c)=\emptyset \iff B\subseteq A$.

As $(A=B)\iff (A\subseteq B)\wedge (B\subseteq A)$, we now have a chain of iff statements that prove the desired result.

$\endgroup$
3
$\begingroup$

For sets $A$ and $B$, $A\triangle B=\emptyset$ implies $$A=A\triangle \emptyset = A\triangle (A\triangle B)=(A\triangle A)\triangle B=\emptyset\triangle B=B\,.$$ The converse is trivial.

$\endgroup$
  • $\begingroup$ I'm sorry. I forgot to write that I haven't proved yet that the symmetric difference is associative. So I can't use this. $\endgroup$ – IMK Sep 21 '17 at 21:26
  • $\begingroup$ @IMK There is a very easy proof of the associativity of $\Delta$. $\endgroup$ – Batominovski Sep 21 '17 at 22:08
2
$\begingroup$

So you have to prove : $A \triangle B = \varnothing \iff A =B$

If $A=B$ then $(A - B)=\varnothing$ and $(B - A)=\varnothing$ so $(A - B) \cup (B-A)=\varnothing \cup \varnothing=\varnothing$

If $A \triangle B = \varnothing$ then $(A - B) \cup (B-A)=\varnothing$. If $A$ and $B$ are disjoint and both non-empty then $A-B$ and $B-A$ are non-empty so $(A - B) \cup (B-A)\neq \varnothing$. If one of them is empty and the other is not then either $A-B \neq \varnothing$ or $B-A \neq \varnothing$ so $(A - B) \cup (B-A)\neq \varnothing$. If both are empty then $A=B= \varnothing$.

If they are not disjoint then $A-B$ and $B-A$ are not both empty except in the case $A=B$ when they are both empty.

$\endgroup$

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.