My proof is: Let $S$ be a set, to show that $∅⊈S$, we must show that $∃x(x∈∅\implies x∉S)$ is true. Because $x∈∅$ is false, the conditional statement $x∈∅\implies x∉S$ is always true. Therefore, $∃x(x∈∅\implies x∉S)$ is true. This completes the proof.

I cannot find anything wrong.

  • $\begingroup$ This doesn't show that $\emptyset \notin S$. $\endgroup$
    – aschepler
    Sep 27 at 13:38
  • 3
    $\begingroup$ "to show that $∅∉S$, we must show that $∃x(x∈∅\implies x∉S)$ is true": no, what you must show is $\forall x(x=∅\implies x∉S)$ (but you won't be able to show it because it is false for many $S$'s). $\endgroup$ Sep 27 at 13:40
  • $\begingroup$ If you change the $\exists$ to $\forall$ you are showing that $\emptyset$ is disjoint from every set, which is true. $\endgroup$ Sep 27 at 13:40
  • 5
    $\begingroup$ You misunderstood the interplay of negation and $\to$: $\subseteq$ is defined as $\forall x (x \in \emptyset \to x \in S)$. Thus, its negation $\nsubseteq$ will be $\lnot \forall x (x \in \emptyset \to x \in S)$ that is $\exists x (x \in \emptyset \land x \notin S)$. $\endgroup$ Sep 27 at 13:51
  • 2
    $\begingroup$ Because $x \in \emptyset$ is always false. The emptyset is .... empty, that means exactly: $\forall x \lnot (x \in \emptyset)$ $\endgroup$ Sep 27 at 13:59

2 Answers 2


Your error is very simple. It is not true that

To show $\varnothing\not\subseteq S$ we must show that $\exists x(x\in\varnothing\implies x\notin S)$.

This is false. You have messed up the negation of "is a subset of".

Recall that $A\subseteq B$ is shorthand for $$\forall x (x\in A\implies x\in B).$$ That means that $A\not\subseteq B$ is shorthand for: \begin{align*} \neg\left(\forall x(x\in A\implies x\in B)\right) &\iff \exists x\left(\neg\bigl( x\in A\implies x \in B\bigr)\right)\\ &\iff \exists x\bigl( (x\in A)\wedge \neg(x\in B)\bigr)\\ &\iff \exists x\bigl( (x\in A)\wedge (x\notin B)\bigr). \end{align*} This because the negation of $P\to Q$ is $P\wedge(\neg Q)$.

So what you actually should have is:

To show $\varnothing\not\subseteq S$, we must show that $\exists x\bigl((x\in\varnothing)\wedge (x\notin S)\bigr)$.

Now note that $(x\in\varnothing)\wedge (x\notin S)$ is always false, since $x\in \varnothing$ is always false.


By definition of subset, for any two sets $A,B$, we have $A \subseteq B$ if and only if

$$\forall x[x \in A \to x \in B]$$

Thus, we show $A \nsubseteq B$ by taking the negation of said formula

$ \begin{array}{11} \neg \forall x[x \in A \to x \in B] & \\ \exists x \neg [x \in A \to x \in B] & \text{Negation Rules for Quantifiers} \\ \exists x \neg [\neg (x \in A) \vee x \in B] & \text{Implication Rule}\\ \exists x [\neg\neg (x \in A) \wedge \neg (x \in B)] & \text{DeMorgan's Law}\\ \exists x [x \in A \wedge \neg (x \in B)] & \text{Double Negation Elimination}\\ \exists x [x \in A \wedge x \notin B] & \text{Definition of $\notin$}\\ \end{array} $

Thus, in order to show $\emptyset \nsubseteq S$ for every set $S$, you must prove

$$ \exists x [x \in \emptyset \wedge x \notin S] $$

for some arbitrary $S$. Of course, the first conjunct $x \in \emptyset$ is always false, so the formula is always false.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .