Empty Sets and Vacuous Truth

I’m going to start this post with a simple question about the empty set, and gradually dive deeper. There will be connections here to previous discussions of conditional statements in logic.

How can a set be empty?

First, how can something empty be called a set in the first place? Isn’t a “set” a collection of things? That means at least one, doesn’t it?

How Can a Set Be Empty?

Why is the empty or null set called a set when it has no elements?  Is there a mathematical proof that it's a set?

Since this is a matter of definition, it can’t be proved; but it can be justified. In this case, I focused on what is called the closure property: We want the operations we do on sets to be “closed”, meaning the result will always still be a set.

We try to make our definitions so that they are as useful as possible. In this case, we would like all the operations we can do between sets to yield sets, just as we want addition and multiplication of two numbers to produce a number. Now, what happens when you take the intersection of a pair of disjoint sets (sets with no elements in common)? The result is an empty set, right? If we didn't call that a set, then in this (rather common) case, the result of the intersection operation would not be a set.

This is typical of the way math is done. We make some natural definition (for example, thinking of a set as any collection of objects), and then work with it; eventually we find that we have to refine our definitions, or clarify the extreme cases, in order to make our new branch of mathematics work neatly. We can't "prove" that the empty set is a set, since we are defining it as such; but we do have to demonstrate that it is a useful and consistent definition that produces interesting mathematics. It does!

Here is another version of the same question, from a teacher:

Definition of Set and How the Empty Set Fits within It

The definition of a set is "A collection of well-defined objects". Whenever I teach this topic, my students become confused about the idea of the null set, because they think every collection must have some elements.  I say to them that a collection can be empty, but still they are not satisfied.  How can I get them to understand that the definition allows for an empty collection?

Doctor Tom, in a long answer that is worth reading, first points out that mathematicians don’t formally define a set this way, and introduces the idea of Axiomatic Set Theory, which gets around this. Then he talks about how students can be introduced to the ideas of sets informally:

I like to tell my students that a set is like a box that may or may not contain objects.  So the set:  {1, 2, 3} is a box containing those particular three numbers.  The empty set is simply an empty box.

This is just a way of thinking about sets that makes the idea of an empty set feel more natural.

How can it be a subset of every set?

So let’s accept that an empty set makes sense. But what about this idea that the empty set (there’s only one) is a subset of every set?

Is an Empty Set a Subset?

The empty set is a subset of all sets, right? What is the proof of the example:

For any event W in the sample space S, what is the proof that the empty set is a subset of W?

Here Anabelle is asking in the context of probability (where an “event” is a set of outcomes), but her question applies to sets in general. I gave not one, but three ways to think about it:

A subset of a given set is simply any set, all of whose elements are contained in the other. Since the empty set has no elements, all of its elements are in any other set! It sounds weird, but that's the way logic works.

To put it another way, a set A is NOT a subset of B if there is some element x of A that is not in B. Since the empty set has no elements that are not in your given set, we can't say it is NOT a subset. That means that it is.

To select a subset, we must look at each member of the set and decide whether to keep it. If we say "yes" to every member, we have the set itself; if we say "no" to all of them, we have the empty set. We could choose to exclude these from the definition of subset, but it makes a lot of things easier if we include them. That way there are no special cases to deal with when we state theorems.

The first answer depends on how mathematicians think of the word “all” when “all” is nothing; we’ll dig into this idea (called vacuous truth) below, so hold on if it makes no sense to you!

The second answer is a justification of the first. If we turn our perspective around and think about what it takes to recognize something that is not a subset, it makes a little more sense. This ties in to the idea I have discussed previously of “innocent until proven guilty”: if there is no proof that it is not a subset, then it is.

The third answer is like my answer to the first question above: This way of defining subsets makes other things work better than if we didn’t take it this way. Specifically, we have chosen to define “subset” so that if you select elements from a set by making a checklist of the elements of the full set and checking off those you want in the subset, any choice – including the choice not to include any – results in a subset. That makes a lot of theorems easier to state, because it is consistent.

Now, some people, trying to have fun with surprising mathematical ideas, take this a little too far. They point out that there is only one empty set, which is a subset of every other set; so they might say that the set of all elephants in Antarctica and the set of all living Tyrannosaurs are the same set. An adult wrote to us in 2015 (not archived) asking about this, pointing out that in such a case, one is really considering two different universal sets. Whenever you deal with sets, you must always be working within some specific universe, or fallacies can result. So, as I told Amit, “they are probably overlooking the fact that their descriptions seem to imply different universes, so that they are really violating proper rules for sets, for the sake of humor or vividness. The point that there is only one empty set (within a universe) is true, but such an illustration probably goes too far.”

Vacuous truth

Now let’s look at that idea of vacuous truth. The following question is about more advanced math, involving functions from one set to another; you don’t have to know anything about that to follow the parts of the answer I will quote. Here is the question:

Vacuous Cases, Empty Sets, and Empty Functions

I am having difficulty understanding 'vacuous' situations as in, if A is an empty set and B is a non-empty set then
 
(i) there is one function f: A \to B namely the empty function but (ii) there is no function f: B \to A. 

An empty set is a set with no element but what is an empty function? There is a function from an empty set to a non-empty set (how) but not vice-versa. 

I am used to the case A and B are non-empty so A x B does not go against (my) intuition.  In the case A is empty and B is non-empty, A x B is non-empty but B x A is empty?

We won’t be looking here at the answer to the specific question about functions; but Doctor Jacques breaks his answer into two parts, and the first part is about “logical statements about the empty set”, which is our topic:

Let us first consider a statement about the elements of a set A.

Assume S(x) is a statement about the object x (a logical proposition): depending on the particular object x, S(x) is either true or false.

We can make a statement S(A) about the set A, by asserting that S(x) is true for every element of A :

  S(A) ::= "For all x in A, S(x) is true".

For example, assume that x represents a ball, and S(x) is the statement "the ball x is red".  Now, if A is a bag of balls, S(A) 
would mean:

  "For all balls x in the bag A, the ball x is red"

or, more simply said:

  "All the balls in A are red"

The question is now, what does this mean if A is empty?

S(A) can only be false if you can find in A a ball that is not red. If A is empty, this is impossible, so S(A) cannot be false, and we conclude that S(A) is true--if the bag is empty, all the balls in it are red (although there are no balls at all).  Note that it is also true that all the balls in the bag are black--there is no contradiction in this if the bag is empty.

In a more abstract way, if S(A) is a statement of the form:

  For all x in A, S(x) is true

then, whenever A is empty, S(A) is true--this does not depend on the particular form of the statement S(x).

We can also see it in another way--S(A) means that A is a subset of the set of objects such that S(x) is true.  Now, the empty set is a subset of any set, so, if A is empty, A is indeed a subset of the set of objects that verify S(x), and S(A) is true.

Here we have several ideas connected: “for all x in A” (the universal quantifier) is equivalent to “if x is in A” (a conditional statement); and also to “A is a subset of …”. As I have previously discussed why a conditional statement is considered true when its condition is false, the same reasoning applies here to the case where there are no x in A.

Not long before that answer, Doctor Jacques had answered a question about proving properties of relations, which you can find here:

Properties of Relation

Even the question depends on knowledge I don’t want to get into, but he starts out by preparing the student for some special situations, which involve vacuous truth:

I think we should first clarify a few issues about mathematical logic, and, in particular, the meaning of statements related to the empty set.

When we say "If P then Q", or "P -> Q" this simply means that P is false or Q is true (or both). This has some consequences that may appear surprising (until you get used to them). For example:

  "If 6 is prime, then 11 is negative"

is a true statement, because the "If" part is false.

A statement like P -> Q does not mean that there is any "logical relationship" between P and Q.

Consider now what happens when we make statements about elements of a set. Let us say we have a statement:

 "For all x in S, P(x)"

where P(x) is some statement about x. This is equivalent to saying:

  x is in S -> P(x)

What does this mean if S happens to be the empty set? In that case, the left part ("x is in S") is false, and therefore the complete statement is true, (whatever P(x) may mean). We can say that any property is true when applied to the elements of the empty set. For example, in a universe without birds, both statements:

 "All birds are green"
 "All birds are red"

are true, and this does not create a contradiction.

Another way to see this is the following example. Assume that you have to inspect bags that may contain red and blue balls, and you want a procedure to decide whether or not all the balls in a given bag are red. This means that, given a bag B, you want to decide whether or not it is true that:

  "For all x in B, x is red"

The procedure would be executed as follows:

(1) if there are no more balls in the bag, exit and return TRUE (i.e. declare that the statement is true)

(2) pick a ball from the bag

(3) if the ball is not red, exit and return FALSE

(4) otherwise, go back to step (1)

Note that you must execute step (1) at the beginning, because step (2) is illegal if there are no more balls.

Now, you can see that, if a particular bag is empty, the procedure will immediately terminate at step (1), and declare the statement true. This shows that this interpretation is consistent.

On the other hand (we will not use that here), a statement like:

  "There exists x in S such that P(x)"

means

  "(There exists x in S) AND (P(x))"

and, if S happens to be the empty set, this statement is false (whatever P(x) may mean), because the first part of the AND statement is false.

To summarize:

* "If P then Q", or "P -> Q" means "P is false or Q is true" (and nothing else).

* The statement "For all x in S, P(x)" is always true when S is the empty set.

* The statement "There exists x in S such that P(x)" is always false if S is the empty set.

The latter two statements do not depend on the definition of P(x).

This ties together much of what we have been saying.