INTRODUCTION

BABY SET THEORY

We shall begin with an informal discussion of some basic concepts of set theory. In these days of the "new math," much of this material will be already familiar to you. Indeed, the practice of beginning each mathematics course with a discussion of set theory has become widespread, extending even to the elementary schools. But we want to review here elementary-school set theory (and do it in our notation). Along the way we shall be able to point out some matters that will become important later. We shall not, in these early sections, be particularly concerned with rigor. The more serious work will start in Chapter 2.

A set is a collection of things (called its members or elements), the collection being regarded as a single object. We write "t ? A" to say that t is a member of A, and we write "t ? A" to say that t is not a member of A.

For example, there is the set whose members are exactly the prime numbers less than 10. This set has four elements, the numbers 2, 3, 5, and 7. We can name the set conveniently by listing the members within braces (curly brackets):

2,3,5,7}.

Call this set A. And let B be the set of all solutions to the polynomial equation

4-17x3+101x2-247x+210=0.

Now it turns out (as the industrious reader can verify) that the set B has exactly the same four members, 2, 3, 5, and 7. For this reason A and B are the same set, i.e., A = B. It matters not that A and B were defined in different ways. Because they have exactly the same elements, they are equal; that is, they are one and the same set. We can formulate the genera) principle:

Principle of Extensionality If two sets have exactly the same members, then they are equal.

Here and elsewhere, we can state things more concisely and less ambiguously by utilizing a modest amount of symbolic notation. Also we abbreviate the phrase "if and only if" as "iff." Thus we have the restatement:

Principle of Extensionality If A and B are sets such that for every object t,

?Aifft?B,

then A = B.

For example, the set of primes less than 10 is the same as the set of solutions to the equation x4 - 17x3 + 101x2 - 247x + 210 - 0. And the set {2} whose only member is the number 2 is the same as the set of even primes.

Incidentally, we write "A = B" to mean that A and B are the same object. That is, the expression "A" on the left of the equality symbol names the same object as does the expression "B" on the right. If A=B, then automatically (i.e., by logic) anything that is true of the object A is also true of the object B (it being the same object). For example, if A = B, then it is automatically true that for any object t, t ? A iff t ? B. (This is the converse to the principle of extensionality.) As usual, we write "A ? B" to mean that it is not true that A = B.

A small set would be a set {0} having only one member, the number 0. An even smaller set is the empty set Ø. The set Ø has no members at all. Furthermore it is the only set with no members, since extensionality tells us that any two such sets must coincide. It might be thought at first that the empty set would be a rather useless or even frivolous set to mention, but, in fact, from the empty set by various set-theoretic operations a surprising array of sets will be constructed.

For any objects x and y, we can form the pair set {x, y} having just the members x and y. Observe that {x, y} = {y, x}, as both sets have exactly the same members. As a special case we have (when x = y) the set {x, x} = {x}.

For example, we can form the set {Ø} whose only member is Ø. Note that {Ø} ? Ø, because Ø ? {Ø} but Ø ? Ø. The fact that {Ø} ? Ø is reflected in the fact that a man with an empty container is better off than a man with nothing-at least he has the container. Also we can form {{Ø}}, {{{Ø}}}, and so forth, all of which are distinct (Exercise 2).

Similarly for any objects x, y, and z we can form the set {x, y, z). More generally, we have the set {x1, ., xn} whose members are exactly the objects x1, ., xn. For example,

Ø,{Ø},{{Ø}}}

is a three-element set.

Two other familiar operations on sets are union and intersection. The union of sets A and B is the set A ? B of all things that are members of A or B (or both). Similarly the intersection of A and B is the set A n B of all things that are members of both A and B. For example,

x,y}?{z}={x,y,z}

and

2,3,5,7}n{1,2,3,4}={2,3}.

Figure 1 gives the usual pictures illustrating these operations. Sets A and B are said to be disjoint when they have no common members, i.e., when A n B = Ø.

A set A is said to be a subset of a set B (written A?B) iff all the members of A are also members of B. Note that any set is a subset of itself. At the other extreme, Ø is a subset of every set. This fact (that Ø ? A for any A) is "vacuously true," since the task of verifying, for every member of Ø, that it also belongs to A, requires doing nothing at all.

If A ? B, then we also say that A is included in B or that B includes A. The inclusion relation (?) is not to be confused with the membership relation (?). If we want to know whether A ? B, we look at the set A as a single object, and we check to see if this single object is among the members of B. By contrast, if we want to know whether A ? B, then we must open up the set A, examine its various members, and check whether its various members can be found among the members of B.

Examples

1. Ø ? Ø, but Ø ? Ø.

2. {Ø} ? {{Ø}} but {Ø} {{Ø}}. {Ø} is not a subset of {{Ø}} because there is a member of {Ø}, namely Ø, that is not a member of {{Ø}}.

3. Let Us be the set of all people in the United States, and let Un be the set of all countries belonging to the United Nations. Then

?Us?Un.

    But John Jones ? Un (since he is not even a country), and hence Us Un.

Any set A will have one or more subsets. (In fact, if A has n elements, then A has 2? subsets. But this is a matter we will take up much later.) We can gather all of the subsets of A into one collection. We then have the set of all subsets of A, called the power1 set A of A. For example,

A very flexible way of naming a set is the method of abstraction. In this method we specify a set by giving the condition-the entrance requirement-that an object must satisfy in order to belong to the set. In this way we obtain the set of all objects x such that x meets the entrance requirement. The notation used for the set of all objects x such that the condition __x__holds is

x|__x__|}.

For example:

1.  is the set of all objects x such that x is a subset of A. Here "x is a subset of A" is the entrance requirement that x must satisfy in order to belong to . We can write

2. A n B is the set of all objects y such that y ? A and y ? B. We can...