Read an Excerpt
AXIOMATIC SET THEORY
By PATRICK SUPPES
Dover Publications, Inc.Copyright © 1972 Dover Publications, Inc.
All rights reserved.
§ 1.1 Set Theory and the Foundations of Mathematics. Among the many branches of modern mathematics set theory occupies a unique place: with a few rare exceptions the entities which are studied and analyzed in mathematics may be regarded as certain particular sets or classes of objects. This means that the various branches of mathematics may be formally defined within set theory. As a consequence, many fundamental questions about the nature of mathematics may be reduced to questions about set theory.
The working mathematician, as well as the man in the street, is seldom concerned with the unusual question: What is a number? But the attempt to answer this question precisely has motivated much of the work by mathematicians and philosophers in the foundations of mathematics during the past hundred years. Characterization of the integers, rational numbers and real numbers has been a central problem for the classical researches of Weierstrass, Dedekind, Kronecker, Frege, Peano, Russell, Whitehead, Brouwer, and others. Perplexities about the nature of number did not originate in the nineteenth century. One of the most magnificent contributions of ancient Greek mathematics was Eudoxus' theory of proportion, expounded in Book V of Euclid's Elements; the main aim of Eudoxus was to give a rigorous treatment of irrational quantities like the geometric mean of 1 and 2. It may indeed be said that the detailed development from the general axioms of set theory of number theory and analysis is very much in the spirit of Eudoxus.
Yet the real development of set theory was not generated directly by an attempt to answer this central problem of the nature of number, but by the researches of Georg Cantor around 1870 in the theory of infinite series and related topics of analysis. Cantor, who is usually considered the founder of set theory as a mathematical discipline, was led by his work into a consideration of infinite sets or classes of arbitrary character. In 1874 he published his famous proof that the set of real numbers cannot be put into one-one correspondence with the set of natural numbers (the non-negative integers). In 1878 he introduced the fundamental notion of two sets being equipollent or having the same power (Mächtigkeit) if they can be put into one-one correspondence with each other. Clearly two finite sets have the same power just when they have the same number of members. Thus the notion of power leads in the case of infinite sets to a generalization of the notion of a natural number to that of an infinite cardinal number. Development of the general theory of transfinite numbers was one of the great accomplishments of Cantor's mathematical researches.
Technical consideration of the many basic concepts of set theory introduced by Cantor will be given in due course. From the standpoint of the foundations of mathematics the philosophically revolutionary aspect of Cantor's work was his bold insistence on the actual infinite, that is, on the existence of infinite sets as mathematical objects on a par with numbers and finite sets. Historically the concept of infinity has played a role in the literature of the foundations of mathematics as important as that of the concept of number. There is scarcely a serious philosopher of mathematics since Aristotle who has not been much exercised about this difficult concept.
Any book on set theory is naturally expected to provide an exact analysis of the concepts of number and infinity. But other topics, some controversial and important in foundations research, are also a traditional part of the subject and are consequently treated in the chapters that follow. Typical are algebra of sets, general theory of relations, ordering relations in particular, functions, finite sets, cardinal numbers, infinite sets, ordinal arithmetic, transfinite induction, definition by transfinite recursion, axiom of choice, Zorn's Lemma. At this point the reader is not expected to know what these phrases mean, but such a list may still give a clue to the more detailed contents of this book.
In this book set theory is developed axiomatically rather than intuitively. Several considerations have guided the choice of an axiomatic approach. One is the author's opinion that the axiomatic development of set theory is among the most impressive accomplishments of modern mathematics. Concepts which were vague and unpleasantly inexact for decades and sometimes even centuries can be given a precise meaning. Adequate axioms for set theory provide one clear, constructive answer to the question: Exactly what assumptions, beyond those of elementary logic, are required as a basis for modern mathematics? The most pressing consideration, however, is the discovery, made around 1900, of various paradoxes in naive, intuitive set theory, which admits the existence of sets of objects having any definite property whatsoever. Some particular restricted axiomatic approach is needed to avoid these paradoxes, which are discussed in §§ 1.3 and 1.4 below.
§ 1.2 Logic and Notation. We shall use symbols of logic extensively for purposes of precision and brevity, particularly in the early chapters. But proofs are mainly written in an informal style. The theory developed is treated as an axiomatic theory of the sort familiar from geometry and other parts of mathematics, and not as a formal logistic system for which exact rules of syntax and semantics are given. The explicitness of proofs is sufficient to make it a routine matter for any reader familiar with mathematical logic to provide formalized proofs in some standard system of logic. However, familiarity with mathematical logic is not required for understanding any part of the book.
At this point we introduce the few logical symbols which will be used. We first consider five symbols for the five most common sentential connectives. The negation of a formula P is written as -P. The conjunction of two formulas P and Q is written as P & Q. The disjunction of P and Q as P V Q. The implication with P as antecedent and Q as consequent as P [??] Q. The equivalence Pif and only ifQ as P ->Q. The universal quantifier For everyv as ([for all]v), and the existential quantifier For somev as ([there exists]v). We also use the symbol (E!v) for There is exactly onevsuch that. This notation may be summarized in the following table.
For every x there is a y such that for every x < y
(1) [for all]x)([there exists]y)(x< y).
For every ε there is a δ such that for every y
if |x - y| < δ then |f(x) - f(y)| > ε
(2) ([for all]ε)([there exists]δ)([for all]y)(|x - y| < δ -> |f(x) - f(y)| < ε).
For every x there is exactly one y such that x + y = 0
([for all]x)(E!y)(x + y = 0).
A given logical symbol may correspond to several English idioms. Thus ([for all]v)P may be read For allv, P as well as For everyv, P. Sentences (1) and (2) illustrate the use of parentheses for purposes of punctuation. No formal explanation seems necessary. However, one convention concerning the relative dominance of the sentential connectives &, V, -> and will [??] reduce considerably the number of parentheses. The convention is that [??] and -> dominate & and V. Thus, the formula:
(x< y & y< z) ->x< z
may be written without parentheses:
(3) x < y & y < z -> x < z.
x + y ≠ 0 [??] (x ≠ 0 v y ≠ 0)
may be written:
x + y ≠ 0 [??] x ≠ 0 v y ≠ 0
Principles of logic which are needed in the sequel and which may not be familiar to some readers will be intuitively explained when used. One principle used, concerning which there is some disagreement in practice among mathematicians, is that the double bar '=' is taken as the sign of identity. The formula 'x = y' may be read 'x is the same as y', 'x is identical with y' or 'x is equal to y'. The last reading is permissible here only if it is understood that equality means sameness of identity (which is what it does mean in almost all ordinary mathematical contexts). The exact status of the relation of identity within set theory is discussed in §2.2.
A few remarks concerning quantifiers may also be helpful. The scope of a quantifier is the quantifier itself together with the smallest formula immediately following the quantifier. What the smallest formula is, is always indicated by parentheses. Thus in the formula
(4) ([there exists]x)(x< y) [disjunction] y = 0
the scope of the quantifier '([there exists]x)' is the formula '([there exists]x)(x< y)'. Following an almost universal practice in mathematics, we shall omit, in the formulation of axioms and theorems, any universal quantifier whose scope is the whole formula. For instance, instead of (1) above, we would write: ([there exists]y) (x< y).
In a few places we shall need the notions of bound and free variables. An occurrence of a variable in a formula is bound if and only if this occurrence is within the scope of a quantifier using this variable. An occurrence of a variable in a formula is free if not bound. Finally, a variable is a bound variable in a formula if and only if at least one occurrence is bound; it is a free variable in a formula if and only if at least one occurrence is free. In formula (1) of this section all variables are bound; in (3) all variables are free; in (4) 'x' is bound and 'y' is free. By virtue of the convention stated in the preceding paragraph concerning omission of universal quantifiers in axioms and theorems, all variables occurring in axioms and theorems are bound.
§ 1.3 Axiom Schema of Abstraction and Russell's Paradox. In his initial development of set theory, Cantor did not work explicitly from axioms. However, analysis of his proofs indicates that almost all of the theorems proved by him can be derived from three axioms: (i) The axiom of extensionality for sets, which asserts that two sets are identical if they have the same members; (ii) the axiom of abstraction, which states that given any property there exists a set whose members are just those entities having that property; (iii) the axiom of choice, which will not be formulated at this point and is not pertinent to our discussion of the paradoxes.
The source of trouble is the axiom of abstraction. The first explicit formulation of it seems to be as Axiom V in Frege . In 1901 Bertrand Russell discovered that a contradiction could be derived from this axiom by considering the set of all things which have the property of not being members of themselves. Because this paradox was historically important in motivating the development of new, restricted axioms for set theory, its derivation will be given here. For symbolic formulation we need to introduce the binary predicate '[member of]' of set membership. The formula 'x [member of] y' is read 'x is a member of y', 'x belongs to y' or sometimes, 'x is in y' Thus, if A is the set of first five odd positive integers, the sentence '7 [member of] A' is true and '6 [member of] A' is false.
Excerpted from AXIOMATIC SET THEORY by PATRICK SUPPES. Copyright © 1972 Dover Publications, Inc.. 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.