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.

  • $\begingroup$ "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$. $\endgroup$ – Git Gud Sep 18 '14 at 17:50
  • 1
    $\begingroup$ 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. $\endgroup$ – Git Gud Sep 18 '14 at 17:53
  • $\begingroup$ 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 :) $\endgroup$ – 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$.

  • $\begingroup$ For more information about the reasoning used at the end: en.wikipedia.org/wiki/Disjunctive_syllogism $\endgroup$ – stochasm Sep 18 '14 at 17:58
  • $\begingroup$ As logical principles go, I think this is one of the more intuitively clear ones. $\endgroup$ – MJD Sep 18 '14 at 18:01
  • $\begingroup$ 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. $\endgroup$ – Spaced Sep 18 '14 at 18:05
  • $\begingroup$ I'm glad I could help. $\endgroup$ – MJD Sep 18 '14 at 18:13

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.