Read an Excerpt

Naive Set Theory

Dover Publications, Inc.

SECTION 1

THE AXIOM OF EXTENSION

A pack of wolves, a bunch of grapes, or a flock of pigeoiis are all examples of sets of things. The mathematical concept of a set can be used as the foundation for all known mathematics. The purpose of this little book is to develop the basic properties of sets. Incidentally, to avoid terminological monotony, we shall sometimes say collection instead of set. The word "class" is also used in this context, but there is a slight danger in doing so. The reason is that in some approaches to set theory "class" has a special technical meaning. We shall have occasion to refer to this again a little later.

One thing that the development will not include is a definition of sets. The situation is analogous to the familiar axiomatic approach to elementary geometry. That approach does not offer a definition of points and lines; instead it describes what it is that one can do with those objects. The semi-axiomatic point of view adopted here assumes that the reader has the ordinary, human, intuitive (and frequently erroneous) understanding of what sets are; the purpose of the exposition is to delineate some of the many things that one can correctly do with them.

Sets, as they are usually conceived, have elements or members. An element of a set may be a wolf, a grape, or a pigeon. It is important to know that a set itself may also be an element of some other set. Mathematics is full of examples of sets of sets. A line, for instance, is a set of points; the set of all lines in the plane is a natural example of a set of sets (of points). What may be surprising is not so much that sets may occur as elements, but that for mathematical purposes no other elements need ever be considered. In this book, in particular, we shall study sets, and sets of sets, and similar towers of sometimes frightening height and complexity — and nothing else. By way of examples we might occasionally speak of sets of cabbages, and kings, and the like, but such usage is always to be construed as an illuminating parable only, and not as a part of the theory that is being developed.

The principal concept of set theory, the one that in completely axiomatic studies is the principal primitive (undefined) concept, is that of belonging. If x belongs to A (x is an element of A, x is contained in A), we shall write

x [member of] A.

This version of the Greek letter epsilon is so often used to denote belonging that its use to denote anything else is almost prohibited. Most authors relegate [member of] to its set-theoretic use forever and use ε when they need the fifth letter of the Greek alphabet.

Perhaps a brief digression on alphabetic etiquette in set theory might be helpful. There is no compelling reason for using small and capital letters as in the preceding paragraph; we might have written, and often will write, things like x [member of] y and A [member of] B. Whenever possible, however, we shall informally indicate the status of a set in a particular hierarchy under consideration by means of the convention that letters at the beginning of the alphabet denote elements, and letters at the end denote sets containing them; similarly letters of a relatively simple kind denote elements, and letters of the larger and gaudier fonts denote sets containing them. Examples: x [member of] A, A [member of] X, X [member of] C.

A possible relation between sets, more elementary than belonging, is equality. The equality of two sets A and B is universally denoted by the familiar symbol

A = B;

the fact that A and B are not equal is expressed by writing

A ≠ B.

The most basic property of belonging is its relation to equality, which can be formulated as follows.

Axiom of extension. Two sets are equal if and only if they have the same elements.

With greater pretentiousness and less clarity: a set is determined by its extension.

It is valuable to understand that the axiom of extension is not just a logically necessary property of equality but a non-trivial statement about belonging. One way to come to understand the point is to consider a partially analogous situation in which the analogue of the axiom of extension does not hold. Suppose, for instance, that we consider human beings instead of sets, and that, if x and A are human beings, we write x [member of] A whenever x is an ancestor of A. (The ancestors of a human being are his parents, his parents parents, their parents, etc., etc.) The analogue of the axiom of extension would say here that if two human beings are equal, then they have the same ancestors (this is the "only if" part, and it is true), and also that if two human beings have the same ancestors, then they are equal (this is the "if" part, and it is false).

If A and B are sets and if every element of A is an element of B, we say that A is a subset of B, or B includes A, and we write

A [subset] B

or

B [contains] A.

The wording of the definition implies that each set must be considered to be included in itself (A [subset] A); this fact is described by saying that set inclusion is reflexive. (Note that, in the same sense of the word, equality also is reflexive.) If A and B are sets such that A [subset] B and A ≠ B, the word proper is used (proper subset, proper inclusion). If A, B, and C are sets such that A [subset] B and B [subset] C, then A [subset] C; this fact is described by saying that set inclusion is transitive. (This property is also shared by equality.)

If A and B are sets such that A [subset] B and B [subset] A, then A and B have the same elements and therefore, by the axiom of extension, A = B. This fact is described by saying that set inclusion is antisymmetric. (In this respect set inclusion behaves differently from equality. Equality is symmetric, in the sense that if A = B, then necessarily B = A.) The axiom of extension can, in fact, be reformulated in these terms: if A and B are sets, then a necessary and sufficient condition that A = B is that both A [subset] B and B [subset] A. Correspondingly, almost all proofs of equalities between two sets A and B are split into two parts; first show that A [subset] B, and then show that B [subset] A.

Observe that belonging ([member of]) and inclusion ([subset]) are conceptually very different things indeed. One important difference has already manifested itself above: inclusion is always reflexive, whereas it is not at all clear that belonging is ever reflexive. That is: A [subset] A is always true; is A [member of] A ever true? It is certainly not true of any reasonable set that anyone has ever seen. Observe, along the same lines, that inclusion is transitive, whereas belonging is not. Everyday examples, involving, for instance, super-organizations whose members are organizations, will readily occur to the interested reader.

SECTION 2

THE AXIOM OF SPECIFICATION

All the basic principles of set theory, except only the axiom of extension, are designed to make new sets out of old ones. The first and most important of these basic principles of set manufacture says, roughly speaking, that anything intelligent one can assert about the elements of a set specifies a subset, namely, the subset of those elements about which the assertion is true.

Before formulating this principle in exact terms, we look at a heuristic example. Let A be the set of all men. The sentence "x is married" is true for some of the elements x of A and false for others. The principle we are illustrating is the one that justifies the passage from the given set A to the subset (namely, the set of all married men) specified by the given sentence. To indicate the generation of the subset, it is usually denoted by Similarly

{x [member of] A: x is married},

Similarly

{x [member of] A: x is not married}

is the set of all bachelors;

{x [member of] A: the father of x is Adam}

is the set that contains Cain and Abel and nothing else, and

{x [member of] A: x is the father of Abel}

is the set that contains Adam and nothing else. Warning: a box that contains a hat and nothing else is not the same thing as a hat, and, in the same way, the last set in this list of examples is not to be confused with Adam. The analogy between sets and boxes has many weak points, but sometimes it gives a helpful picture of the facts.

All that is lacking for the precise general formulation that underlies the examples above is a definition of sentence. Here is a quick and informal one. There are two basic types of sentences, namely, assertions of belonging,

x [member of] A,

and assertions of equality,

A = B;

all other sentences are obtained from such atomic sentences by repeated applications of the usual logical operators, subject only to the minimal courtesies of grammar and unambiguity. To make the definition more explicit (and longer) it is necessary to append to it a list of the "usual logical operators" and the rules of syntax. An adequate (and, in fact, redundant) list of the former contains seven items:

and,
or (in the sense of "either — or — or both"),
not,
if — then — (or implies),
if and only if,
for some (or there exists),
for all.

As for the rules of sentence construction, they can be described as follows. Put "not" before a sentence and enclose the result between parentheses. (The reason for parentheses, here and below, is to guarantee unambiguity. Note, incidentally, that they make all other punctuation marks unnecessary. The complete parenthetical equipment that the definition of sentences calls for is rarely needed. We shall always omit as many parentheses as it seems safe to omit without leading to confusion. In normal mathematical practice, to be followed in this book, several different sizes and shapes of parentheses are used, but that is for visual convenience only.) Put "and" or "or" or "if and only if" between two sentences and enclose the result between parentheses, (iii) Replace the dashes in "if — then —" by sentences and enclose the result in parentheses, (iv) Replace the dash in "for some —" or in "for all —" by a letter, follow the result by a sentence, and enclose the whole in parentheses. (If the letter used does not occur in the sentence, no harm is done. According to the usual and natural convention "for some y (x [member of] A)" just means "x [member of] A". It is equally harmless if the letter used has already been used with "for some —" or "for all —." Recall that "for some x (x [member of] A)" means the same as "for some y (y [member of] A)"; it follows that a judicious change of notation will always avert alphabetic collisions.)

We are now ready to formulate the major principle of set theory, often referred to by its German name Aussonderungsaxiom.

Axiom of specification.To every set A and to every condition S(x) there corresponds a set B whose elements are exactly those elements x of A for which S(x) holds.

A "condition" here is just a sentence. The symbolism is intended to indicate that the letter x is free in the sentence S(x); that means that x occurs in S(x) at least once without being introduced by one of the phrases "for some x or "for all x" It is an immediate consequence of the axiom of extension that the axiom of specification determines the set B uniquely. To indicate the way B is obtained from A and from S(x) it is customary to write

B = {x [member of] A:S(x)}.

To obtain an amusing and instructive application of the axiom of specification, consider, in the role of S(x), the sentence

not (x [member of] x).

It will be convenient, here and throughout, to write "x [member of]' A" (alternatively "x [not member of] A") instead of "not (x [member of] A)"; in this notation, the role of S(x) is now played by

x [member of]' x.

It follows that, whatever the set A may be, if B = {x [member of] A: x [member of]' x}, then, for all y,

(*) y [member of] B if and only if (y [member of] A and y [member of]' y).

Can it be that B [member of] A? We proceed to prove that the answer is no. Indeed, if B [member of] A, then either B [member of] B also (unlikely, but not obviously impossible), or else B [member of]' B. If B [member of] B, then, by (*), the assumption B [member of] A yields B [member of]' B — a contradiction. If B [member of]' B, then, by (*) again, the assumption B [member of] A yields B [member of] B — a contradiction again. This completes the proof that B [member of] A is impossible, so that we must have B [member of]' A. The most interesting part of this conclusion is that there exists something (namely B) that does not belong to A. The set A in this argument was quite arbitrary. We have proved, in other words, that

nothing contains everything,

or, more spectacularly,

there is no universe.

"Universe" here is used in the sense of "universe of discourse," meaning, in any particular discussion, a set that contains all the objects that enter into that discussion.

In older (pre-axiomatic) approaches to set theory, the existence of a universe was taken for granted, and the argument in the preceding paragraph was known as the Russell paradox. The moral is that it is impossible, especially in mathematics, to get something for nothing. To specify a set, it is not enough to pronounce some magic words (which may form a sentence such as "x [member of]' x"); it is necessary also to have at hand a set to whose elements the magic words apply.

SECTOPM 3

UNORDERED PAIRS

For all that has been said so far, we might have been operating in a vacuum. To give the discussion some substance, let us now officially assume that

there exists a set.

Since later on we shall formulate a deeper and more useful existential assumption, this assumption plays a temporary role only. One consequence of this innocuous seeming assumption is that there exists a set without any elements at all. Indeed, if A is a set, apply the axiom of specification to A with the sentence "x ≠ x" (or, for that matter, with any other universally false sentence). The result is the set {x [member of] A: ≠ x}, and that set, clearly, has no elements. The axiom of extension implies that there can be only one set with no elements. The usual symbol for that set is

[empty set];

the set is called the empty set.

The empty set is a subset of every set, or, in other words, [empty set] [subset] A for every A. To establish this, we might argue as follows. It is to be proved that every element in [empty set] belongs to A; since there are no elements in [empty set], the condition is automatically fulfilled. The reasoning is correct but perhaps unsatisfying. Since it is a typical example of a frequent phenomenon, a condition holding in the "vacuous" sense, a word of advice to the inexperienced reader might be in order. To prove that something is true about the empty set, prove that it cannot be false. How, for instance, could it be false that [empty set] [subset] A? It could be false only if [empty set] had an element that did not belong to A. Since [empty set] has no elements at all, this is absurd. Conclusion: [empty set] [subset] A is not false, and therefore [empty set] [subset] A for every A.

The set theory developed so far is still a pretty poor thing; for all we know there is only one set and that one is empty. Are there enough sets to ensure that every set is an element of some set? Is it true that for any two sets there is a third one that they both belong to? What about three sets, or four, or any number? We need a new principle of set construction to resolve such questions. The following principle is a good beginning.

---

Excerpted from Naive Set Theory by Paul R. Halmos. Copyright © 2017 Paul R. Halmos. Excerpted by permission of Dover Publications, Inc..
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.

---