Tuesday, September 11, 2012

The Empty Set

In my previous post I talked about counting the total number of subsets of sets with a finite number of elements. In order to get all possible subsets we had to include the empty set, the set with nothing in it.

It turns out that the empty set is a subset of any set no matter what that set is. In this post I will provide a proof of this. But first let me tell you what I mean by subset.

Let A and B be two nonempty sets. A is a subset of B if all elements of A are also elements of B. For example let A = {1,3,5,7} and B = {0,1,2,3,4,5,6,7}. A is a subset of B, because every element of A is also an element of B. Now consider the set C = {1,3,5,7,9}. C is not a subset of B, because there is an element of C that is not an element of B. C is an example of a set that is not a subset of B. This will be an important part of the proof to show that the empty set is a subset of any set.

For those of you who are confused by the proof of statement (ii) let me put it in words.
Let A be any nonempty subset of U. By way of contradiction suppose the empty set is not a subset of A. It follows that there exists an element x in the empty set such that x is not an element of A. But the empty set has nothing in it; therefore x cannot be an element of the empty set. [By the definition of the empty set] It follows that for all x in U, x cannot be in the empty set. Therefore there are no elements in the empty set that are not in the set A (this is our equivalent definition of what it means to be a subset). Thus the empty set must be a subset of A.
I've probably made this proof more complicated than it should be, but once you understand it, it is truly an elegant proof!

1 comment:

  1. This post brings back memories of logic class. Putting the proof in words is helpful.