Andrew Browder Mathematical Analysis An Introduction Pdf

• 9,281,071 books books
• 84,837,646 articles articles
• ZLibrary Home
• Home

Main Mathematical Analysis: An Introduction

Mathematical Analysis: An Introduction

Andrew Browder

How much do you like this book?

What's the quality of the file?

Download the book for quality assessment

What's the quality of the downloaded files?

Among the traditional purposes of such an introductory course is the training of a student in the conventions of pure mathematics: acquiring a feeling for what is considered a proof, and supplying literate written arguments to support mathematical propositions. To this extent, more than one proof is included for a theorem - where this is considered beneficial - so as to stimulate the students' reasoning for alternate approaches and ideas. The second half of this book, and consequently the second semester, covers differentiation and integration, as well as the connection between these concepts, as displayed in the general theorem of Stokes. Also included are some beautiful applications of this theory, such as Brouwer's fixed point theorem, and the Dirichlet principle for harmonic functions. Throughout, reference is made to earlier sections, so as to reinforce the main ideas by repetition. Unique in its applications to some topics not usually covered at this level.

Series:

Undergraduate Texts in Mathematics

The file will be sent to your email address. It may take up to 1-5 minutes before you receive it.

The file will be sent to your Kindle account. It may takes up to 1-5 minutes before you received it.

Please note: you need to verify every book you want to send to your Kindle. Check your mailbox for the verification email from Amazon Kindle.

Undergraduate Texts in Mathematics Anglin: Mathematics: A Concise Ebbinghaus/Flum/Thomas: History and Philosophy. Mathematical Logic. Second Reintings in Mathematics. edition. Anglin/Lamk: The Heritage of Edgar: Measure, Topology, and Thales. Fractal Geometry. Readings in Mathematics. Elaydi: Introduction to Difference Apostol: Introduction to Analytic Equations. Number Theory. Second edition. Fischer: Intermediate Real Analysis. Armstrong: Basic Topology. Flanigan/Kazdan: Calculus Two: Armstrong: Groups and Symmetry. Linear and Nonlinear Functions. Axlr: Linear Algebra Done Right. Second edition. Bak/Newman: Complex Analysis. Fleming: Functions of Several Banchoff/Wermer: Linear Algebra Variables. Second edition. Through Geometry. Second edition. Foulds: Combinatorial Optimization l]-b'lan: A First Course in Real for Undergraduates. Analysis. Foulds: Optimization Techniques: An Brmaud: An Introduction to Introduction. Probabilistic Modeling. Franklin: Methods of Mathematical Bressoud: Factorization and Economics. Primality Testing. Hairer/Wanner: Analysis by Its Bressoud: Second Year Calculus. History. Readings in Mathematics. Readings in Mathematics. Brlmm: Mathematical Halmos: Finite-Dimensional Vector Introduction to Linear Spaces. Second edition. Programming and Game Theory. Halmos: Naive Set Theory. Browder: Mathematical Analysis: An Hnmerlin/Hoffmann: Numerical Introduction. Mathematics. C.lbm-g: A Course in Modern Readings in Mathematics. Geometries. Iooss/Joseph: Elementary Stability ' Childs: A Concrete Introduction to and Bifurcation Theory. Second Higher Algebra. Second edition. edition. Chung: Elementary Probability Irainc: The Pleasures of Probability. Theory with Stochastic Processes. Readings in Mathematics. Third edition. James: Topological and Uniform Cox/Llttle/O'Shea: Ideals, Spaces. Varieties, and Algorithms. J'dnich: Linear Algebra. Croom: Bic Concepts of Algebraic J'dnich: Topology. Topoio. Kemeny]Snell: Finite Markov C,t]: Linear Algebra: An Chains. lntaxu-y Approach. Fourth Kinsey: ; Topology of Surfaces. edition. Kiambauer: Aspects of Calculus. I)rlin: The Joy of Sets: Lang: A First Course in Calculus. Fun of Contemporary Fifth edition. Set Time. Second edition. Lang: Calculus of Several Variables. C, eneral Topology. Third edition. l)ri Why Math? Lang: Introduction to Linear Algebra. (continued follon,,n(j ider l  Andrew Browder Mathematical Analysis An Introduction Springer  Provi RI 02912 USA E,dsr Board S. Axler F.W. Gehring P.R. Halmos of Department of Department of Mstim Mathematics Mathematics Michigan State University University of Michigan Santa Clara University F_amt Lansing, MI 48824 Ann Arbor, MI 48109 Santa Clara, CA 95053 USA USA USA With five illustrations. Mathematics Subject Ciamificatio (1991): 2601, 26Axx, 54Cxx, 28Axx, 58Cxx Library of Congreta Cataloging-in-Publication Data Browder, Andrew. Mathematical analysis: an introduction / Andrew Browder. p. cm. - (Undergraduate text in mathematics) Includes bibliographical references and index. ISBN 0-387-94614-4 (hardcover: alk. paper) 1. Mathematical analysis. I. Title. II. Series QA300.B727 1996 515-dc20 95-44877 Pri on acid-free paper. I 1996 Springer-Verlag New York, Inc. All right rerv. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer-Verlag New York, Inc., 175 Fifth Av- enue, New York, NY 10010, USA), except for brief excerpts in connection with reviews or holarly analysis. Ue in connection with any form of information storage and retrieval, electronic laptation, computer software, or by similar or dissimilar methodology now known or developed is forbidden. The ue of dcriptive names, trade names, trademarks, etc., in this publication, bven ff the former are not especially identified, is not to be taken as a sign that such names, a understood by the rade Marks and Merchandi Marks Act, may accordingly b amd frmly by toOone. Production manag by Robert Wexler; manufacturing supervised by Jacqui Ashri. Photocompom copy pmpml from.the author's files. Print and bound by R.R Donneli and Sons, Harrisonburg, VA. Printed in the United S of America. 987654321 ISBN 0-7-94614.4 Springer-Verlag New York Berlin Heidelberg  For Anna  Preface This is a textbook suitable for a year-long course in analysis at the ad- vanced undergraduate or possibly beginning-graduate level. It is intended for students with a strong background in calculus and linear algebra, and a strong motivation to learn mathematics for its own sake. At this stage of their education, such students are generally given a course in abstract algebra, and a course in analysis, which give the fundamentals of these two areas, as mathematicians today conceive them. Mathematics is now a subject splintered into many specialties and sub- specialties, but most of it can be placed roughly into three categories: al- gebra, geometry, and analysis. In fact, almost all mathematics done today is a mixture of algebra, geometry and analysis, and some of the most in- teresting results are obtained by the application of analysis to algebra, say, or geometry to analysis, in a fresh and surprising way. What then do these categories signify? Algebra is the mathematics that arises from the ancient experiences of addition and multiplication of whole numbers; it deals with the finite and discrete. Geometry is the mathematics that grows out of spatial experience it is concerned with shape and form, and with measur- ing, where algebra deals with counting. Analysis might be described as the mathematics that deals with the ideas of the infinite and the infinitesimal; more specifically, it is the word used to describe the great web of ideas that has grown in the last three centuries from the discovery of the differ- ential and integral calculus. Its basic arena is the system of real numbers, a mathematical construct which combines algebraic concepts of addition, multiplication, etc., with the geometric concept of a line, or continuum. There is no general agreement on what an introductory analysis course  viii Preface should include. I have chosen four major topics: the calculus of functions of one variable, treated with modern standards of rigor; an introduction to general topology, focusing on Euclidean space and spaces of functions; the general theory of integration, based on the concept of measure; and the calculus, differential and integral, for functions of several variables, with the inverse and implicit function theorems, and integration over manifolds. Inevitably, much time and effort go into giving definitions and proving technical propositions, building up the basic tools of analysis. I hope the reader will feel this machinery is justified by some of its products displayed here. The theorems of Dirichlet, Liouville, Weyl, Brouwer, and Riemann's Dirichlet principle for harmonic functions, for instance, should need no applications to be appreciated. (In fact, they have a great number of ap- plications.) An ideal book of mathematics might uphold the standard of economy of expression, but this one does not. The reader will find many repetitions here: where a result might have been proved once and subsequently referred to, I have on occasion simply given the old argument again. My justification is found in communications theory, which has shown mathematically that redundancy is the key to successful communication in a noisy channel. I have also on occasion given more than one proof for a single theorem; this is done not because two proofs are more convincing than one, but becau the second proof involves different ideas, which may be useful in some new context. I have included some brief notes, usually historical, at the end of each chapter. The history is all from secondary sources, and is not to be relied on too much, but it appears that many students find these indications of how things developed to be interesting. A student who wants to learn the material in the early chapters of this book from a historical perspective will find Bressoud's recent book [1] quite interesting. While this book is meant to be used for a year-long course, I myself have never managed to include everything here in such a course. A year and a haft might be reasonable, for students with no previous experience with rigorous analysis. In different years, I have omitted different topics, always regretfully. Every. topic treated here meets one of two tests: it is either something that everybody should know, or else it is just too beautiful to leave out. Nevertheless, life is short, and the academic year even shorter, and anyone who teaches with this book should plan on leaving something out. I expect that most teachers who use this book might also be tempted to include some topic that I have not treated, or develop further some theme that is touched on lightly here. Thoe students whose previous mathematical experience is mostly with calculus are in for some culture shock. They will notice that this book is only about 30% as large as their calculus text, and contains about one-tenth as many exercises. (So far, so good.) But it will quickly become clear that some of the problems are quite demanding; I believe that (certainly at this  Preface ix level) more is learned by spending hours, if necessary, on a few problems, sometimes a single problem, than in routinely dispatching a dozen exercises, all following the same pattern. I hope the reader is not discouraged by difficulty, but rewarded by difficulty overcome. This book consists of theorems, propositions, and lemmas (these words all mean the same thing), along with definitions and examples. Most of these are set off formally as Theorem, Proposition, etc., but some defini- tions, examples, md theorems are in fact sneaked into the text between the formally announced items. I have been persuaded to number the Theorems, Examples, Definitions, etc. by one sequence. Thus Example 4.4 refers to the fourth item in Chapter 4, where an item could be either a Theorem, Proposition, Lemma, Definition, or Example. It would have been more log- ical to have it refer to the fourth example in this chapter, but it would have made navigation more difficult. One of the important things that one learns in a course at this level is how to write a mathematical proof. It is quite difficult to prescribe what constitutes a proper proof. It should be a clear and compelling argument, that forces a reader (who has accepted previous theorems and understands the hypotheses) to accept its assertions. It should be concise, but not cryp- tic; it should be detailed, but not verbose. We learn to do it by imitating models. Here are two models from ancient Greece. Throughout this book, the symbol will mark the conclusion of a proof. Theorem. There are infinitely many primes. Proof. If p, p2,...,p, are primes, let N = pp2...p + 1. Then N is not divisible by any pj, j = 1,2,..., n, so either N is a prime, or N is divisible by some prime other than p,p2,...,p,. In either case, there are at least n + 1 primes. ] Note that this proof assumes a knowledge of what a prime number is, and a previously obtained result that every integer N > 1 is divisible by some prime. Note also that the last sentence of the proof, omitted above, might be either to the effect that the hypothesis that the set of all primes can be listed in a finite sequence p, P2,..., p, has led to a contradiction, or that we have given the recipe for finding a new prime for each natural number, so that the sequence 2, 3, 7, 43,..., can be extended indefiAtely. Theorem. The square on the htpotenuse of a right triangle is the sum of the squares on the two shorter sides. Proof. If the sides of the triangle are a, b, and c, with c the hypotenuse, then the square of side a + b can be dissected in two ways, as shown below. Removing the four copies of the triangle present in each dissection, the theorem follows. ] This is one of the rare occasions when I would accept a picture as a proof. (Having once bn shown the proof, by a carefully drawn diagram,  x Preface Figure 0.1. The Pythagorean Theorem. that every triangle is isosceles, I could never again believe that pictur.. don't lie.) In this argument, the picture is clear and convincing. By the way, there are few pictures in what follows, and they are all simple and hand- drawn, meant to serve as a guide to simple ideas that are (unfortunately but necessarily) being expressed in awkward or complicated notation. I would urge the readers (of this or any other mathematics) to make their own sketches at all times, preferably crude and schematic. Acknowlcdgments. It is impossible to list all the writers and individuals who have influenced me in the writing of this book, but for me the model of analysis textbooks at this level has always been Rudin's Principles of Mathematical Analysts [11]. The second half of this book (which was written first) was greatly influenced by Spivak's Calculus on Manifolds [13], the first clear and simple introduction to Stokes' theorem in its modern form. I was fortunate to read in manuscript Munkres' excellent book Analysis on Manifolds [10] while I was writing that earlier version, and profited froin it. Many students found typographical errors and other infelicities in the class notes which formed the first version of the first half of the book, and I want to thank especially Andrew Brecher, Greg Friedman, Ezra Miller, and Max Minzner for their detailed examination, and their suggestions for that part. Eva Kallin made many useful criticisms of an earlier version of the notes on which the second half of this book is based. I am gratefiJi to Xiang-Qian Chang, who read the entire manuscript, and pointed out a great number of rough places. The mistakes that remain are all my own. I would appreciate hearing bot them.  Contents Preface vii I Real Numbers 1 1.1 Sets, Relations, Functions ................... 1 1.2 Numbers ............................. 4 1.3 Infinite Sets ........................... 6 1.4 Incommensurability ...................... 8 1.5 Ordered Fields ......................... 10 1.6 Functions on R ......................... 16 1.7 Intervals in R .......................... 18 1.8 Aigebraic and Transcendental Numbers .......... . 20 1.9 Existence of R ......................... 21 1.10 Exercises ............................ 23 I. 11 Notc .............................. 25 2 Sequences and Series 28 2.1 Sequences ............................ 28 2.2 Continued Fractions ...................... 36 2.3 Infinite Series .......................... 39 2.4 Rearrangements of Series ................... 45 2.5 Unordered Series ....................... 47 2.6 Exercises ........................... 50 2.7 Notes .............................. 53  xii Contents 3 Continuous Functions on Intervals 55 3.1 Limits and Continuity ..................... 55 3.2 Two Fundamental Theorems ................. 59 3.3 Uniform Continuity ...................... �1 3.4 Sequences of Functions ..................... 62 3.5 The Exponential Function ................... 65 3.6 Trigonometric Functions .................... 66 3.7 Exercises ............................ 69 3.8 Notes .............................. 72 4 Differentiation 74 4.1 Derivatives ........................... 74 4.2 Derivatives of Some Elementary Functions .......... 76 4.3 Convex Functions ........................ 78 4.4 The Differential Calculus ................... 81 4.5 L'Hospital's Rule ........................ 86 4.6 Higher Order Derivatives ................... 88 4.7 Analytic Functions ....................... 90 4.8 Exercises ............................ 93 4.9 Notes .............................. 95 5 The Riemann Integral 98 5.1 Riemann Sums ......................... 98 5.2 E_tence Results ........................ 102 5.3 Properties of the Integral ................... 107 5.4 Fundamental Theorems of Calculus .............. 110 5.5 Integrating Sequences and Series ............... 113 5.6 lmpr6per Integrals ....................... 114 5.7 Exercises ............................ 115 5.8 Notes .............................. 121 Topology 123 6.1 Topological Spaces ....................... 123 6.2 Continuous Mappings ..................... 126 6.3 Metric Spaces .......................... 127 6.4 Constructing Topological Spaces ............... 131 6.5 Sequences ............................ 135 6.6 Compactness .......................... 140 6.7 Connectedness ......................... 147 6.8 Exercises ........................... 150 6.9 Notes .............................. 153 7 Function Spaces 155 7.1 The Weierstrass Polynomial Approximation Theorem .... 155 7.2 Lengths of Paths ........................ 159  Contents xiii 7.3 Folrier Series .......................... 161 7.4 Weyl's Theorem ........................ 170 7.5 Exercises ............................ 171 7.6 Notes .............................. 173 8 Differentiable Maps 175 8.1 Linear Algebra ......................... 176 8.2 Differentials ........................... 182 8.3 The Mean Value Theorem ................... 185 8.4 Partial Derivatives ....................... 186 8.5 Inverse and Implicit Functions ................ 191 8.6 Exercises ............................ 196 8.7 Notes .............................. 199 9 Measures 201 9.1 Additive Set Functions ..................... 202 9.2 Countable Additivity ...................... 204 9.3 Outer Measures ......................... 208 9.4 Constructing Measures ..................... 211 9.5 Metric Outer Measures ..................... 213 9.6 Measurable Sets ........................ 215 9.7 Exercises ............................ 219 9.8 Notes .............................. 221 10 Integration 223 10.1 Measurable Functions ..................... 223 10.2 Integration ........................... 226 10.3 Lebesgue and Riemann Integrals ............... 231 10.4 Inequalities for Integrals .................... 233 10.5 Uniqueness Theorems ..................... 237 10.6 Linear Transformat ions .................... 240 10.7 Smooth Transformations .................... 241 10.8 Multiple and Repeated Integrals ............... 244 10.9 Exercises ............................ 247 10.10Notes .............................. 251 11 Manifolds 253 11.1 Definitions ............................ 253 11.2 Constructing Manifolds .................... 258 11.3 Tangent Spaces ......................... 260 11.4 Orientation ........................... 262 11.5 Exercises ............................ 265 11.6 Notes .............................. 267 12 Multilinear Algebra 269  xiv Contents 12.1 Vectors and Tensors ...................... 269 12.2 Alternating Tensors ...................... 272 12.3 The Exterior Product ..................... 277 12.4 Change of Coordinates ..................... 280 12.5 Exercises ............................ 282 12.6 Notes .............................. 283 13 Differential Forms 285 13.1 Tensor Fields ......................... 285 13.2 The Calculus of Forms ..................... 13.3 Forms and Vector Fields .................... 288 13.4 Induced Mappings ....................... 29() 13.5 Closed and Exact Forms .................... 2!!1 13.6 Tensor Fields on Manifolds .................. 293 13.7 Integration of Forms in R" .................. 294 13.8 Exercises ............................ 295 13.9 Notes .............................. 296 14 Integration on Manifolds 297 14.1 Partitions of Unity ....................... 297 14.2 Integrating k-Forms ...................... 300 14.3 The Brouwer Fixed Point Theorem .............. 305 14.4 Integrating Functions on a Manifold ............. 307 14.5 Vector Analysis ......................... 312 14.6 Harmonic Functions ...................... 314 14.7 Exercises ............................ 318 14.8 Notes .............................. 321 Referen 323 Index 325  1 Real Numbers In this chapter, we describe the system of real numbers, deducing some of their esmntial properties from the axioms for a complete ordered field. Before doing so, we take a quick look at the ideas and notations of sets, relations, and functions, sketch the construction of the integers and the rational numbers (starting from the natural numbers), and indicate the need for a field larger than the rational numbers. At the end of the chapter, we sketch the proof of the existence and (essential) uniqueness of a complete ordered field. 1.1 Sets, Relations, Functions We assume no knowledge of formal set theory, but do assume familiarity with the basic notations and elementary calculations. Thus, x E A means that x is an element of A, A C B (also written B D A) means that x E B whenever x ( A. The sets A and B are equal if and only if A C B and B C A. For any Sets A, B, the intersection A C B and the union A U B are given by A c B = {x : x A and x B}, A to B = {x : x A or x E B}, where the "or" above is the nonexclusive "or," that is, is understood to mean "and/or." The lative complement A\B is defined by A\B = {z: A and x B}.  2 1. Re Numbers Here, x B means that x is not an element of B; similar notations, such as x it or x I/, will be used later without comment. More generally, if is a collection of sets, i.e., a set whose elements are sets, we write N A = x: x E A for every A E .t), U A = {x:x A for some A . AE The empty set has no elements; it enjoys the property 0 C A for every set A. When all the sets currently under consideration are subsets of some set X (which will always be the case in what follows), we often write A c to stand for X\A, and call it the complement of A. We will often make use of the formulas = = known a DeMorgan's laws. If X and Y are sets, their C'arteian product X x Y is the set of all ordered (x, 1/) with z X and 1/ Y. The set of all subsets of a set X is ced the Ixwer et of X, and denoted by .(X). We observe that is not empty; it h exactly one element, 0, and has two distinct subsets, namely, t and {}. While the reader is undoubtedly familiar with the real and complex num- bers, in this book we assume only the eigtence, and the familiar properties, of the set N = (1, 2,...} of natural numbers. We will show, at least in out- line, how the more complicated number systems arise from N. Given sets X and Y, a relation fro X to Y is a subset R of X x Y. We say R is a relation on X ff Y = X. We write zR 1/if (z, 1/) 6 R. Three kindz of relations have frequent applications. 1. A relation ~ on X is c11ed an e/iva/ence relation if it satisfies the thre conditions: (a) for all x E X, x ~ x; (b) if x ~ 1/, then y ~ x; and (c) if z ~ It and y ~ z, then x z. proim e fity, met, d tmitity, in tt oer. The spl eple of the relation of uity. ff en rehtion on X, it itiom X into uience c: f h x X, et C= - X: y }. We 1 C= the en c of x. Sm x C= (a), we that X the on of the en c. ff there es z C= C, then z x d z y; t ip y z (b) d hence y x  1.1 Sets, Relations, Functions 3 by (c), we obtain / Cz. Another application of (c) shows that if u ~ /, then u ~ x, i.e., that Cy C Cz. In the same way, C'z C C, so C = C. We summarize: either C and Cy are disjoint, or Cz = C. Thus the distinct equivalence classes form a disjoint family of sets whose union is X. It is common practice to denote the equivalence class of an element x by Ix], rather than C. 2. A relation < on X is called a partial order if it satisfies two conditions: (a) it is transitive, i.e., x < y and y < z implies x < z; and (b) for all x 6 X, x x. When (a) holds, it is easily seen that (b) is equivalent to antisy'mme- tr/f. if x < /, then y x. A relation < on X is called a total order if it is a partial order, and satisfies the further condition: for any x and 1/in X, either x < /or y < x or x = / (trichotomy). In view of (a) and (b), these alternatives are mutually exclusive, so exactly one of them holds. An example of a partial order is the relation of proper inclusion on any family of sets. When < is a partial order on X, we write x <_ y to mean that either x < y or x - /. Some writers define a partial order to be a relation _< which is transitive and has the property that x _< /and /_< x together imply that x = y; given such a relation, one can define x < /to mean that x _< /and x y, and find that < is a partial order in our sense. 3. A relation f from X to Y is called a function if for each x .6 X there is exactly one / Y such that xf y. We write y = f(x), or sometimes /= f, to mean xfy. This definition of a function identifies a function with its graph, and so furthers the program, popular among mathematicians in this century, that all mathematical objects should be sets. In practice, of course, almost everybody thinks of a function from X to Y as a rule f which assigns to each x X an element f(x) of Y. One never uses the relation notation xf /in respectable society when f is a function. We write f: X , Y to mean that f is a function from X to Y; here, X is called the domain of f, and (f(x) :x X) is called the range of f, or the image of f. We note that the range of f is to be distinguished from the target space Y of f. We say that f is surjective, or onto, if the image of f is all of Y, and we say that f is injectire, or one-one, if f(x) - f(y) only when x = y. A function which is both surjective and injective is called bijective. A bijective function is also referred to as a one- to-one correspondence. The words map and mapping are synonyms for function. We often use the notation f :.x:: f(x)..For instance, f: n -* n 2 is another way of saying that f s the function for which f(n) = n2; the notation here suggests that the domain of f is either the set of integers, or some subset of that set. A function x: N --. X  4 1. Re Numbers is also called a sequence in X; here, it is standard practice to the notation xn instead of x(n). If E: A (X) is a function, we speak of an indexed family of subsets of X; we usually write a in this situation. When A = N, this means a sequence of subsets of X. The symbols JoA Eo and [A Eo have the obvious meanings; when A = N, it is customary to write J,,__ E,, and oo__ En instead. 1.2 Numbers We are familiar with the set of natural numbers N. This set comes with an algebraic structure and an order relation. That is, there are two operations that assign a natural number to any given pair of natural numbers (i.e., maps of N x N -, N), called addition and multiplication, and they have familiar formal properties such as m + n = n + m for every m, n E N, etc. There is also an order relation on N: we say m < n if there exists k E N such that m + k = n. We emphasize the following property of this order relation: if A is a nonempty subset of N, then A has a least element; i.e., there exists a A such that a < n for all n A. This fi., described technically by the phrase "N is well-ordered," and which is easily seen to imply that N is totally ordered by <, is easily seen to be equivalent to the following, known as the principle of finite induction: Let A be a subset of N, satisfying the two conditions: (a) 1 A; and (b) if n A, then n + 1 A. Then A = N. A variant of this is equivalent, and sometimes convenient: Let A be a subset of N, satisflting the two conditions: (a) 1 6 A; and (b') if k A for all k N with k < n, then n A. Then A=N. The principle of induction is essential in proving many theorems, and we assume at least some familiarity with this procedure. The set Z of integers is sometimes obtained from N by the following procedure. Let Z be the set of all ordered pairs (m, n) of natural numbers, i.e., let Z. = N x N. Define a relation ~ on 2, by declaring (m, n) ~ (j, k) if and only if m + k = n + j. This is easily seen to be an equivalence relation. We define Ira, hi to be the equivalence class of (re, n) for each (m, n) Z, and denote by Z the set of all such equivalence classes. We give the name integers to the elements of Z. We define addition in Z by Ira, n] + [j, k] =[m + j, n + k]; to see that this makes sense, it must be verified that ff (m, n) (m', n') and (j, k) ~ (j, k), then (m + j, n + k) ~ (m' + j', n + k'), but this is very easy. We define multiplication in Z by  1.2 Numbers 5 the r,de: [m, n][j, k] = [mj + nk, nj + mk]. We define an order relation in Z by [m, n] < LJ, k] if and only if rn + k < j + n. (We use the same symbol here for the order relation in N and the order relation in Z, even though this is not really correct; correctness can carry a high price in notation, and finally even in comprehension.) Again, for the multiplication and for the order relation to be well-defined, it must be verified that the definitions yield the same result independent of the choice of representative for the equivalence cls. For any , ( N, (m, ,) (1, 1); we denote {1, 1] by 0. We ob.rve that for any m, n ( N, [n, n] + In, m] =[m + n, n + rn] = [1, 1] = 0. If rn ;> n there is some k ( N with rn = k + n, and we see that (rn, n) (k + 1, 1); similarly, if n > rn, there is some k ( N such that (rn, n) (1, k + 1). The map : k: ; [k + 1, 1] of N --, Z is injective, and prerves all the structre of N. By this we mean that for all j, k 6 N, we have (j + k) = (j) + (k), (jk) = (j)(k), and that if j k, then (j) < (k). In other words, N' = ([k + k N} is an exact replica of N; we have N =. {z 6 Z: z > 0}, the set of all positive integers. We say that the map s an Uomorphism of N onto N . Henceforth, we shall identify N with N , i.e., regard N as a subset of Z. We write k to mean [k + 1, 1], and -k for [1,k + 1]. This somewhat elaborate construction of Z was geared toward the result: for any a,b ( Z, there exists a unique c 6 Z such that a = b + c. An analogous path lets us construct the rational numbers. We want to expand the integers to a system which not only has addition, subtraction, and multiplication, but division as well, i.e., where the equation ax -- b has a solution x for any given a and b, provided a 0. We let denote the set of all ordered pairs (rn, n) of integers such that n 0, i.e., = Z x (Z\0)). We define a relation ~ on by the rule (rn, n) (j, k) means mk= nj. We verify this is an equivalence relation, and let Q be the set of equivalence classes. We call Q the set of rational numbers. We write rn/n or to denote the equivalence class of (rn, n). We make the definitions: (rn/n)(j/k) = (mj/nk), (m/n) + (j/k) = (ink + nj)/nk, and (m/n) < (j/k) if and only if rnk <: nj when n and k are positive. We can verify that these definitions make sense: they are independent of the choice of (m, n) in the equivalence class m/n, etc., and for the order relation, we note we can always choose n ;> 0 in writing an element of Q as rn/n. Again, we observe that the map rn: ; m/l is an injective maplfing of Z into Q, which preserves all the structure of Z. We henceforth identify Z with the subset {(rn, 1): rn 6 Z} of Q. The construction of Q was engineered in view of the goal: for any a, b 6 Q, with a 0, there exists a unique c ( Q with ac = b. It is frequently useful to use the "best" representation of a rational num- ber, i.e., to write it as a quotient of integers without common factor. We illustrate induction arguments by proving this can be done. Given q 6 Q, consider { k N : q = m/k for some rn Z} = {k N: kq 6 Z).  6 1. Re Numbers This is a nonempty subset of N, hence contains a smallest element n. In the representation q = m/n, m and n have no common factor greater than 1; for if m = ij and n = kj, with j E N, j > 1, we would have.q = i/k, though k < n, which is impossible. If also m ( N and mq ( Z, It is easy to see that m is an integer multiple of n. 1.3 Infinite Sets A set F is said to be finite ff for some n N there exists a bijective mapping $ from (1, 2,..., n} to F. The natural number n here is uniquely determined, and we call it the cardinality of F, written either as card F or az #F. If : j .x), we have F = 0{.x x2,.. x, }. We also call the empty set finite, and assign it cardinality a set ' not finite, it is infinite. If X is an infinite set, there exists an injective mapping of the natural numbers N into X. If there exi a bijective map of N onto X, we say that X is cmmtably infinite Thus, X is countably infinite if and only if its elements can be listed in an infinite sequence: X = (x, x2,...}. We call a set E countab/e if it is either finite or countably infinite; if X is infinite but not countable, we say X is uncounle. If X is countably infinite, we also write card X = R0, pronounced "aleph naught." We give just a few results about countability. 1.1 Propozition. Every subset of N is countable. Proof. Suppo A is an infinite subset of N. Define b(1) to be the smallest element of A; since A is infinite, it is nonempty, so b(1) is well-defined by the fundamental property of N. Having defined b(n- 1), set b(n) to be .the smallest element of (k A:k > k(n- 1)). Again, the set in brackets m nonempty since A is infinite, so b(n) is well-defined. In this way, we construct a map b: N A, and it is easy to check that this map is bijective. I 1.2 Corollary. Every subset of a countable set is countable. 1.3 Proposition. A set A is countable ff and only ff there exists an in- jective map of A into N, if and only if there exists a surjective map of N onto A. Proof. It is trivial that if A is finite, there exists an injective map of A into N and a surjective map of N onto A. Suppose that A is infinite. If A is countable, there eists a bijective map g of N onto A, so/- g-1 is an injectire map of A onto N. If there ex_sts an injective map A into N, then by the last proposition there exists a bijective map b of f(A) onto N, and then b o f is a bijective map of A onto N, so A is countable. If  1.3 Infinite Sets 7 g: N , A is surjective, define f: A , N by taking f(a) to be the smallest element of (n ( N: g(n) = a}. It is easy to see that f is injective, so A is countable. 1.4 Proposition. If A and B are countable, then so is A x B. Proof. It suffices to prove this proposition for the special case A = B = N. By Proposition 1.3, it suffices to produce an injective map f: N x N N. Let f be defined by f(m,n) = n + 2 "+m. Then f is injective; for if f(m,n) = f(j, k) with n _> k, then we have 0 _< n- k = 2 k+) - 2 n+m < n, and since n < 2" < 2 "+m, we get from the above that 2 n+m < 2 :+j < n + 2 n+m < 2 n+m+l. It follows that n + m _< k + j < n + m + 1, so n + rn = k + j, and hence n - k = 2 + - 2 "+m = 0. Thus n = k, and m -- j. The more usual way to establish the last proposition is to list the elements of N x N by listing in order the elements of the finite sets { (j, k): j + k = n}, thus (1, 1), (1,2), (2, 1), (1, 3), (2, 2), (3, 1), (1,4), (2, 3), (3, 2), (4, 1),..., which gives a bijective map of N 2 to N directly. 1.5 Corollary. The set Q of all rational numbers is countable. Proof. The set fl is countable by Proposition 1.4 and Corollary 1.2, and it follows from Proposition 1.3 that Q is countable. 1.6 Proposition. If An is a countable set for each n E N, then A = {,in��= An is countable. 1 Proof. For each n ( N there exists a surjective map n: N An. Define f: N 2 -, A by f(n., .m) = n(m). Then f is surjective, and since N 2 is countable by Proposition 1.4, it follows that A is countable by Proposition 1.3. 1.7 Theorem. For any set A, there is no surjective mapping of A onto (A). In particular, it' A is a countably infinite set, then (A) is countable. Proof. Suppose that A , o.(AB). Let B = (a . A :a. (a)}. If B = (a) for some a ,, then a ( is impossible, since thin would say a 6 (A), so a B. But also a � B is impossible, since this would say a � (A), so a B. The only conclusion possible is that B (a) for every a ( A, so is not surjective.  8 1. Real Numbers 1.8 Corollary. If X is the set of all mappings of N into {0, 1 , i.e., all sequences of zeros and ones, then X is uncountable. Proof. For each A C: N, let 1A : N --. (0, 1 be deftnell t,y 1A(n) = I if n 6 A, and 1A(n) = 0 if n A. It is easy to check that the map A: 1A is a bijective map of (N) onto X, ,so it follows from the last theorem that X is uncuntable. 1.4 Incommensurability The natural numbers are also called counting numbers; but from the ear- liest historic times, they were used for measuring as well, for instance, for measuring the length of a line segment. This application of course depends on choosing a unit of length, and then marking off on the given line seg- ment a sequence of subsegments of this unit length, these subsegments to have only endpoints in common, while the segment to be measured is to be the union of the subsegments. If this is impossible, i.e., if the last sub- segment marked off extends beyond the endpoint of the original segment, then hopefully a smaller choice of unit can rectify the situation. However, it was discovered in classical Greece (ca. 400 B.c.) that there is no choice of unit which makes the side and diagonal of a square simultaneously have integral lengths: these quantities are incommensurable. The classical proof cannot be improved: Let s be the side, and let d be the diagonal of a square. Then d 2 = 2s 2 by the Pythagorean theorem. If s and d are integers, then we may suppose them to have no common factor (in partic- ular, we may suppose them to be not both even). But d -- 2s 2 tells us that d 2 is even, and it follows that d is even (it is easy to check that the square of an odd number is odd), so d = 2rn for some .integer rn. But then 2s 2 = d 2 4rn 2, whence s = 2m so s 2 m even, and hence s is even. Thin contradiction shows that the hypothesis that d and s are integers is untenable. This proof is remarkable in that the geometric hypothesis is reduced at once to an algebraic one (d 2 = 2s2), and the rest of the argument is strictly algebraic, or number-theoretic if you will: it is shown that the equation x 2 = 2 has no solution x in the rational numbers. Some readers may prefer an argument whose methods are as geometric as possible. Here is such a geometric proof: Suppose that the side and diagonal of the square ABCD are commensurable, so that for some choice of unit length the side AB has length s and the diagonal AC has length d, where s and d are integers. We shall produce another square, with strictly  1.4 lncommensurability 9 D C A B R Figure 1.1. Geometric proof of incommensurability. smaller sides, whose side and diagonal also are integral. On the diagonal AC of the square ABCD, mark off the point P which is at distance s from A. Draw the line through P perpendicular to AC, let Q be the intersection of this line with the side BC, and let R be the intersection of this line with the line through A and B. (See Figure 1.) We observe that the isosceles right triangle AAPR is congruent to /XABC, since each has sides of length s. Hence the hypotenuse AR of/XARP has length d, and hence BR = PC = d- s. (We note that d- s < s, i.e., d < 2s, since the line segment AC joining the points A and C is shorter than the path made up of AB followed by BC.) But BQ = BR, so CQ has length s- (d- s) = 2s- d, an integer. Ths the isosceles right triangle /xC'PQ has a hypotenuse of integral length, as well as sides which are of integral length d- s, strictly smaller than those of/XABC. Completing it to a square, we have verified the claim made above. A repetition of this construction, fewer than s times, leads to a contradiction, since s _< 1 is obviously impossible. The geometricproof above leads us to a different algebraic proof, perhaps the shortest possible. We can argue as follows: if s and d are positive integers with d 2 = 2s 2, and s is the smallest possible, we consider m --- d- s and n = 2d- s. Since s < d < 2s is clear, we have 0 < rn < s, and a quick computation gives n 2 = (2s -- d) 2 = 452 - 4sd + d 2 = 2d 2 - 4sd + 2s 2 -- 2(d - s) 2 = 2rn 2, contradicting the minireality of s. This proof is indeed efficient, but rather uncivil.  10 1. Re Numbers The discovery of incommensurable quantities was a severe blow to the Pythagorean program of understanding nature by means of numbers. (The slogan of the Pythagoreans was "All is number.") The Greeks developod a sophisticated theory of ratios, presumably the work of Eudoxus, to work around the problem that certain quantities, even certain lengths, could not be reduced to numbers, as then understood. This theory anticipates the development of the real number system by Dedekind and Cantor in the nineteenth century. 1.5 Ordered Fields In this section, we describe the formal properties that the set of rational numbers possesses, along with one useful property that it lacks. 1.9 Definition. A field is a set K, containing at least two elements, to- gether with two mappings of K x K , K called addition and multiplication, and written (a, b): : a + b and (a, b): ab, respectively, with the following properties: 1. for all a, b, c 6 K, (a + b) + c = a + (b + c); 2. for all a, b K, a + b = b + a; 3. for all a, b 6 K, there exists c K such that a + c = b; 4. for all a, b,c K, (ab)c = a(bc); 5. for all a, b K, ab = ba; 6. for all a, b K such that a + b b, there exists c K such that ac = b; and 7. for all a, b, c 6 K, a(b + c) = ab + ac. The reader can observe that the first three properties refer only to a(l- dition, the next three only to multiplication, while the last connects the two operations. The first and fourth are known as the associative laws, the second and fifth as the commutative laws, and the last as the distributive law. We now deduce a few properties from these axioms. 1.10 Proposition. In any field K, there exist distinguished elements 0 and 1 with the properties: a + 0 = a for all a K, al = a for all a K. I� a, b K and a + b = a, then b = O; it' a, b K and ab = a, then either a = 0 or b = 1. Lastly, aO = 0 for all a K, and I O.  1.5 Ordered Fields 11 / Proof. Let x E K (K is not empty by a,sumption). By property 3, there exists 0 E K such that x + 0 = x. Now if a is any element of K, there exists b K with b + x = a; tnt then a +0 = (b+ x) +0 = b+ (x +0) = b+ x =a, as claimed. Now suppo that a + b = a; there exists c such that a + c = 0, and it follows that b = b+ (a +c) = (b+a) +c= a + c=0. Similarly, choose y 6 K with y y 0 (K has at least two elements by assumption.) For any a ( K, we have a + y a, so by property 6 there exists an element 1 of K such that y l = y. Now for any a ( K, there exists by property 6 .some b E K such that/ry = a; it follows that al = (b)l -- b(yl) = by -- a, as desired. Now suppose that ab = a and a 0. Then there is some c 6 K with ac = 1, and we have 1 = ac = (ab)c = (ba)c = b(ac) = bl = b, as desired. Finally, if a K, we have a + a0 = al + a0 = a(1 + 0) = al = a, so a0 = 0. It follows that if 1 = 0, then a = al = 0 for all a � K, which contradicts the assumption that K has at least two elements. 1.11 Corollary. For each a, b K, there is a unique c E K such that a + c = b; we denote this element c by b- a, or when b = O, simply by -a. Clearly, -(-a) = a for all a K. Similarly, if a K, a y O, there is a unique b K vith ab = 1; we denote this element b as a - , or 1/a. We will not go on and list and prove all the usual commonplaces of algebra, such ms that -a = (-1)a for each a K, or the general a&sociative laws which enable us to write a +a2+.' '+an and aa2.. 'an without any ambiguity. If the reader has never engaged in such exercises, this might be a good time to do so. Observe that the symbols 0 and 1 are badly chosen; we should write 0� and 1 � to avoid confusion with the integers (or rational numbers) 0 and 1. By paying attention to context, we will hopefully always be clear what is meant. In fact, the fields we are most interested in can be regarded as containing the rational numbers, so there is no danger. Let K be a field, and a E K. We define na for each natural number n inductively: la = a, and na = a + (n- 1)a for n > 1. It may happen that pa = 0 for .some p N and a 6 K with a 0 (this clearly occurs if and  12 1. Real Numbers only if pl = 0, where 1 here is the element of K, not the natural number). If p is the smallest natural number for which this occurs, we say that K hn.s characteristic p. If nl 0 for every n 6 N, we say that K has characteristic 0. Of course, our basic example Q is a field of characteristic 0. Every field, according to Proposition 1.10, has the elements 0 and 1, and the smallest field consists of exactly these two elements, with the addition rule 1 + 1 = 0 and all the other addition and multiplication rules forced by that proposition. But among fields with characteristic 0, the smallest field is the field Q of rational numbers. Indeed, if K has characteristic 0, the map n: n l is an injectlye mapping of N into K. This injection extends in the obvious way to the field Q of rationals, and this injection is an tsornorphisrn, i.e., it carries the addition and multiplication of Q the addition and multiplication in the field K. We identify the image of this map with Q itself, i.e., regard Q as a subset of K. It is evilently smallest subfield of K. 1.12 Definition. An ordered field is a field K, together with a total order relation < on K, satisfying the �ollowing conditions: (a) if a < b, then a + c < b + c for every c K; and (b) if a < b and 0 < c, then ac < bc. We write a > b to mean b < a, and a <_ b to mean: either a < b or a = b. Similarly, a ;> b means that either a > b or a = b. Taking c = -a in (a) of the definition, we see that a < b implies b-a > O, and similarly b - a > 0 implies a < b. 1.13 Proposition. Let K be an ordered field. Then (a) �or each a K, a > 0 i� and only i�-a < 0; (b) if a < b and c < O, then ac > bc; (c) �or each a K, either a = 0 or a 2 > O; and (d) for each a K, either a = 0 or na 0 for every natural number n. Proof. Suppose a > 0. Take c = -a in condition (a) of Dvefinition 1.12 to deduce that -a < 0. Since a = -(-a), this gives also that -a < 0 implies a > 0. Thus (a) is proven. Since c < 0 implies -c > 0 by (a), we have a < b implies a(-c) < b(-c) by (a) of Definition 1.12, which gives -ac < -bc or ac > bc by another use of (a). If a 0, then either a > 0, when a 2 > 0 by property (b) of Definition 1.12, or -a > 0, when a 2 = (-a) 2 > 0. In particular, I > 0, since 1 = 12. It follows that I + 1 > I > 0 and by induction that n l > 0 for every natural number n; in particular, n l 0. Thus na can be interpreted as the product of the positive element nl and a, so na > 0 whenever a > O, and na < 0 whenever a < O.  1.50rderc Fields 13 Of course. part (d) of this proposition can be restated as: every ordered field ha. characteristic zero. 1.14 Proposition. Let K be a field, and let P C K have the properties: 1. if a, b 6 P, then a + b 6 P; 2. if a, b 6 P, then ab 6 P; and . 3. h,r aO' a 6 K, exactly one of the alternatives a 6 P, -a 6 P, a = 0 holds. If w,. th.tim. the. n.lation < by the rule: a ,c b if and only if b- a 6 P, then K with < is an orth,nl tiehi. We h'ave tle proof of this ms an exercise. We note that the converse of this proposition is also trivially true: if K is an ordered field, and we put P -- a K: a 0, then P has the properties of the proposition, and b : a if and only if a - b 0, a.s we have seen. ' 1.15 Example. It is evident that Q is an ordered field, with the usual meaning of :. Here is a less obvious ordered field: let Q(X) be the field of all rational functions in the indeterminate X. More precisely, consider the col- lection of all expressions of the form p(X)/q(X), where p and q are polyno- mials in the indeterminate X with rational coelcients, and q 0. Declare two such expressions p(X)/qI(X) and p(X)/q(X) to be equivalent if p(X)q(X) = p(X)ql(X), and let Q(X) be the set of equivalence classes. The addition and multiplication in Q(X) are the familiar ones. To define an order, we decree that a polynomial p(X) = ao+alX +a2X +...+a,X ' is positive if a 0, where k is the smallest integer with a 0. Thus, if a0 0, then every polynomial of the form ao + a lX + ... + aX is positive, and in particular, the constant polynomial a0 is bigger than any polynomial blX +... + bnX without a constant term. Next we define r(X) = p(X)/q(X) to be positive if either both p(X) and q(X) are posi- tive, or both are negative. It is easy to see that this does not depend on the particlar choice of p(X) aml q(X ) used to represent r(X), and that ttw set P f mwh posit, iw: eh:mets has the l)rOl)erties of the last l)ropsitim. Of course, we could have made such a construction starting with any ordered field K instead of Q. 1.16 Definition. Let S be a subset of the partially ordered set X. We say that M 6 X is an upper bound for S if x _ M for all � 6 S. Similarly, we say that m 6 X is a lower bound for S if m _ x for all x 6; S. We say that M is a maximal elenent of S if M S and there exists no x 6 S with M x. Similarl.: m is a minimal element of S means that m 6 S and for no x 6 S do we have x m.  14 1. Real Numbers We note that when X is totally ordered, a maximal element M of S is an upper bound for S, and a minimal element of S is a lower bound. There can be at most one maximal element of S in this case; for if also M' E S and M' is an upper bound for S, we would have M _ M' and M' _ M, so M = M'. Similarly, there exists at most one minimal element of S. Thus, M is a maximal element of S means M is the greatest element of S, and m is a minimal element of S means m is the least element of S. It is easy to see that if X is totally ordered, any finite subset F of X has a greatest and a least element, denoted, respectively, by max{x: x E F} and min{x: x F}. Here are two simple examples, with X = Q. If S = { 1In: n E N}, then every q Q with q _ 1 is an upper bound for 5, and I is a maximal element of S. Every q 6 Q with q _ 0 is a lower bound for S, while for any q > 0 there exists n E N with 1In <qql so q is not a lower bound for S. Thus the set of lower bounds for S is { q _ 0}. The greatest lower bound for S is 0, but $ admits no minimal element. Here is a more conplicatod example. 1.17' Exnnple. Let S = {q E Q � q2 < 2}. If M 2 _ 2 and M > 0, then M is an upper bound for S; for if q 6 Q and q > M, then q2 qM > M 2 _ 2, so q 5. Conversely,J M is an upper bound for S, then M > 0 and M _> 2. For 1 6 S, so :> 1 > 0. If M 2 < 2, then for each n N we have M + - = +- 2M + <_ + -(2M + 1), and wecan choose n so that (1/n)(2M+l) < 2-M 2, which gives M+ 1In E S. Since M < M + 1 In, this contradicts the supposition that M is an upper bound for S. Thus M is an upper bound for S if and only if M > 0 and M 2 _ 2. Now if M 2 > 2, then (M- l/n) > 2 for some n 6 N, by a calculation like the one just made. Thus a least upper bound for $ would be a number M 0 with the property that M 2 = 2. As we saw in the ls section, there exists no such M E Q. Thus S has upper bounds, but no least upper bound. If K is an ordered field, it is easy to see that the set of upper bounds of a set S C K is either empty or infinite; indeed, if M is an upper bound, .so is M for any M' >_ M. We note that m is a lower bound for S (or minimal element of S) if and only if -m is an upper bound for (resp., maximal element of) the set -S = {-x: x 6 S}. This observation makes it easy to deduce generalities about lower bounds or minimal elements from the corresponding generalities about upper bounds or maximal elements. 1.18 Definition. We say that K is a complete ordered field if K is an ordered field with the property: given any subset $ o� K, i� the set h'[s o� upper bounds of the set $ is nonempty, then Js possesses a !e&st element.  1.5 Ordered Fields 15 In other words, the ordered field K is complete if and only if every subset S of K which has an upper bound must have a least upper bound. It is an immediate con.,luence that any subt S of a complete ordered field which has a lower bomd must have a greatest lower bound. Example 1.17 shows that the ordered field Q is not complete. We shall use the word suprernurn as a synonym for least upper bound, and infirnurn as a synonym for greatest lower bound. The notations sups or supx, infS or inf x xE$ xE$ will denote the supremum, infimum respectively, of the set S. If S has no upper bound, we write sups = +, and if S has no lower bound, we write inf S = -o. It is sometimes convenient to also take sup0 = -oo and inf 0 = +o. (After all, every x is an upper bound and a lower bound for It turns out that there exists a complete ordered field (not an obvious fact), and (essentially) only one. We sketch this result in a later section of this chapter, and for now go on to study the properties of such a field, assuming it does exist. We introduce the following notation, to be fixed for the rest of the book: let R be a complete ordered field. We call R the field of real numbers. We define the set R of extended real numbers to be R with two more elements adjoined, denoted + and -, with the order relation of R extended by the rule -x) < x < +o for all x E R. We will not at this time consider any algebraic operations among elements of ; we emphasize that is a totally ordered set, but not a field. 1.19 Theorem. Let R, > O. For any M R, there exists n N such that n > M. Proof. Let S = {n: n 6 N}. The theorem asserts that S is unbounded. If on the contrary S has an upper bound, then by the definition of complete ordered field, it has a least upper bound R. Then we have n _< R for every n 6 N, since R is an upper bound for S, but, since R is the smallest upper bound for S, there exists rn E N with rn > R-; this implies (rn + 1)( > R, a contradiction. 1.20 Corollary. Let x R. There exists a unique n Z such that n _< x < n + 1; this integer n is called the largest integer in x, and denoted Proof. Suppose x > 0. By Theorem 1.19, (k 6 N: .k > x} is not empty, and hence there is a smallest integer n with n > x; evidently, Ix] = n- 1. If x < 0, let rn = min{k N: k >_ -x}, which exists by the same reasoning; it is easy to see that -m -- Ix].  16 1. Pa,al Numbers The property of R described in Theorem 1.19 is known as the Archireed- eau property. The property also holds for the field Q (and is trivial), but it does not hold in every ordered field. For instance, it does not hold in the field Q(X) discussed in Example 1.15 (or in R(X) for that matter), since, for instance, X > 0 but nX < 1 for every n. We next show that the rational numbers come arbitrarily close to any real number. Again, we use only the Archimedean property of R. 1.21 Definition. A subset E of R is said to be dense in R if for any x ( R, and any � > 0, there exists t E with x - e < t < x + .. 1.22 Proposition. The rational numbers Q form a dense subset of R. Proof. l.t x � R m,d > 0. Tilere exists n � N su(:! that n > 1, i..., such that 1/n < �. t m = [nx], m � N and m nx < m + 1. Pt q = m/n; then q x < q + l/n, x- e < q < x + e. [ The elements of RQ e call itional hum&rs. Here is a pretty threm of Dirichlet. 1.23 Theorem. If a/s an irrational number, then S= {na+m:mcZ, nN} is a dense subset of R. Proof. Let us begin with the observation that if 6 S and k is a positiw, integer, then k + m � S for any integer m. To show that S is dense in R, it suffices to show that for any positive integer N, there exists � S such that [1 < 1IN. For imtance, if 0 < < I/N, the, given any t R, we first choose m � Z so that t + m > 0, then let k be the smallest positive integer such that k > t + m; we have rl = k - m S, and t < < t + 1IN. I! -1/N < < 0, we c. an choos.e m ,so t + m < 0, and proceed in a simfiar manner. Now if N as a positave integer, let ,, = na- [nal, for n = 1, 2,..., N + 1. (Here, as usual, [4 th,, greatest integer not greater than ) We observe that: .i < 1, an.d (ii) if n < k, then - � S (: Consader the N antervals particular, . ) 0 <. , ((i- 1)/N, i/N) (i = 1,... ,N); in view of (i), and the fact that each , is irrational, each belongs to one of these intervals. But there are N + 1 of these �,, so there must exist an interval ((i- 1)IN, i/N) which contains and for some n < k. But then = - , � S by (ii), and 1.6 Functions on R The algebraic operations on R can be used to define many functions from R (or subsets of R) to R. Thus, for each c R we have the constant  1.6 Functions on R 17 function x : c, and the functions x: c + x and x: . cx; colnbining these two ideas, we construct x: . c + dx, for any given c, d 5 R. Ite:ating these ideas, we obtain the polynomial functions p on R, where p(x) = ao + aax + ax 2 + ... + anx n. Such a polynomial, we recall, is said to have degree n if a, 0 above; thus constant functions are polynomials of degree 0, with one exception: the zero polynomial (with all coetScients aj = 0) is said to have degree -oo. (This enables the rule that the degree of a product is the sum of the degrees of the factors to be true without exceptions.) Similarly, if f and g are functions from X to R, g 0, we define fig by the formula (f/g)(x) = f(x)(x); the domain of fig is, of course, not all of X in general, but (x : g(x) : 0}. If p and q are polynomials, q (), the function p/q is called a rational finction. When q / �), tl:(' z(,r() s(,t (,f q is fi:it.(,, a.,4 w(, s(,(* fr(.:: t!:(, (!ivisi(.i algorit, h for polynonaials: if the (legr( of q is n > 0, then for ally a R we can write q(x) = (x- a)q(x) + r(x), where the degree of r(x) is less than 1, i.e., r(x) is a constant. If q(a) = 0, it follows that r(a) = 0, i.e., that r = 0, or q(x) = (x- a)qa (x). Here the degree of q is evidently n- 1. Since q(b) = 0 if and only if b = a or ql (b) = 0, we obtain inductively that q has at most n zeros. Another uful function is Ix I, defined by Ix[ = { x if x > O; -x ifx 0. This function h,., ,.s is crazily see. n, the following properties: for all x, y R, JxyJ = JxlJyJ, Ix + y[ _ [xl + JYl, [xl 0 unle,4 x = O. We shall use these properties frequently throughout the rest of this book. Related is the sign function: sgnx = x/Ix I for x 0, and sgn0 = 0. We note that x = Ix[ sgn x for all x R. We will later want to use also the functions x: x + and x: , x-, defined by x + = max{x,0} and x- = max{-x,0}. We note that for any x, we have x + > 0, x- >_ 0, x = x + -x- and Ixl = x + + x-. We denote by R+ the set of nonnegative real numbers, The power functions z: = z" are defined on all R when n 6 N, and they are injective when restricted to R+. ndeed, if 0 _< z < U, we have z" < U". t follows that when n is odd, : = z" is injective on R, since (-z)" = -z" for n odd. These simple remarks are valid in any ordered field. The next theorem, which is a generalized complement to Example 1.1 ?, uses the completeness of R in an essential way. Afe need the following lemma: 1.24 Lemma. Let n N, and x, y 6 R, x _> 0 and y > 0. fix" < y, there exists t > x with t" < y, anti if x" > y, there exists 0 < t < x with t" > y.  18 1. Real Numbers Proof. We recall the algebraic identity b" - a" = (b- a)(b "- + b"-2a +... + a "-) valid in any field. If 0 <_ a < b, this gives the inequality b" < a" + (b- a)nb '- . If x" < y, taking a = x and b = x + h in this inequality (with h > 0) we get (x+h) n < x"+hn(x+h)n-,soforO < h < 1 withh < (y-xn)/n(x+l) "-, we have (x + h)" < y. Similarly, if 0 < h < x, taking b = x and a = x - h in the inequality gives (x- h)" > x" - hnx "-, so if x" > y and we take 0 <: h < x with h < (x" - y)/nx n-l, we get (x - h)" > y. I 1.25 Theorem. Let n E N. Then the map x: x" of R+ to R+ is bijective. In other words, for each 11 R, y ?_ O, there exists a unique x R, with x _ 0 and x n = y. Proof. We have already observed that the map is injective, so we have only to prove that it is surjective, i.e., that for every y _ 0, there exists x _ 0 such that x n = y. The result is obviou when y = 0, so we assume now that y > 0. Let S = t _ 0: t n < y}. Since 0 S, S lb. Furthermore, S is bounded above. In fact, if t > 1 + y, we have t n > (1 + y)" > 1 + y > y, so t � S: thus t <: 1 + y for all t S. Hence there exists a least upper bound x for S. If x n y, there exists, by the last lemma, t x with t" y; but then t S, contradicting that x is an upper bound for $. On the other hand, if x n > y, there exists u with 0 < u < x and u n y. Now if t u, it follows that t" > y, so we conclude that t _ u for all t 6 S, i.e., that u is an upper bound for S. But u <: x, so this is impossible. We conclude that x" = y. I We denote the unique x _ 0 with x" = y by y/, or r/'. When n is odd, and y < 0, there exists t 0 with t n = -y, so -t) = (-1)ntn -- y; thus, when n is odd, there exists for every y 6 R a unique x 6 R with x" = y. We denote this number x by y/'. We can now define (for x _ 0) x q for any rational q = m/n by x m/n as (Xm)/n; we should show that this does not depend on the particular choice of the representation = m/n, that (x") /' = (x/') ", that x q+ = xqx , and that x q = (x q for any rational q and r, etc. 1.7 Intervals in R 1.26 Definition. Let K be an ordered field. We say J is an interval in K if J is a subset of K with the property: if a < b < c with a, c J, then b6J.  1.7 Intervals in H. 19 Note that this definition counts both K and 0 as intervals. Note also that each singleton set (a is an interval. Given any a,b K with a b, we define (a, b) = (x 6 K: a < x < b). (The danger of confusion of the interval (a, b) with the ordered pair (a, b) is sually minimal. Some writers consider it serious enough to use the notation ]a,b[ instead of (a, b), but we'll risk it.) It is imnediate that (a, b) is an interval; we call it the open interval with endpoints a and b. Similarly, we define the closed interval with endpoints a and b to be [a,b] = {x K: a _< x <_ b}, and two kinds of semiclosed intervals: [a, b) = {x 6 K :a <_ x < b) and (a, b] = {x ( K :a < x _< b}. This does not exhaust the possibilities for intervals; we also note that { x 6 K: x > a } is an interval, which we denote by (a, +oo), as is {x ( K :x _> a}, denoted by [a, +oo). The intervals (-oo, b) and (-oo, b] are deftned in an analogous manner. We sometimes write (-oo, +o) instead of K. We call (-o, b] and [a, +oo) closed intervals, and call (-oo, b) and (a, +cx)) open intervals. In the case of a complete ordered field, it is easy to classify all the in- tervals, s.sfollows. Let J be a nonempty interval in R. Let a = inf J, and let b = sup J. We note -oo _< a _< b _< +oo, but a = +oo and b = -oo are excluded since J is nonempty. If a < x < b, then (from the definition of inf and sup) there exist c, d ( J with a < c < x < d < b, and it follows that x 6 J. Thus J D (a, b). We have a _< x _< b for all x ( J. If b < +oo, there are two possibilities: either b 6 J or b � J. Similarly, if a > -oo, there are the two possibilities. Thus we see that every nonempty interval J in R must have one of the forms described above: (a, b) or (a, b] or [a, b) or [a, b] or (-oo, b) or (-oo, b] or (a, +oo) or [a, +oo) or (-oo, +oo). The first four of these are called bounded intervals, the next five are called unbounded. 1.27 Theorem. Suppose that ['or each n N, J, is a tlolwmpty closed bounded intervaJ in R, with J,+i C J, for each n. Then Nn��__l Jn ). Proof. By hypothesis, each Jn has the form R, a, < b,. In fact, we have an _< bm for any rn, n ( N. For if k = max{rn-n), we have J C Jn, which implies an _< a, and J C J,, which implies b _< bin; thus we have an _< a _< b <_ bin. Let c = sup(an: n N. Then an < c for every n, and c <bm for every rn, so an < c < bn for every n, I.e., C The hypothesis that each Jn is closed cannot be dispensed with in this theorem, nor that each Jn is bounded, nor that the ordered field involved is complete. See the exercises at the end of this chapter. 1.28 Theorem. The interval (0, 1) in R is not countable� Proof. Let E be a countable subset of (0, 1): say E = {x,,x2,...}. W.e make the following practically trivial remark: gven a nonempty open interval (a, b) in R, and x ( R, there exist c d such that It, d] C (a, b) and '  20 1. Real Numbers [c, d]. By this remark, we can choose a l < b such that x l a [a, bl] C (0, l). Having chosen a. b. as, b2,..., an, bn such that an < for k = 1, 2 .... , n, and such that [an+ , bn+l] C (an, bn) for k = 1, .... n - 1, the remark enables us to choose an+ < bn+ such that [an+ , b+ l ] C (an. b) and Xn+. q [an+ , bn+ ]. Thus we have inductively defined for each n N a closed interval Jn = [an, bn], such that Jn+ C Jn and Xn q J, for every. n 6 N. According to Theorem 1.27, there exists x 6 n__l J. Since x, [ J for every m N, we conclude x E. Thus E (0, 1). I 1.8 Algebraic and Transcendental Numbers 1.29 Definition. A real number x is said to be algebraic if there exists a positive integer n, and integers ao, a,..., an, an 0, such that anX n + an-i + ... + ax + a0 = 0. (1.1) We say that x is algebraic of degree n if n is the smallest positive inte- ger for which x satisfies an equation of the form (1.1). We say that x is transcendental if it is not algebraic. We were motivated to expand from Q to R in order to be able to solve the equation x = 2. We found that in R we could solve any equation xn = a, but that still leaves open the possibility that every real number is algebraic. There are at least two ways to see that this is not ,so. 1.30 Proposition. The set of transcendental numbers is uncountable. Proof. Let Av be the set of all numbers x which satisfy an equation of the form (1.1), with n + --y-0 lal _ N. Clearly, each Av is finite, since each such equation has at most n solutions, and there are a finite number of such equations. But [.J_2 Av is the set of all algebraic numbers. Thus the set of algebraic numbers is the union of a sequence of finite sets, and hence is countable. Since R is uncountable, the set of transcendental numbers is uncountable. It is perhaps a little disappointing that this existence proof for transcen- dental numbers fails to exhibit a single one. Here is another approach. The following theorem of Liouville says that algebraic numbers which are not rational cannot be approximated too closely by rational numbers. 1.31 Theorem. Let x be an algebraic number of degree not more than n. Then there exists a constant C such that for any integers p, q (q O) with x : p/q, we have p c q q'  1.9 Existence of R 21 Proof. Let f(t) = a,t n + an_t "-I +... + ao, where aj is an integer for j = 0, 1,..., n, such that f(x) = 0. Then f(t) = (t- x)g(t), where g is a polynomial of degree less than n (with real coefficients). Since g has at most n- 1 zeros, there exists 5 > 0 such that 0 < It - x[ _< 5 implies g(t) : O, and hence also f(t) : 0. It is easy to see that there exists M such that [g(t)[ _ M for all t with It-x] _ 5. For instance, if g(t) = ,=0 bjt), choose N large enough so that [x-5, x+5] C [-N,N] and take M = ,-I , j=0 ' Now suppost, [x - p/q[ <_ 5, x p/q. Then g(p/q) : O, so we have p f(p/q) anp n + an-l q +'" + aoq n p,,- l q g(p/q) qng(p/q) ' Now the nulnerator of this last fraction is an integer, and it is not 0: since f(t) : 0 for 0 ( It - xl _ 5. Hence the numerator has absolute value at least 1, and we have fq.- But if [x - p/q[ p 5, then of coukse [x - p/q[ 5/q n, since q _ 1. Thus taking any C smaller than both 5 and 1/M gives us the theorem. 1.32 Example. Let x l = �, and inductively define 1 n --Xn-1 '- 2,! � (n+)' ... (n+m)' Then zn+, - zn = 2- ' + + 2- ' ( 2.2- � for every n,m. Let z = sup{z.,z,...). We have then z z ( 2- 2 -(+). But z = pn2 -n for me nteger p. Thus we have (tng q= 2 n) inualities 0 �- Pn/qn ( 2.2 -n-/qn for eve n. According to the threm, this is impible if z is algebraic, z is trendental. 1.9 Existence of R In this section, we outline the construction first given by Dedekind. Dede- kind presented his real numbers as "cuts" of the line, i.e., as pairs of sets of rationals, one set lying entirely to the left of the other, the union being the set of all rationals. Nowadays, we dispense with one element of the pair, since the left side of the cut carries all the information anyway. The following sketch omits many, perhaps most of the details, which are rather tedious. 1.33 Theorem. There exists a complete ordered field R. It' R1 and R2 are complete ordered fields, there exists an isomorphism of ordered fields between them, i.e., there exists a bijective mapping : R -- R2 which  22 1. Numbers preserves the structure: for any x, y E R, we have (x + y) - () + (y) and (xy) = p(x)(y); for any x, y e R with x < y, we have (x) < /(y). Proof. We define the set R to consist of all subsets of the rational numbers Q, having the properties: (a) if q 6 c and r <: q, then r 6 ; (b) c has no greatest element; and (c) Z # # Q. For each q. 6 Q, the set q = (r 6 Q: r < q} evidently belongs to R, and the map q: . 4 is clearly injective. We observe that each c E R is bounded above, as a subset of Q. We define c fl to mean that c is a proper subset of/. We define the sum It is not hard to show that c + 6 R. It is clear that c +/ = + c, and that c + (fl + ?) = (c + fl) + ?. We next construct -c for any given c 6 R, as follows: let & be the set of all upper bounds for c in Q, with the exception of the least upper bound, if that exists (c has a least upper bound if and only if = for some q E Q). Define -c = -q: q 6 &}. It is easy to verify that - 6 R for each c 6 R, and that given any c 6 R, / R, the element ? = fl + (-c) satisfies the equation c + = /. We have verified the first three properties of a field (see Definition 1.9). We next define multiplication in R; to do this, we first consider the case > 0. For such c, f we put c/= {ab: a c, a >_ O, b /, b >_ O LJ O. If c > 0 and < 0 we define cfl = -c(-), and if c 0 and fl < 0, we put c = (-c)(-). We define 0 = 0 for all c. Again, it is clear that the operation is commutative and associative (properties 4 and 5 of Definition 1.9). If c > 0, we define 1/c = l/q: q E &} kJ {.q 6 Q: q < 0}. If c < 0, we define 1/c = -1/(-c). It is not hard to verify that c/c) = i, and more generally, that setting = (1/c)/gives a solution to the equation cr = f], whenever c 0. Thus property 6 of Definition 1.9 is satisfied. It remains to check the distributive law to see that R is a field. The path to this is to first prove it for positive elements, then consider the several other cases. Next, we have to check that R is an ordered field (see Definition 1.12). Since c fl is easily seen to be equivalent to - c > 0, this follows from the easy observation that c + / 0 and a 0 whenever c > 0 and f] > 0. Finally, we have to prove that R is a complete ordered field. Suppose that A is any subset of R. We define sup A to be JoE, c. If A is bounded above, say c _ ' for all c 6 A, there exists M 6 Q such that < /f for all c 6 A (take any M E ). This means that a < M for every a � . every c 6 A, so UeA c/f/, i.e., sup A 6 R. It is clear that sup A is t he least upper bound of A. The existence of R is thus established. Note that if we leave out condition (c) in the definition of R, and put +oc = Q and -o = 0, we arrive at , the extended reals.  1.10 Exercises 23 Finally, we give a sketch of the proof of the uniqueness of R. If Rl and R2 are complete ordered fields, we want to show that there exists an order- preserving isomorphism of R onto R2. Let Qj be the smallest subfield of Rj (j = 1,2). Each Qj is isomorphic to the field of rational numbers Q, so there exists an isomorphism of Q l onto Q2. This isomorphism is unique, and order-preserving. We now define a map of Rl into R2 as follows: for x R, let p(x) = sup{b(q) :q ( Ql,q < x}. We note this makes sense: for any x 6 Rl, there exists M 6 Ql with M > x, and hence M > q for any q < x; then �(q) < b(M) for every q E Q1 with q < x, since b is order-preserving, so {�(q): q E Q l, q < x}.has an upper boun. d in R2, and hence a least upper bound. If x, y 6 R1 with x < y, there exists q, r 6 Ql with x < q < r < y; it follows easily that !P(x) _ b(q) < b(r) _ p(y), so p is order-preserving, and in particular is injective. It is easy to see that is surjective: given y 6 R2, let x = sup{-(q2) :q2 6 Q2,q2 < y}, and check that (x) = y. It remains to verify that is a field homomorphism, i.e., that p(x + y) = O(x) + O(Y) and �,(xy) = (x)(y) for every x, y E R. We leave this to the reader. 1.10 Exercises 1. List all the subsets of (((0))). 2. Show that a set X is infinite if and only if there exists a bijective map of X to a proper subset of X. 3. Criticize the following proof by induction of the proposition, "Happy families are all alike." Consider a set consisting of one happy family. Obvi- ously all its elements are the same. Suppose it has bccn shown that for a set of n happy families, say {f,..., f,}, we have fi = f2 = '" = f,. Consider a set { f, f2,. �., f,+. } of n + 1 happy families. Then {fi, f:,..., f, } is a set of n happy families, so f = f2 = '" = f,. Similarly, {f2, fa,..., f,+} is a set of n happy families, so f,+: = --- = f2. Thus f,+ = fi also, and the set of n + 1 happy families are all alike. By the principle of induction, we see that for any finite set of happy families, they are all alike. Since the set of all happy families is finite, we conclude: happy families are all alike. 4. (The results of this exercise will be used in later chapters.) The bino- mial coefficients () (pronounced "n choose k") are defined for nonnegative integers n and k by the formulas = k!(n - k)!' k = O, 1,...,n where O! = 1 and n! = n(n- 1)! for n = 1,2, .... We put () = 0 for .k > n.  24 1. Real Numbers (a) Show that for k = 1,2,...,n. (b) Show that k=O for any nonnegative integer n, and deduce for any a, b. (c) Find and 5. Prove by induction that for any positive integers a, b, n, -- 6. Prove, ming induction or otherwise, that __(2k - 1) = n 2 k2 = n(n + l)(2n + 1) ' 6 k=l k=l 7. Show that for each positive integer n, 1 1 1 2(v- ) < + + +... + < 2v. HINT: The identity v/k + 1 - / = (/ + 1 + v)- might be helpful. 8. Which is larger, 9950 + 10050 or 10150? Try to answer without using a calculator. 9. Show that v/ and are irrational. Better yet, show that if n N, then V is either an integer or irrational. 10. Show that if a field K has characteristic p 0, then p is a prime.  1.11 Notes 25 11. Let K -- {q + r v: q, r 6 Q}. Show that K, with the operations it inherits from R, is an ordered field with the Archimedean property. 12. The complex field C is defined to be the set R x R of all ordered pairs of real numbers, together with the operations of addition and multiplication given by the rules (a, b) + (c, d) = (a + c, b + d) and (a, b)(c, d) - (ac - bd, ad + bc). (a) Show that C is a field, having a subfield isomorphic to R. (We will denote this red, field also by R, sowing a crop of confusion that is unlikely to ever be reaped.) (b) Show that C cannot be made into an ordered field. 13. Let K be an ordered field, in which the Archincdcan property is sat- isfied. Show that if every bounded increasing sequence in K has a least upper bound in K, then K is a complete ordered field. 14. Find a bijective map from (0, 1) to R. 15. Find a bijective map from (0, 1) to [0, 1]. 16. Deduce from Theorem 1.23 the slightly stronger result: if c (E R is irrational, and M is any integer, then {nc + m: n M, rn Z} is dense in R. 17. Show that for any c R, there exist infinitely many rational numbers m/n with I - m/n[ < 1/n 2. This is a stronger, quantitative, version of the proposition that the rational mmbers are dense in R. 18. Give an exm,aplc of eaclJ of the following: (a) Nonempty intervals J, in R (n � N) which are bounded, with J,+ c J, for each n, and J = 0. (b) Nonempty intervals J in R (n N) which are closed, with J+ C J for each n, and n�= J = 0. (c) Nonempty intervals J = [a,,b,] in Q (n N) such that J,+ C J for every n, and n,__a J = 0. 1.11 Notes 1.1 For a closer look at set theory, with an introduction to cardinal and or- dinal numbers, I highly recommend Halmos [2]. An important point of view among mathematicians (in fact, the dominant one) believes that  26 I. Real Numbers the foundations of mathematics lie in set theory. From this point of view, it is natural to want to construct the .st N of natural numbers, with its order relation and algebraic structure, from a rea.sonable set of axioms for set theory. In this book, the natural numbers are taken for granted. 1.2 According to Whittaker and Watson [15], even the concept of negative number was rejected by conservative mathematician,s at surprisilgly late times. They cite authors of works on algebra, trigonometry., etc., in the latter half of the eighteenth century in which the use of nega- tive numbers was disallowed, although Descartes had used them un- restrictedly more than a hundred years before. The notations N (for nmb,r), Q (for qotient), and R (for real) sem obvisl., spcak(.rs, but Z may .sem obscure. It derives from the G(,rar Zahl, meaning number. Its use has become universal. 1.3 The ideas of countable and uncountable are due to Cantor, a.s is the whole idea of set. Theorem 1.4, for instance, is due to Cantor. The problems of infinity of course presented themselves much earlier; Galileo, for instance, discussed the apparent paradox that there are many even numbers as whole numbers, at the same time that there are only half as many. Cantor, incidentally, was not led to the creation of set theory by the desire for greater abstraction, but through his research on the convergence of trigonometric series. 1.4 The discovery of incommensurability, or rather the fact that it had gone so long undiscovered, had a great effect on Plato, for one. I quote from Toeplitz [14]: Plato puts considerable emphasis on the fundamental na- ture of this discovery. In the Laws, at the point where he assigns that mathematical discovery a place in higher school instruction, he mentions that he first learned of it when he was a comparatively old man and that he had felt ashamed, for himself and for all Greeks, of this ignorance which "befits more the level of swine than of men." (Toeplitz. Calculus: A Genetic Approach. Copyright University of Chicago Press, Chicago, 1963) 1.5 The concept of field (K6rper in German, hence the conventional K or k) seems to be due to Dedekind. Theorem 1.10 was probably first proved by Eudoxus, who dealt of course with the prevailing Greek idea of quantity, not quite (though close to) the modern idea of real num- ber. Archimedes employed it, realizing its fundamental importance, and explicitly credited Eudoxus with the theorem. Today, a reference to the property of Eudoxus, as it should be called, would only earn a blank stare.  1.11 Note 27 1.6 One inagines that the name absolute value, and the symbol Ixl, go back to an('iont times. In fact, they were introduced by Karl Weier- str.ss in 1859. 1.7 Theorem 1.27 is of fundamental significance; it could be used as the basic "completeness" property of the real numbers, instead of the "order conpleteness" that we have chosen. The uncountability of the real mnbers w. first, proveil by Cantor, who gave two different proofs at different times. We have followed his first proof; his other proof uses a different method (the so-called diagonal argument). 1.8 Theorem 1.31, ,s already mentioned, is due to Liouville (1851), who first, ,xlilit,'! a t. rasce.!ent,al mlmr (t,!.. m, give, or a close rela- tiw,), a.l I)r,lat'! lr)l)sit. i) 1.30, wlicl is lac to Cantor. Cator's argument, which does not look constructive, can be seen to "exhibit" a transcendental number; for the listing of the algebraic numbers as i tlw proof of Proposition 1.30 can be used to provide a nest-.d se- quence of closed bounded intervals (with rational endpoints) whose inter.ction contains no algebraic number. The supremum of the left endpoints of the. intervals is then a transcendental number which has bccn "exhibited" in the same sense as the one in Liouville's example. It was shown by Hermite in 1873 that e is transcendental, and by Lindemann in 1882 that r is transcendental. (The reader has heard of e and r elsewhere; we will introduce e in the next chapter, and r later.) For a proof of Hermite's theorem, see Herstein [5]. 1.9 Dedekind developed his construction of real numbers in 1858, though it was not published until 1872, the same year that Cantor published on the same subject. Dedekind declared a real number to be a division (a "Dedekind cut") of the rational numbers Q into two nonempty sets, L and R say, with the property that q <: r for every q L and r R; for convenience, we can also assume that L has no greatest element. While it must have bccn obvious from the start that in working with Dedekind cuts it sufficed to consider the left half of the cut, this artifice seems to have bccn first suggested by Bertrand Russell, better known to the world at large as a philosopher than as a mathematician. Hardy was aware of this, but preferred (in his classic calculus text [3]) to carry on with a cut being defined as two intervals of rationals.  2 Sequences and Series 2.1 Sequences In the first chapter, we defined a sequence in X to be a napping fr,,n N to X. Let us broaden this definition slightly, and allow the mapping to have a domain of the form {n E Z: m _< n <_ p}, or {n E Z: n _> m }, for some m Z (usually, but not always, m = 0 or m = 1). The most common notation is to write n: : xn instead of n: x(n). If the domain of the sequence is the finite set {m,m + 1,... ,p}, we write the sequence as (Xn)Pn=m, and speak of a finite sequence (though we emphasize that the sequence should be distinguished from the set {xn: m <_ n <_ p}). If the domain of the ,sequence is a set of the form {m, m + 1, m + 2,...} = {n Z: n _> m}, we write it as (xn)n=m, and speak of an infinite sequence. Note that the corresponding set of values {xn : n _> m} may be finite. When the domain of the sequence is understood from the context, or is not relevant to the discussion, we write simply (xn). In this chapter, we shall be concerned with infinite sequences in R. 2.1 Definition. A sequence (xn)n=m in R is said to converge to the limit x R, and w'e write xn x as n o, or limn-oo x, = x, or simply limx, = x, it'�or every > 0 there exists no N such that x--e < xn < x + for every n _> no. A sequence ,vhich does not converge to any limit in R is said to diverge. We say x, +o, or lira xn = +oo, if for every M R there ex/sts no N such that x, > M for every n >_ no, and ,re say that x -oo, or lira xn = -o, if for every M R there exists no N such that x, < M for every n _> no.  2.1 Sequences 29 Note that if x, , +o, then (x,) diverges. A simple example of a diver- gent sequence is given by putting x, -- (-1). We begin with a proposition establishing a few bmic rules for (tealing with convergent sequences. 2.2 Proposition. Suppose that (Cn) and (dn) are convergent sequences in R, say !i,.__. c,, - C and !im,_.oo d,, = D. Let a R. Then the sequences (UCn), (C, + tin), and (cd,) are all convergent, and in tact lim (acn) = aC, lim (on + d.) = C + D, lim (c,d,) -- CD. If D : O, then for some k _> m, dn : 0 for all n _> k, and (1/d)��__ converges; in fact limn_.o 1/dn = 1/D. Proof. Let ( > 0. If a 0, there exists no such that Ic -CI < /la[ for all n >_ no, and then lacn - aCI = lallcn - CI < for all n >_ no. If a = 0, this is trivial. Thus iim(ac.) = aC. There exist nl and n2 such that Ic- CI < /2 for all n _ nl and Id. - DI < /2 for all n _> n2. Let no -- max{hi, n2, and we have I(c. + d.) - (C + D)[ = I(c - C) + (d. - h)r all n _> no. Thus lim(c + dn) = C + D. Choose M mx{IC [, IDI}. Choose n so that Ic,- CI < /(2M) for all n _> n, and n2 so that Id, - DI < /(2M) and Id, - DI < M- IDI for all n _ n2. Then [dn[ '- [dn - D + D[ _ Ida, - D[ + [D[ < M for all n _ n2. For n > no = max{n, n2 ), we have [cd. - CD[ = [(c - C)d. + C(d. - D)[ . [c -C[[d.i + [C[[d. - D[ < -cl + Id. - < /2 + /2 = . Thus lim(cdn) = CD. Finally, choo, k .so that [dn - D[ [D[ for n k; it follows that Id,[ > [D[ for all n _ k. Next choo no > k so thatd. - D[ < [D[2e/2 for all n > no. We have then for n _> no 1 1 D - d. 2 = < [d- D[ < d. D d.D -IDI 2 ' Thus lim(1/dn) = lID. I This proposition will be used quite frequently in the future, usually with- out explicit citation. Another, even simpler, fact is the following:  30 2. Sequences and Series 2.3 Proposition. If ( n)n=m is a convergent sequence in R, and for some k N we have x, _ 0 for all n >_ k, then lim x, _> O. Similarly, ira <_ Xn <_ b for some a, b R and MI n _ k, then a <: lim Xn _ b. Proof. If xn _> 0 for all n >_ k, and L < 0, taking e = ILl in the definition of limit shows that L cannot be the limit of (xn). The second statement follows from the first by considering the sequences (xn - a) and (b- Xn) and applying the last proposition. 2.4 Example. Let 1 1 1 for each n E N. Suppose that (sn) converges, say lim s,, = s. It is clear from the definition of convergence that if sn , s, then also s2n , s, but we observe that I I I I 1 s2r - sn '- -'-' + '-' = n- 1 2n n n ' so we would have @ = lim(s2n - Sn) _ 1/2, using the last two propositions. This contradiction shows that (Sn) does not converge. The next proposition presents a few examples of convergent sequences. We will use two simple inequalities, which can be proved directly by induc- tion on n, or (for t _ 0) seen immediately from the binomial theorem. 2.5 Lemma. For every real t > -1, and every n N, we have (1 + t)" _ 1 + at, (1 + t) n _ 1 + at + �n(n - 1)t2; when t O, the inequalities are strict for n > 1, n > 2, respectively. The proof is left as an exercise. 2.6 Proposition. //a > 0, then na , +2 as n , x), and a/n , 0 .s n , c; ifs > 1, then a n , +c, and ifO < b < 1, then b n , O, as n , c. If a O, then lim._.o a 1/n = 1. Finally, lim.-.oo n 1/n = 1. Proof. That na , +c as n , c is simply a rephrasing of the Archimed- can property of R,.i.e., of Theorem 1.19. If > 0, then Theorem 1.19 asserts the existence of no such that n0 > a, and hence n a for all n _ no, which gives 0 < a/n < for all n _ no, limn...(a/n) = O. Ira 1, let 6 -a-l, so6 0; thena n = (1+6) ' l+n,soa ' , +2 since n6 , +c. If 0 b < 1, let a = l/b, so a 1. If ) 0, then there exists no such that a ) 1/ for n _ no, which is equivalent to 0 < b n for n _ no, so lim_. b - 0.  2.1 Sequence 31 For n > 1, let bn = n 1" - 1; clearly, b, > O. Then n = (1 + 6n)" > 1 + n6. + n(n- 1)6 > -n(n- 1)6, from which we conclude that 0 < 52, < 2/(n- 1). Given e > 0, choose no N with no > 1 + 2/e 2. Then 1 < n /" < 1 + [2/(n- 1)] /2 < 1 + e for _ n l/" = 1 every n > no. Thus iimn-.oo � If a _> 1, then 1 _< a l/n _< n /' for every n > a, so lima /" = 1. Finally, if 0 < a < 1, let b = l/a, so lima /" = 1/limb /n = 1. 2.7 Example. Fix the integer b _ 2, and x R, 0 _ x < 1. Define d = [bx], so d is an integer with 0 _ d < b, and put x = d/b, so () _<' .r � l/b; having ol)tainod sucl itegers d,...,d, and numbers x x so that 0 < x-x < b - we proc to t d+ = [b+(x-x)] and zn+ = + dn+b --, that inductively we obtn a uence such that 0 < x- Xn < b -n where eh dn is an element of (d.).=, _ , {0, 1,..., b - 1 } and x, = dib- + d2b -2 +.-- + dnb -n. If x = x, for me n, then d = 0 for all m > n. We write symbolicMly x ---- 0.did2..., where each dj is an integer, 0 _< dj < b, to mean that the sequence (xk), where xk = d b- +--. + d,b -, converges to x. This is called a representa- tion, or expansion, of x in the base b. When b = 10 this is called the decimal expansion, when b = 2 the binary expansion, when b--- 16 the hexadecimal expansion. We have seen that any x e [0, 1) admits a representation in any base b. We observe that if x is a rational that can be expressed in the form p/b" for some integers p and n, there exist two representations of x in the base b; one has the form 0.dd2... dn000..., and the other looks like 0.d d2... (d, - 1) (b - 1) (b - 1) (b - 1) .... The above procedure produces the "terminating" expansion, when there is a choice, e.g., with b --- 10 the expansion of x = - is 0.5000... rather than 0.4999 .... If x does not have the form p/b", the expansion is unique. We leave this fact as an exercise. 2.8 Example. Theorem 1.25 demonstrates that every positive real num- ber has a square root, but does not show how to find it. Indeed, what does it mean to "find" V, for instance? We know it is not a rational number. We have seen that each real number has a decimal expansion, so one answer to the question would be to display the decimal expansion of /, perhaps by finding an explicit formula for the integer dn in the nth place after. the dec- imal point, or perhaps by finding an inductive procedure for determining d,. Now we can interpret the truncated finite decimal expansions as being a sequence of rational numbers which converge to the number represented by the infinite decimal expansion. Any other sequence of rational numbers converging to v would be just as good in principle, and possibly better in  32 2. Sequences and Series practice, in that the nth term in the sequence might be much closer to than the decimal fraction 1.dd2... dn. Here is one such sequence, which represents the oldest known method for computing square roots. Given a > 0, we define a sequence (xn) inductively, as follows. Choose x0 > 0 and let x,+ = (x. +a/x.) for n _> 0. It is clear from the definition ' (x + ,,/x) of convergence that if x. , x, then also xn+ , x, so that x = , or 2x 2 = x 2 + a, that is x 2 = a. It is also clear that x. > 0 for all n, so x _> 0: thus x = v. To show that in fact (xn) does converge, we calculate as follows: 2 > a for every n 1. In particular, we see that xn+ >_ for all n, and x. _ _ Similarly, we find that � - � + + By induction, it follows that for every n Now Ix0 - vl < x0 + V, since x0 > 0 nd V > 0. Thus equation (2.1) implies that x. , V as n , x), and indeed, that the convergence is quite rapid. We note incidentally that so that x.+ <_ x, for 11 n _> 1. In prticular, Xn + V <_ x + _< 2x for every n >_ 1. From this, and equation (2.1), we can write down the estimate 0 <_ x.- v <_ 2x x-- ' (2.2) Thus this method seems to be a highly efficient method for calculating square roots to any given degree of accuracy. For instance, with a = 10, we might take a rough first guess x0 = 3. We see easily that 3 < v0 < 3.5,  2.1 Sequence 33 [xo - v/'[ < 1/2, and xo + vf > 6. Thus the timate (2.2) gives us (after we calcfiate 2x = 19/3 < 7) 0 < Xn -- f < 7- 12 -2" Thus x4 approximates vf0 to an accuracy better than 10-15, which should be good enogh for household use. 2.9 Definition. Let (a,) be a sequence in R. We say that (a,) is an in- crea.sing seqmnce if a,, <_ a,,+ for all n; we call it strictly increasing if an < a,+ for all n. Similarly, (an) is called decreasing (or strictly de- crea.ing) if a, _> a,,+ (resp., a,, a,,+ ) for all n. A sequence is called monotone if it is either increasing or decreasing. 2.10 Proposition. If (an)n�e__m is an increasing sequence in R, then either (an) is convergent, or an Proof. If (a,) is not bounded above, for every M there exists k such that an > M; since (a,,) is increasing, we have a,, _> an > M for every n > k. Thus a,, , o a.s n , oo. Suppose (a,) is bounded above; then there exists a lea.st upper b(nmd M for the set { a,: n m}. Given any > 0, M- e is not an upper tonl for {a,, � n m. Ths there exists k with a > 1 -; since {an) is incremsing, it follows that M- < an AI for every n k. Thus, an , M ms n , . I 2.11 Corollary. If (a,) is a decreasing sequence in R, then either (an) is convergent, or (a,,) , -c as n , c. Thus every bounded monotone sequence converges. 2.12 Example. Let c,, = (1 + l/n) n for each n ( N. Then (On) is an inctea.sing sequence. One way to see this is to recall the identity b - a = (b - a)(b - + b-2a +... + ba -2 + a -l) valid for any a, b ( R (or any field) and any positive integer r, which we used to advantage in the first chapter. It gives the inequality b r < a r -{- r(b- a)b - (2.3) whenever 0 < a < b. Taking a = 1 + 1/(n + 1), b = 1 + l/n, and'using r = n + 1 in the inequality (2.3), we get 1 ) bn+ 1 an+ 1 (n + 1)b n 1  34 2. Sequences and Series from which c ( c+ follows at once. Furthermore, the sequence (c,,) is bounded; in fact, taking a = 1 and b = 1 + 1/(2n) with r = n in the inequality (2.3), we get ( 1) n 1 ( 1) n-I 1( 1) n 1- n <l+nn n l+2n <1+ 14 2-n ' from which we get 1 + 2n < 2, so c2, < 4. Since (c) is an increasing sequence, it follows that cn < 4 for all n. Hence, by Proposition 2.10 it follows that (c) converges. We denote the limit by e. We have not seen the last of this number. The notion of subsequence is fairly natural, but let us give a formal definition. 2.15 Definition. A sequence (bn)n��__p is said to be a subsequence of the sequence (an),��= m if there exists a strictly increasing sequence (nk)�=p in Z, such that bk = ank for every k _ p. Let (an)n=k be a bounded sequence. For each m > k, let us set bm= supn_> m an = sup{am, am+i, a,+2,...}. Clearly, (bm)m=k is a decreasing sequence; each bm 6 R since (an) is bounded above, and the sequence (bin) is bounded below, since the sequence (an) is bounded below. By the Corollary above, the sequence (bn) is convergent; we call this limit the limes superior, or upper limit, of the sequence (an). The limes inferior or lower limit is defined in an analogous way. If (an) is not bounded above, we put its upper limit to be +c, and if it is not bounded below, its lower limit is said to be -oo. We summarize: 2.14 Definition. If (an)n��__/s any sequence in R, we define limsupan = inf sup an = lim sup an liminfan - sup inf an -- lim inf an One often sees the symbol lim used for lim sup, and lim for lim inf. We can describe the upper and lower limits also in the following way: 2.15 Proposition. Let (an) be a sequence in R. The following are equiv- alent: (a) limsupa, = A; and (b) for every A' > A, an < A' for all but tinitely many n; for every A" < A, an > A" for infinitely many n.  2.1 Sequences 35 Proof. Suppose A = limsupa,. Then for any A' > A, there exists m such that sup,>,, an < A', so, in particular, an < A' for all n _ m. But since supn>, an _> A for every m, it follows that if A" < A, then for every m thereexists n _> m with an > A". Thus (a) implies (b). Now suppose (b) holds. Then for every A > A, there exists m such that an < A' for all n m, and hence supn>m a, _ A'; it follows that limsupan <_ A for every A' > A, and hence that limsupan <_ A. On the other hand, for any A" < A, (b) assures us that for every m there exists n >_ m with an > A". It follows that for every m, supn>, a, > A", and hence that lim sup an _> A". Since this holds for every A'r< A, it follows that limsupan _> A. Thus limsupan = A. We have proved (b) implies (a). [ We leave it to the reader to fernrelate and prove the corresponding char- acterization of the lower limit. Some of the basic properties of the upper and lower limits are summarized in the next proposition. 2.16 Proposition. If (an) and (bn) are sequences in R, then: (a) lim sup(-an) = - lim inf an; (b) limsupca,, = climsupan for any c > 0; (c) limsup(an + bn) _< limsupan + limsupbn; (d) lim inf an _ lim supan, with equality if srid only if(an) is convergent, in which case viim sup an = lim an; and (e) if (bn) is a subsequence of (an), then lim inf an _< lim inf bn _< lim sup bn _< lim sup an. The proof of this proposition is left as an exercise. 2.17 Theorem. Every bounded .sequence in R has a convergent subse- quence. Proof. Let (a) be a bounded sequence in R. Let A = lim sup an. We shall construct a subsequence of (an) which converges to A. By Proposition 2.15 there exists nl such that an > A- 1. Having obtained n < n2 < ... < n such that an > A-1/j for j = 1, 2,... ,k, we can find (by Proposition 2.15) n+l > n such that an+ > A- 1/(k + 1), thus defining the subsequence (an) inductively. We have A <_ lira inf an _< lira sup an _< lim sup a. = A, so lim an~ = A. This very important theorem is known as the Bolzano-Weierstrass the- orem. Of court, we could equally well have constructed a sutxsequence converging to B = liminfa,. According to Proposition 2.16(e), any con- vergent subsequence would have a limit between A and B.  36 2. Sequences and Series 2.18 Definition. Let (an) be a sequence in R. We say that (a,) is a Cauchy sequence if for every e > 0 there exists no such that [an - a, I < for every n, m >_ no. The next result is known as the Cauchy criterion for convergence. 2.19 Theorem. A sequence in R is convergent if and only if it is a Cauchy sequence. Proof. Suppose (a,) converges to A 6 R. Then for every > 0, there exists no such that lan - AI < e/2 for every n _ no. Then for every n, m _ n. we have lan - a.nl =!an - A + A - a.,l _ lan - AI + [am -- AI < , so (an) is a Cauchy sequence. Less trivial is the converse. If (an) is a Cauchy sequence, then for each ) 0 there exists no such that lan - a,l < for every n _ no, m _ no. Then an,, - < an < ano+ whenever n _> no, so a o - < inf an < lim inf a < lim sup a, < sup a, < ano + (, n _ no n _ no which gives lim sup a, - lim inf an _< 2. Since > 0 was arbitrary, it follows that lim sup a = lim inf a, so (a) is convergent. 2.2 Continued Fractions This section is not needed for subsequent developments, and may be omit- ted in a first reading. Let 6n be an integer, and let an � N for each n 6 N. The expr.ssin 1 a0 + 1 al + aa +-.. 1 + an is called a continued fraction of order n; we shall denote it more concisely as [a0; a 1,..., an]. Such an expression makes sense more generally if aj are any real numbers, as long as a : 0 for j > 0. We call [a0;al, aa,...] an infinite continued fraction; it denotes the sequence of continued fractions of order n described above. We obtain an explicit representation of the finite continued fractions as quotients of integers as follows. Define sequences (p,) and (qn) by putting p_ = 1, q_ = 0, P0 = a0, q0 = 1, and define inductively for n >_ 1 Pn = a,p,_ + Pn- 2, (2.4) qn = an qn - l + qn- 2, (2.5)  2.2 Continued Fractions 37 so that each pn and qn is a positive integer when each an is a positive integer� We observe that Po Pl alao+ 1 1 -- So, = = aO d- qo ql al d- 0 and indeed we have in general: 2.20 Lemma. For every n _ O, and any positive rems al, a2,..., an, Pn = [ao;al, a2,...,an]. qn Proof. We just observed the formula holds for n = 0 and n = 1. Assume it holds for a particular n. Then [ao;al,...,an,an+l] = [ao;a,...,an-,an + 1/an+] (an + 1/an+)pn- + Pn-2 (an + 1/an+)qn- + qn-2 Pn + Pn- / an+ 1 an+ l Pn d- Pn- 1 qn + qn-/an+l an+lqn + qn- Pn+l qn+l completing the induction. 2.21 Lemma. For each n _> O, we have Pn-lqn --qn-lPn = (-1) n. Proof. Using the defining equations, we have Pn-iqn - qn-iPn = pn-l(anqn- + qn-2) - qn-l(anpn-I + Pn-2) = -(Pn-2qn- 1 -- qn-2Pn- ) = (-1)n(p-qo- q-P0)= (-1) n- 2.22 Corollary. ff an N for each n, then the positive integers pn and qn have no common divisor greater than 1. 2.23 Corollary. For each n _ 1, Pn Pn- 1 1 qn qn- 1 qn qn- 1 2.24 Lemma. ff a, N for each n, then qn > (v) n- 1 for each n > O.  38 2. Sequences and Series Proof. Since q. = anqn-I + q.-2 and an _ 1, it follows that q. :> q._ for all n, and hence that qn > 2qn-2. Iterating this estimate, we arrive at q2n > 2"q0 = 2 n, and q2n+l > 2"ql _ 2 n, and the lemma follows. oo in N, and any ao Z the 2.25 Theorem. For any sequence (an)n=! , infinite continued fraction In0; a, a2,...] converges. Proof. By Corollary 2.23 and Lemma 2.24, we see that Pn + 1 Pn 1 = ( 2-(n- 1), qn + 1 qn qn + I qn which implies that (Pn/qn) is a Cauchy sequence, hence conw?rgent. 2.26 Theorem. For every irrational real number x, there exists a uniqw infinite continued fraction which converges to x. Proof. Let a0 = [x], the greatest integer not greater than x, so 0 1. Define r = (x - a0) -, so ra > 1, and let aa = Ifil, so a is a positive integer. tlaving defined rn and an = [rn], we define put a., = [rn+a]. Since x is irrational, we see that every r. is irrational, so 0 < r. - an < 1, and rn+! is well-defined, with rn+! > 1. Now x = [ao;a,a2,...,an_l,rn] (2.6) for every n > 1. Indeed, x = a0 .9 1/r - [a0;r], and if the formula (2.6) holds for some n, then using rn - an .9 1/r,+, we get equation (2.6) with n replaced by n .9 1, so that (2.6) holds for all n. Now from equation (2.6) and Lemma 2.20 we have rnPn- 1 '9 Pn- 2 rnqn-I '9 qn-2 for n _ 2. Correspondingly, we have the formula Pn anpn-I '9 Pn-2 qn an qn- + qn- 2 so we have, after simplifying, Pn (rn - an) n- %-2 - qn- Pn- 2) qn (rnqn-! + qn-2)(anqn-! + qn-2) so that Pn I 1 x <: qn q2n 2 n-l' the last inequality coming from Lemma 2.24. Thus, p./q. , x, and the existence is proved. To show uniqueness, suppose that we had two continued fraction representations X ---- ; al , a2, . . . -- ao, al , a 2, ....  2.3 Infinite Series 39 Clearly, ao = a = Ix]. Suppose that we have established a = a'. for j = 0, 1,..., n. Then (with an obvious notation) pj = p and qj q for 0 _< j _< n as well. Putting rk = [ak;a+,a+2,...], with the analogous definition of r, we have x = ;al,a2, � � � ,an,rn+l ---- ao;al,a 2, � � � ,an,m+ 1 , so that we have I I I pnrn+l d' Pn-1 Pnrn+l d' Pn-I pnrn+l d' Pn-I qnrn+l + qn-! qnrn+! + ' ' qn- 1 1 qn rn + d' qn- 1 = r' and hence from which we can .,lve to get r.+l .+, ' for all n. Jr'.+ 1] = a',,+a. Thus a,, = a. It is not hard to see that if x was rational, the process described ibove would terminate after finitely many steps, and x would be represented by a finite continued fraction. Note that Theorems 2.25 and 2.26 establish a one-to-one cor- respondence between the set of irrational numbers in (0, 1) and the set N N of mappings of N into N. But we also have seen (the binary expansion) that there is an injective mapping of the irrational numbers in (0, 1) into the set 2 N of mappings of N into {0, 1 . Thus there is an injective mapping of N into 2 m. 2.3 Infinite Series Given a sequence (a.).__. in R, consider the associated sequence (s.).�__. defined by $n --' am d' arn+l d' ''' d' an -' k----m the number s. is called the nth partial sum of the infinite series and we say that the series converges if the sequence (s.) converges. If limn-,oo Sn s, we write oo = n=m an = s. (Actually, this is an abuse of language, since, properly, n��__m an denotes the sequence (sn)n��__m, rather than its limit.) We also write Zn=m an = 4-00 if limn-.oo s. = 4-00. Thus the notion of infinite series is totally equivalent to that of infinite sequence; given any sequence (sn) �� we can realize it as the sequence of partial sums of the series oo n=,. an, where a,. = s,. and an = sn- sn- for n > m. We shall often omit the limits of summation, i.e., write an instead of n=m an, when m is either understood from the context or irrelevant. 2.27 Proposition. If an converges, then lim an = 0.  40 2. Sequences and Series Proof. If sn denotes the nth partial

Andrew Browder Mathematical Analysis An Introduction Pdf

Source: https://3lib.net/book/1176920/cf031b

Posted by: barberfolve1970.blogspot.com

Share this post