6
$\begingroup$

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$
15
$\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$
  • 2
    $\begingroup$ I didn't know about vacuous truths. From what I just read, its a proposition of the form $P\implies Q$ where one knows $P$ to be false. It's still a little confusing because, in this statement, $x\in A$ might be true, I guess this requires studying other examples of vacuous proofs to understand well the concept. Thank you! $\endgroup$ – taue2pi Jan 8 '14 at 6:00
  • $\begingroup$ There were a couple of threads about vacuous truths on the site before. You might as well read them. $\endgroup$ – Asaf Karagila Jan 8 '14 at 6:04
  • $\begingroup$ I came across this question in the first chapter of Rudin's book on analysis and initially I went to proof by contradiction and did it "correctly" by most standards but I still feel as though there is something of fundamental nature that I am missing. It is not as if $\varnothing$ contains the integer 0; it's empty, yeah? It contains no element, so how can it be the case that this "no element-ness" is represented in every single set as $\varnothing\subseteq A$ means? Apologies since this is quite naive; but it's really tripping me up! $\endgroup$ – ofey73 Apr 19 '19 at 23:07
  • 1
    $\begingroup$ @Theodore: It's a matter of syntax, or semantics if you will. It's how mathematical conditionals are built. I actually wrote an answer about this recently. The short version is that implications in mathematics are difference from implications in natural language, and $\subseteq$ is defined by an implication. $\endgroup$ – Asaf Karagila Apr 19 '19 at 23:12
16
$\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$
  • 2
    $\begingroup$ This proof is really nice! I already accepted another answer because introduced me to vacuous proofs but yours is very neat. Thank you $\endgroup$ – taue2pi Jan 8 '14 at 6:05
6
$\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$
4
$\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$
0
$\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:

  1. $\forall a: \neg a\in \emptyset$ (by defintion, better to use $\neg$ than $\notin$ in this case)

  2. Let $S$ be any set.

  3. Suppose $x\in \emptyset$

  4. $\neg x\in \emptyset$ (from 1)

  5. $\neg\neg x\in \emptyset\implies x\in S$ (arbitrary consequent rule applied to 4)

  6. $x\in \emptyset\implies x\in S$ (from 5)

  7. $x\in S$ (from 3 and 6)

  8. $x\in \emptyset \implies x\in S$ (conclusion from 3 and 7)

  9. $\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$
0
$\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$
  • $\begingroup$ First you need to prove that $A\cup B=A$ if and only if $B\subseteq A$. $\endgroup$ – Asaf Karagila Aug 30 '16 at 6:24
-1
$\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$
  • $\begingroup$ "But according to general English usage", mathematics is its own language. What if I teach my students in Hebrew, or in Esperanto or Inuit? What if I invented a new language just to teach my students about the empty set and there the statement "If all elements of $A$ are elements of $B$" does not presupposes the existence of any elements in $A$? What if this language sounds extremely like English, or Hebrew, or Esperanto, or even Inuit? Is it okay then? $\endgroup$ – Asaf Karagila May 2 '14 at 5:38
  • $\begingroup$ Maybe your students would just figure that your statement meant my first definition. I'm only pointing out the possible motivation of the OP's question by making an association with something outside of the self-contained, consistent system that is mathematics. After all, one can always question how meaningful it is merely to show that an assertion follows from certain mathematical definitions, principles, procedures, etc., which is what the OP seems to be doing. Perhaps the OP is wondering if "the empty set is a subset of every set" is asserted only for the sake of mathematical consistency. $\endgroup$ – Jean Forgeron May 2 '14 at 7:23
  • $\begingroup$ I'm sorry. Your answer makes no sense, and your comment makes no sense either. One can always question everything, that's the point of skepticism, I can even question your understanding of mathematics and mathematical language (and I should). I also don't know of any mathematical statement that is asserted for anything other than mathematical purposes. $\endgroup$ – Asaf Karagila May 2 '14 at 7:34
  • $\begingroup$ Now, now... (Please!) "I also don't know of any mathematical statement that is asserted for anything other than mathematical purposes." Really? A physicist would certainly disagree with you. $\endgroup$ – Jean Forgeron May 2 '14 at 7:36
  • 1
    $\begingroup$ Yes, physicists think that mathematics exists to describe the universe; and engineers think that physics exist to guide their constructions; and mindless drones think that engineering exists so they can live their thoughtless lives faster. I don't think that anything physicists say about mathematics has any weight here. It might be true, or it might be false. But that claim you refer, which is more about philosophy of mathematics has little to no relation to physicists and their work; and they have absolutely nothing to contribute to this sort of discussion. $\endgroup$ – Asaf Karagila May 2 '14 at 7:39
-1
$\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$

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.