Read an Excerpt
Basic Set Theory
By Azriel Levy Dover Publications, Inc.
Copyright © 1979 Springer-Verlag Berlin Heidelberg
All rights reserved.
ISBN: 978-0-486-15073-4
CHAPTER 1
The Basic Notions
All branches of mathematics are developed, consciously or unconsciously, in set theory or in some part of it. This gives the mathematician a very handy apparatus right from the beginning. The most he usually has to do in order to have his basic language ready is to describe the set theoretical notation he uses. In developing set theory itself we have no such advantage and we must go through the labor of setting up our set theoretical apparatus. This is a relatively long task. Even the question as to which objects to consider, only sets or also classes, is by no means trivial, and its implications will be discussed here in detail. In addition, we shall formulate the axioms of set theory; we shall show how the concepts of ordered pair, relation and function, which are so basic in mathematics, can be developed within set theory, and we shall study their most basic properties. By the end of this chapter we shall be just about ready to begin our real mathematical investigation of the universe of sets.
1. The Basic Language of Set Theory
In the present section and in Sections 3 and 4 we shall thoroughly discuss the language we are going to use for set theory. Usually when one studies a branch of mathematics one is not concerned much with the question as to which exactly is the language used in that branch. The reason why here we must look carefully at the language lies in the difference between set theory and most other branches of mathematics. Most mathematical fields use a relatively "small" fragment of set theory as their underlying theory, and rely on that fragment for the language, as well as for the set theoretical facts. The source of the difficulty we have in set theory with the language is the fact that not every collection of objects is a set (something which will be discussed in detail in the next few sections), but we still have to refer often to these collections, and we have to arrange the language so that we shall be able to do it handily. This difficulty does not come up in the fragments of set theory used for most mathematical theories, since those fragments deal only with a very restricted family of collections of objects, and all these collections are indeed sets.
Our present aim is to obtain for set theory a language which is sufficiently rich and flexible for the practical development of set theory, and yet sufficiently simple so as not to stand in the way of metamathematical investigation of set theory. For this purpose we start by choosing for set theory a very simple basic language. The simplicity of this language will be a great advantage when we wish to discuss set theory from a metamathematical point of view. The only objects of our set theory will be sets. One could also consider atoms, i.e., objects which are not sets and which serve as building blocks for sets, but they are not essential to what we shall do and, therefore, will not be considered in the present book. As a consequence of this decision, we view the sets as follows. We start with the null set 0, from it we obtain the set {0}, from the two sets 0 and {0} we obtain the sets {0, {0}} and {{0}}, and so on. Much of set theory is concerned with what is meant by this "and so on".
The language which we shall use for set theory will be the first-order predicate calculus with equality. Why first-order? Because a second-order or a higher-order theory admits already a part of the set theory in using its higher order variables. To see, for example, that second-order variables are essentially set variables let us consider the following axiom of second-order logic: [there exists]A]for all]x(x [member of] A [left and right arrow] Φ(x)), where Φ(x) is, essentially, any formula. This axiom is read: there exists a set A such that for every x, x is a member of A if and only if Φ(x). It would, of course, change nothing if we would choose another term instead of "set", since "set" is what we mean anyway. When we develop a formal system of set theory it does not seem right to handle sets in two or more parts of the language, i.e., by considering some sets as first-order objects, while having around also second-order objects which are sets. As a consequence of our decision we shall have, in principle, just one kind of variable, lower case letters, which will vary over sets.
The reason why we take up first-order predicate calculus with equality is a matter of convenience; by this we save the labor of defining equality and proving all its properties; this burden is now assumed by the logic.
Our basic language consists now of all the expressions obtained from x=y and x [member of] y, where x and y are any variables, by the sentential connectives [logical not](not), -> (if ... then ...), [disjunction] (or), [conjunction] (and), [left and right arrow] (if and only if), and the quantifiers [there exists]x (there exists an x) and [for all]x(for all x). These expressions will be called formulas. For metamathematical purposes we can consider the connectives [logical not] and v as the only primitive connectives, and the other connectives will be considered as obtained from the primitive connectives in the well known way (e.g., Φ [conjunction] ψ is [logical not] ([logical not]Φ[disjunction] [logical not]ψ), Φ -> ψ is [logical not]Φ [disjunction] ψ, etc.). For the same reason, we can consider [there exists] as the only primitive quantifier and the quantifier [for all] as defined by means of [there exists] by taking [for all]xφ to be an abbreviation of [logical not] [there exists]x [logical not] φ. We shall also use the abbreviations x ≠ y and x [not member of] y for [logical not] x = y and [logical not] x [member of] y. We shall write [there exists] ! xφ, and read: there is exactly one x such that φ for the formula [there exists]y]for all]x(x = y [left and right arrow] φ), where y is any variable which is not free in φ. Finally, we shall write ([there exists]x [member of] y)φ and ([for all]x [member of] y)φ for [there exists]x(x [member of] y [conjunction] φ) and [for all]x(x [member of] y -> φ), respectively, and read: "there is an x in y such that φ", and "for all x in y, φ".
By a free variable of a formula we mean, informally, a variable occurring in that formula so that it can be given different values and the formula says something concerning the values of the variable. E.g., x is a free variable in each of the following formulas (which are not necessarily taken from set theory): x< 3x, x2 = y, x is a real number, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], [for all]y(z< y ->x< y). x is not a free variable in the formulas [for all]x(x2 ≥ 0), [logical not] [there exists]x(x [member of] y), [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. In the latter three formulas x is an auxilliary variable which cannot be given a definite value and which can be replaced throughout each formula by another variable, say z, without changing the meaning of the formula. In these examples x is used as a bound variable. Note that [for all]x(x2 ≥ 0) says exactly what [for all]z(z2 ≥ 0) says, while sin x > 1/2 does not say the same thing as sin z > 1/2; in fact, for appropriate values of x and z sin x > 1/2 may be true, while sin z 1/2 may be false. A variable may have both free and bound occurrences in the same formula, even though one would usually try to avoid it; e.g., in 7 < z [conjunction] [there exists]z(z >x), the occurrences of z in [there exists]z(z >x) are bound, while the occurrence of z in 7 < z is free (since the quantifier [there exists]z applies only to z >x).
A formula with free variables says something about the values of its free variables. A formula without free variables makes a statement not about the value of some particular variable, but about the universe which the language describes. A formula of the latter kind is called a sentence. We shall also refer, informally, to formulas and sentences as statements.
Whenever we use a formula with free variables as an axiom or as a theorem we mean to say that the formula holds for all possible values given to its free variables. Thus, if we state a theorem [there exists]z(z = x]union]y) we mean the same thing as [for all]x]for all]y]for all]z(z = x]union]y).
By a theory we mean a set of formulas, which are called the axioms of the theory. If T is a theory, we shall write T]??]φ] for "φ is provable from T".
When we refer to a formula as φ(x) this does not mean that x is necessarily a free variable of φ(x) nor does it mean that φ(x) has no free variables other than x; it means that the interesting cases of what we shall say are those where x is indeed a free variable of φ(x). When we shall mention φ(z) after we have first mentioned φ(x), then φ(z) denotes the formula obtained from φ(x) by substituting the variable z for the free occurrences of x. (z may also be a bound variable of φ(x), and then before we substitute z for the free occurrences of x we may have to replace the bound occurrences of z by some other variable.)
2. The Axioms of Extensionality and Comprehension
By a set we mean a completely structure-free set, and therefore a set is determined solely by its members. This leads us to the first axiom of set theory.
2.1 Axiom of Extensionality (Frege 1893). [for all]x(x [member of] y [left and right arrow] x [member of] z) ->y = z.
In words: if y and z have the same members they are equal. The converse, that equal objects have the same members, is a logical truth.
2.2 The Existence of Sets. Now we face the question of finding or constructing the sets. We want any collection whatsoever of objects, i.e., sets, to be a set. This is not a precise idea and therefore we cannot translate it into our language. We must therefore be satisfied with a somewhat weaker stipulation. We shall require that every collection of sets which is "specifiable" in our language is a set; i.e., for every statement of our language the collection of all objects which satisfy it is a set. We shall by no means assume that it is necessarily true that all sets are specifiable; moreover, by introducing the axiom of choice we shall require the existence of sets which are not necessarily specifiable. The requirement that all specifiable collections are indeed sets is the following one.
2.3 Axiom of Comprehension (Frege 1893). [there exists]y]for all]x (x]member of]y [left and right arrow] φ(x)), where φ(x) is any formula (of the language of set theory) in which the variable y is not free (since if y were free in φ(x) this would cause a confusion of the y free in φ(x) with the y whose existence is claimed by the axiom). Our only reason in writing φ(x) instead of just φ is to draw attention to the fact that the "interesting" cases of this axiom schema are those for which the formula φ does actually contain free occurrences of the variable x.
The axiom of comprehension is an axiom schema, i.e., it is not a single sentence but an infinite set of sentences obtained by letting φ vary over all formulas. Any single sentence obtained from 2.3 by choosing a particular formula for φ in 2.3 is said to be an instance of the axiom schema, and is also called "an axiom of comprehension."
Those readers who were convinced by the axiom schema of comprehension are now in for a shock; the axiom schema of comprehension is not consistent — Theorem 2.4 below is the negation of one of its instances.
2.4 Theorem (Russell's antinomy — Russell 1903). [logical not] [there exists]y]for all]x(x [member of] y [left and right arrow] x [not member of] x).
Proof. Notice that this theorem is not just a theorem of set theory; it is a theorem of logic, since we do not use in its proof any axiom of set theory. We prove it by contradiction. Suppose y is a set such that [for all]x(x [member of] y [left and right arrow] x [not member of] x), then, since what holds for every x holds in particular for y, we have y [member of] y [left and right arrow] y [not member of] y, which is a contradiction.
Russell's antinomy is the simplest possible refutation of an instance of the comprehension schema. We refer to a refutation of such an instance as an antinomy. The first antinomy to be discovered is the Burali-Forti paradox discovered by Cantor and by Burali-Forti in the 1890's; it is given in II.3.6 and II.3.15. Some variants of Russell's antinomy are given in 2.5.
(Continues...)
Excerpted from Basic Set Theory by Azriel Levy. Copyright © 1979 Springer-Verlag Berlin Heidelberg. 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.
