Read an Excerpt
Introduction to Abstract Analysis
By Marvin E. Goldstein, Burl M. Rosenbaum Dover Publications, Inc.
Copyright © 2015 Dover Publications, Inc.
All rights reserved.
ISBN: 978-0-486-79991-9
CHAPTER 1
Elementary Set Concepts
Aside from being one of the principal tools of mathematics, set theory serves also as a unifying principle and foundation upon which mathematics can be based. A few mathematicians might even claim that mathematics is nothing more than set theory. In any event, attempts to put mathematics on set theoretic foundations have led to important contributions to the understanding of some of the more basic concepts of mathematics. However, our interest here in set theory is its use as a tool in mathematics.
The study of sets began with Cantor, around 1874, and grew out of his studies of the fundamental aspects of trigonometric series. Around the turn of the century great progress had been made in the theory of sets by Cantor, Russell, Frege, and others, and it appeared that there could be nothing which would prevent basing all mathematics on set theory alone. However, in 1903, when Frege was about to publish the second volume of his "Grundgesetze der Arithmetik," which was essentially his life work and relied heavily on the theory of sets, Russell sent Frege his ingenious paradox, which seemed so shattering to the foundations of set theory that Frege closed this volume with the following acknowledgment:
A scientist can hardly encounter anything more undesirable than to have the foundation collapse just as the work is finished. I was put in this position by a letter from Mr. Bertrand Russell when the work was almost through the press.
Immediately set theoretic paradoxes began appearing in large numbers. In some sense these paradoxes always seem to stem from the fact that sets which are "too large" are encountered. From a practical point of view these paradoxes may be avoided by always assuming that there is some possibly large but fixed set from which, roughly speaking, all objects, which are considered in a given discussion, are taken. We will express this principle a little more precisely in the subsequent discussion.
This procedure assures that no known paradoxes will occur, but we can never be absolutely certain that any system will be completely free from contradictions. This was pointed out by Gödel who proved that no consistent system can be used to prove its own consistency.
It is possible to treat set theory itself as a mathematical discipline by taking the concepts of set and membership as undefined and then setting up exact rules to describe their interrelation. However, we make no attempt to develop "axiomatic set theory" here. On the contrary, our aim is only to develop (in a fairly intuitive way) those concepts of set theory which will be useful for the work in the following chapters. In this way, we shall follow the ideas of Halmos as set forth in his "Naive Set Theory" (ref. 1).
Before proceeding with the discussion of sets, let us briefly introduce some terminology which is encountered frequently in mathematics.
Statements which must be either true or false (even though we may not know which) are called propositions. For example, "Sauerkraut is better than potato salad" is a statement which cannot be classified as being either true or false. On the other hand, a statement such as "The sauerkraut sold in this supermarket is more expensive per pound than the potato salad" is a statement which must be either true or false. In this chapter propositions will be designated by single letters.
Suppose that p and q are any two propositions. In mathematics, the sentences "p implies q", "if p, then q", "p only if q", "p is a sufficient condition for q", and "q is a necessary condition for p" occur frequently. They all mean that whenever the proposition p is true, then the proposition q must also be true or, what is the same thing, whenever q is false, p must also be false (for if q were false, p could not be true since this would imply that q had to be true also). The sentences "p is necessary and sufficient for q" and "p if and only if q" mean both p implies q and q implies p. The first of these shows that if p is true, q must be true. The second shows that if p is false, then q is false also. Hence, p and q must either both be true or both be false. Thus, for example, if the proposition p is "Paul is taller than Harry" and the proposition q is "Harry is shorter than Paul," it is clear that p if and only if q. If p is the proposition "Paul is taller than Harry and Harry is taller than Mary" and q is the proposition "Paul is taller than Mary," it is clear that p implies q but it is not true that q implies p.
A set is any collection of objects called elements or members. The only characteristic of a set is the particular objects which it contains. Sets are generally denoted by capital letters. Lowercase letters are used mostly for the members of sets. The notation x [member of] E means that x is a member of the set E, and x is said to be contained in E or to belong to E or, simply, to be in E. The negation of the statement x [member of] E, denoted by x [not member of] E, means that x is not a member of E. For example, if E is the set of positive integers, then 2 [member of] E but -2 [not member of] E. In general, a diagonal line running through a symbol usually denotes the logical "not statement:" for example, the symbol ≠ means "not equal to."
Sets are, in fact, completely determined by the members which they contain. In line with this idea we make the following definition of equality.
Definition 1.1:Two sets E and D are said to be thesame setorequalif they contain the same objects. This is denoted by writing E = D.
Stated in a slightly different way, the two sets E and D are defined to be equal if there is no element of E which is not an element of D and if there is no element of D which is not an element of E. This means that E and D are equal if every element of E is an element of D and every element of D is an element of E. From a practical point of view this last form of the definition of equality is the most useful one because it is most directly related to the method most used in practice to decide if two sets are equal. It will be useful to have a special name (subset) for the situation when the first half (but not necessarily the second half) of the requirements of this definition is met by two sets.
Definition 1.2:If there isnoelement of a set E which isnotan element of a set D, E is said to be asubsetof D, or E is said to becontainedorincludedin D, or D is said to contain E. This is denoted by writing E [subset] D or sometimes D [contains] E.
This definition means that if E [subset] D then every element of E must be an element of D. Note that the symbol [subset] only connects sets. If D is the set of positive integers and E is the set whose elements are 1, 2, and 3, then E [subset] D. However, it is not correct to write 2 [subset] D.
It is often very helpful to visualize sets as regions in the plane. The pictures obtained in this way corresponding to the various types of operations between sets (which will be discussed subsequently) are called Venn diagrams. Figure 1–1 illustrates the meaning of "D is a subset of E."
To avoid any of the known set theoretic paradoxes, mathematical structures are always set up in a manner which assures that there is some large but fixed set X (sometimes referred to as the universal set) such that all sets which arise can be considered as being either subsets of X or sets whose elements are subsets of X, etc. Sometimes this universal set is not mentioned explicitly in a given discussion but it will always be clear from the context that such a set exists. There is no reason why the elements of sets cannot be sets themselves! In fact, this is a situation which frequently arises in mathematics. Sets whose elements are sets are usually called families or collections in order to keep the various levels of set construction clearly in view. Actually, there is no reason why a given set D cannot simultaneously have a set E as one of its elements and an element of E as another. For example, suppose that the universal set is the set of positive integers and that the set E consists of the elements 1 and 2. If D is the set whose elements are 1, 2, 3, and E, then it is not only true that E [member of] D, but it is also true that E [subset] D. On the other hand, if D is the set whose elements are 1, 3, and E, it is still true that E [member of] D but it is no longer true that E [subset] D. Thus, a set E is not a subset of a set D unless all the elements of E are included among the elements of the set D. This example illustrates a difference between elements and sets. It is, however, unfortunate that both the symbols E and [subset] are read as contained in even though they refer to very different things. Sometimes, then, it is necessary to decide from the context which of these two meanings is to be attributed to the phrase "contained in."
The form of the definition of equality of sets is given in the paragraph immediately following Definition 1.1 shows that, if E and D are any two sets, E = D if and only if E [subset] D and D [subset] E. It also follows directly from Definition 1.2, for arbitrary sets E, D, and A, that if E [subset] D and D [subset] A, then E [subset] A. According to the wording of Definition 1.2, E [subset] E for every set E. On the other hand, for any reasonable set E, it is never true that E [member of] E. If E [subset] D and there is at least one element of D which is not an element of E (i.e., the second half of the requirements of the last form of the definition of equality is not met), E is said to be a proper subset of D.
Some authors use the notation E [subset] D to mean E is a proper subset of D. If this is done, they write E [subset or equal to] D where we have written E [subset] D. We shall not follow this convention here.
One usually conceives of sets as having at least some elements but as it turns out it is very desirable to consider also the set which has no elements. Because a set is completely determined by its elements, there is only one such set and it is denoted by the symbol [empty set] and called the empty set. Now [empty set] must be a subset of every set D, since [empty set] contains no elements and therefore there is no element of [empty set] which is not an element of D.
Clearly, if E, D, and A are any subsets of a set X, and x is any element of X, statements like "E [subset] D," "E [subset] D and D [subset] A," "x [member of] E," etc, are propositions. Large parts of mathematical proofs are composed of statements containing propositions of these types.
Before discussing the methods for specifying sets it will be helpful to introduce a certain concept from logic. Propositions usually contain the "names" of (or symbols for) certain objects. For example, the proposition "Paul is taller than Harry" discussed previously contains the names of the objects Paul and Harry. If E is a particular subset of some universal set X and t is a particular element of X, then the statement "t [member of] E" is a proposition which contains the "names" of the objects t and E. In this latter example, we can obtain a different proposition by replacing t by the name of some other element of X and, in general, can obtain an entire collection of propositions by successively replacing t by the names of all the elements of X. This collection of propositions may be described as consisting of all propositions "x [member of] E" as x varies over all the elements of X. Any statement of this type, which contains a symbol x of variable meaning in a place where the "name" of a particular object would normally occur and which becomes a proposition when x is replaced by the "name" of a member of some set D, is called a propositional scheme and is denoted by a symbol such as P(x). The set D is called the domain of P(x). If s is the "name" of some member of D, the proposition resulting from replacing x by s in P(x) is denoted by P(s). Thus, in the preceding example, P(x) is the symbol for "x [member of] E" and the domain (i.e., D) of P(x) is X. Note that x serves only to save the place where the name of an object is to be inserted.
Effectively, sets are specified in one of two ways. First, if a set consists of a finite number of elements, since a set is completely determined by its elements, we can specify the set by listing its elements. When this is done, the elements are enclosed by braces and separated by commas. Thus {d, 1, 2, 3} is the set whose elements are d, 1, 2, and 3. For sets with an "infinite" number of elements, this procedure cannot be used.
On the other hand, suppose P(x) is some propositional scheme with a domain D. For each particular element s [member of] D, P(s) will either be true or false. There will then be a certain subset of D, say E, which consists of all the elements x of D for which P(x) is true. The set E is denoted by
E = {x [member of] D|P(x)}
which reads "E is the set of all x contained in D such that P(x) (is true)," the words in parentheses usually being omitted. Sometimes, when it is understood from the context, the domain D is omitted and we write
E = {x|P(x)}
For example, suppose P(x) is the propositional scheme x2 = x and its domain is the set J of all positive integers. Then the set {x [member of] J|x2 = x} is the set of x [member of] J (or the set of all positive integers x) such that x2 = x. This is just the one element subset {1} of J. On the other hand, the set {x [member of] J|x + 1 = x} is the empty set [empty set].
In this manner then, every propositional scheme defines a set and since, for any set E, "x [member of] E" is a propositional scheme, every set determines a propositional scheme. In fact, this method of specifying sets includes the method of listing the elements. For example, if E = {1, 2, 3} and J is the set of all positive integers, then
E = {x [member of] J|x [member of] {1, 2, 3}
since x [member of] {1, 2, 3} is a propositional scheme.
We might point out that two different propositional schemes, say P(x) and Q(x), with the same domain D may define the same set. For suppose that, for each d [member of] D, P (d) if and only if Q(d). Then P (x) and Q (x) are either both true or both false at every point x [member of] D. Hence, the set of all x for which P (x) is true is the same as the set of all x for which Q (x) is true. That is
{x [member of] D|P(x)} = {x [member of] D|Q(x)} (1-1)
On the other hand, if equation (1–1) holds, then, for any d [member of] D, either d [member of] {x [member of] D|P (x)} in which case d [member of] {x [member of] D|Q (x)} and hence P (d) and Q (d) are both true or d [not member of] {x [member of] D|P (x)} in which case d [not member of]{x [member of] D|Q(x)} and hence P(d) and Q{d) are both false. Thus, P (d) if and only Q {d).
(Continues...)
Excerpted from Introduction to Abstract Analysis by Marvin E. Goldstein, Burl M. Rosenbaum. Copyright © 2015 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.
