# Prove that $E \cap E^{c} = \varnothing$.

This is a 'simple' question on elementary set theory. I said 'simple' because statement like this is presented all over introductory sections in advanced math books, but they are not really proved in most texts that I read.

Here is my proof for $E \cap E^{c} = \varnothing$, where $E$ is a subset of some universe set $U$.

For the $\subset$ part, we want to show that if $x \in E \cap E^{c}$, then $x \in \varnothing$.

Let $x \in E \cap E^{c}$. It follows that $x$ is in both $E$ and $E^{c}$. However, if $x \in E$, $x \notin E^{c}$. Therefore the first part of the implication is false. Obviously the second part of the implication is false also (i.e. $x \in \varnothing$ is false). This implies that the statement if $x \in E \cap E^{c}$, then $x \in \varnothing$ is actually true vacuously.

For the $\supset$ part, well again we can say that the statement is true vacuously.

Therefore, we conclude that $E \cap E^{c} = \varnothing$. Q.E.D

I feel uneasy because of all these vacuously true statements. So does this proof really hold?

• Yes, it holds : $x \in \emptyset$ if and only if $x \in E \land x \notin E$. As you say, both parts are false, and thus the iff (the bi-conditional) is true. – Mauro ALLEGRANZA Jul 29 '15 at 10:07
• If $p$ is false then $p\rightarrow q$ is true for any $q$, but you cannot conclude that $q$ is false (as you are doing: "obviously the second part of the implication is false") – drhab Jul 29 '15 at 10:08
• to avoid the vacuously uncertainty, suppose $E \cap E^c \neq \emptyset$, then $\exists x : x \in E \cap E^c$ and then use this to derive a contradiction – KyleW Jul 29 '15 at 10:18
• @KyleW yes that is very helpful – Daniel Jul 29 '15 at 11:23

## 2 Answers

If $p$ is false then $p\rightarrow q$ is true for any statement $q$.

This becomes evident by realizing that $p\rightarrow q$ is actually the same as $\neg p\vee q$.

So defining $p$ as the (false) statement $x\in E\cap E^c$ and $q$ as the statement $x\in\varnothing$ we arrive at the conclusion that $x\in E\cap E^c\rightarrow x\in\varnothing$ is a true statement.

Likewise it can be shown that $x\in\varnothing\rightarrow x\in E\cap E^c$ is a true statement. This because $x\in\varnothing$ is false.

You did prove that the implication $x \in E^c \cap E \implies x \in \varnothing$ is true, which means that $E^c\cap E \subseteq \varnothing$, but there's an easier way to prove that $E^c\cap E = \varnothing$: you could try proving it by assuming that there is an element $x$ in $E^C\cap E$ and reaching a contradiction.

Using this technique, you could have actually ended the proof at

Let $x \in E \cap E^{c}$. It follows that $x$ is in both $E$ and $E^{c}$. However, if $x \in E$, [then] $x \notin E^{c}$.

because at this point you had $x \in E^c$ (because the intersection is a subset of $E^c$) and $x \notin E^c$, a contradiction.