3
$\begingroup$

So I was trying to prove that a null set is a subset of any set.

First, to define when $A$ is a subset of $B$:

$$A \subseteq B \iff \forall x(x \in A \implies x \in B)$$

(At least I think that's right?)

So then consider the empty set $\emptyset$ for which $\forall x(x \not\in \emptyset)$ is true.

I tried to prove that the empty set is a subset of any other set, or:

$$\emptyset \subseteq B \iff \forall x(x \in \emptyset \implies x \in B) \vdash \text{T}$$

To me this seemed true because it was "vacuously true"... somehow. Like it makes sense to call it vacuously true that "all $0$ items in $\emptyset$ can be found in $B$, yep!" but that isn't satisfying to me, how do I "prove" this is the case?

Is $x \in \emptyset$ a false... statement? A false predicate? Something else? Something that results in false so that the implication itself is true. Is this a $(\text{F}\implies \text{F}) \vdash \text{T}$ thing?

Or is it the $\forall$ that makes it false somehow?

What if I had said $\exists x \in \emptyset$, this feels like it would certainly be false but again I can't prove why, it's just an intuition.

Can anyone clarify the correct definitions / implications and why they're true or false or what have you?

$\endgroup$
  • 1
    $\begingroup$ You don't seem to be using the symbol $\vdash$ in the usual way (see en.wikipedia.org/wiki/Turnstile_(symbol) ). Normally $P\vdash Q$ means you have proven $Q$ using assumptions $P$. In this case you want to show $\vdash\emptyset\subseteq B$, and the vacuous implication you are looking for would be $F\vdash P$ (or equivalently $\vdash F\Rightarrow P$) for any $P$. $\endgroup$ – stewbasic Apr 4 '18 at 4:46
  • 1
    $\begingroup$ $x\in\emptyset$ is a predicate. It's neither true nor false until you substitute for $x$, but of course, whatever $x$ you substitute makes it false. So, for every $x$, the statement $x \in \emptyset \implies x \in B$ is true. I don't know if this will help you, but I hope so. $\endgroup$ – saulspatz Apr 4 '18 at 5:03
  • $\begingroup$ "x∈∅ is a predicate. It's neither true nor false until you substitute for x". True. But saying $x \in \emptyset$ is false for all $x$ is perfectly legitimate. $\endgroup$ – fleablood Apr 4 '18 at 5:22
  • $\begingroup$ @stewbasic I was trying to say that "(a iif for all x(p implies q)) is true" is there a better symbol to use? Equal sign? $\endgroup$ – user525966 Apr 4 '18 at 13:18
  • $\begingroup$ @user525966 You could write $\vdash\emptyset\subseteq B\Leftrightarrow\forall x(x\in\emptyset\Rightarrow x\in B)$ or just $\emptyset\subseteq B\Leftrightarrow\forall x(x\in\emptyset\Rightarrow x\in B)$. $\endgroup$ – stewbasic Apr 4 '18 at 21:09
3
$\begingroup$

The proof relies on Ex falso :

$\vdash \lnot P \to (P \to Q)$.

We have to apply it in the form :

$\lnot (x \in \emptyset) \to (x \in \emptyset \to x \in B)$.

We have (axiom or theorem) : $\mathsf {ZF} \vdash \forall x \ \lnot (x \in \emptyset)$.

By Universal instantiation we get : $\lnot (x \in \emptyset)$ and thus from Ex falso, by Modus Ponens : $(x \in \emptyset \to x \in B)$.

Finally, by Universal generalization we conclude with :

$\mathsf {ZF} \vdash \forall x \ (x \in \emptyset \to x \in B)$.

$\endgroup$
  • $\begingroup$ What does it mean to have the turnstile on the far left with nothing before it? $\endgroup$ – user525966 Apr 4 '18 at 15:33
  • $\begingroup$ @user525966 - that is a "law of logic" (in this case: of propositional logic, i.e. a tautology) and thus we can use in every theory. $\endgroup$ – Mauro ALLEGRANZA Apr 4 '18 at 15:35
  • $\begingroup$ In my original post was I using turnstile incorrectly? What's the correct symbol to use there instead? Equal sign? $\endgroup$ – user525966 Apr 4 '18 at 15:53
  • $\begingroup$ The "turnstile" $\vdash$ means derivable (in a system). Thus $\mathsf {ZF} \vdash \varphi$ means that $\varphi$ is a theorem of Zermelo-Frenkel set theory. $\endgroup$ – Mauro ALLEGRANZA Apr 4 '18 at 15:56
  • $\begingroup$ Thus, you want to prove: $\mathsf {ZF} \vdash \forall B \ (\emptyset \subseteq B)$. It is equivalent to say that $\forall B \ (\emptyset \subseteq B)$ is TRUE in every model of the theory. $\endgroup$ – Mauro ALLEGRANZA Apr 4 '18 at 15:58
1
$\begingroup$

1)

$A\subset B$ if all elements of $A$ are elements of $B$. As $\emptyset$ has no elements, then all of them are in $B$.

That's vacuously true.

So $\emptyset \subset B$.

2)

$A\subset B$ if any elements not in $B$ are not in $A$ either. As any element that is not in $B$ is not in $\emptyset$ either, $\emptyset \subset B$.

That's true-true; nothing vacuous about it.

3)

$A \subset B$ if $x \in A \implies x \in B$ is true for all $x$. As $x \in \emptyset$ is always false and $FALSE \implies P$ is always true, $x \in \emptyset \implies x \in B$ is always true.

So $\emptyset \subset B$.

===

So for the most part, yes, they are vacuously true statements, or they are a false premise implies anything true statements.

But it's not all smoke and mirrors. A subset is "embedded" in the superset and everything you can pull out of the subset most come directly from the superset, and there is nothing in the subset that isn't in the superset.

All of those are true about an empty set and a set $B$ and, to me at least, the all feel directly true with no semantic slick word play or gimmicks. The empty skein of the the emptyset (with nothing in it) is embedded every where in the ether of existent space. That doesn't seem to me to be a "trick". And because nothing can be pulled out of the emptyset, if we are standing in the general vacinity of $B$ nothing can be pulled out of the empty set that isn't from $B$. That's a direct objective fact.

$\endgroup$
0
$\begingroup$

In general, the predicate logic statement that $\forall x(x \in A \implies x \in B)$ is written as $A \subseteq B$.

The empty set $\emptyset$ is the set that contains no elements. Therefore, the empty set is a subset of any set, that is, $\emptyset \subseteq X$ for all $X$. This is because the statement $x \in \emptyset$ is false for any $x$, so the imiplication

$$ \forall x(x \in \emptyset \implies x \in X) $$

must be true. (See the truth table below for the for the implication connective.)

$$ \begin{array}{c|l|c} \text{p} & \text{q} & \text{$p \implies q$} \\ \hline T & T & T \\ T & F & F \\ F & T & T \\ F & F & T \end{array} $$

Note that the bottom two rows of the truth table are vacuously true.

$\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.