Handbook of Analysis and Its Foundations

By Eric Schechter

Handbook of Analysis and Its Foundations is a self-contained and unified handbook on mathematical analysis and its foundations. Intended as a self-study guide for advanced undergraduates and beginning graduatestudents in mathematics and a reference for more advanced mathematicians, this highly readable book provides broader coverage than competing texts in the area. Handbook of Analysis and Its Foundations provides an introduction to a wide range of topics, including: algebra; topology; normed spaces; integration theory; topological vector spaces; and differential equations. The author effectively demonstrates the relationships between these topics and includes a few chapters on set theory and logic to explain the lack of examples for classical pathological objects whose existence proofs are not constructive. More complete than any other book on the subject, students will find this to be an invaluable handbook.

• Covers some hard-to-find results including:
• Bessagas and Meyers converses of the Contraction Fixed Point Theorem
• Redefinition of subnets by Aarnes and Andenaes
• Ghermans characterization of topological convergences
• Neumanns nonlinear Closed Graph Theorem
• van Maarens geometry-free version of Sperners Lemma
• Includes a few advanced topics in functional analysis
• Features all areas of the foundations of analysis except geometry
• Combines material usually found in many different sources, making this unified treatment more convenient for the user
• Has its own webpage: http://math.vanderbilt.edu/

• Language: English
• Publisher: Academic Press
• Release date: Oct 24, 1996
• ISBN: 9780080532998

Eric Schechter

Eric Schechter obtained his Ph.D. in mathematics at the University of Chicago. He is currently Associate Professor at Vanderbilt University, and has also taught at Duke University. Schechters research focuses on differential equations, fixed point theory, and the Axiom of Choice. He currently resides in Nashville, Tennessee with his wife, Elvira Casal, and his two children. Please visit the web page for hisbook: http://math.vanderbilt.edu/~schectex/ccc/

Book preview

Handbook of Analysis and Its Foundations

Eric Schechter

Vanderbilt University

Table of Contents

Cover image

Title page

Copyright

Inside Front Cover

Preface

Part A: SETS AND ORDERINGS

Chapter 1: Sets

MATHEMATICAL LANGUAGE AND INFORMAL LOGIC

BASIC NOTATIONS FOR SETS

WAYS TO COMBINE SETS

FUNCTIONS AND PRODUCTS OF SETS

ZF SET THEORY

Chapter 2: Functions

SOME SPECIAL FUNCTIONS

DISTANCES

CARDINALITY

INDUCTION AND RECURSION ON THE INTEGERS

Chapter 3: Relations and Orderings

RELATIONS

PREORDERED SETS

MORE ABOUT EQUIVALENCES

MORE ABOUT POSETS

MAX, SUP, AND OTHER SPECIAL ELEMENTS

CHAINS

VAN MAAREN’S GEOMETRY-FREE SPERNER LEMMA

WELL ORDERED SETS

Chapter 4: More about Sups and Infs

MOORE COLLECTIONS AND MOORE CLOSURES

SOME SPECIAL TYPES OF MOORE CLOSURES

LATTICES AND COMPLETENESS

MORE ABOUT LATTICES

MORE ABOUT COMPLETE LATTICES

ORDER COMPLETIONS

SUPS AND INFS IN METRIC SPACES

Chapter 5: Filters, Topologies, and Other Sets of Sets

FILTERS AND IDEALS

TOPOLOGIES

ALGEBRAS AND SIGMA-ALGEBRAS

UNIFORMITIES

IMAGES AND PREIMAGES OF SETS OF SETS

TRANSITIVE SETS AND ORDINALS

THE CLASS OF ORDINALS

Chapter 6: Constructivism and Choice

EXAMPLES OF NONCONSTRUCTIVE MATHEMATICS

FURTHER COMMENTS ON Constructivism

THE MEANING OF CHOICE

VARIANTS AND CONSEQUENCES OF CHOICE

SOME EQUIVALENTS OF CHOICE

COUNTABLE CHOICE

DEPENDENT CHOICE

THE ULTRAFILTER PRINCIPLE

Chapter 7: Nets and Convergences

NETS

SUBNETS

UNIVERSAL NETS

MORE ABOUT SUBSEQUENCES

CONVERGENCE SPACES

CONVERGENCE IN POSETS

CONVERGENCE IN COMPLETE LATTICES

Part B: ALGEBRA

Chapter 8: Elementary Algebraic Systems

MONOIDS

GROUPS

SUMS AND QUOTIENTS OF GROUPS

RINGS AND FIELDS

MATRICES

ORDERED GROUPS

LATTICE GROUPS

UNIVERSAL ALGEBRAS

EXAMPLES OF EQUATIONAL VARIETIES

Chapter 9: Concrete Categories

DEFINITIONS AND AXIOMS

EXAMPLES OF CATEGORIES

INITIAL STRUCTURES AND OTHER CATEGORICAL CONSTRUCTIONS

VARIETIES WITH IDEALS

FUNCTORS

THE REDUCED POWER FUNCTOR

EXPONENTIAL (DUAL) FUNCTORS

Chapter 10: The Real Numbers

DEDEKIND COMPLETIONS OF ORDERED GROUPS

ORDERED FIELDS AND THE REALS

THE HYPERREAL NUMBERS

QUADRATIC EXTENSIONS AND THE COMPLEX NUMBERS

ABSOLUTE VALUES

CONVERGENCE OF SEQUENCES AND SERIES

Chapter 11: Linearity

LINEAR SPACES AND LINEAR SUBSPACES

LINEAR MAPS

LINEAR DEPENDENCE

FURTHER RESULTS IN FINITE DIMENSIONS

CHOICE AND VECTOR BASES

DIMENSION OF THE LINEAR DUAL (OPTIONAL)

PREVIEW OF MEASURE AND INTEGRATION

ORDERED VECTOR SPACES

POSITIVE OPERATORS

ORTHOGONALITY IN RIESZ SPACES (OPTIONAL)

Chapter 12: Convexity

CONVEX SETS

COMBINATORIAL CONVEXITY IN FINITE DIMENSIONS (OPTIONAL)

CONVEX FUNCTIONS

NORMS, BALANCED FUNCTIONALS, AND OTHER SPECIAL FUNCTIONS

MINKOWSKI FUNCTIONALS

HAHN-BANACH THEOREMS

CONVEX OPERATORS

Chapter 13: Boolean Algebras

BOOLEAN LATTICES

BOOLEAN HOMOMORPHISMS AND SUBALGEBRAS

BOOLEAN RINGS

BOOLEAN EQUIVALENTS OF UF

HEYTING ALGEBRAS

Chapter 14: Logic and Intangibles

SOME INFORMAL EXAMPLES OF MODELS

LANGUAGES AND TRUTHS

INGREDIENTS OF FIRST-ORDER LANGUAGE

ASSUMPTIONS IN FIRST-ORDER LOGIC

SOME SYNTACTIC RESULTS (PROPOSITIONAL LOGIC)

SOME SYNTACTIC RESULTS (PREDICATE LOGIC)

THE SEMANTIC VIEW

SOUNDNESS, COMPLETENESS, AND COMPACTNESS

NONSTANDARD ANALYSIS

SUMMARY OF SOME CONSISTENCY RESULTS

QUASICONSTRUCTIVISM AND INTANGIBLES

Part C: TOPOLOGY AND UNIFORMITY

Chapter 15: Topological Spaces

PRETOPOLOGICAL SPACES

TOPOLOGICAL SPACES AND THEIR CONVERGENCES

MORE ABOUT TOPOLOGICAL CLOSURES

CONTINUITY

MORE ABOUT INITIAL AND PRODUCT TOPOLOGIES

QUOTIENT TOPOLOGIES

NEIGHBORHOOD BASES AND TOPOLOGY BASES

CLUSTER POINTS

MORE ABOUT INTERVALS

Chapter 16: Separation and Regularity Axioms

KOLMOGOROV (T-ZERO) TOPOLOGIES AND QUOTIENTS

SYMMETRIC AND FRÉCHET (T-ONE) TOPOLOGIES

PREREGULAR AND HAUSDORFF (T-TWO) TOPOLOGIES

REGULAR AND T-THREE TOPOLOGIES

COMPLETELY REGULAR AND TYCHONOV (T-THREE AND A HALF) TOPOLOGIES

PARTITIONS OF UNITY

Normal Topologies

PARACOMPACTNESS

HEREDITARY AND PRODUCTIVE PROPERTIES

Chapter 17: Compactness

CHARACTERIZATIONS IN TERMS OF CONVERGENCES

BASIC PROPERTIES OF COMPACTNESS

REGULARITY AND COMPACTNESS

Tychonov’s Theorem

COMPACTNESS AND CHOICE (OPTIONAL)

COMPACTNESS, MAXIMA, AND SEQUENCES

PATHOLOGICAL EXAMPLES: ORDINAL SPACES (OPTIONAL)

BOOLEAN SPACES

Eberlein-Smulian Theorem

Chapter 18: Uniform Spaces

LIPSCHITZ MAPPINGS

UNIFORM CONTINUITY

PSEUDOMETRIZABLE GAUGES

COMPACTNESS AND UNIFORMITY

UNIFORM CONVERGENCE

EQUICONTINUITY

Chapter 19: Metric and Uniform Completeness

CAUCHY FILTERS, NETS, AND SEQUENCES

COMPLETE METRICS AND UNIFORMITIES

TOTAL BOUNDEDNESS AND PRECOMPACTNESS

BOUNDED VARIATION

CAUCHY CONTINUITY

CAUCHY SPACES (OPTIONAL)

COMPLETIONS

Banach’s Fixed Point Theorem

Meyers’s Converse (Optional)

Bessaga’s Converse and Bunsted’s Principle (Optional)

Chapter 20: Baire Theory

G-DELTA SETS

MEAGER SETS

GENERIC CONTINUITY THEOREMS

TOPOLOGICAL COMPLETENESS

BAIRE SPACES AND THE BAIRE CATEGORY THEOREM

ALMOST OPEN SETS

RELATIVIZATION

ALMOST HOMEOMORPHISMS

TAIL SETS

BAIRE SETS (OPTIONAL)

Chapter 21: Positive Measure and Integration

Measurable Functions

JOINT MEASURABILITY

POSITIVE MEASURES AND CHARGES

NULL SETS

LEBESGUE MEASURE

SOME COUNTABILITY ARGUMENTS

CONVERGENCE IN MEASURE

INTEGRATION OF POSITIVE FUNCTIONS

ESSENTIAL SUPREMA

Part D: TOPOLOGICAL VECTOR SPACES

Chapter 22: Norms

(G-) (SEMI) NORMS

BASIC EXAMPLES

SUP NORMS

CONVERGENT SERIES

BOCHNER-LEBESGUE SPACES

STRICT CONVEXITY AND UNIFORM CONVEXITY

HILBERT SPACES

Chapter 23: Normed Operators

Norms of Operators

EQUICONTINUITY AND JOINT CONTINUITY

THE BOCHNER INTEGRAL

HAHN-BANACH THEOREMS IN NORMED SPACES

A FEW CONSEQUENCES OF HB

DUALITY AND SEPARABILITY

UNCONDITIONALLY CONVERGENT SERIES

NEUMANN SERIES AND SPECTRAL RADIUS (OPTIONAL)

Chapter 24: Generalized Riemann Integrals

DEFINITIONS OF THE INTEGRALS

BASIC PROPERTIES OF GAUGE INTEGRALS

ADDITIVITY OVER PARTITIONS

INTEGRALS OF CONTINUOUS FUNCTIONS

Monotone Convergence Theorem

ABSOLUTE INTEGRABILITY

HENSTOCK AND LEBESGUE INTEGRALS

MORE ABOUT LEBESGUE MEASURE

MORE ABOUT RIEMANN INTEGRALS (OPTIONAL)

Chapter 25: Fréchet Derivatives

DEFINITIONS AND BASIC PROPERTIES

PARTIAL DERIVATIVES

STRONG DERIVATIVES

DERIVATIVES OF INTEGRALS

INTEGRALS OF DERIVATIVES

SOME APPLICATIONS OF THE SECOND FUNDAMENTAL THEOREM OF CALCULUS

PATH INTEGRALS AND ANALYTIC FUNCTIONS (OPTIONAL)

Chapter 26: Metrization of Groups and Vector Spaces

F-SEMINORMS

TAG’s AND TVS’s

ARITHMETIC IN TAG’s AND TVS’s

NEIGHBORHOODS OF ZERO

CHARACTERIZATIONS IN TERMS OF GAUGES

UNIFORM STRUCTURE OF TAG’s

PONTRYAGIN DUALITY AND HAAR MEASURE (OPTIONAL; PROOFS OMITTED)

ORDERED TOPOLOGICAL VECTOR SPACES

Chapter 27: Barrels and Other Features of TVS’s

BOUNDED SUBSETS OF TVS’S

BOUNDED SETS IN ORDERED TVS’S

DIMENSION IN TVS’S

FIXED POINT THEOREMS OF BROUWER, SCHAUDER, AND TYCHONOV

BARRELS AND ULTRABARRELS

PROOFS OF BARREL THEOREMS

INDUCTIVE TOPOLOGIES AND LF SPACES

THE DREAM UNIVERSE OF GARNIR AND WRIGHT

Chapter 28: Duality and Weak Compactness

HAHN-BANACH THEOREMS IN TVS’S

BILINEAR PAIRINGS

WEAK TOPOLOGIES

WEAK TOPOLOGIES OF NORMED SPACES

POLAR ARITHMETIC AND EQUICONTINUOUS SETS

DUALS OF PRODUCT SPACES

CHARACTERIZATIONS OF WEAK COMPACTNESS

SOME CONSEQUENCES IN BANACH SPACES

MORE ABOUT UNIFORM CONVEXITY

Duals of the Lebesgue Spaces

Chapter 29: Vector Measures

BASIC PROPERTIES

THE VARIATION OF A CHARGE

INDEFINITE BOCHNER INTEGRALS AND RADON-NIKODYM DERIVATIVES

CONDITIONAL EXPECTATIONS AND MARTINGALES

EXISTENCE OF RADON-NIKODYM DERIVATIVES

SEMIVARIATION AND BARTLE INTEGRALS

MEASURES ON INTERVALS

PINCUS’S PATHOLOGY (OPTIONAL)

Chapter 30: Initial Value Problems

ELEMENTARY PATHOLOGICAL EXAMPLES

CarathÉodory Solutions

LIPSCHITZ CONDITIONS

GENERIC SOLVABILITY

Compactness Conditions

ISOTONICITY CONDITIONS

GENERALIZED SOLUTIONS

SEMIGROUPS AND DISSIPATIVE OPERATORS

References

Index and Symbol List

LIST OF SYMBOLS

Copyright

This book is printed on acid-free paper.

Copyright © 1997 by Academic Press

All rights reserved.

No part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopy, recording, or any information storage and retrieval system, without permission in writing from the publisher.

ACADEMIC PRESS, INC.

525 B Street, Suite 1900, San Diego, CA 92101-4495, USA

1300 Boylston Street, Chestnut Hill, MA 02167, USA

http://www.apnet.com

ACADEMIC PRESS LIMITED

24–28 Oval Road, London NW 1 7DX, UK

http://www.hbuk.co.uk/ap/

Library of Congress Cataloging-in-Publication Data

Schechter, Eric, 1950–

Handbook of analysis and its foundations / Eric Schechter.

p. cm.

Includes bibliographical references and index.

ISBN 0-12-622760-8 (alk. paper)

1. Mathematical analysis. I. Title.

QA300.S339 1997

515—dc20 96-32226

CIP

Printed in the United States of America

96 97 98 99 00 IP 9 8 7 6 5 4 3 2 1

Inside Front Cover

In dealing with mathematical problems, specialization plays, as I believe, a still more important part than generalization. Perhaps in most cases where we seek in vain the answer to a question, the cause of the failure lies in the fact that problems simpler and easier than the one in hand have been either not at all or incompletely solved. All depends, then, on finding out these easier problems, and on solving them by means of devices as perfect as possible and of concepts capable of generalization. – David Hilbert

Logic sometimes makes monsters. During half a century we have seen the rise of a crowd of bizarre functions which seem to try to resemble as little as possible the honest functions which serve some purpose. No longer continuity, or perhaps continuity but no derivatives, etc. Nay, more: from the logical point of view, it is these strange functions which are the most general. Those which one meets without seeking, no longer appear except as a particular case. – Henri Poincard

Mathematics belongs to man, not to God. We are not interested in properties of the positive integers that have no descriptive meaning for finite man. When a man proves a positive integer to exist, he should show how to find it. If God has mathematics of his own that needs to be done, let him do it himself. – Errett Bishop

He considered, perhaps in his moments of less lucidity, that it is possible to achieve happiness on earth when it is not very hot, and this idea made him a little confused. He liked to wander through metaphysical obstacle courses. That was what he was doing when he used to sit in the bedroom every morning with the door ajar, his eyes closed and his muscles tensed. However, he himself did not realize that he had become so subtle in his thinking that for at least three years in his meditative moments he was no longer thinking about anything. – Gabriel García-Márquez (novelist)

Preface

ABOUT THE CHOICE OF TOPICS

Handbook of Analysis and its Foundations — hereafter abbreviated HAF — is a self-study guide, intended for advanced undergraduates or beginning graduate students in mathematics. It will also be useful as a reference tool for more advanced mathematicians. HAF surveys analysis and related topics, with particular attention to existence proofs.

HAF progresses from elementary notions — sets, functions, products of sets — through intermediate topics — uniform completions, Tychonov’s Theorem — all the way to a few advanced results — the Eberlein-Smulian-Grothendieck Theorem, the Crandall-Liggett Theorem, and others. The book is self-contained and thus is well suited for self-directed study. It will help to compensate for the differences between students who, coming into a single graduate class from different undergraduate schools, have different backgrounds. I believe that the reading of part or all of this book would be a good project for the summer vacation before one begins graduate school in mathematics. At least, this is the book I wish I had had before I began my graduate studies.

HAF introduces and shows the connections between many topics that are customarily taught separately in greater depth:

set theory, metric spaces, abstract algebra, formal logic, general topology, real analysis, and linear and nonlinear functional analysis, plus a small amount of Baire category theory, Mac Lane-Eilenberg category theory, nonstandard analysis, and differential equations.

Included in these customary topics are the usual nonconstructive proofs of existence of pathological objects. Unlike most analysis books, however, HAF also includes some chapters on set theory and logic, to explain why many of those classical pathological objects are presented without examples.

HAF contains the most fundamental parts of an entire shelf of conventional textbooks. In his automathography, Halmos [1985] said that one good way to learn a lot of mathematics is by reading the first chapters of many books. I have tried to improve upon that collection of first chapters by eliminating the overlap between separate books, adhering to consistent notation, and inserting frequent cross-referencing between the different topics. HAF’s integrated approach shows connections between topics and thus partially counteracts the fragmentation into specialized little bits that has become commonplace in mathematics in recent decades. HAF’s integrated approach also supports the development of interdisciplinary topics, such as the intangibles discussed later in this preface.

The content is biased toward the interests of analysts. For instance, our treatment of algebra devotes much attention to convexity but little attention to finite or noncommutative groups; our treatment of general topology emphasizes distances and meager sets but omits manifolds and homology. HAF will not transform the reader into a researcher in algebra, topology, or logic, but it will provide analysts with useful tools from those fields.

HAF includes a few hard analysis results: Clarkson’s Inequalities, the Kobayashi-Rasmussen Inequalities, maximal inequalities for martingales and for Lebesgue measure, etc. However, the book leans more toward soft analysis — i.e., existence theorems and other qualitative results. Preference is given to theorems that have short or elegant or intuitive proofs and that mesh well with the main themes of the book. A few long proofs — e.g., Brouwer’s Theorem, James’s Theorem — are included when they are sufficiently important for the themes of the book.

As much as possible, I have tried to make this book current. Most mathematical papers published each year are on advanced and specialized material, not appropriate for an introductory work. Only occasionally does a paper strengthen, simplify, or clarify some basic, classical ideas. I have combed the literature for these insightful papers as well as I could, but some of them are not well known; that is evident from their infrequent mentions in the Science Citation Index. Following are a few of HAF’s unusual features:

• A thorough introduction to filters in Chapters 5 and 6, and nets in Chapter 7. Those tools are used extensively in later chapters. Included are ideas of Aarnes and Andenæs [1972] on the interchangeability of subnets and superfilters, making available the advantages of both theories of convergence. Also included, in 15.10, is Gherman’s [1980] characterization of topological convergences, which simplifies slightly the classic characterization of Kelley [1955/1975].

• an introduction to symmetric and preregular spaces, filling the conceptual gaps that are left in most introductions to T0, T1, T2, and T3 spaces — see the table in 16.1.

• a unified treatment of topological spaces, uniform spaces, topological Abelian groups, topological vector spaces, locally convex spaces, FreAchet spaces, Banach spaces, and Banach lattices, explaining these spaces in terms of increasingly specialized kinds of distances — see the table in 26.1.

• converses to Banach’s Contraction Fixed Point Theorem, due to Bessaga [1959] and Meyers [1967], in Chapter 19. These converses show that, although Banach’s theorem is quite easy to prove, a longer proof cannot yield stronger results.

• the Brouwer Fixed Point Theorem, proved via van Maaren’s geometry-free version of Sperner’s Lemma. This approach is particularly intuitive and elementary in that it involves neither Jacobians nor triangulations. It decomposes the proof of Brouwer’s Theorem into a purely combinatorial argument (in 3.28) and a compactness argument (in 27.19).

• introductions to both the Lebesgue and Henstock integrals and a proof of their equivalence in Chapter 24. (More precisely, a Banach-space-valued function is Lebesgue integrable if and only if it is almost separably valued and absolutely Henstock integrable.)

• pathological examples due to Nedoma, Kottman, Gordon, DieudonneA, and others, which illustrate very vividly some of the differences between n and infinite-dimensional Banach spaces.

• an introduction to set theory, including the most interesting equivalents of the Axiom of Choice, Dependent Choice, the Ultrafilter Principle, and the Hahn-Banach Theorem. (For lists of equivalents of these principles, see the index.)

• an introduction to formal logic following the substitution rules of Rasiowa and Sikorski [1963], which are simpler and — in this author’s opinion — more natural than the substitution rules used in most logic textbooks. This is discussed in 14.20.

• a discussion of model theory and consistency results, including a summary of some results of Solovay, Pincus, Shelah, et al. Those results can be used to prove the nonconstructibility of many classical pathological objects of analysis; see especially the discussions in 14.76 and 14.77.

• Neumann’s [1985] nonlinear Closed Graph Theorem.

• the automatic continuity theorems of Garnir [1974] and Wright [1977]. These results are similar to Neumann’s, but instead of assuming a closed graph, they replace conventional set theory with ZF + DC + BP. Their result explains in part why a Banach space in applied math has a usual norm; see 14.77.

In compiling this book I have acted primarily as a reporter, not an inventor or discoverer. Nearly all the theorems and proofs in HAF can be found in earlier books or in research journal articles — but in many cases those books or articles are hard to find or hard to read. This book’s goal is to enhance classical results by modernizing the exposition, arranging separate topics into a unified whole, and occasionally incorporating some recent developments.

I have tried to give credit where it is due, but that is sometimes difficult or impossible. Historical inaccuracies tend to propagate through the literature. I have tried to weed out the inaccuracies by reading widely, but I’m sure I have not caught them all. Moreover, I have not always distinguished between primary and secondary sources. In many cases I have cited a textbook or other secondary source, to give credit for an exposition that I have modified in the present work.

EXISTENCE, EXAMPLES, AND INTANGIBLES

Most existence proofs use either compactness, completeness, or the Axiom of Choice; those topics receive extra attention in this book. (In fact, Choice, Completeness, Compactness was the title of an earlier, prepublication version of this book; papers that mention that title are actually citing this book.) Although those three approaches to existence are usually quite different, they are not entirely unrelated – AC has many equivalent forms, some of which are concerned with compactness or completeness (see 17.16 and 19.13).

The term foundations has two meanings; both are intended in the title of this book:

(i) In nonmathematical, everyday English, foundations refers to any basic or elementary or prerequisite material. For instance, this book contains much elementary set theory, algebra, and topology. Those subjects are not part of analysis, but are prerequisites for some parts of analysis.

(ii) Foundations also has a more specialized and technical meaning. It refers to more advanced topics in set theory (such as the Axiom of Choice) and to formal logic. Many mathematicians consider these topics to be the basis for all of mathematics.

Conventional analysis books include only a page or so concerning (ii); this book contains much more. We are led to (ii) when we look for examples of pathological objects.

Students and researchers need examples; it is a basic precept of pedagogy that every abstract idea should be accompanied by one or more concrete examples. Therefore, when I began writing this book (originally a conventional analysis book), I resolved to give examples of everything. However, as I searched through the literature, I was unable to find explicit examples of several important pathological objects, which I now call intangibles:

• finitely additive probabilities that are not countably additive,

• elements of ( ∞)*\ 1 (a customary corollary of the Hahn-Banach Theorem),

• universal nets that are not eventually constant,

• free ultrafilters (used very freely in nonstandard analysis!),

• well orderings for ,

• inequivalent complete norms on a vector space,

etc. In analysis books it has been customary to prove the existence of these and other pathological objects without constructing any explicit examples, without explaining the omission of examples, and without even mentioning that anything has been omitted. Typically, the student does not consciously notice the omission, but is left with a vague uneasiness about these unillustrated objects that are so difficult to visualize.

I could not understand the dearth of examples until I accidentally ventured beyond the traditional confines of analysis. I was surprised to learn that the examples of these mysterious objects are omitted from the literature because they must be omitted: Although the objects exist, it can also be proved that explicit constructions do not exist. That may sound paradoxical, but it merely reflects a peculiarity in our language: The customary requirements for an explicit construction are more stringent than the customary requirements for an existence proof. In an existence proof we are permitted to postulate arbitrary choices, but in an explicit construction we are expected to make choices in an algorithmic fashion. (To make this observation more precise requires some definitions, which are given in 14.76 and 14.77.)

Though existence without examples has puzzled some analysts, the relevant concepts have been a part of logic for many years. The nonconstructive nature of the Axiom of Choice was controversial when set theory was born about a century ago, but our understanding and acceptance of it has gradually grown. An account of its history is given by Moore [1982]. It is now easy to observe that nonconstructive techniques are used in many of the classical existence proofs for pathological objects of analysis. It can also be shown, though less easily, that many of those existence theorems cannot be proved by other, constructive techniques. Thus, the pathological objects in question are inherently unconstructible.

The paradox of existence without examples has become a part of the logicians’ folklore, which is not easily accessible to nonlogicians. Most modern books and papers on logic are written in a specialized, technical language that is unfamiliar and nonintuitive to outsiders: Symbols are used where other mathematicians are accustomed to seeing words, and distinctions are made which other mathematicians are accustomed to blurring — e.g., the distinction between first-order and higher-order languages. Moreover, those books and papers of logic generally do not focus on the intangibles of analysis.

On the other hand, analysis books and papers invoke nonconstructive principles like magical incantations, without much accompanying explanation and — in some cases — without much understanding. One recent analysis book asserts that analysts would gain little from questioning the Axiom of Choice. I disagree. The present work was motivated in part by my feeling that students deserve a more honest explanation of some of the non-examples of analysis — especially of some of the consequences of the Hahn-Banach Theorem. When we cannot construct an explicit example, we should say so. The student who cannot visualize some object should be reassured that no one else can visualize it either. Because examples are so important in the learning process, the lack of examples should be discussed at least briefly when that lack is first encountered; it should not be postponed until some more advanced course or ignored altogether.

Though most of HAF relies only on conventional reasoning — i.e., the kind of set theory and logic that most mathematicians use without noticing they are using it — we come to a better understanding of the idiosyncrasies of conventional reasoning by contrasting it with unconventional systems, such as ZF + DC + BP or Bishop’s constructivism. HAF explains the relevant foundational concepts in brief, informal, intuitive terms that should be easily understood by analysts and other nonlogicians.

To better understand the role played by the Axiom of Choice, we shall keep track of its uses and the uses of certain weakened forms of AC, especially

the Principle of Dependent Choices (DC), which is constructive and is equivalent to several principles about complete metric spaces;

the Ultrafilter Principle (UF), which is nonconstructive and is equivalent to the Completeness and Compactness Principles of logic, as well as dozens of other important principles involving topological compactness; and

the Hahn-Banach Theorem (HB), also nonconstructive, which has many important equivalent forms in functional analysis.

Most analysts are not accustomed to viewing HB as a weakened form of AC, but that viewpoint makes the Hahn-Banach Theorem’s nonconstructive nature much easier to understand.

This book’s sketch of logic omits many proofs and even some definitions. It is intended not to make the reader into a logician, but only to show analysts the relevance of some parts of logic. The introduction to foundations for analysts is HAF’s most unusual feature, but it is not an overriding feature — it takes up only a small portion of the book and can be skipped over by mathematicians who have picked up this book for its treatment of nonfoundational topics such as nets, F-spaces, or integration.

ABSTRACT VERSUS CONCRETE

I have attempted to present each set of ideas at a natural level of generality and abstraction – i.e., a level that conveys the ideas in a simple form and permits several examples and applications. Of course, the level of generality of any part of the book is partly dictated by the needs of later parts of the book.

Usually, I lean toward more abstract and general approaches when they are available. By omitting unnecessary, irrelevant, or distracting hypotheses, we trim a concept down to reveal its essential parts. In many cases, omitting unnecessary hypotheses does not lengthen a proof, and it may make the proof easier to understand because the reader’s attention is then focused on the few possible lines of reasoning that still remain available. For instance, every metric space can be embedded isometrically in a Banach space (see 22.14), but the more concrete setting of Banach spaces does not improve our understanding of metric space results such as the Contraction Fixed Point Theorem in 19.39.

Here is another example of my preference for abstraction: Some textbooks build Hausdorffness into their definition of uniform space or topological vector space or locally convex space because most spaces used in applications are in fact Hausdorff. This may shorten the statements of several theorems by a word or two, but it does not shorten the proofs of those theorems. Moreover, it may confuse beginners by entangling concepts that are not inherently related: The basic ideas of Hausdorff spaces are independent from the other basic ideas of uniform spaces, topological spaces, and locally convex spaces; neither set of ideas actually requires the other. In HAF, Hausdorffness is a separate property; it is not built into our definitions of those other spaces. Our not-necessarily-Hausdorff approach has several benefits, of which the greatest probably is this:

The weak topology of an infinite-dimensional Banach space is an important nonmetrizable Hausdorff topology that is best explained as the supremum of a collection of pseudometrizable, non-Hausdorff topologies.

(If the reader is accustomed to working only in Hausdorff spaces, HAF’s not-necessarily-Hausdorff approach may take a little getting used to, but only a little. Mostly, one replaces metric with pseudometric or with the neutral notion of distance; one replaces the limit with a limit or with the neutral notion of converges to.)

However, a more general approach to a topic is not necessarily a simpler approach. Every idea in mathematics can be made more general and more abstract by making the hypotheses weaker and more complicated and by introducing more definitions, but I have tried to avoid the weakly upper hemisemidemicontinuous quasipseudospaces of baroque mathematics. It is unavoidable that the beginning graduate student of mathematics must wade through a large collection of new definitions, but that collection should not be made larger than necessary. Thus we sometimes accept slightly stronger hypotheses for a theorem in order to avoid introducing more definitions. Of course, ultimately the difference between important distinctions and excessive hair-splitting is a matter of an individual mathematician’s own personal taste.

Converses to main implications are included in HAF whenever this can be managed conveniently, as well as in a few inconvenient cases that I deemed sufficiently important. Lists of dissimilar but equivalent definitions are collected into one long definintion-and-theorem, even though that one theorem may have a painfully long proof. The single portmanteau theorem is convenient for reference, and moreover it clearly displays the importance of a concept. For instance, the notion of ultrabarrelled spaces seemed too advanced and specialized for this book until I saw the long list of dissimilar but equivalent definitions that now appears in 27.26. To prevent confusion, I have called the student’s attention to contrasts between similar but inequivalent concepts, either by juxtaposing them (as in the case of barrels and ultrabarrels) or by including cross-referencing remarks (as in the case of Bishop’s constructivism and Godel’s constructivism).

Although the content is chosen for analysts, the writing style has been influenced by algebraists. Whenever possible, I have made degenerate objects such as the empty set into a special case of a rule, rather than an exception to the rule. For instance, in this book and in algebra books, {S : S ⊆ X} is an improper filter on X, though it is not a filter at all according to the definition used by many books on general topology.

ORDER OF TOPICS

I have followed a Bourbaki-like order of topics, first introducing simple fundamentals and later building upon them to develop more specialized ideas. The topics are ordered to suit pedagogy rather than to emphasize applications. For instance, convexity is commonly introduced in functional analysis courses in the setting of Banach spaces or topological vector spaces, but I have found it expedient to introduce convexity as a purely algebraic notion, and then add topological considerations much later in the book. Most topological vector spaces used in applications are locally convex, but HAF first studies topological vector spaces without the additional assumption of local convexity.

Topics covered within a single chapter are closely related to each other. However, in many cases the end of a chapter covers more advanced and specialized material that can be postponed; it will not be needed until much later in the book, if at all. Most of Part C (on topological and uniform spaces) can be read without Part B (logic and algebra). However, most readers should skim through Chapters 5, 6, and 7. Those chapters introduce filters and nets — tools that are used more extensively in this book than in most analysis books.

I have felt justified in violating logical sequencing in one important instance. The real number system is, in some sense, the foundation of analysis, so it must be used in examples quite early in the book. Examples given in early chapters assume an informal understanding of the real numbers, such as might be acquired in calculus and other early undergraduate courses. A more precise definition of the reals is neither needed nor attainable until Chapter 10. Much conceptual machinery must be built before we can understand and prove a statement such as this one:

There exists a Dedekind complete, chain ordered field, called the real numbers. It is unique up to isomorphism if we use the conventional reasoning methods of analysts. (It is not unique if we restrict our reasoning methods to first-order languages and permit the use of nonstandard models.)

The existence and uniqueness of the complete ordered field justify the usual definition of . I am surprised that these algebraic results are not proved (or even mentioned!) in many introductory textbooks on analysis.

A traditional course on measure and integration would correspond roughly to part of Chapter 11, all of Chapter 21, and parts of Chapters 22, 25 and 29. Integration theory is commonly introduced separately from functional analysis, but I have mixed the two topics together because I feel that each supports the other in essential ways. All of the usual definitions of the Lebesgue space L¹[0, 1] (e.g., in 19.38, 22.28, or 24.36) are quite involved; these definitions cannot be properly appreciated without some of the abstract theory of completions or Banach spaces or convergent nets. Conversely, an introduction to Banach spaces is narrow or distorted if it omits or postpones the rather important example of Lp spaces; the remaining elementary examples of Banach spaces are not diverse enough to give a proper feel for the subject.

HOW TO USE THIS BOOK

Because students’ backgrounds differ greatly, I have tried to assume very few prerequisites. The book is intended for students who have finished calculus plus at least four other college math courses. HAF will rely on those four additional courses, not for specific content, but only for mathematical maturity – i.e., for the student’s ability to learn new material at a certain pace and a certain level of abstraction, and to fill in a few omitted details to make an exercise into a proof. Students with that amount of preparation will find HAF self-contained; they will not need to refer to other books to read this one. Students with sufficient mathematical maturity may not even need to refer to their college calculus textbooks; Chapters 24 and 25 reintroduce calculus in the more general setting of Banach spaces. Proofs are included, or at least sketched, for all the main results of this book except a few consistency results of formal logic. For those consistency results we give references in lieu of proofs, but the conclusions are explained in sufficient detail to make them clear to beginners.

Parts of HAF might be used as a classroom textbook, but HAF was written primarily for individual use. My intended reader will skip back and forth from one part of the book to another; different readers will follow different paths through the book. The reader should begin by skimming the table of contents to get acquainted with the ordering of topics. To facilitate skipping around in the book, I have included a large index and many cross-referencing remarks. Newly defined terms are generally given in boldface to make them easy to find. These definitions are followed by alternate terminology in italics if the literature uses other terms for the same concept or by cautionary remarks if the literature also uses the same term for other concepts. The first few pages of the first chapter introduce many of the symbols and typographical conventions used throughout the book; the index ends with a list of symbols. A list of charts, tables, diagrams, and figures is included in the index under charts.

Mathematics textbooks usually postpone exercises until the end of each subchapter or each chapter, but HAF mixes exercises into the main text. In fact, HAF does not always distinguish sharply between discussions, theorems, examples, and exercises. All such assertions are true statements, with varying degrees of importance, generality, or difficulty, and with varying amounts of hints provided. Every student knows that reading through any proof in any math book is a challenge, whether that proof is marked exercise or not. Some computations and deductions are easier or more instructive to do than to watch, so for brevity I have intentionally given some proofs as sketches. All the exercises are actually part of the text; most of them will serve as essential examples or as steps in proofs of later theorems. Thus, in each chapter that is studied, the reader should work through, or at least READ through, every exercise; no exercise should be skipped.

ACKNOWLEDGMENTS

I am especially grateful to Isidore Fleischer, Mai Gehrke, Paul Howard, and Constantine Tsinakis, who helped with innumerable questions about algebra and logic. I am also grateful to many other mathematicians who helped or tried to help with many different questions: Richard Ball, Howard Becker, Lamar Bentley, Dan Biles, Andreas Blass, Douglas Bridges, Norbert Brunner, Gerard Buskes, Chris Ciesielski, John Cook, Matthew Foreman, Doug Hardin, Peter Johnstone, Bjarni Jonsson, William Julian, Keith Kearnes, Darrell Kent, Menachem Kojman, Ralph Kopperman, Wilhelmus Luxemburg, Hans van Maaren, Roman Manka, Peter Massopust, Ralph McKenzie, Charles Megibben, Norm Megill, Michael Mihalik, Zuhair Nashed, Neil Nelson, Michael Neumann, Jeffrey Norden, Simeon Reich, Fred Richman, Saharon Shelah, Stephen Simons, Steve Tschantz, Stan Wagon, and others too numerous to list here. I am also grateful to many students who read through earlier versions of parts of this book. Of course, any mistakes that remain in this book are my own.

This work was supported in part by a Summer Award from the Vanderbilt University Research Council. I would also like to thank John Cook, Mark Ellingham, Martin Fryd, Bob Messer, Ruby Moore, Steve Tschantz, John Williams, and others for their help with TEX. This book was composed using several different computers and wordprocessors. It was typeset using LATEX, with some fonts and symbols imported from AMS-TEX.

I am also grateful to my family for their support of this project.

TO CONTACT ME

I’ve surveyed the literature as well as I could, but it’s enormous; I’m sure there is much that I’ve overlooked. I would be grateful for comments from readers, particularly regarding errors or other suggested alterations for a possible later edition. I will post the errata and other insights on the book’s World Wide Web page on the internet.

Eric Schechter, August 16, 1996

http://math.vanderbilt.edu/~schectex/ccc/

Part A

SETS AND ORDERINGS

Chapter 1

Sets

MATHEMATICAL LANGUAGE AND INFORMAL LOGIC

1.1. A few typographical conventions. Certain kinds of mathematical objects are most often represented by certain kinds of letters. For instance, mathematicians often represent a point by "x and a function by f," and very seldom the other way around. This book will usually adhere to the following guidelines, which are consistent with much (but not all!) of the literature of algebra, topology, and analysis. The reader is cautioned that there is no standard usage, in the literature or even in this book. The guidelines in the following list will be helpful, but the guidelines will have exceptions (which should be clear from the context). There is even some overlap between the categories listed above. For instance, in atomless set theory, discussed in 1.46, all sets are sets of sets.

1.2. All letters are variables, but some letters are more variable than others (as George Orwell might have put it). Every high school student has understood at least one example of this:

Here the letters a,b,c are treated as real constants, but they can be any real constants; they vary only slightly less than x does. Usually it should be clear from the context just which letters are varying more than others.

1.3. Notes on and and "or. Although mathematicians base their language on English or other natural" languages, mathematicians alter the language slightly to make it more precise or to make it fit their purposes better. Some of the differences between English and mathematics may confuse the beginner.

For instance, there are two different meanings for the English word or:

Latin distinguishes between these two meanings by using two different words: "vel and aut;" see Rosser [1953/1978]. In everyday English, the term or is ambiguous; it could have either meaning. For clarification in English, vel is sometimes called and/or, and aut is sometimes called either/or. In mathematics, or generally means vel, unless specified otherwise.

Undergraduate mathematics students sometimes confuse and and or in the following fashion: What is the solution set of x² − 4x + 3 > 0, in the real line? It is

Thus, the appropriate word is or. However, some calculus students write the solution as "x < 1 and x > 3, by which they mean the points x that satisfy x < 1, and also the points x that satisfy x > 3 — thus they are using and" for ∪ (union). Though such students may think that they know what they mean, this usage is not standard in mathematics and should be discontinued by students who wish to proceed in higher mathematics.

Another word for or is disjunction; the most commonly used symbol for it is ∨. Another word for and is conjunction; the most commonly used symbol for it is ∧. However, we shall use ⨆ and for or and and, in order to reserve the symbols ∨ and ∧ for use in some related lattices.

We shall use "not-A or ¬A as abbreviations for the statement that statement A is not true;" some mathematicians use other symbols such as ∼ A. The symbol ¬, meaning not, is also called negation. In conventional (ordinary) logic, used throughout most of this book, ¬¬A = A; that is, not-not-A is equal to A. That equality fails in constructivist or intuitionist logic, which is discussed very briefly in Chapters 6 and 13.

1.4. The statement "AimpliesB will sometimes be abbreviated as A ⇒ B or A → B; the latter expression will be used in our chapter on logic. Either of these expressions means ifA is true thenB is true — or more precisely, whenever A is true, then B is also true. The usage of if … then" in mathematics differs from the usage in, English, because the mathematical statement A ⇒ B makes no prediction about B in the case where A is false. For instance, in everyday English the statement If it rains, then I will take my umbrella is ambiguous — it could have either of the following meanings:

(i) If it rains, then I will take my umbrella. If it doesn’t rain, then I won’t take my umbrella.

(ii) If it rains, then I will take my umbrella. If it doesn’t rain, then I might or might not take my umbrella.

In mathematics, however, (ii) is the only customary interpretation of if … then.

The mathematicians’ implication also differs from the nonmathematicians’ implication in this respect: we may have A ⇒ B even if A and B are not causally related. For instance, if ice is hot then grass is green is true in mathematics, but it is nonsense in ordinary English, since there is no apparent connection between the temperature of ice and the color of grass. The mathematicians’ implication is sometimes referred to as material implication, to distinguish it from certain other kinds of implications not commonly used in mathematics but sometimes studied by philosophers and specialized logicians.

The converse of the statement "A ⇒ B is the statement B ⇒ A." These two statements are not equivalent; the beginner must be careful not to confuse them. For instance, "x = 3 implies x is a prime number, but x is a prime number does not imply x = 3."

The statement "A if and only if B may be abbreviated AiffB; it is also written A ⇔ B." This statement means that both A ⇒ B and the converse implication B ⇒ A are true.

Statement A is stronger than statement B if A ⇒ B; then we may say B is weaker than A. More generally, a property P of objects is stronger than a property Q if every object that has property P also must have property Q — i.e., if the statement "X has property P is stronger than the statement X has property Q. (A related but slightly different meaning of stronger than" is introduced in 9.4.) The mathematical usage of the terms stronger and weaker (and of other comparative adjectives such as coarser, finer, higher, lower) differs from the common nonmathematical English usage in this important respect: In English, two objects cannot be stronger than each other, but in mathematics they can. Thus, when A ⇔ B, each statement is stronger than the other. In particular, a statement is always stronger than itself. To say that

we could say that A is strictly stronger than B. For instance, the property of being equal to 3 is strictly stronger than the property of being a prime number.

In general, if … then is quite different from if and only if. However, in mathematical definitions the words and only if generally are omitted and are understood implicitly, particularly when the defined word or phrase is displayed in boldface or italics. For instance, in our earlier sentence

Statement A is stronger than statement B if A ⇒ B; then we may say B is weaker than A.

the if is really understood to be if and only if.

1.5. When A and B are variables taking the values true or false, then an expression such as "A and B is a function of those variables — that is, the value of A and B" depends on the values of A and B. The truth table below shows how several functions of A and B depend on the values of A and B. In the table, T and F stand for true and false, respectively.

If a statement A is known to be always false, then the statement "A ⇒ B" is true, regardless of what we know or do not know about B; under these circumstances we may say that the implication "A ⇒ B" is vacuously true, or trivially true. The term trivially true can also be used to describe the implication "A ⇒ B" if B is known to be always true, since in that case the validity of A need not be considered.

1.6. Exercises.

a. The statement "A ⇒ B is equivalent to the statement B or not-A." Explain.

b. The contrapositive of "A ⇒ B is the statement not-B ⇒ not-A." Show that an implication and its contrapositive are equivalent. We shall use them interchangeably.

c. (De Morgan’s Laws for logic.) Explain:

1.7. Duality arguments. Some concepts in mathematics occur in pairs; each member of the pair is said to be dual to the other. A few examples are listed in the table below; these examples and others are developed in more detail in later chapters. The statements about these concepts occur in pairs. In some cases, one of the two statements is preferred, because it is more relevant to applications or is simpler in appearance.

Generally there is a simple and mechanical method for transforming a statement into its dual statement and for transforming the proof of a statement into the proof of the dual statement. For instance, De Morgan’s Laws for logic (given in 1.6.c) can be used to convert between ands and ors, by inserting a few nots. Other such conversion rules will be given in later chapters. In some cases, for brevity, we state and/or prove only one of the two statements in the pair. The other statement is left unstated and/or unproved, but the reader should be able to fill in the missing details without any difficulty.

1.8. On parsing strings of symbols. In this book, we generally read set-theoretical operations (∩, ∪, , etc.) first, then set-theoretical relations (=, ⊆, , etc.), then logical relations between statements. For instance,

(*)

should be interpreted as

Generally we omit the parentheses, but we may sometimes use extra spacing to make the correct interpretation more obvious:

We emphasize that this order of precedence depends on the context — i.e., the present book is concerned with abstract analysis. In a different context, the expression (*) could be read in an entirely different order. For instance, in some books on logic, ∩ means and and ⫆ means is implied by. Hence all four of the symbols =, ⇔, ∩, and ⫆ are binary operations on statements — i.e., they are operators with the syntax that if P and Q are statements, then P Q is a statement. Therefore, in a logic book, the displayed equation (*) could make sense with any arrangement of parentheses, and it would have different meanings with different arrangements of parentheses. In that context, (*) would be highly ambiguous; some parentheses would be needed for clarification.

1.9. Proof by contradiction is a nonconstructive technique of logic, so widely used in mainstream mathematics that it generally goes unremarked. It may be confusing to beginning mathematicians who have never seen it explained. The technique is this:

If we wish to prove A ⇒ B, we can assume the truth of both A and not-B. From those two assumptions we deduce a contradiction; the contradiction demonstrates that indeed A ⇒ B.

The justification of this technique is 1.6.a.

Proof by contradiction has this advantage: We work from two assumptions (both A and not-B) rather than just the one assumption of A; thus we have more statements on which to build. Consequently, proofs by contradiction are often easier to discover than direct proofs.

Proofs by contradiction also have a couple of disadvantages:

• Proofs by contradiction are often harder to read than direct proofs because they are conceptually more complicated. Proofs by contradiction are conceptually complicated. A beginning student of mathematics may prefer to assume that A is true and try to discover what else is then true — a sort of one-directional approach. But a proof by contradiction works simultaneously in two directions, mixing together statements (such as A and its consequences) that we take to be true with statements (such as not-B) that we temporarily pretend are true but shall eventually decide are false. This scheme must seem diabolical, or at least amoral, to beginners: It is not concerned so much with what is true, but rather with what implies what.

• A proof by contradiction is often nonconstructive: It may prove the existence of some mathematical object without producing any explicit example of that object. For a very vivid example of this lack of examples, see 6.5. The availability or unavailability of explicit examples is one of the main themes of this book. A proof by contradiction may convince us that a statement is true, but it may not give us as much intuitive understanding of that statement as a direct proof would.

1.10. The phrase "we may assume" is often used in the literature in ways that may bewilder the novice. For instance, consider a proposition of this formml:

Proposition A. Let X be a mathematical object satisfying hypothesis H(X). Then X satisfies conclusion C(X).

A published proof of Proposition A might begin something like this:

(!) We may assume that X also satisfies property P(X).

The reasoning step (!) has several possible meanings; we shall describe three of them below. The simplest meaning of (!) would be that

(1) Hypothesis H(X) actually implies property P(X), by some reasoning that should be evident to a sufficiently advanced reader.

Readers who are not so advanced may spend many hours trying to fill in that reasoning. However, (!) may not mean (1) after all. Indeed, if (1) were true then (!) would probably be worded a bit differently — e.g., the proof might have begun by saying "We first observe that, obviously, H(X) ⇒ P(C)." A more likely meaning of (!) is this:

(2) H(X) and not-P(X) together imply C(X), by some reasoning that should be evident to the reader. Hence, in trying to prove H(X) ⇒ C(X), we may concentrate on the case where P(X) holds.

That is harder but still manageable. Alas, (!) has yet a third meaning, and this one is much too subtle for some beginners:

(3) The text will now give the details of a proof of a slightly easier proposition. After reading the proof provided for the easier proposition, the reader is expected to figure out the details of how to use that easier proposition to prove Proposition A. The easier proposition is as follows:

Proposition B. Let Y be a mathematical object satisfying hypotheses H(Y) and P(Y). Then Y satisfies conclusion C(Y).

The missing details might go as follows: Let any object X be given, satisfying hypothesis H(X) but not necessarily property P(X). By some clever method (which the reader must figure out), we now construct a collection of related objects Y1, Y2, Y3, …, with each Yk satisfying both hypothesis H(Yk) and property P(Yk). Then Proposition B is applicable to the Yk’s, and so we can draw conclusions C(Y1), C(Y2), C(Y3), …. By some clever method(which, again, the reader must figure out), we may then use that information to help us prove C(X).

In such an argument, object X does not necessarily satisfy P(X), despite the wording of statement (!). The effect of statement (!) is to discard the original object X, replace it with the new object Yk, and relabelYk to call it X now. Some other relabeling arguments will be discussed and used in 2.19, 7.21, and 16.5.

1.11. How much formalism do we need? It is not necessary to learn the definitions of noun and verb to become a fluent speaker of English (or any other natural language). One can learn the language quite well just by studying examples; this is the method by which toddlers learn their native tongue.

Similarly, most mathematicians use logic properly without ever knowing its formal rules. This book is intended for most mathematicians, and we shall discuss logic and formal set theory as little as possible. The few concepts from logic and set theory that we shall need will be developed briefly and informally. For a more complete and formal development, the interested reader is referred to more advanced and specialized books and papers.

Informal reasoning is not always reliable, in part because informal language is not always reliable. Natural languages (such as English) evolved to suit the mundane, ordinary, real world, but mathematicians often find themselves considering extraordinary ideas.

For instance, a self-referencing statement such as

This statement is false

cannot be true or false. (This is the simplest form of the Paradox of the Liar, also known as the Paradox of Epimenides.) Such statements do not arise in ordinary reality, but such statements show mathematicians a need for careful rules about language and reasoning.

The simplest way to deal with self-referencing statements is to simply prohibit them and avoid the confusion. We shall follow that policy in this book. However, we remark that self-referencing recently has been analyzed in a meaningful and useful way by Aczel [1988] and Barwise and Etchemendy [1987]. Such analyses are especially useful in the theory of computer programs. A computer program may operate on data files that are stored in memory; one of those files may be the program that is operating.

1.12. We should mention one more type of self-referencing before we leave the topic. The self-referencing in Epimenides’s Paradox is very direct: The word this in the sentence This sentence is false points directly to the sentence in which that word is located. But Quine’s Paradox, below, involves a more indirect type of self-referencing, which has some important uses in logic.

A typical sentence in English consists of a subject followed by a predicate. For instance, in each of the sentences

Jane is a girl.

Jane runs with the ball.

the subject is Jane and the predicate is the remainder of the sentence. The subject is some thing that is being discussed; the predicate says that the subject is something or does something.

Mathematicians often wish to discuss mathematical objects, so in a mathematics text the subject of a sentence can be a mathematical symbol or formula. For instance,

is a box symbol.

" " is a box symbol.

x is a variable.

x is a variable.

x = y is an equation.

are all acceptable sentences in a mathematics book or paper. Whether we include or omit the quotation marks is generally a matter of taste; our main rule is that the intended meaning should be clear. In this author’s opinion, the last example would become confusing if the quotation marks were omitted, but the quotation marks are optional in the other examples. (Of course, in a book or paper on logic, the quotation marks may have a more technical meaning, and then their use or omission is no longer a matter of taste.)

We shall now consider sentences that follow the format described above, but in these sentences the subject will be some phrase of the English language — i.e., a sentence fragment. Thus, we shall consider sentences that discuss certain sentence fragments. In each case, the sentence fragment will consist of a sentence whose subject has been omitted.

is a girl is a sentence fragment composed of three words.

runs with the ball is a sentence fragment composed of four words.

is a sentence fragment is a sentence fragment.

is composed of five words is composed of five words.

Each of those four sentences is true. The last two sentences have a peculiar structure: they consist of a sentence fragment in quotes, followed by the same sentence fragment without quotes, followed by a period. In Hofstadter [1979], the process of forming such a sentence from such a fragment is called quining. Thus, the last sentence displayed above is the result of starting from the fragment

is composed of five words

and then quining that fragment.

Now, Quine’s Paradox consists of the peculiar sentence

yields a falsehood when preceded by its quotation yields a falsehood when preceded by its quotation.

or, in Hofstadter’s terminology,

yields a falsehood when quined yields a falsehood when quined.

These sentences are paradoxical: they are false if true, and true if false. (Think about it for a moment.) These sentences do not involve direct self-referencing of the sort found in Epimenides’s Paradox; there is no this that points to itself. However, in either formulation, Quine’s peculiar sentence discusses another sentence that would be formed as the result of a quining. Just by coincidence (not really), the sentence being discussed happens to be identical to the sentence doing the discussing. Quine formed this paradox in order to explain Gödel’s Proof; see 14.62.

BASIC NOTATIONS FOR SETS

1.13. A set is a collection of objects. This is not really a definition, since we do not state what a collection is; we shall rely on the reader’s intuition about these terms. A more formal approach will be introduced in 1.44 and the sections thereafter.

Three common ways to specify a set are by listing the objects in the set, by specifying a larger set and a property that determines the subset in question, and by listing a parameter set and a way to form some object from each value of the parameter. For instance, the set of odd positive integers can be represented in any of these ways:

In the last expression, is used as a index set, or parameter set. (Some mathematicians would write that last expression as {2m + 1|m ∈ }, but this book will have too many other uses for vertical bars.)

The order of the elements of a set is not relevant, and repetitions are ignored; for instance, {1,2,3,4} = {4,3,1,2} = {1,2,3,1,4}. To emphasize this we may occasionally refer to a set as an unordered set to contrast it with ordered sets, such as those in 1.32. Two sets A and B are defined to be equal (as sets) if they contain the same elements — i.e., if they satisfy x ∈ A ⇔ x ∈ B.

Two mathematical objects may be equal as sets even though they have different additional structures associated with them. For instance, the real number system with its usual topology is different from the real number system with the discrete topology — i.e., these are different topological spaces. But these topological spaces are equal as sets, since they have the same members.

The term collection will usually mean the same thing as set, but occasionally collection may have the more general meaning of class, discussed in 1.44.

1.14. Here are the two most basic notions of sets:

x ∈ S is read as: xbelongs to S, or x is an element of S, or x is a member of S. It is occasionally written as S ∋ x.

A ⊆ B means x ∈ A ⇒ x ∈ B; that is, each element of A is also an element of B. It is read as: A is a subset of B, or B is a superset of A. It is also written as B ⫆ A.

Unfortunately, the terms include and contain are ambiguous. As they are commonly used in the mathematical literature,

either of the statements "UincludesV or UcontainsV can have either of the meanings U ∋ V or U ⫆ V.".

When the words include or contain are used, the reader must determine the intended meaning from context.

The statement "x is not an element of S" can be written x ∉ S; the statement "A is not a subset of B" is occasionally written as A B. When S ⊆ X and S ≠ X, we say S is a proper subset of X, or X is a proper superset of S; this is sometimes written S X or X S.

The symbols ⊂ and ⊃ are ambiguous: They are used for ⊆ and ⫆ by some mathematicians, and for and by other mathematicians. We shall not use ⊂ or ⊃ in this book.

1.15. Some sets of numbers. Numbers are the basis of what most analysts consider to be analysis. The list below shows some of the most commonly used sets of numbers.