Direct proof of empty set being subset of every set
Recently I finished my first pure mathematics course but with some intrigue about some proofs of definitions by contradiction and contrapositive but not direct proofs (the existence of infinite primes for example), I think most of them because the direct proof extends away from a first mathematics course or the proofs by contradiction/contrapositive are more didactic. The one that most bothers me in particular is the demonstration that the empty set is a subset of every set, and it is unique. I understand the uniqueness and understand the proof by contradiction:
"Suppose $\emptyset \subsetneq A$ where $A$ is a set. So it exists an element $x \in \emptyset$ such that $x \notin A$ wich is absurd because $\emptyset$ does not have any elements by definition."
but I would like to know if there exists a direct proof of this and if indeed extends from a first course. Thanks beforehand.
$\endgroup$9 Answers
$\begingroup$For any $B\subseteq A$, we have $A\setminus B\subseteq A$. So $A\setminus A=\varnothing\subseteq A$.
(This proof operates at a slightly higher level of abstraction than verifying the definition of $\varnothing\subseteq A$. Since the definition is so easy to verify, you might think that it's silly to take a different strategy. If so, fair enough!)
$\endgroup$ 1 $\begingroup$There is a direct proof, if you know what a vacuous truth is. But the problem is that when one sees this statement $\varnothing\subseteq A$, it's usually before fully understanding vacuous arguments. So it's slightly more instructive to first give a proof by contradiction, and then discuss vacuous arguments. At least from my experience teaching this argument.
The proof is simple. We verify that $\forall x\in\varnothing$ it holds that $x\in A$. However, since $\forall x(x\notin\varnothing)$, the argument holds vacuously. And we are done.
$\endgroup$ 4 $\begingroup$Yes, there's a direct proof:
The way that we show that a set $A$ is a subset of a set $B$, i.e. $A \subseteq B$, is that we show that all of the elements of $A$ are also in $B$, i.e. $\forall a \in A, a\in B$.
So we want to show that $\emptyset \subseteq A$. So consider all the elements of the empty set. There are none. Therefore, the statement that they are in $A$ is vacuously true: $\forall x \in \emptyset, x \in A$. So $\emptyset \subseteq A$.
$\endgroup$ $\begingroup$Here is another direct proof, more calculational, where we first use the definitions and basic properties of $\;\emptyset,\subseteq\;$ and then simplify using predicate logic: \begin{align} & \emptyset \subseteq A \\ \equiv & \qquad\text{"definition of $\;\subseteq\;$"} \\ & \langle \forall x :: x \in \emptyset \Rightarrow x \in A \rangle \\ \equiv & \qquad\text{"basic property of $\;\emptyset\;$"} \\ & \langle \forall x :: \text{false} \Rightarrow x \in A \rangle \\ (*) \quad \equiv & \qquad\text{"logic: false implies anything"} \\ & \langle \forall x :: \text{true} \rangle \\ \equiv & \qquad\text{"logic: leave out unused quantified variable"} \\ & \text{true} \\ \end{align} Note how the last steps are really just a more detailed proof of the principle of 'vacuous truth', as used by earlier answers.
If you want more detail on the third step $(*)$: \begin{align} & \text{false} \Rightarrow P \\ \equiv & \qquad\text{"rewrite"} \\ & \lnot \text{false} \lor P \\ \equiv & \qquad\text{"simplify"} \\ & \text{true} \lor P \\ \equiv & \qquad\text{"simplify"} \\ & \text{true} \\ \end{align}
$\endgroup$ $\begingroup$Another way to look at vacuous proofs. Make use of the logical principle that anything follows from a falsehood (the arbitrary consequent rule): $$P\implies[\neg P \implies Q]$$
Your proof:
$\forall a: \neg a\in \emptyset$ (by defintion, better to use $\neg$ than $\notin$ in this case)
Let $S$ be any set.
Suppose $x\in \emptyset$
$\neg x\in \emptyset$ (from 1)
$\neg\neg x\in \emptyset\implies x\in S$ (arbitrary consequent rule applied to 4)
$x\in \emptyset\implies x\in S$ (from 5)
$x\in S$ (from 3 and 6)
$x\in \emptyset \implies x\in S$ (conclusion from 3 and 7)
$\forall a:[a\in\emptyset\implies a\in S]$ (generalizing from 8)
Yes, lines 6 and 8 look the same, but they play different roles in the proof. We can't immediately generalize on line 6.
$\endgroup$ $\begingroup$For any set A, union of set A and nullset, gives set A. this proves that null set is subset of every set A. Using union operation for subset definition is the trick.
$\endgroup$ 1 $\begingroup$Let say we have two sets
A = {1,2,3,4} and B = {2,3,4}
A $\cup$ B = {1,2,3,4} = A
Applying Union operation does not changes anything to set A. Which means we are performing Union operation between set and its subset.
It implies B $\subset$ A
In same manner, if we perform Union operation between A and empty set.
A $\cup$ $\emptyset$ = A
it implies $\emptyset$ $\subset$ A.
$\endgroup$ $\begingroup$Here's a definition of "subset" that works:
"If set A contains an element that is not also in set B, then A is not a subset of B; otherwise, it is."
So, it is not true that the empty set contains an element that is also not in some (other) set or another. Therefore, the empty set is a subset of every set.
The problem is that the definition of a "subset" is sometimes (or even usually) stated like this:
"If all of the elements of set A are also in B, then A is a subset of B; otherwise, it is not."
But according to general English usage, this definition pre-supposes at least one element in set A and therefore can't be applied to the empty set -- at least, not according to general English usage.
An interesting follow-on question is, I think: "Why do mathematicians even conceive of the empty set, given that it constitutes 'nothingness'?"
$\endgroup$ 13 $\begingroup$A set $A$ is a subset of a set $B$ if $A$ has no elements that are not also in $B:$
$¬∃x∈A:x∉B$
Since the $empty$ $set$ has $no$ $elements$, it is clearly a subset of every set.
$\endgroup$
