# I have a proof that " For every set $S, ∅⊈S$" BUT I cannot find anything wrong.

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.

• This doesn't show that $\emptyset \notin S$. Sep 27 at 13:38
• "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). Sep 27 at 13:40
• If you change the $\exists$ to $\forall$ you are showing that $\emptyset$ is disjoint from every set, which is true. Sep 27 at 13:40
• 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)$. Sep 27 at 13:51
• Because $x \in \emptyset$ is always false. The emptyset is .... empty, that means exactly: $\forall x \lnot (x \in \emptyset)$ Sep 27 at 13:59

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.