# how to prove: $A=B$ iff $A\bigtriangleup B \subseteq C$

I am given this: $A=B$ iff $A\bigtriangleup B \subseteq C$. And $A\bigtriangleup B :=(A\setminus B)\cup(B\setminus A)$.

I dont know how to prove this and I dont know where to start.

-
What is $C$? Any set? – Asaf Karagila Apr 28 '13 at 17:05
@AsafKaragila, oh yeah, i forgot to mention. yes, $C$ is any set – doniyor Apr 28 '13 at 17:07

Hint: For an arbitrary set $C$, what is the one and only set that is the subset of every set?

So given $\,A\triangle\,B \subseteq C$, where $C$ is any arbitrary set, what does this tell you about the set $A\triangle B$?

And what does that tell you about the relationship between $A$ and $B$?

-
very sharp hints!! I am thinking now... – doniyor Apr 28 '13 at 17:12
I cannot bind $C$ with $A,B$ :( – doniyor Apr 28 '13 at 17:15
The only set that's a subset of every set is the empty set. Now, use the fact that $A \triangle B$ must be the empty set, if it is to be a subset of all sets, and use the definition of $A\triangle B$ to conclude $A\triangle B = \varnothing \iff A = B$ – amWhy Apr 28 '13 at 17:17
wooow!! didnot come to this. very nice, learnt new thing. thanks in tons – doniyor Apr 28 '13 at 17:19
You're welcome, doniyor! – amWhy Apr 28 '13 at 17:20

Here is a another way to do this, where the empty set almost automatically falls out of the calculation.

You have to prove that $A = B \;\equiv\; \langle \forall C :: A \Delta B \subseteq C \rangle$. (Note that I write $\equiv$ where many others write $\Leftrightarrow$.)

One heuristic that often works when proving statements about sets, is to use set extensionality ("two sets are equal iff they have the same elements") and something similar for $\subseteq$ etc. That translation brings us from the level of sets to the logic level, where simpler laws usually apply. For example, we have the following law (which can be used as the definition) for $\Delta$: $$(0) \;\;\;\;\; x \in A \Delta B \equiv x \in A \not\equiv x \in B$$ Now looking at the problem in these terms, you have to prove that $$\langle \forall x :: x \in A \equiv x \in B \rangle$$ is equivalent to $$\langle \forall C :: \langle \forall x :: x \in A \Delta B \Rightarrow x \in C \rangle \rangle$$ Another heuristic is that if you need to prove a relationship (here: equivalence), you start with the most complex side (here: the last expression), and transform until you've reached the other side. So we can calculate as follows: \begin{align} & \langle \forall C :: \langle \forall x :: x \in A \Delta B \Rightarrow x \in C \rangle \rangle \\ \equiv & \;\;\;\;\;\text{"definition of \Delta -- really the only thing we can do"} \\ & \langle \forall C :: \langle \forall x :: (x \in A \not\equiv x \in B) \Rightarrow x \in C \rangle \rangle \\ \equiv & \;\;\;\;\;\text{"logic: expand \Rightarrow -- work towards our goal by introducing x \in A \equiv x \in B"} \\ & \langle \forall C :: \langle \forall x :: (x \in A \equiv x \in B) \lor x \in C \rangle \rangle \\ \equiv & \;\;\;\;\;\text{"logic: exchange quantifications -- to bring \forall C nearer the only place it is used"} \\ & \langle \forall x :: \langle \forall C :: (x \in A \equiv x \in B) \lor x \in C \rangle \rangle \\ \equiv & \;\;\;\;\;\text{"logic: move x \in A \equiv x \in B outside of \forall C -- again to move \forall C nearer its use"} \\ & \langle \forall x :: (x \in A \equiv x \in B) \lor \langle \forall C :: x \in C \rangle \rangle \\ \end{align} At this point we are almost where we want to be, except for that pesky $\langle \forall C :: x \in C \rangle$. To make progress, we have to stop and think: given any $x$, when is $\langle \forall C :: x \in C \rangle$ true? I.e., which $x$ is an element of every set? The answer, obviously, is that there is no such $x$, since the empty set has no elements: \begin{align} & \langle \forall C :: x \in C \rangle \\ \Rightarrow & \;\;\;\;\;\text{"choose C := \emptyset"} \\ & x \in \emptyset \\ \equiv & \;\;\;\;\;\text{"definition of \emptyset"} \\ & \textrm{false} \\ \end{align} (Note that this is a proof by contradiction to show that $\langle \forall C :: x \in C \rangle \equiv \textrm{false}$.) Therefore we can complete our first calculation: \begin{align} & \langle \forall x :: (x \in A \equiv x \in B) \lor \langle \forall C :: x \in C \rangle \rangle \\ \equiv & \;\;\;\;\;\text{"by our second calculation"} \\ & \langle \forall x :: (x \in A \equiv x \in B) \lor \textrm{false} \rangle \\ \equiv & \;\;\;\;\;\text{"logic: simplify"} \\ & \langle \forall x :: x \in A \equiv x \in B \rangle \\ \end{align} Putting all of this together, we've proved that $\langle \forall C :: A \Delta B \subseteq C \rangle \equiv A = B$, which is what you set out to prove.

-
Of course the answer from @amWhy suggests the much shorter \begin{align} & \langle \forall C :: A \Delta B \subseteq C \rangle \\ \equiv & \;\;\;\;\;\text{"set theory: only \emptyset is a subset of every set"} \\ & A \Delta B = \emptyset \\ \equiv & \;\;\;\;\;\text{"set theory: the difference between A and B is empty"} \\ & A = B \\ \end{align} However, that proof assumes a number of fairly specific set theory laws. In my proof I attempted to use mostly general predicate logic, with the least number of surprising/creative steps. – Marnix Klooster Apr 29 '13 at 4:51
Thank you so much, Marnix. fantastic explanation!! – doniyor Apr 29 '13 at 5:09
@doniyor You're welcome. :-) – Marnix Klooster Apr 29 '13 at 5:10