2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Mauro ALLEGRANZA Jul 29 '15 at 10:07
  • 1
    $\begingroup$ 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") $\endgroup$ – drhab Jul 29 '15 at 10:08
  • 1
    $\begingroup$ 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 $\endgroup$ – KyleW Jul 29 '15 at 10:18
  • $\begingroup$ @KyleW yes that is very helpful $\endgroup$ – Daniel Jul 29 '15 at 11:23
3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

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.