25 October 2002

Setting up for the Future

by George E. Hrabovsky, President, MAST

Where We Have Been

The last column covered a lot of ground; we discussed how to become a mathematician, then we discusses the concepts of propositions and their truth tables, connectives, and implications. We also discussed the use of truth tables to create proofs. I must also point out that I made a mistake on the truth table for the conditional. It should have read,

T

F

T

T

my thanks goes out to Joe Giddes for correcting me, keep up the good work!

Where Will We Go in This Column

In this column we will explore how to combine things. We will establish some principles about combining things and prove them with the principles from the last column.

The Idea of a Set

You have almost certainly heard of the idea called a set, but have you really thought about what it means? As a first attempt to explain the idea we could say that any collection of things is a set. The things that are contained within a set are called the elements of the set or simple elements. It would get pretty tedious to write the word set repeatedly, so we will use upper case letters to describe sets, for example . Similarly we will use lower case letters to denote the elements of a set, . We can say that an element belongs to a set ,

.

We can also say that the set has an element ,

.

Of course it is also possible to say that an element does not belong to a set,

.

Now that we can assign membership to a set, in other words determine whether or not an element belongs to a set, does that mean we can define sets in general? This is a curious thing, if we attempt to define such a general set we will need to talk of elements or things or the like. Yet we can't talk about elements without talking about sets. This leads us to a situation where we need to include what we are defining in the definition of what we are defining. As unsettling as this is we must accept the fact that there are ideas that we cannot define. Ideas that we will just have to understand, and we will agree to call these concepts undefined terms. The best we can hope for is to understand how we use these terms.

Does this mean we can never define any set? No. We can define a set by listing its elements. This is called the roster method. For example, we can define the set of letters in the word January,

.

Note that we only list each element once.

Another method is more sophisticated. If you think about it a little while you will see that the roster method becomes unwieldy if the number of elements in a set is large. Instead we can assign a rule that determines membership in the set. If we state that for to be an element of it must obey the proposition , we can write,

Another way of writing the phrase, "...such that..." is with the symbol |, so,

For example, let us say that we want to consider the set of even whole numbers less than one thousand,

This technique is called set-builder notation. If we adopt the symbol for the set of whole numbers, then we can write,

There is a special kind of set that has no elements. We call this the empty set and we denote it with the symbol ,

.

Subsets

If you think about it, you will eventually ask the question, "Can we consider a set to be an element of another set?" The answer is yes. If we say that the set is an element of the set , then we call a subset of . We can write this,

.

We can define a subset more formally by saying that,

.        (1)

Another way of writing it is,

.                        (2)

We can now make the following statement, "The empty set is a subset of every set." Assuming we want anyone to believe us when we say this we now have to prove that this statement is true. One way of proving something true is to prove that it cannot be false. Think about formula (1), this defines what must be true if something is a subset, but it also tells us that for something to not be a subset it must have some elements not in common with the other set in question. If we assume for a moment that is not a subset of any set, then it must have some element not in common with any set. Since it has no elements at all, this cannot be true. The empty set cannot not be a subset of any set. Thus is a subset of every set. Since we have proven this statement it takes on a special significance, it is called a theorem. When numbering theorems the first number will denote the column number and the second number will be the place in the numerical order of theorems in the column.

Theorem 2-1: The empty set is a subset of every set.

How many subsets can a set have? We could list them all and cover every combination. This would take us a very long time and would be a lot of work even for small sets. If we think about it for a while we will realize that each subset is a combination of various elements in the set. If there is only one element in the set, it is called a singleton set. For a singleton set we have the empty set and the subset of the single element, so there are two subsets. This tells us that for each element there are two possible options, it is a member of a subset or not, thus there are two combinations of subsets for each element. If a set has elements then it has possible subsets, where there are products. Another way of writing this is subsets exist in a set of elements. Since we have proven this statement to be true we can write it as,

Theorem 2-2: The number of subsets in a set of elements is .

    The set of all subsets of a set is called the power set. The power set for a set is denoted as, .

The idea of a subset forces us to confront our understanding of the idea of sets itself. Think about it this way, what is the set of all sets? Seriously, this can't be done. If a set contains all possible sets, then it contains itself. This means that there must be another set that contains it, and so one. This is called Russell's Paradox. We can clear up this issue of our understanding of sets by adjusting our understanding by saying that a set is any collection of elements and is not a subset of itself.

Equality of Sets and Proper Subsets

When two sets have exactly the same elements they are said to be equal. A more formal way of writing this is,

.                        (3)

    We can use this principle to specify a new kind of subset,

.

This is called a proper subset.

Suggested Practice Problems

1. Invent three sets using the roster method.

2. Invent three sets using set-builder notation.

3. Make a truth table for (2).

4. How many elements does the power set of any set have?

5. How many subsets do each of your sets from assignment 1 and 2 above have?

6. Are any of your sets equal?

7. Are any of your sets proper subsets of one another?

8. Make a truth table for (3).

Converted by Mathematica  (October 23, 2002)