Set Theory: The Structure of Arithmetic

1

THE ELEMENTS OF THE THEORY OF SETS

1.1.INTRODUCTION

At a first and casual thought the word set fails to conjure up any familiar mental associations in the mind of a novice at the Theory of Sets. Yet, the set concept is so much a part of our culture and our daily lives that the language we speak contains many special words to denote particular kinds of sets. For instance:

1. A herd is a collection or set of cattle.

2. A flock of sheep is a set of sheep.

3. A bevy is a set of quail.

4. A clutch is a set of eggs in a nest.

5. A legal code is a set of laws.

Similarly, there is a school of fish, a pride of lions, a brace of ducks, a moral code, and so on.

In elementary mathematics the use of set-theoretic concepts occurs with great frequency, albeit in a hidden way. Consider a few examples from elementary algebra and geometry.

6. The solutions, 1 and 2, of the quadratic equation x² – 3x + 2 = 0 comprise the set of solutions of the given quadratic equation.

7. The locus of the equation x² + y²=1, a circle, is the set of all points whose coordinates satisfy this equation.

8. In algebra school books we find statements such as:

In general, a(b + c) = ab + ac.

The meaning of this statement is that for every replacement of a, b, c by names of real (and, also, of complex) numbers the statement resulting from a(b + c) = ab + ac is true. Thus, the general statement is a statement concerning the members of the set of all real (or complex) numbers.

The list of examples of the concealed use of the set concept in the statements of elementary mathematics can be extended indefinitely since all of them are really statements concerning sets or about the totality of members of certain sets. The use of set-theoretic language in mathematics has the advantages of clarity and precision in the communication of mathematical ideas. But if these were the only advantages, one might argue: Clarity and precision can be obtained by care in speaking and writing ordinary English (or whatever language is used in the school) without bothering to develop a special language for this purpose. Although this thesis is debatable, we do not join the debate at this point. Our reason is that the use of set-theoretic concepts goes deeper than the introduction of clarifying terminology. Most mathematical disciplines can be regarded as branches of set theory. Thus the theory of sets provides a mechanism for unifying and simplifying substantial parts of mathematics. In the course of the present book, it will be seen that the few simple set-theoretic ideas presented in this chapter are adequate for the development of much of elementary arithmetic (Volume I), algebra (Volume II), and elementary (Euclidean) plane geometry (Volume III). The same few basic ideas of set theory will be used time and again in each of these disciplines. And every concept in each of the above-named disciplines will be expressed exclusively in terms of the concepts studied in this chapter.

Although the ideas presented in Chapter 1 are truly simple, they may appear strange to the uninitiated reader. He may find himself asking, What does this have to do with the mathematics with which I am familiar? The strangeness will disappear as he progresses further into the text. Its vanishing can be accelerated by constructing numerous examples of the concepts introduced. The connection between this chapter and the more familiar aspects of elementary mathematics will require time to expound. Indeed, this is the subject matter of our book. We urge the reader to have a little patience and read on.

What prior knowledge is required to read this book? In the strictest sense one need only know how to read carefully and to write; little previous mathematical experience is needed. However, we shall, on occasion, rely upon the reader’s acquaintance with some of the simplest facts of elementary arithmetic, algebra and geometry. These facts will not be used directly in the development of the subjects under consideration. Their sole uses will be to illustrate certain concepts, to motivate others and, in general, to act as a source of inspiration for what we do here.

This book should not be read as a novel or a newspaper; a sharp pencil and a pad of paper are essential tools for a comprehension of what follows. Careful attention to details will be rewarded.

1.2.THE CONCEPT OF SET

It is beyond the scope of this book to attempt a formal (axiomatic) development of set theory, and therefore we begin by describing the concept of set in a heuristic way.

By a set we mean any collection of objects; the nature of the objects is immaterial. The important characteristic of all sets is this: Given any set and any object, then exactly one of the two following statements is true:

(a) The given object is a member of the given set.

(b) The given object is not a member of the given set.

The above description of the concept of set is by no means the last word on the subject. However, it will suffice for all the purposes of this book. A deeper study of the basic ideas of set theory usually requires an introduction such as the present one. Moreover, it would take us in a direction different from our proposed course—the study of elementary arithmetic, algebra and geometry.

EXAMPLES

1.The set of all men named Sigmund Smith residing in the United States at 1:00 P.M., June 22, 1802.

2.The set of all unicorns that are now living or have ever lived in the Western Hemisphere.

3.The set of all points in the coordinate plane on the graph of x² + y² = l.

4.The set of all points in the coordinate plane on the graph of | x | ≥ 1.

5.The set of all points in the coordinate plane common to the graphs of x² + y² < 1 and x > 1.

6.The set Z of all integers.

7.The set Ε of all even integers.

8.The set of all tenor frogs now living in the Mississippi River.

9.The set of all tenor frogs now living in the Mississippi River and of all points in the coordinate plane on the graph of x > 1.

Before continuing with the technicalities of set theory, a few preliminary ideas are required. These will be discussed in Sections 1.3 and 1.4.

1.3.CONSTANTS

No doubt the reader is aware that the language in which this book is written—American English—possesses many ambiguities. Were it not so, the familiar and occasionally amusing linguistic trick known as the pun would be a rare phenomenon. Although there is no objection to being funny, any mathematical text should resist strenuously all tendencies to ambiguity and confusion. We shall try to minimize such tendencies by describing carefully the uses of several crucial terms and expressions. Foremost among such terms are the words constant, variable and equals. These terms are familiar to the reader from his earliest study of high-school algebra. But our uses of these words may differ from those he is accustomed to. Therefore it is suggested that he read this section as well as Section 1.4 with care.

Definition 1. A constant is a proper name. In other words, a constant is a name of a particular thing. We say that a constant names or denotes the thing of which it is a name.

EXAMPLES

1.Calvin Coolidge is a constant. It is a name of a president of the United States.

2.2 is a constant. It is a name of a mathematical object—a number—which will be described in detail in Chapter 2.

Of course, a given object may have different names, and so distinct constants may denote the same thing.

3.During his political life, Calvin Coolidge earned the sobriquet Silent Cal, because of his extraordinary brevity of speech. Thus Silent Cal is a constant and denotes Calvin Coolidge.

4.The expressions 1 + 1 and

are constants and both denote the number two.

It may come as a surprise that some constants are built of parts which are themselves constants. Thus 2 + 1 is a constant built of 2 and 1, both of which are constants. In ordinary English, there are analogous situations. For instance, the name Sam Jones is composed of the two names Sam and Jones.

Constants which denote the same thing are synonyms of each other. Calvin Coolidge and Silent Cal are synonyms; similarly, 2 and 1 + 1 are synonyms. Observe that a sentence which is true remains true if it is altered by replacing a name by a synonym. Similarly, if the original sentence is false, then the sentence so altered is likewise false. For example, consider the paragraph

Calvin Coolidge was the third president of the United States. Calvin Coolidge was also, at one time, a governor of the State of Massachusetts.

The first sentence is false and the second one is true. If Calvin Coolidge is replaced throughout by Silent Cal, we obtain

Silent Cal was the third president of the United States. Silent Cal was also, at one time, a governor of the State of Massachusetts.

Again, the first sentence is false, the second is true.

In ordinary, daily conversation it happens rarely, if at all, that a name of a thing, i.e., a constant, and the thing denoted are confused with each other. No one would mistake the name Silent Cal for the person who was the thirtieth president of the United States. In mathematical discourse, on the other hand, confusions between names and the things named do arise. It is not at all uncommon for the constant 2 to be regarded as the number two which it names. Let us make the convention that enclosing a name in quotation marks makes a name of the name so enclosed. To illustrate this convention, consider the expressions

and

written inside the two boxes. The expression inside the upper box is a name for the thirtieth president of the United States. The expression inside the lower box is a name for the expression inside the upper box. Similarly, the expression inside

is a name for the expression inside the box printed five lines above.

Now consider the sentence

Silent Cal was famous for his brevity of speech.

This sentence mentions (or, refers to) the thirtieth president of the United States but it uses the name Silent Cal. The name Silent Cal occurs in the sentence, while the thirtieth president in the flesh is not sitting on the paper. The sentence

Silent Cal has nine letters

mentions a name, and it uses a name of the name mentioned, to wit Silent Cal. In referring to, or mentioning, the name Silent Cal, we no more put that name in the sentence than we put Calvin Coolidge himself into the sentence referring to the thirtieth president. Notice that the sentence

Silent Cal was famous for his brevity of speech

is not only false, but even downright silly. For it asserts that a name was famous for a property attributable only (as far as we know) to a person.

1.4.VARIABLES AND EQUALITY

Variables occur in daily life as well as in mathematics. We may clarify their use by drawing upon experiences shared by many people, even non-mathematicians.

Official documents of one kind or another contain expressions such as

(1.1)I, ______, do solemnly swear (or affirm) that …

What is the purpose of the _______ in (1.1)? Obviously, it is intended to hold a place in which a name, i.e., a constant, may be inserted. The variable in mathematics plays exactly the same role as does the _______ in (1.1); it holds a place in which constants may be in serted. However, devices such as a ______ are clumsy for most mathematical purposes. Therefore, the mathematician uses an easily written symbol, such as a letter of some alphabet, as a place-holder for constants. The mathematician would write (1.1) as, say,

(1.2)I, x, do solemnly swear (or affirm) that …

and the "x" is interpreted as holding a place in which a name may be inserted.

Definition 2. A variable is a symbol that holds a place for constants.

Suppose a variable occurs in a discussion. What are the constants that are permitted to replace it? Usually an agreement is made, in some manner, as to what constants are admissible as replacements for the variable. If an expression such as (1.1) (or (1.2)) occurs in an official document, the laws under which the document is prepared will specify the persons who may execute it. These, then, are the individuals who are entitled to replace the variable by their names. Thus, with this variable is associated a set of persons and the names of the persons in the set are the allowable replacements for the variable. In general:

With each variable is associated a set; the names of the elements in the set are the permitted replacements for the given variable. The associated set is the range of the variable.

The range of a variable in a mathematical discussion is usually determined by the requirements of the problem under discussion.

Variables occur frequently together with certain expressions called quantifiers. As one might judge from the word itself, quantifiers deal with how many. We use but two quantifiers and illustrate the first as follows:

Let x be a variable whose range is the set of all real numbers. Consider the sentence

(1.3)For each x, if x is not zero, then its square is positive.

The meaning of (1.3) is

For each replacement of x by the name of a real number, if the number named is not zero, then its square is positive.

The quantifier used here is the expression for each. Clearly, the intention is, when for each is used, to say something concerning each and every member of the range of the variable. For this reason, for each is called the universal quantifier. It is a common practice to use the expressions for all and for every as synonymous with for each, and these three expressions will be used interchangeably in this text.

Observe that if in place of (1.3) we write

(1.4)For each y, if y is not zero, then its square is positive.

where the range of y is also the set of all real numbers, then the meanings of (1.3) and (1.4) are the same. Similarly, y can be replaced by z or some other suitably chosen symbol without any alteration of meaning. Such replacement allows us considerable freedom in the choice of symbols for variables.

The use of the second quantifier is illustrated by the sentence

(1.5)There exists an x such that x is greater than five and smaller than six

where the range of x is the set of all real numbers. The meaning of (1.5) is

There is at least one replacement of x by the name of a real number such that the number named is greater than five and smaller than six.

The expression there exists is the existential quantifier. The expression there is is regarded as synonymous with there exists. Again, the reader may observe that if the variable x is replaced throughout (1.5) by y or some other properly chosen symbol, the range being the same, then the meaning of the new sentence is the same as that of (1.5).

Definition 3. If an occurrence of a variable is accompanied by a quantifier that occurrence of the variable is bound; otherwise it is free.

In mathematical discourse, variables frequently occur as free variables. For instance, one finds discussions beginning with expressions such as

If x is a nonzero real number, then …

or, such as

Let x be a nonzero real number. Then …

Many mathematicians regard such forms of expression as ones in which the entire discussion is understood to be preceded by a quantifier. For example, in elementary algebra texts, one sees statements such as

Let x be a real number. Then,

x + 2 = 2 + x.

This is to be interpreted as meaning :

For all real numbers, x, x + 2 = 2 + x.

The practice of beginning a discussion with "If x is … or Let x be …," i.e., the practice of using the variable as free, will be adopted in many places throughout this book. Just which of the two quantifiers is intended to precede the discussion will always be clear from the context. Therefore we shall not attempt to give any formal rules for supplying the missing quantifier.

We have said that letters are used as variables. It will also happen that letters will occur as constants. The contexts in which a letter occurs will make clear whether a constant or a variable is intended.

We conclude this section with a brief discussion of equality. Suppose x, y, z, … are variables all having the same range.

Definition 4. The expression "x = y" means that x and y are the same object. The symbol = is called equals, "x ≠ y" means that x and y are not the same object.

For instance, 2 + 2 = 4 means that 2 + 2 and 4 are the same number. Similarly, Euclid = Author of the ‘Elements’ means that Euclid and Author of the ‘Elements’ are the same person.

Throughout, we assume the following:

I. For each x, x = x. In words, equals is reflexive.

II. For each x and for each y, if x = y, then y = x. (Equals is symmetric.)

III. For each x, for each y, and for each z, if x = y and if y = z, then x = z. (Equals is transitive.)

1.5.SOME BASIC NOTATIONS AND DEFINITIONS

Definition 5. If an object x is a member of a set A, we say that x is an element of A and write

x ∈ A.

For instance, the integer 1 is an element of the set Z (Example 6, page 4); therefore we write 1 ∈ Z.

If an object y is not an element of a set B, we write

y ∉ B,

and say "y is not an element of B." Thus 1 ∉ E, where E is the set of Example 7, page 4.

Now suppose that S is a set consisting only of the objects denoted by "a, b, c, d." We write

(1.6)S = {a,b,c,d};

thus, S and {a,b,c,d} are the same set. If we know the names of all the elements of a set, and if the objects in it are not too numerous, then (1.6) gives a convenient way of representing this set.

EXAMPLES

1.Suppose a geometry class consists of the students Dan Doe, Evelyn Earp, Jane Jones, Sam Small, Joe Zilch. Then we write

Geometry class = {Dan Doe, Evelyn Earp, Jane Jones, Sam Small, Joe Zilch}.

2.{0,1,2,3} is the set consisting of the numbers 0, 1, 2 and 3. In Chapter 2 this set will receive a simpler name.

The order in which the names of objects in a set are listed is immaterial. Therefore we regard

{Sam Small, Jane Jones, Dan Doe, Joe Zilch, Evelyn Earp}

and

{Jane Jones, Joe Zilch, Evelyn Earp, Sam Small, Dan Doe}

etc., as being the same geometry class. Similarly, the set of Example 2 above may also be denoted by {0,1,2,3}, {0,3,1,2}, etc.

On occasion one knows names for all the elements of a set, but the elements are too numerous for the names to be listed conveniently. In such a case, one may use dots (…). For instance, suppose the set Τ consists of all the integers beginning with 0 and ending with 4,257. Then one writes

T = {0, 1,…, 4, 257}.

There will be another notation for sets, but it will, together with some questions on notation not yet raised, be deferred until Section 1.10.

Again we emphasize that the elements of a set may be of any nature whatsoever. In particular, the elements of a set may themselves be sets.

EXAMPLES

1.Let F be the set of all families now residing in the town of Foosland.¹ Thus the elements of F might be the Jones family, the Smith family, the Robertson family, etc., and we write

F = {the Jones family, the Smith family, the Robertson family, …}

the dots indicating the names of the families which could be secured from a town directory or by means of a house-to-house canvass. Each of the elements of F is a family, and each family is, in turn, a set of persons. For instance, the Jones family might consist of the people Sam, Zelda, Joe; i.e., Jones = {Sam, Zelda, Joe}. But neither Sam Jones, nor Zelda Jones, nor Joe Jones is an element of F, since F is a set of families and none of these three persons is a family.

2.The National League (denoted by "N.L.") can be defined as the set of teams consisting of the Giants (G), the Dodgers (D), etc. (Your local newspaper will supply the names of the remaining teams.) So

N.L. = {G,D,…}.

In turn, each team is a set of players. If Zilch is a pitcher for the Dodgers, then Zilch ∈ D; but by definition of N.L., Zilch ∉ N.L.

3.If the National League were defined as consisting of all of its teams and all of its players, then

N.L. = {G,D, …, Zilch, Brown, …};

in this case we would have

Zilch ∈ D, D ∈ N.L., and also Zilch ∈ N.L.

in contrast to Example 2.

EXERCISES

1.Using Examples 1–9 (pages 3 and 4), name several sets whose elements are, in turn, sets.

2.Name a few sets whose elements are sets of sets.

1.6.SUBSETS; EQUALITY OF SETS; THE EMPTY SET

A comparison of the sets Z and Ε (defined in Examples 6 and 7, respectively, page 4) yields the conclusion that Ε is a part of Z. How is this conclusion reached? We deduce it in the following way:

Every element of Ε is an even integer (definition of E).

Every even integer is certainly an integer.

Hence every element of Ε is an integer.

But Z is the set of all integers (definition of Z).

Therefore every element of Ε is an element of Z.

Thus, Z contains all the elements of E.

The relationship between Ε and Z illustrates the concept of subset.

Definition 6. Let A and B be sets. A is a subset of B means that every element of A is an element of B. The symbol "A ⊂ B is used to abbreviate the sentence, A is a subset of B. We also say A is contained in B, A is included in B. The symbol B ⊃ A is defined as meaning the same as A ⊂ B; in words, B contains A, B includes A."

If we use the ∈-notation, the definition of subset can be stated in the following brief and convenient way:

Definition 6′. A is a subset of B means: for all x, if x ∈ A, then x ∈ B.

EXERCISES

1.Among Examples 1–9 (pages 3 and 4), find those sets which are subsets of other sets in the list.

2.Name several examples of sets and subsets.

Under what condition can one say that a set A is not a subset of a set B? Let us reason as follows:

(α)"A is a subset of B means that every element of A is an element of B."

(β)If A is not a subset of B, then the statement "every element of A is an element of B" must be false. Hence the negation of "every element of A is an element of B must be true. Therefore our task is to determine what is the negation of every element of A is an element of B."An example may help.

Consider the statement, Every Martian is a bug-eyed monster. This statement can be rephrased in terms of set theory in the following way: Let M be the set of all Martians and let BEM be the set of all bug-eyed monsters. Then the assertion, Every Martian is a bug-eyed monster, is expressed by

M ⊂ BEM.

Now, suppose it is not true that every Martian is a bug-eyed monster. In other words, suppose it is false that every Martian is a bug-eyed monster. This means that at least one (and possibly more than one) Martian is not a bug-eyed monster. That is to say, there is a (at least one) Martian who is not a bug-eyed monster. Thus, the statement:

There is a y ∈ M such that y ∉ BEM

is the negation of

M ⊂ BEM.

Returning to the general situation, we see that if the negation of "A is a subset of B" is true, then

(γ) There is a z such that z ∈ A and z ∉ B.

On the other hand, if (γ) is true,