8
$\begingroup$

I'm new in here. Considering my person: I am physics student (BSc.) who has finished 2 semesters by now. Within the first two semesters, I discovered that mathematics is beautiful and that I want to learn maths in more depth than the courses at my university teach it. Therefore I'm trying to self-study the book "Principles of Mathematical Analysis", by Walter Rudin, in my leisure time. I have a question concerning

Chapter 2, Exercise 1: Prove that the empty set is a subset of every set.

My first intention would have been:

Let X be an arbitrary set, then $\varnothing \cup X = X \cup \varnothing = X \implies \varnothing \subseteq X$ since $S \subseteq S \cup T$ and $T \subseteq S \cup T$ for arbitrary sets $S$ and $T$. $X$ was arbitrary, thus the assertion holds. $\Box$

But I'm not completely sure, if the prove is complete, as I haven't seen this version anywhere within a quick google search. What would you say?

$\endgroup$
  • 3
    $\begingroup$ I would say yes, the proof is sound, but the thing you're proving is so elementary you mightn't be "supposed" to use such a high-level result. I would prove it a different way, using the definition of subset and the empty set. $\endgroup$ – Colm Bhandal Aug 27 '15 at 14:37
  • 6
    $\begingroup$ But how do you know that $X\cup\varnothing=X$? $\endgroup$ – Asaf Karagila Aug 27 '15 at 14:52
  • 1
    $\begingroup$ $A$ is a subset of $B$ if there's no $x$ with $x\in A$ and $x\notin B$. $\varnothing$, then, is a subset of $B$ because there's no $x$ with $x\in\varnothing$! $\endgroup$ – Akiva Weinberger Aug 27 '15 at 15:16
  • $\begingroup$ @AsafKaragila: Following the questioner's textbook, it looks like that's equation (13) following Remark 2.11. It's stated as “easily verified.” $\endgroup$ – Matthew Leingang Aug 28 '15 at 20:45
  • $\begingroup$ @Matthew: It is possible to define $X\cup\varnothing=X$ axiomatically. But that would be a shame. As for easily verified, I guess that would depend on additional previous statements given in the book. $\endgroup$ – Asaf Karagila Aug 28 '15 at 20:48
21
$\begingroup$

The proof is sound, but here's something more basic. Start with the following pointwise definition for subset:

$A \subseteq B \equiv \forall a \in A \implies a \in B$

Then you're left to prove

$\forall a \in \varnothing \implies a \in B$

But the above is then vacuously true because there is no $a \in \varnothing$.

$\endgroup$
2
$\begingroup$

Note that the first step in a rigorous proof is to find that the empty set exists and is unique. This means that we have to choose some set theory and, depending on the chosen theory this can be an axiom or a consequence of the assumed axioms (see here). Then the fact that the empty set is a subset of any set is a form of vacuous truth. You can find different forms of this result in this question.

$\endgroup$
1
$\begingroup$

Just to add a bit to Colm's very good answer. You want to prove $$ \forall a (a\in \varnothing \implies a \in B) $$

Membership in the empty set can be hard to get your head around. So first, look at the implication. The statement $p\to q$ is equivalent to $\neg p \vee q$. (Think of it as “it is never true that $p$ is true and $q$ is not also true.” This means $p \to q \equiv \neg(p \wedge \neg q)$, and apply DeMorgan's laws.) So what we want to prove is $$ \forall a (a\notin\varnothing \vee a \in B) $$ But since $a\notin\varnothing$ is always true, $a\notin\varnothing \vee a \in B$ is always true, too. QED.

$\endgroup$
1
$\begingroup$

Here's some proofs:

First the direct proof using the definition of vaccous truth. In logic, we have defined that any implication of the form "If False then X", where X is any statement, to be a (vaccously) true statement. For instance the statement "If pigs could fly then I'd be president" is vaccously true since the statement "pigs could fly" is logically equivalent ($\equiv $) to false. Thus logically we have:

$$(False \implies \text {"I'd be president"}) \equiv True $$

Applying this logic to the problem at hand, we want to show $ \forall x, x \in \emptyset \implies x \in A $. But by defn of $\emptyset$ we know $\forall x, x \notin \emptyset $. Thus: $$ (\forall x, False \implies x \in A) \equiv True $$. Thus the claim is proved.

Another good proof is by contradiction. To do a proof by contradiction, assume the opposite of what we want to prove is true, ie assume $\exists x \in \emptyset: x \notin A$. We have an immediate contradiction since $\emptyset $ contains no elements. Therefore our assumption is false, and therefore the claim, since it was the opposite of our assumption, is 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.