# An Exercise on showing thoroughly that two sets are equal

I have never had too many exercises on this subject. So while doing a couple of exercises I stumbled across a problem that keeps me confused, especially because I cannot honestly say that I understand what's going on:

$$U \setminus (U \setminus A ) = A , \text{ where } A \subset U$$

Of course this is right, a simple venn-diagram shows that, however showing the two inclusions I have a feeling that my reasoning is not good enough:

\begin{align}\text{Let $x \in U \setminus (U \setminus A)$ be fixated but arbitrary} &\implies x \in U \wedge x \notin (U \setminus A) \\ &\implies x \in U \wedge \neg( x \in (U \setminus A)) \\ &\implies x \in U \wedge \neg(x \in U \wedge x \notin A) \\ &\implies x \in U \wedge(x \notin U \vee x \in A) \\ \implies \underbrace{(x \in U \wedge x \notin U )}_{\text{false}} \vee (x \in U \wedge x \in A) \implies x \in A\end{align}

If I have done the exercise correctly, then I fail to understand the vacuously wrong statement that x is an element of $U$ and at the same time isn't. This seems to be equivalent with the statement that $x \in \emptyset$ which exists in Mathematics as a general wrong statement, meaning that if $x \in \emptyset \implies$Euler was my teacher.

If I can work with the empty set then I have an idea how to show the other inclusion $A \subset U \setminus (U \setminus A)$, if not then I must practice some more on the topic.

I'd appreciate some comments/answer on how to read/understand my derived result and if possible a hint on the remaining inclusion.

• "If I have done the exercise correctly, then I fail to understand the vacuously wrong statement that $x$ is an element of $U$ and at the same time isn't". But you didn't conclude that, did you? So there's no problem. Minor nitpick: I wouldn't say it's vacuously wrong, but rather vacuously false. Edit: And if this makes you uncomfortable, then you should also think about the possibility $U=\varnothing$. – Git Gud Sep 18 '14 at 17:50
• For the other inclusion take $x\in A$. The goal is to prove that $x\in U \setminus (U \setminus A)$. Recall that $A\subseteq U$, so $x\in U$ and $x\in A$. Thus $x\not \in U\setminus A$. Try to conclude. – Git Gud Sep 18 '14 at 17:53
• You can change $\Rightarrow$ to $\Leftrightarrow$ everywhere with no mistake and obtain the result. I don't see what is wrong with the vacuously wrong statement. It is OK in math to come to such things :) – Tigran Saluev Sep 18 '14 at 18:36

If you are unhappy with

$$\underbrace{(x \in U \wedge x \notin U )}_{\text{false}} \vee (x \in U \wedge x \in A)$$

then don't go there. Instead, go back to the last part that you are comfortable with:

$$x \in U \wedge(x \notin U \vee x \in A)$$

Which you can separate into two statements:

$$x \in U \\ x \notin U \vee x \in A$$

The statement $x \notin U \vee x \in A$ admits two possibilities: $x\notin U$ or $x \in A$. But you know $x\in U$, so it isn't the first one, and must be the second one, $x\in A$.

It is a general principle of logical reasoning that from $A$ and $\lnot A \lor B$, you may conclude $B$.

• For more information about the reasoning used at the end: en.wikipedia.org/wiki/Disjunctive_syllogism – stochasm Sep 18 '14 at 17:58
• As logical principles go, I think this is one of the more intuitively clear ones. – MJD Sep 18 '14 at 18:01
• Thanks a lot @MJD, going back one step really made all the difference, I was focussed too much on the final statement rather than aligned the previous one in a clear way as you did. – Spaced Sep 18 '14 at 18:05
• I'm glad I could help. – MJD Sep 18 '14 at 18:13