# Set theory proof $(S_1 \cap S_2') \cup (S_1' \cap S_2) = \emptyset$

Prove $S_1 = S_2$ if and only if

$(S_1 \cap S_2') \cup (S_1' \cap S_2) = \emptyset$

I get why it is, I just don't know how to write formal proofs.

$S_2'$, $S_1'$ in this modified notation means it has a line over it.

Thanks

-

When you’re asked to prove a statement of the form ‘$A$ if and only if $B$’, your first thought should be to prove that $A$ implies $B$ and $B$ implies $A$. Take them one at a time.

1. Prove that if $S_1=S_2$, then $\left(S_1\cap\overline{S_2}\right)\cup\left(\overline{S_1}\cap S_2\right)=\varnothing$.

2. Then prove that if $\left(S_1\cap\overline{S_2}\right)\cup\left(\overline{S_1}\cap S_2\right)=\varnothing$, then $S_1=S_2$.

The first part is pretty straightforward: just assume that $S_1=S_2$, and see what that tells you about the expression $\left(S_1\cap\overline{S_2}\right)\cup\left(\overline{S_1}\cap S_2\right)$.

Suppose that $S_1=S_2$. Then \begin{align*}\left(S_1\cap\overline{S_2}\right)\cup\left(\overline{S_1}\cap S_2\right)&=\left(S_1\cap\overline{S_1}\right)\cup\left(\overline{S_1}\cap S_1\right)\\&=\varnothing\cup\varnothing\\&=\varnothing\;.\end{align*}

That’s all there is to it.

The second part is a little harder. You can do it directly, by assuming that $$\left(S_1\cap\overline{S_2}\right)\cup\left(\overline{S_1}\cap S_2\right)=\varnothing$$ and proving that $S_1=S_2$, but it’s easier to prove the contrapositive, which is logically equivalent: prove that if $S_1\ne S_2$, then $\left(S_1\cap\overline{S_2}\right)\cup\left(\overline{S_1}\cap S_2\right)\ne\varnothing$.

Suppose that $S_1\ne S_2$. Then $S_1$ and $S_2$ do not have exactly the same members, so either there is some $x\in S_1$ that is not in $S_2$, or there is some $x\in S_2$ that is not in $S_1$. In symbols, either there is some $x\in S_1\cap\overline{S_2}$, or there is some $x\in S_2\cap\overline{S_1}$. From the definition of union we know that this is the same as saying that there is some $x\in\left(S_1\cap\overline{S_2}\right)\cup\left(\overline{S_1}\cap S_2\right)$, i.e., that $$\left(S_1\cap\overline{S_2}\right)\cup\left(\overline{S_1}\cap S_2\right)\ne\varnothing\;.$$

If you prove the second implication directly, the argument will look something like this.

Suppose that $\left(S_1\cap\overline{S_2}\right)\cup\left(\overline{S_1}\cap S_2\right)\ne\varnothing$. Note that this immediately implies that $S_1\cap\overline{S_2}=\varnothing$ and $\overline{S_1}\cap S_2=\varnothing$. To prove that $S_1=S_2$, I’ll show that $S_1\subseteq S_2$ and $S_2\subseteq S_1$. Suppose that $x\in S_1$. Then since $S_1\cap\overline{S_2}=\varnothing$, it must be the case that $x\notin\overline{S_2}$, and therefore $x\in S_2$. Since $x$ was an arbitrary element of $S_1$, this shows that $S_1\subseteq S_2$. The proof that $S_2\subseteq S_1$ is exactly similar: just interchange the subscripts $1$ and $2$ in the previous three sentences.

-

$S_1=S_2\iff [S_1\subseteq S_2,\,S_2\subseteq S_1]\iff [S_1\cap S_2'=\varnothing,\,S_2\cap S_1'=\varnothing]$

$\qquad\qquad\iff (S_1\cap S_2')\cup(S_2\cap S_1')=\varnothing$

-

To prove an "if and only if" statement, you have to go both ways:

If $S_1 = S_2$, then $(S_1 \cap \overline{S_2}) \cup (\overline{S_1} \cap S_2) = \emptyset$

Proof: Since $S_1 = S_2$, we have:

$$(S_1 \cap \overline{S_2}) \cup (\overline{S_1} \cap S_2) = (S_1 \cap \overline{S_1}) \cup (\overline{S_1} \cap S_1) = \emptyset \cup \emptyset = \emptyset$$

If $(S_1 \cap \overline{S_2}) \cup (\overline{S_1} \cap S_2) = \emptyset$, then $S_1 = S_2$.

Proof: Since $(S_1 \cap \overline{S_2}) \cup (\overline{S_1} \cap S_2) = \emptyset$, it means that $S_1 \cap \overline{S_2} = \emptyset$ and $\overline{S_1} \cap S_2 = \emptyset$. Take the complement of both sides of the second equation:

\begin{align*} \overline{(\overline{S_1} \cap S_2)} &= \overline{\emptyset} \\ S_1 \cup \overline{S_2} &= U \end{align*}

Together with the first equation, we have:

$$S_1 \cap \overline{S_2} = \emptyset \\ S_1 \cup \overline{S_2} = U$$

What can you conclude about the relationship between $\overline{S_1}$ and $\overline{S_2}$ from above?

-

Hint: the union of two sets can only be empty if both sets are empty. You need to prove that every element that is in S1 is also in S2 and every element in S1' is not in S2. So let $a \in S1$. If $a \not \in S2, \ldots$

-

It is not really necessary to do a two-way proof for this one. Starting with the expression $(S_1 \cap \overline{S_2}) \cup (\overline{S_1} \cap S_2)$, I would calculate \begin{align} & x \in (S_1 \cap \overline{S_2}) \cup (\overline{S_1} \cap S_2) \\ \equiv & \;\;\;\;\;\text{"expand definition of \cup, of \cap twice, and of \overline{\cdot} twice"} \\ & (x \in S_1 \land x \not\in S_2) \lor (x \not\in S_1 \land x \in S_2) \\ \equiv & \;\;\;\;\;\text{"logic: simplify by introducing \not\equiv"} \\ & x \in S_1 \not\equiv x \in S_2 \\ \end{align} That simplifies things a lot. Now we can prove the original statement as follows: \begin{align} & (S_1 \cap \overline{S_2}) \cup (\overline{S_1} \cap S_2) = \emptyset \\ \equiv & \;\;\;\;\;\text{"property of \emptyset"} \\ & \langle \forall x :: \lnot (x \in (S_1 \cap \overline{S_2}) \cup (\overline{S_1} \cap S_2)) \rangle \\ \equiv & \;\;\;\;\;\text{"using the previous calculation"} \\ & \langle \forall x :: \lnot (x \in S_1 \not\equiv x \in S_2) \rangle \\ \equiv & \;\;\;\;\;\text{"logic: simplify"} \\ & \langle \forall x :: x \in S_1 \equiv x \in S_2 \rangle \\ \equiv & \;\;\;\;\;\text{"set extensionality"} \\ & S_1 = S_2 \\ \end{align}

-