errata & addenda for the preface and SETS AND ORDERINGS (chapters 1-7)

errata & addenda for the preface and SETS AND ORDERINGS (chapters 1-7) in HAF

Additional remarks for page xiv in the preface, about "short or elegant proofs." Of course, what is a "short proof" depends on what you already know. In most cases I have preferred elementary proofs, but occasionally I have used shortcuts that are made available by powerful and deep theorems developed earlier in the book. For a reader who is not already familiar with those theorems, the shortcut may be a very long proof.
Additional remarks for page xix in the preface, about the "single portmanteau theorem." When I was a student, I found it troublesome that different books used substantially different definitions for the same term. It took me some time to determine whether the several definitions were equivalent. In this book I hope to spare the student that trouble, by giving several definitions and proving their equivalence. With HAF in hand, the student can look through those other books; in most cases the definition used by the other book is either identical to or trivially equivalent to one of the several definitions in HAF.
In 1.17, in the TIMES table, the second "neg." in the leftmost column should be "pos." [NM]
In 1.26, the definition of partition could be improved this way: When the set X being partitioned is not the empty set, allow only nonempty sets for members of the partition. This has the advantage that then there is a natural bijection between the set of partitions of X and the set of equivalence relations on X. [GL]
Clarification for section 1.45. The two main approaches to axiomatic set theory are ZF set theory (listed in 1.47) and NBG set theory (not described in any detail in my book). NBG stands for von Neumann, Bernays, Godel. The approaches of NBG and ZF are essentially equivalent --- i.e., they ultimately accomplish essentially the same results, and the consistency of either implies the consistency of the other --- but they describe some ideas in different ways, and ZF has become a bit more popular. ... Formally, we should use either ZF or NBG, and not mix the two. Informally, however, I think that most mathematicians (unless they are logicians or set theorists) tend to use ZF most of the time, but slip into NBG when it is convenient --- e.g., to mention a proper class, as I did in section 1.45; that is one of the differences between ZF and NBG. In NBG set theory, all things are classes, and some classes are sets; the classes that aren't sets can be called ``proper classes'; only a set can be a member or nonmember of other things. In ZF set theory, all things are sets, and proper classes do not exist; we don't even need to talk about ``classes'' except to informally discuss some strings of words that do not correspond to any ``things.'' This distinction is seldom important to ordinary mathematicians. ... NBG permits an unlimited version of the Axiom of Comprehension: for any property P, {x: P(x)} is a class; it might or might not be a set. Contrast that with the more limited Axiom of Comprehension in ZF set theory (stated in section 1.47 of my book). ZF set theory does not permit us to assert the existence of an object of the form
R = {x: x is not a member of itself},
and so Russell's Paradox cannot be carried out. In NBG set theory, on the other hand, we can form R; it is a class. In that setting, Russell's argument does not yield a contradiction; it merely yields a proof that the class R is a proper class.
In 1.47, The Axiom of Replacement (on page 30) should be stated a little differently. It should say: "Let f be a rule, defined on a set or on a proper class -- i.e., assume that to each x in its domain, f assigns some set f(x). Let X be a set, and assume X is a subset of the domain of f. Then the class {f(x) : x in X} is a set." [NM]
Additional remarks for 2.1. Perhaps the beginning of Chapter 2 would be a good place to insert a preview chart, listing some of the classes of functions that will be studied in the book. Although not all the classes of functions can be ordered linearly, quite a few of them can. In order of increasing generality, here are a few important classes:
- differentiable functions with bounded derivatives
- Lipschitzian functions
- uniformly continuous functions
- continuous functions
- lower semicontinuous functions
- functions measurable from Borel sets to Borel sets
- Lebesgue-measurable functions
- functions
Different classes of functions are useful for different purposes. For instance, the uniform limit of continuous functions is continuous, but a pointwise limit of continuous functions is not necessarily continuous; when working with pointwise limits, it may be more natural to study measurable functions. Another helpful remark: When we turn to more general classes of functions, we get functions which are not as "nice" and regular, so they are harder to work with; but we also get more functions, and thus the solutions to more problems. Some problems have nasty functions for their answers; a nasty answer is better than no answer at all.
In 2.2.e, "unique polynomial of degree at most n" should be "unique polynomial of degree less than n".
In 2.7, a couple of the F's should be f's. [SS]
Additional remarks for 2.13 and 5.31 and thereabouts. The student who has little or no previous experience with uniform continuity may have difficulty seeing the point of the definition of uniformity in 5.31. To alleviate this problem, perhaps it would help to add a few ADDITIONAL PARAGRAPHS (requires graphical browser) around 2.13.
In 2.15.b, a gauge is separating "in the sense of 2.11" -- that should be "in the sense of 2.13." [JT]
Additional remarks for 3.3.e: Most readers are probably more familiar with functions than with relations. Thus, this observation may be helpful: Verify that the composition QoR of two relations has graph equal to the union of the graphs of all the compositions fog, where f and g are functions whose graphs are contained in the graphs of Q and R respectively.
In 3.8, the definition of "equivalence relation" isn't quite right. An equivalence relation is a preorder that is symmetric -- that much is correct -- but then the definition of "symmetric" is restated incorrectly in parentheses. The book says x preceq x, but it should say x preceq y implies y preceq x. [SS]
In 3.8, the definition of "equivalence relation" isn't quite right. An equivalence relation is a preorder that is symmetric -- that much is correct -- but then the definition of "symmetric" is restated incorrectly in parentheses. The book says x preceq x, but it should say x preceq y implies y preceq x. [SS]
Indeed, in most cases the only picture drawn is a periodic tiling of the plane (or some portion of it) by congruent triangles. This picture suggests that, in a similar fashion, 3-dimensional space can be tiled with congruent tetrahedrons. It can't! Try it (with cardboard models); you'll find that you need to alternate tetrahedrons and octahedrons. This sort of thing is not easy to visualize, and so pictures can be misleading.
There seem to be two common ways to get around the difficulty, although neither method completely eliminates the difficulty:
(i) Instead of a periodic tiling, use an aperiodic one. Any polygon in the plane can be subdivided into triangles (generally not congruent); indeed, any n-gon can be subdivided into n-2 triangles. Similarly, any polyhedron in 3-space (e.g., any octahedron) can be subdivided into tetrahedrons, etc. A mathematician with a reliable imagination can then convince himself or herself of the validity of various assertions about the number of simplexes that any facet is contained in. However, the relevant pictures are hard to visualize and impossible to draw in dimensions higher than 2, and so it is not clear just how "reliable" are the imaginations of the mathematicians involved. I would not want to rely on mine for this purpose. -- The subject of triangulations is not a simple one. There are entire books devoted to this subject, and they're not simple books. For instance, see
C. Y. Dang, Triangulations and simplicial methods, Lecture Notes in Economics and Mathematical Systems 421, Springer-Verlag, Berlin, 1995. (Math Reviews 96f:90079.)
(ii) Instead of a geometric approach, we could take an algebraic approach. Describe the relevant simplexes and facets entirely in terms of their barycentric coordinates, without trying to visualize the picture for any dimensions higher than 2. This approach lends itself more readily to being made into a rigorous proof, but the proof includes some rather long and tedious steps, verifying in higher dimensions what was obvious in two dimensions. Among the fully detailed expositions that I've looked at thus far, the most readable is the one in
R. Webster, Convexity, Oxford University Press, 1994.
However, because the proof of Sperner's Lemma in that book is complete, it is also quite long. There are two parts to the proof:
- Lemma. Let some triangulation of the simplex S be given. Suppose F is a facet of at least one subsimplex in the triangulation. Then F is a facet of precisely two subsimplexes, unless F lies in a facet of S, in which case F is a facet of only one subsimplex. (This result is obvious in two dimensions, and so it is glossed over by some expositions.)
- Sperner's Theorem. For any proper labeling of the triangulation, there is an odd number of subsimplexes that are completely labeled.
But we have essentially the same two parts in Wolsey's proof of the cubical Sperner Lemma! So no simplicity is gained by using triangulations, and much simplicity is lost. If the triangulation proofs look shorter than Wolsey's proof, I suspect that it is only because some of the difficulty has been glossed over.
3.16.b. The last sentence -- i.e., about this set being nonempty -- is is incorrect. For instance, it fails when the partial order relation (curly less-than-or-equal) is equality; then the corresponding not-equal relation (curly less-than) is empty. Found by [MG].
Additional remarks and reference(s) for 3.28 and 3.37. I have continued looking at different expositions of Sperner's Lemma in the literature, and I have been disappointed by most of them. They all draw a diagram for the 2-dimensional case (since that is the only case we really can draw), and then most of them say that the higher-dimensional cases are similar. That is not true. The higher-dimensional case is a generalization of the 2-dimensional case, but most of the expositions do not present the 2-dimensional case so that it generalizes in an obvious fashion to higher dimensions.
3.28-3.35. There are one or more mistakes in this section, and I haven't tracked them all down yet. Some of them are fixed if you add the assumption that the sets involved are all finite. That's not a severe problem, since that assumption is satisfied in the only case where we need to use this -- i.e., in 3.36. You may also have to change the definition of the curved less-than symbol. I defined it as curved-less-than-or-equal-but-not equal. It may need to be defined instead as curved-less-than-or-equal-but-not-curved-greater-than-or-equal. When I have more time I may investigate this further.
In 3.37, in the First Approximate Fixed Point Theorem, K should be S. [JI]
In 3.41, change "lower set" to "proper lower set". [RT]
Additional hint for 3.41. Some of the omitted steps ("verify this, show that...") may be easier if you first prove this lemma about the set X₀ and the function F: If u is a member of X₀ then F(u) is the lowest member of Y \ F(Pre(X₀)).
3.46. The empty set has not been handled correctly. Let script-F be the empty set; then script-F has finite character but has no inclusion-maximal element. This can easily be fixed in either of two ways (whichever suits your taste better): (i) Make it part of the definition of "finite character", that script-F must contain at least one set (and therefore must contain the empty set); or (ii) In the "Finite Character Theorem (canonical choice version)", don't just use *any* collection script-F that has finite character; rather, assume also that script-F is nonempty. -- Analogous changes probably need to be made later in the book, where this concept shows up again.
Additional remark for 4.14. Still another meaning for "complete" is given in 21.16; this notion is entirely unrelated to the ones given in 4.14. All these notions of "complete" mean "not having any holes," but they refer to entirely different kinds of holes. The student would probably be least confused by viewing it as a coincidence that the same word, "complete," is used in these several different contexts.
5.5.b. Add to clause (A) the assumption that the set A is a member of F. Without that additional assumption, clause (A) does not imply clauses (B) and (C). Example: Let X be the real line, and let F be the filter generated by the closed intervals of the form [0,r], where r is a positive number. Found by [CD].
Additional example for 5.26. Let X be a set. Let P be a partition of X -- that is, let P be a collection of disjoint sets whose union is X. Let S be the collection of all sets that can be obtained by taking the union of some of the members of P. Then S is a sigma-algebra of subsets of X. Actually, S satisfies a slightly stronger property: S is closed under complementation and under arbitrary union. This sigma algebra will be used in part of the proof of 21.8, for the sigma algebra T-prime.
Additional material after 5.26. Many students at first get the erroneous idea that the sigma-algebra generated by a collection G of sets can be obtained by finitely many iterations of the set operations -- e.g., let G* be the collection of all countable unions of members of G and their complements; then some students think that G*, or perhaps G**, is a sigma-algebra. That's not true. Let H(0) = G and let H(n+1) = H(n)*; then you have to keep going. In fact, even the union of H(1), H(2), H(3), ... may not be enough: If you take a set S(j) in H(j) for each j, then the union of the S(j)'s might not be in any H(j). -- That kind of iteration is the beginning of the proof of an interesting theorem:
card{Borel subsets of R} = card(R).
For a proof, continue the iteration indicated above, but don't just use the positive integers for the subscripts; use the ordinals. Define H(alpha) = (union of H(beta)'s for beta less than alpha)*. Let W be the first uncountable ordinal. The union of countably many predecessors of W is a predecessor of W; from that it follows that the sigma-algebra generated by G is equal to H(W). This result can be found in Section 5, Exercise (9) in Halmos's book MEASURE THEORY. -- A related result: it is easy to show that
card{Lebesgue measurable subsets of R} is greater than card(R).
Indeed, define C as in 24.39, and then consider the collection of all subsets of C.
Additional remarks for 5.42-5.46. It would be helpful to give an example or two of a transitive set that is *not* an ordinal, but I seem to have omitted that. Here are two such examples. As in 5.44, let 0 denote the empty set.
{0, {0}, {{0}} } is transitive (easy to verify). But it is not an ordinal. Perhaps the easiest (i.e., laziest) way to prove that it is not an ordinal is as follows: By 5.46.c, all the members of an ordinal are ordinals. But {{0}}={1} is not transitive, as we noted in 5.43.a, so it's not an ordinal.
Let T be any ordinal greater than 1, and let X be the powerset of T -- that is, X=P(T). I claim that X is transitive but not an ordinal. To see that X is transitive, suppose A is a member of S and S is a member of X; we want to show A is a member of X. Since S is a member of X=P(T), S is a subset of T. Since A is a member of S, A is a member of T. Since T is transitive, A is a subset of T. Thus A is a member of P(T)=X, and so X is transitive. To show X is not an ordinal, note that 1 is a member of T, so {1} is a subset of T, so {1} is a member of X. But {1} is not an ordinal, as we've already noted above. So by 5.46.c, X is not an ordinal.
In 5.52, in the definition of psi, omit the phi and change A to S; the definition should just be: psi(S)=u{psi(T):T in S}. Then a couple of sentences later, instead of "Hence f(u(C(S))) exists," it is simpler to reason "Hence u(C(S)) exists." [JI]
Additional remarks for 6.12 or 6.13. We should emphasize that an arbitrary product can be DEFINED without using the Axiom of Choice. That was done in 1.33. The Axiom of Choice is merely needed if we wish to prove that the product set is NONEMPTY.
Comment for 6.21: Probably the simplest application of Zorn's Lemma is that given in 11.29.
In 6.33, the result at the bottom of the page is due to Pospi\v sil (1937), not Tarski. [JI]
In 7.3, it is true that the universal ordering is an example of a directed ordering that is not antisymmetric. But the book says the universal ordering is "xRx for all x in X". That should be "xRy for all x,y in X". [MG]
Additional remarks for 7.3: Examples of directed sets can be found elsewhere in the book, but 7.3 would be a good place to add a brief list reviewing such examples:
- N with its usual order (see 7.8.b);
- N ordered by "is a factor of" (see 7.8.c);
- (0,1) with reverse ordering (this corresponds to epsilon and delta decreasing to 0 in calculus proofs);
- finite subsets of an infinite set, ordered by inclusion;
- the neighborhoods of a point in a topological space, ordered by reverse inclusion;
- (generalizing the previous example) a proper filter of sets, ordered by reverse inclusion;
- the directed set used in the definition of the Riemann integral (see 24.7).
In 7.16.d, on page 163, that last "(y_n)" should be "(x_m)".
Remarks for 7.30, 7.38, and 15.4.. The terms "convergence closure" and "convergence interior," defined as in 15.4, are my own terminology, and I regret using that terminology. For the operators defined in 15.4, a better choice of words would be "preclosure" and "preinterior." It would be better to reserve the word "closure" for a different meaning. Let X be any convergence space (as in 7.30) and let S be a subset of X. We shall say that S is closed (for the convergence) if it has this property: whenever a net in S converges to a limit, then that limit also lies in S. This is a generalization of topological closure, different from the generalization given in 15.4, and more in conformity with the literature. It is easy to see that the sets which are "closed" in this sense form a Moore collection (defined in 4.3), and thus determine a Moore closure operator as in 4.3. -- Fleischer [1989] defines a convergence to be regular if it has this property: Whenever F is a filter converging to a point z, then F contains a filterbase G which also converges to z and which consists of closed sets. This is relevant for the discussion below. -- Now consider the consequences in a poset (with convergence as in 7.38 and 7.40.d). It is easy to see that any order interval (defined as in 3.14) is a closed set. Fleischer [1989] uses that fact to show that the order convergence of a poset is regular: Let x,S,T,z be as in 7.38 of my book, and let F be the filter of the net x. Then for each s in S and t in T the order interval [s,t] belongs to F. The set of such intervals is the required filterbase G. -- Fleischer goes on to prove the following interesting result: Let (X,lim) be a convergence space. Then there exists a partial ordering of some superset of X which yields the given lim as the order convergence if and only if lim satisfies these four conditions:
1. lim is centered, as defined in 7.34.a. (Fleischer calls this "convergence of singletons.")
2. lim is isotone, as defined in 7.34.b. (Fleischer calls this "refinement stable." By the way, I neglected to point out in my book just why some mathematicians call this "isotone;" it is because a larger filter yields a larger set of limits.)
3. lim is Hausdorff, as defined in 7.36. (Fleischer calls this "separated." In retrospect, I think I like Fleischer's term better, and I'll use it in place of "Hausdorff" if there is a second edition.)
4. lim is regular, as defined above.
The proof is a couple of paragraphs long. For details see
I. Fleischer, Order-convergence in posets, Math. Nachr 142 (1989), 215-218.