Real Mathematical Analysis Charles Chapman Pugh Pdf

Real mathematical analysis

Pugh C.C.

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?

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.

Charles Chapman Pugh REAL MATHEMATICAL ANALYSIS Springer  Charles Chapman Pugh Real Mathematical Analysis With 133 Illustrations Springer  Charles Chapman Pugh Mathematics Department University of California at Berkeley Berkeley, CA 94720-3840 USA Editorial Board S. Axler Mathematics Department San Francisco State University San Francisco, CA 94132 USA F.W. Gehring Mathematics Department East Hall University of Michigan Ann Arbor, MI 48109 USA K.A. Ribet Mathematics Department University of California, Berkeley Berkeley. CA 94720-3840 USA Mathematics Subject Classification (2000): 26-01 Library of Congress Cataloging-in-Publication Data Pugh, C.C. (Charles Chapman), 1940- Real mathematical analysis/Charles Chapman Pugh. p. cm. — (Undergraduate texts in mathematics) Includes bibliographical references and index. ISBN 0-387-95297-7 (alk. paper) 1. Mathematical analysis. I. Title. II. Series. QA300.P994 2001 515- dc21 2001032814 Printed on acid-free paper. © 2002 Springer-Verlag New York. Inc. All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer-Ver lag New York, Inc., 175 Fifth Avenue, New York, NY 10010, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed is forbidden. The use of general descriptive names, trade names, trademarks, etc., in this publication, even if the former are not especially identified, is not to be taken as a sign that such names, as understood by the Trade Marks and Merchandise Marks Act, may accordingly be used freely by anyone. Production managed by Michael Koy; manufacturing supervised by Erica Bresler. Formatted from the author's WT^K.2e files by T^Xniques, Inc., Cambridge, MA. Printed and bound by Maple-Vail Book Manufacturing Group, York, PA. Printed in the United States of America. ; 987654321 ISBN 0-387-95297-7 SPIN 10838675 Springer-Verlag New York Berlin Heidelberg Λ m.ember of BertelsmannSpringer Science+Business Media GmbH  To the students who have encouraged me — especially A.W., D.H., and M.B.  Preface Was plane geometry your favorite math course in high school? Did you like proving theorems? Are you sick of memorizing integrals? If so, real analysis could be your cup of tea. In contrast to calculus and elementary algebra, it involves neither formula manipulation nor applications to other fields of science. None. It is pure mathematics, and [ hope it appeals to you, the budding pure mathematician. Berkeley, California, USA Charles Chapman Pugh  Contents 1 Real Numbers 1 1 Preliminaries 1 2 Cuts 10 3 Euclidean Space 21 4 Cardinality 28 5* Comparing Cardinalities 34 6* The Skeleton of Calculus 36 Exercises 40 2 A Taste of Topology 51 1 Metric Space Concepts 51 2 Compactness 76 3 Connectedness 82 4 Coverings 88 5 Cantor Sets 95 6* Cantor Set Lore 99 7* Completion 108 Exercises 115  χ Contents 3 Functions of a Real Variable 139 1 Differentiation 139 2 Riemann Integration 154 3 Series 179 Exercises 186 4 Function Spaces 201 1 Uniform Convergence and C°[a, b] 201 2 Power Series 211 3 Compactness and Equicontinuity in C° 213 4 Uniform Approximation in C° 217 5 Contractions and ODE's 228 6* Analytic Functions 235 7* Nowhere Differentiable Continuous Functions 240 8* Spaces of Unbounded Functions 248 Exercises 251 5 Multivariable Calculus 267 1 Linear Algebra 267 2 Derivatives 271 3 Higher derivatives 279 4 Smoothness Classes 284 5 Implicit and Inverse Functions 286 6* The Rank Theorem 290 7* Lagrange Multipliers 296 8 Multiple Integrals 300 9 Differential Forms 313 L0 The General Stokes' Formula 325 11* The Brouwer Fixed Point Theorem 334 Appendix A: Perorations of Dieudonne 337 Appendix В: The History of Cavalieri's Principle 338 Appendix C: A Short Excursion into the Complex Field 339 Appendix D: Polar Form 340 Appendix E: Determinants 342 Exercises 345  Contents xi 6 Lebesgue Theory 363 1 Outer measure 363 2 Measurability 367 3 Regularity 371 4 Lebesgue integrals 376 5 Lebesgue integrals as limits 383 6 Italian Measure Theory 387 7 Vitali coverings and density points 391 8 Lebesgue's Fundamental Theorem of Calculus 396 9 Lebesgue's Last Theorem 401 Appendix A: Translations and Nonmeasurable sets 407 Appendix В: The Banach-Tarski Paradox 409 Appendix C: Riemann integrals as undergraphs 409 Appendix D: Littlewood's Three Principles 411 Appendix E: Roundness 412 Appendix F: Money 413 Suggested Reading 414 Bibliography 415 Exercises 417 431  1 Real Numbers 1 Preliminaries Before discussing the system of real numbers it is best to make a few general remarks about mathematical outlook. Language By and large, mathematics is expressed in the language of set theory. Your first order of business is to get familiar with its vocabulary and grammar. A set is a collection of elements. The elements are members of the set and are said to belong to the set. For example, N denotes the set of natural numbers, 1, 2, 3, The members of N are whole numbers greater than or equal to 1. Is 10 a member of N? Yes, 10 belongs to N. Is π a member of N? No. Is 0 a member of N? No. We write χ e A and у ф В to indicate that the element χ is a member of the set A and у is not a member of B. Thus, 6819 € N and y/l φ N. We try to write capital letters for sets and small letters for elements of sets. Other standard sets have standard names. The set of integers is denoted by Z, which stands for the German word zahlen. (An integer is a positive  2 Real Numbers Chapter 1 whole number, zero, or a negative whole number.) Is y/2 e Z? No, л/2 ^ Z. How about -15? Yes, -15 e Z. The set of rational numbers is called Q, which stands for "quotient." (A rational number is a fraction of integers, the denominator being nonzero.) Is л/2 a member of Q? No, \/2 does not belong to Q. Is π a member of Q? No. Is 1.414 a member of Q? Yes. You should practice reading the notation "{jc e A :" as "the set of χ that belong to Λ such that." The empty set is the collection of no elements and is denoted by 0. Is 0 a member of the empty set? No, 0^0. A singleton set has exactly one member. It is denoted as {x} where χ is the member. Similarly if exactly two elements χ and у belong to a set, the set is denoted as {x. y]. If Л and В are sets and each member of Л also belongs to В then Л is a subset of В and Л is contained in B. We write1 А С В. Is N a subset of Z? Yes. Is it a subset of <Q>? Yes. If A is a subset of В and В is a subset of C, does it follow that Л is a subset of C? Yes. Is the empty set a subset of N? Yes, 0 С N. Is 1 a subset of N? No, but the singleton set {1} is a subset of N. Two sets are equal if each member of one belongs to the other. Each is a subset of the other. This is how you prove two sets are equal: show that each element of the first belongs to the second, and each element of the second belongs to the first. The union of the sets A and В is the set A U B4 each of whose elements belongs to either A, or to B, or to both A and to B. The intersection of A and В is the set Α Π Β each of whose elements belongs to both A and to B. If Α Π Β is the empty set then A and В are disjoint. The symmetric difference of A and В is the set Α Δ Β each of whose elements belongs to A but not to B, or belongs to В but not to A. The difference of A to β is the set A \ В whose elements belong to A but not to B. See Figure 1. A class is a collection of sets. The sets are members of the class. For example we could consider the class £ of sets of even natural numbers. Is the set {2, 15} a member of £? No. How about the singleton set {6}? Yes. How about the empty set? Yes, each element of the empty set is even. When is one class a subclass of another? When each member of the former belongs also to the latter. For example the class Τ of sets of positive integers divisible by 10 is a subclass of £, the class of sets of even natural ' When some mathematicians write А С В ihey mean that Λ is a subset of B, but Α Φ Β. We do not adopt this convention. We accept А С A.  Section 1 Preliminaries 3 Figure 1 Venn diagrams of union, intersection, and differences. numbers, and we write Τ С S. Each set that belongs to the class Τ also belongs to the class £. Consider another example. Let S be the class of singleton subsets of N and T> be the class of subsets of N each of which has exactly two elements. Thus {10} e S and {2, 6} e V. Is S a subclass of VI No. The members of S are singleton sets and they are not members of V. Rather they are subsets of members of V. Note the distinction, and think about it. Here is an analogy. Each citizen is a member of his or her country - I am an element of the USA and Tony Blair is an element of the UK. Each country is a member of the United Nations. Are citizens members of the UN? No, countries are members of the UN. In the same vein is the concept of an equivalence relation on a set S. It is a relation s ~ s' that holds between some members s, s' e S and it satisfies three properties: For all s, s\ s" e S (a) s ~ s. (b) s ~ s' implies that s' ~ s. (c) s ~ s' ~ s" implies that s — s". The equivalence relation breaks S into disjoint subsets called equivalence classes1 defined by mutual equivalence: the equivalence class containing s consists of all elements s' e S equivalent to s and is denoted [s]. The element s is a representative of its equivalence class. See Figure 2. Think again of citizens and countries. Say two citizens are equivalent if they are citizens of the same country. The world of equivalence relations is egalitarian: I represent my equivalence class USA just a s much as does the President. Truth When is a mathematical statement accepted as true? Generally, mathematicians would answer "Only when it has a proof inside a familiar mathematical ' The phrase "equivalence class" is standard and widespread, although it would be more consistent with the idea that a class is a collection of sets to refer instead to an "equivalence set." <o  4 Real Numbers Chapter 1 Figure 2 Equivalence classes and representatives. framework." A picture may be vital in getting you to believe a statement. An analogy with something you know to be true may help you understand it. An authoritative teacher may force you to parrot it. A formal proof, however, is the ultimate and only reason to accept a mathematical statement as true. A recent debate in Berkeley focused the issue for me. According to a math teacher from one of our local private high schools, his students found proofs in mathematics were of little value, especially compared to "convincing arguments." Besides, the mathematical statements were often seen as obviously true and in no need of formal proof anyway. I offer you a paraphrase of Bob Osserman's response. But a convincing argument is not a proof. A mathematician generally wants both, and certainly would be less Likely to accept a convincing argument by itself than a formal proof by itself. Least of all would a mathematician accept the proposal that we should generally replace proofs with convincing arguments. There has been a tendency in recent years to take the notion of proof down from its pedestal. Critics point out that standards of rigor change from century to century. New gray areas appear all the time. Is a proof by computer an acceptable proof? Is a proof that is spread over many journals and thousands of pages, that is too long for any one person to master, a proof? And of course, venerable Euclid is full of flaws, some filled in by Hubert, others possibly still lurking.  Section 1 Preliminaries 5 Clearly it is worth examining closely and critically the most basic notion of mathematics, that of proof. On the other hand, it is important to bear in mind that all distinctions and niceties about what precisely constitutes a proof are mere quibbles compared to the enormous gap between any generally accepted version of a proof and the notion of a convincing argument. Compare Euclid, with all his flaws to the most eminent of the ancient exponents of the convincing argument — Aristotle. Much of Aristotle's reasoning was brilliant, and he certainly convinced most thoughtful people for over a thousand years. In some cases his analyses were exactly right, but in others, such as heavy objects falling faster than light ones, they turned out to be totally wrong. In contrast, there is not to my knowledge a single theorem stated in Euclid's Elements that in the course of two thousand years turned out to be false. That is quite an astonishing record, and an extraordinary validation of proof over convincing argument. Here are some guidelines for writing a rigorous mathematical proof. See also Exercise 0. 1. Name each object that appears in your proof. (For instance, you might begin your proof with a phrase, "consider a set X, and elements jc, у that belong to X," etc.) 2. Draw a diagram that captures how these objects relate, and extract logical statements from it. Quantifiers precede the objects quantified; see below. 3. Proceed step-by-step? each step depending on the hypotheses, previously proved theorems, or previous steps in your proof. 4. Check for "rigor": all cases have been considered, all details have been tied down, and circular reasoning has been avoided. 5. Before you sign off on the proof, check for counter-examples and any implicit assumptions you made that could invalidate your reasoning. Logic Among the most frequently used logical symbols in math are the quantifiers V and 3. Read them always as "for each" and "there exists." Avoid reading V as "for all," which in English has a more inclusive connotation. Another common symbol is =>. Read it as "implies."  6 Real Numbers Chapter 1 The rules of correct mathematical grammar are simple: quantifiers appear at the beginning of a sentence, they modify only what follows them in the sentence, and assertions occur at the end of the sentence. Here is an example. (1) For each integer η there is a prime number ρ which is greater than n. In symbols the sentence reads VneZ Эр e Ρ such that ρ > n, where Ρ denotes the set of prime numbers. (A prime number is a whole number greater than 1 whose only divisors in N are itself and 1.) In English, the same idea can be re-expressed as (2) Every integer is less than some prime number or A prime number can always be found which is greater than any given integer. These sentences are correct in English grammar, but disastrously WRONG when transcribed directly into mathematical grammar. They translate into disgusting mathematical gibberish: (WRONG 2) VneZn<p3peP (WRONG 3) Эр e Ρ ρ > η Wn e Ζ. Moral Quantifiers first and assertions last. In stating a theorem, try to apply the same principle. Write the hypothesis first and the conclusion second. See Exercise 0. The order in which quantifiers appear is also important. Contrast the next two sentences in which we switch the position of two quantified phrases. (4) (Vn e N) (Vm e N) (Эр e P) such that (nm < /?). (5) (Vn e N) (Эр e P) such that (Vm e N) (nm < p). (4) is a true statement but (5) is false. A quantifier modifies the part of a sentence that follows it but not the part that precedes it. This is another reason never to end with a quantifier.  Section 1 Preliminaries 7 Moral Quantifier order is crucial. There is a point at which English and mathematical meaning diverge. It concerns the word "or." In mathematics "a or fe" always means "a or b or both a and fc," while in English it can mean "a or b but not both a and fe." For example, Patrick Henry certainly would not have accepted both liberty and death in response to his cry of "Give me liberty or give me death." In mathematics, however, the sentence "17 is a prime or 23 is a prime" is correct even though both 17 and 23 are prime. Similarly, in mathematics a =^ b means that if a is true then b is true but that b might also be true for reasons entirely unrelated to the truth of a. In English, a =^ b is often confused with b => a. Moral In mathematics, "or" is inclusive. It means and/or. In mathematics, a => b ik not the same as b =^ a. It is often useful to form the negation or logical opposite of a mathematical sentence. The symbol ~ is usually used for negation, despite the fact that the same symbol also indicates an equivalence relation. Mathematicians refer to this as an abuse of notation. Fighting a losing battle against abuse of notation, we write -· for negation. For example, if m, η e N then -*(m < n) means it is not true that m is less than n. In other words —>(m < n) = m > n. (We use the symbol = to indicate that the two statements are equivalent.) Similarly, -*(x e A) means it is not true that χ belongs to Λ. In other words, -■(jc € A) = χ φ A. Double negation returns a statement to its original meaning. Slightly more interesting is the negation of "and" and "or." Just for now, let us use the symbols & for "and" and ν for "or." We claim (6) -.(a &b) = -я ν -.fc. (7) -i(avfe) = ^a&^b. For if it is not the case that both a and b are true then at least one must be false. This proves (6), and (7) is similar. Implication also has such interpretations: (8) a => b = --Α <<= -«& = -чя ν b.  8 Real Numbers Chapter 1 (9) -«(a =* b) = a& Чэ. What about the negation of a quantified sentence such as -»(Vn 6 N, 3/7 6 Ρ such that η < p). The rule is: change each V to 3 and vice versa, leaving the order the same, and negate the assertion. In this case the negation is 3n e N, V/7 e Ρ, η > p. In English it reads "There exists a natural number n, and for all primes /?, η > /7." The sentence has correct mathematical grammar but of course is false. To help translate from mathematics to readable English, a comma can be read as "and" or "such that." All mathematical assertions take an implication form a => b. The hypothesis is a and the conclusion is b. If you are asked to prove a => b, there are several ways to proceed. First you may just see right away why a does imply b. Fine, if you are so lucky. Or you may be puzzled. Does a really imply bl Two routes are open to you. You may view the implication in its equivalent contrapositive form —*a <= —*b as in (8). Sometimes this will make things clearer. Or you may explore the possibility that a fails to imply b. If you can somehow deduce from the failure of a implying b a contradiction to a known fact (for instance if you can deduce the existence of a planar right triangle with legs x, у but x2 + у2 ф h2 where h is the hypotenuse) then you have succeeded in making an argument by contradiction. Clearly (9) is pertinent here. It tells you what it means that a fails to imply b, namely that a is true and, simultaneously, b is false. Euclid's proof that N contains infinitely many prime numbers, is a classic example of this method. The hypothesis is that N is the set of natural numbers and that Ρ is the set of prime numbers. The conclusion is that Ρ is an infinite set. The proof of this fact begins with the phrase "Suppose not." It means: suppose, after all, that the set of prime numbers Ρ is merely a finite set, and see where this leads you. It does not mean that we think Ρ really is a finite set, and it is not a hypothesis of a theorem. Rather it just means that we will try to find out what awful consequences would follow from Ρ being finite. In fact if Ρ were1 finite then it would consist of m 'In English grammar, the subjunctive mode indicates doubt, and I have written Euclid's proof in that form - "if Ρ were finite" instead of "if Ρ is finite," "each prime would divide N evenly," instead of "each prime divides N evenly," etc. At first it seems like a fine idea to write all arguments by contradiction in the subjunctive mode, exhibiting clearly their impermanence. Soon, however, the subjunctive and conditional language becomes ridiculously stilted and archaic. For consistency then, as much as possible, use the present tense.  Section 1 Preliminaries 9 numbers ρ γ, ..., pm. Their product TV = 2 · 3 - 5 pm would be evenly divisible (i.e., remainder 0 after division) by each pt and therefore N + 1 would be evenly divisible by no prime (the remainder of pi divided into N -\-l would always be 1), which would contradict the fact that every integer > 2 can be factored as a product of primes. (The latter fact has nothing to do with Ρ being finite or not.) Since the supposition that Ρ is finite led to a contradiction of a known fact, prime factorization, the supposition was incorrect, and Ρ is, after all, infinite. Afficionados of logic will note our heavy use here of the "law of the excluded middle," to wit, that a mathematically meaningful statement is either true or false. The possibilities that it is neither true nor false, or that it is both true and false, are excluded. Metaphor and Analogy In high school English, you are taught that a metaphor is a figure of speech in whfch one idea or word is substituted for another to suggest a likeness or similarity. This can occur very simply as in "The ship plows the sea." Or it can be less direct, as in "his lawyers dropped the ball." What give a metaphor its power and pleasure are the secondary suggestions of similarity. Not only did the lawyers make a mistake, but it was their own fault, and, like an athlete who has dropped a ball, they could not follow through with their next legal action. A secondary implication is that their enterprise was just a game. Often a metaphor associates something abstract to something concrete, as "Life is a journey." The preservation of inference from the concrete to the abstract in this metaphor suggests that like a journey, life has a beginning and an end, it progresses in one direction, it may have stops and detours, ups and downs, etc. The beauty of a metaphor is that hidden in a simple sentence like "Life is a journey" lurk a great many parallels, waiting to be uncovered by the thoughtful mind. Metaphorical thinking pervades mathematics to a remarkable degree. It is often reflected in the language mathematicians choose to define new concepts. In his construction of the system of real numbers, Dedekind could have referred to A \ В as a "type-two, order preserving equivalence class," or worse, whereas "cut" is the right metaphor. It corresponds closely to one's physical intuition about the real line. See Figure 3. In his book, Where Mathematics Comes From, George Lakoff gives a comprehensive view of metaphor in mathematics.  10 Real Numbers Chapter 1 An analogy is a shallow form of metaphor. It just asserts that two things are similar. Although simple, analogies can be a great help in accepting abstract concepts. When you travel from home to school, at first you are closer to home, and then you are closer to school. Somewhere there is a halfway stage in your journey. You know this, long before you study mathematics. So when a curve connects two points in a metric space (Chapter 2), you should expect that as a point "travels along the curve," somewhere it will be equidistant between the curve's endpoints. Reasoning by analogy is also referred to as ''intuitive reasoning." Moral Try to translate what you know of the real world to guess what is true in mathematics. Two pieces of advice A colleague of mine regularly gives his students an excellent piece of advice. When you confront a general problem and do not see how to solve it, make some extra hypotheses, and try to solve it then. If the problem is posed in η dimensions, try it first in two dimensions. If the problem assumes that some function is continuous, does it get easier for a differentiable function? The idea is to reduce an abstract problem to its simplest concrete manifestation, rather like a metaphor in reverse. At the minimum, look for at least one instance in which you can solve the problem, and build from there. Moral If you do not see how to solve a problem in complete generality, first solve it in some special cases. Here is the second piece of advice. Buy a notebook. In it keep a diary of your own opinions about the mathematics you are learning. Draw a picture to illustrate every definition, concept, and theorem. 2 Cuts We begin at the beginning and discuss Ж. = the system of all real numbers from a somewhat theological point of view. The current mathematics teaching trend treats the real number system IR as a given — it is defined axiomatically. Ten or so of its properties are listed, called axioms of a complete ordered field, and the game becomes: deduce its other properties from the axioms. This is something of a fraud, considering that the entire structure of analysis is built on the real number system. For what if a system satisfying the axioms failed to exist? Then one would be studying the empty set! However, you need not take the existence of the real numbers on faith alone — we will give a concise mathematical proof of it.  Section 2 Cuts 11 It is reasonable to accept all grammar school arithmetic facts about The set N of natural numbers, 1, 2, 3, 4, The set Ζ of integers, 0,1,-1,-2,2,.... The set Q of rational numbers p/q where /?, q are integers, q Φ 0. For example, we will admit without question facts like 2 + 2 = 4, and laws like a + b = b + a for rational numbers a.b. All facts you know about arithmetic involving integers or rational numbers are fair to use in homework exercises too.f It is clear that N С Ζ С Q. Now Ζ improves N because it contains negatives and Q improves Ζ because it contains reciprocals. Ζ legalizes subtraction and Q legalizes division. Still, Q needs further improvement. It doesn't admit irrational roots such as л/2 or transcendental numbers such as π. We aim to go a step beyond Q, completing it to form R so that NcZcQcR. As an example of the fact that Q is incomplete we have 1 Theorem No number r in Q has square equal to 2; i.e., л/2 ф Q. Proof To prove that every r — p/q has r2 φ 2 we show that ρ2 φ 2q2. It is fair to assume that ρ and q have no common factors since we would have canceled them out beforehand. Two integers without common factors can not both be even, so at least one of /?, q is odd. Case 1. ρ is odd. Then p2 is odd while 2q2 is not. Therefore ρ2 φ 2q2. Case 2. ρ is even and q is odd. Then p2 is divisible by 4 while 2q2 is not. Therefore ρ2 φ 2q2. D The set Q of rational numbers is incomplete. It has "gaps," one of which occurs at л/2. These gaps are really more like pinholes; they have zero width. Incompleteness is what is wrong with Q. Our goal is to complete Q by filling in its gaps. An elegant method to arrive at this goal is Dedekind cuts in which one visualizes real numbers as places at which a line may be cut with scissors. See Figure 3. Definition A cut in Q is a pair of subsets А, В of Q such that (a) A U В = Q, Α φ 0, Β φ 0, Α Π Β = 0. (b) If a € A and b e В then a < b. (c) A contains no largest element. ' A subtler fact that you may find useful is the prime factorization theorem mentioned above. Any integer > 2 can be factored into a product of prime numbers. For example, 120 is the product of primes 2 · 2 · 2 ■ 3 · 5. Prime factorization is unique except for the order in which the factors appear. An easy consequence is that if a prime number ρ divides an integer к and if к is the product mn of integers then ρ divides m or it divides n. After all, by uniqueness, the prime factorization of к is just the product of the prime factorizations of m and n.  12 Real Numbers Chapter 1 Figure 3 A Dedekind cut. A is the left-hand part of the cut and В is the right-hand part. We denote the cut as χ = A\B. Making a semantic leap, we now answer the question "what is a real number?" Definition A real number is a cut in Q. IR is the class* of all real numbers χ = A\B. We will show that in a natural way IR is a complete ordered field containing Q. Before spelling out what this means, here are two examples of cuts. (i) A\B = {r e Q : r < 1} | [r e Q : r > 1}. (ii) A\B = {r e Q : r < 0 or r2 < 2} | {r e Q : r > 0 and r1 > 2}. It is convenient to say that A \ В is a rational cut if it is like the cut in (i): for some fixed rational number c, A is the set of all rationals < с while В is the rest of Q. The £-set of a rational cut contains a smallest element c, and conversely, if A \ В is a cut in Q and В contains a smallest element с then A | В is the rational cut at c. We write c* for the rational cut at c. This lets us think of Q С IR by identifying с with c*. It is like thinking of Ζ as a subset of Q since the integer η in Ζ can be thought of as the fraction n/1 in Q. In the same way the rational number с in Q can be thought of as the cut at с It is just a different way of looking at c. It is in this sense that we write NcZcQct. There is an order relation χ < у on cuts that fairly cries out for attention. ' The word "class" is used instead of the word "set" to emphasize that for now the members of IR are set-pairs A\B, and not the numbers that belong to A or β. The notation A\B could be shortened to A since В is just the rest of Q. We write A\B, however, as a mnemonic device. It looks like a cut.  Section 2 Cuts 13 Definition The cut χ — A \B is less than or equal to the cut у — C\D if А С С We write χ < у if χ is less than or equal to у and we write χ < j if χ < >' and χ 7^ j. If χ = A\B is less than у = C|D then Л С С and A ^ С, so there is some cq € С \ A. Since the Α-set of a cut contains no largest element, there is also a c\ € С with c0 < ci. All the rational numbers с with со < с < c\ belong to С \ A. Thus, χ < у implies that not only is С \ A non-empty, but it contains infinitely many elements. The property distinguishing IR from Q and which is at the bottom of every significant theorem about IR involves upper bounds and least upper bounds; or equivalently, lower bounds and greatest lower bounds. Μ 6 IR is an upper bound for a set S С IR if each s e S satisfies s < M. We also say that the set S is bounded above by M. An upper bound for S that is less than all other upper bounds for S is a least upper bound for S. The least upper bound for S is denoted l.u.b. (S). For example, \3 is an upper bound for the set of negative integers. — 1 is the least upper bound for the set of negative integers. I is the least upper bound for the set {x e Q : 3n e Nandx = 1 - \/n). —100 is an upper bound for the empty set. A least upper bound for S may or may not belong to S. This is why you should say "least upper bound for S" rather than "least upper bound of S." 2 Theorem The set IR, constructed by means ofDedekind cuts, is complete* in the sense that it satisfies the Least Upper Bound Property: If S is a non-empty subset ofR and is bounded above then in IR there exists a least upper bound for S. Proof Easy! Let & С IR be any non-empty collection of cuts which is bounded above, say by the cut X\Y. Define С = {a e <Q> : for some cut A\B e <?, a e A} and D — the rest of Q. It is easy to see that ζ = C\D is a cut. Clearly, it is an upper bound for g since the "A" for every element of С is contained in C. Let z! — C\D' There is another, related, sense in which Ж is complete. See Theorem 5 below.  14 Real Numbers Chapter ] be any upper bound for β. By the assumption that A\B < C'\D' for all A\B e β, we see that the "A" for every member of β is contained in C. Hence CcC',soz<z'. That is, among all upper bounds for {£, ζ is least. D The simplicity of this proof is what makes cuts good. We go from Q to Ж. by pure thought. To be more complete, as it were, we describe the natural arithmetic of cuts. Let cuts χ = A | Б and у = C\D be given. How do we add them? subtract them? ... Generally the answer is to do the corresponding operation to the elements comprising the two halves of the cuts, being careful about negative numbers. The sum of χ and у is χ -\-у = E\F where Ε = [r e Q : for some a e A and ceC,r = a-\-c} F= the rest of Q. It is easy to see that E\F is a cut in Q and that it doesn't depend on the order in which χ and у appear. That is, cut addition is well defined and x + у = у + χ. The zero cut is 0* and 0* + χ = χ for all χ e R. The additive inverse of χ = A\B is — χ = C\D where С = {r e Q : for some b e B, not the smallest element of B, r = —b} D = the rest of Q. Then (—x) + χ = 0*. Correspondingly, the difference of cuts is χ — у = χ + (—у). Another property of cut addition is associativity: (x + j) + z = x + (j + z). This follows from the corresponding property of Q. Multiplication is trickier to define. It helps to first say that the cut χ = A | В is positive if 0* < χ or negative if χ < 0*. Since 0 lies in A or β, a cut is either positive, negative, or zero. If χ = A\B and у = C\D are nonnegative cuts then their product is χ ■ у = E\ F where E = {reQ : r <0or3a e A, such that a > 0, с > 0, and r — ac], and F is the rest of Q. If χ is positive and у is negative then we define the product to be — (x · (—y)). Since χ and — у are both positive cuts this makes sense and is a negative cut. Similarly, if χ is negative and у is positive then by definition their product is the negative cut — ((—x) · j), while if χ and у are both negative then their product is the positive cut (—x) · (—y).  Section 2 Cuts 15 Verifying the arithmetic properties for multiplication is tedious, to say the least, and somehow nothing seems to be gained by writing out every detail. (To pursue cut arithmetic further you could read Landau's classically boring book, Foundations of Analysis.) To get the flavor of it, let's the check the commutativity of multiplication: χ · у = у · χ for cuts x = A\B, у = C\D. If χ, у are positive then {ac : a e A,c e C,a > 0,c > 0} = {ca : с e C,a e A,c > 0,a > 0} implies that χ ■ у = у · χ. If x is positive and у is negative then x-y = -{x · (-у)) = -((-у) · x) = у · χ. The second equality holds because we have already checked commutativity for positive cuts. The remaining two cases are checked similarly. There are eight cases to check for associativity and eight more for distributivity. All are simple and we ornit their proofs. The real point is that cut arithmetic can be defined and it satisfies the same field properties that Q does: The operation of cut addition is well defined, natural, commutative, associative, and has inverses with respect to the neutral element 0*. The operation of cut multiplication is well defined, natural, commutative, associative, distributive over cut addition, and has inverses of nonzero elements with respect to the neutral element 1*. By definition, a field is a system consisting of a set of elements and two operations, addition and multiplication, that have the preceding algebraic properties - commutativity, associativity, etc. Besides just existing, cut arithmetic is consistent with Q arithmetic in the sense that if с, г е Q then c* +r* = (c + r)* and c* - r* = (cr)*. By definition, this is what we mean when we say that Q is a subfield of Ш. The cut order enjoys the additional properties of transitivity, χ < у < ζ implies χ < ζ. trichotomy. Either x < у, у < χ, or χ — у, but only one of the three things is true. translation, χ < у implies χ + ζ < у Η- ζ. By definition, this is what we mean when we say that IR is an ordered field. Besides, the product of positive cuts is positive and cut order is consistent with Q order: c* < r* if and only if с < r in Q. By definition, this is what we mean when we say that Q is an ordered subfield of R. To summarize  16 Real Numbers Chapter 1 3 Theorem The set R of all cuts in Q is a complete ordered field that contains Q as an ordered subfield. The magnitude or absolute value of χ e Ш is Ix if x > 0 -x if*<0. Thus, χ < |x|. A basic, constantly used fact about magnitude is the following. 4 Triangle Inequality For all χ, у е IR, \x + y\ < \x\ + \y\. Proof The translation and transitivity properties of the order relation imply that adding у and — у to the inequalities χ < \x\ and — χ < \x\ gives x + y<\x\ + y< \x\ + \y\ -x-y<\x\-y< \x\ + \y\. Since χ + у < \x\ + \y\ and — (x + y) < \x\ + \y\9 we infer that \x + y\ < |лс| + | v| as asserted. D Next, suppose we try the same cut construction in IR that we did in Q. Are there gaps in IR that can be detected by cutting IR with scissors? The natural definition of a cut in IR is a division A\B where Л and В are disjoint, non-empty subcollections of IR with Л U В = IR, and a < b for all a e A, b e B. Further, Л contains no largest element. Now, each b e В is an upper bound for A. Therefore у — 1. u. Ь.(Л) exists and a < у < b for all a e A and b e B. By trichotomy, A\B = {x e R : χ < ν} | {χ e IR : χ > у}. In other words, IR has no gaps. Every cut in IR occurs exactly at a real -number. Allied to the existence of IR is its uniqueness. Any complete ordered field F containing Q as an ordered subfield corresponds to IR in a way preserving all the ordered field structure. To see this, take any ^eF and associate to it the cut A \ В where Л = {r e Q : r < φ in ¥}. This correspondence makes F equivalent to Ш.  Section 2 Cuts 17 Upshot The real number system Ш exists and it satisfies the properties of a complete ordered field; the properties are not assumed as axioms, but are proved by logically analyzing the Dedekind construction of IR. Having gone through all this cut rigmarole, it must be remarked that it is a rare working mathematician who actually thinks of IR as a complete ordered field or as the set of all cuts in Q. Rather, he or she thinks of IR as points on the x-axis, just as in calculus. You too should picture IR this way, the only benefit of the cut derivation being that you should now unhesitatingly accept the least upper bound property of IR as a true fact. Note ±00 are not real numbers since Q|0 and 0|Q are not cuts. Although some mathematicians think of IR together with —00 and +00 as an "extended real number system," it is simpler to leave well enough alone and just deal with IR itself. Nevertheless, it is convenient to write expressions like "x -» 00" to indicate that a real variable χ grows larger and larger without bound. If S is a non-empty subset of IR then its supremum is its least upper bound when S is bounded above and is said to be +00 otherwise; its infimum is its greatest lower bound when S is bounded below and is said to be —00 otherwise. (In Exercise 17 you are asked to invent the notion of greatest lower bound.) By definition the supremum of the empty set is —00. This is reasonable, considering that every real number, no matter how negative, is an upper bound for 0, and the least upper bound should be as far leftward as possible, namely —00. Similarly, the infimum of the empty set is +00. We write sup S and inf S for the supremum and infimum of S. Cauchy sequences As mentioned above there is a second sense in which Ж is complete. It involves the concept of convergent sequences. Let αχ, a,2, «3, «4, ■ ■ · = (a„), η e N, be a sequence of real numbers. The sequence (an) converges to the limit b e Ш as η -» oo provided that for each 6 > 0 there exists N e N such that for all η > N, \an -b\<€. The statistician's language is evocative here. Think of η = 1,2,... as a sequence of times and say that the sequence (an) converges to b provided that eventually all its terms nearly equal b. In symbols, V6 > 0 3N eN such that η > N =* \an - b\ < 6.  18 Real Numbers Chapter 1 If the limit b exists it is not hard to see that it is unique, and we write lim an — b or an —> b. n—>oo Suppose that lim„_^oo an = b. Since all the numbers an are eventually near b they are all near each other; i.e., every convergent sequence obeys a Cauchy condition: V6 > 0 3N e N such that я, m > N =>► \an - am\ < €. The converse of this fact is a fundamental property of K. 5 Theorem Ж. is complete with respect to Cauchy sequences in the sense that if(an) is a sequence of real numbers obeying a Cauchy condition then it converges to a limit in Ш. Proof Let A be the set of real numbers comprising the sequence (an), A = {x e R : 3n e N and an = x}. We first observe that Л is a bounded set in IR. Taking e = 1 in the Cauchy condition, there is an integer N\ such that for all n, m > Af], \an — am \ < 1. Then, for each η > Ν\ (10) \an -aNl\ < 1. Clearly the finite set ab a2, ..., ащч αΝχ — 1, aNl + 1 is bounded, (any finite set is bounded); say all its elements belong to the interval [—Μ, Μ]. According to (10), [—Μ, Μ] contains A so A is bounded. Next, consider the set S = {s e [—M, M] : 3 infinitely many η e N, for which an > s]. That is, an > s infinitely often. Clearly —MeS and S is bounded above by M. According to the least upper bound property of Μ there exists b e M, b = I. u. b. S . We claim that the sequence (an) converges to b. Given 6 > 0 we must show that there exists an Af such that for all η > Ν, \an — b\ < 6. The Cauchy condition provides an 7V2 such that (11) m,n>N2 => \am—an\<-. All elements of 5 are < fc, so the larger number b + e/2 does not belong to S. Only finitely often does an exceed b + б/2. That is, for some N3 > N2, n> N3 => a„ < b + -.  Section 2 Cuts 19 Since b is a least upper bound for S, the smaller number b — e/2 can not also be an upper bound for S. Some s e S is > b — б/2, which implies that an > s > b — 6/2 infinitely often. In particular, there exists N > N3 such that aN > b — 6/2. Since N > 7V3, aN < b + 6/2 and a^v e (b-€/2, b + e/2). Since N > 7V2, (11) implies \an - b\ < \an - aN\ + \aN - b\ < 6, which verifies convergence. D Restating Theorem 5 gives the 6 Cauchy Convergence Criterion for sequences A sequence (an) in Μ converges if and only if Уб > 0 3Af 6 N such that n,m > Ν =ϊ \an — am\ < €. Further description of Μ The elements of Ж\ Q are irrational numbers. If χ is irrational and r is rational then у = χ + r is irrational. For if у is rational then so is у — r = x, the difference of rationals being rational. Similarly, if r φ Ο then rx is irrational. It follows that the reciprocal of an irrational number is irrational. From these observations we will show that the rational and irrational numbers are thoroughly mixed up with each other. Let a < b be given in R Define the intervals (a4 b) and [a, b] as (a4 b) = {x e R : a < χ < b] [a,b] = {x e R : a < χ < b]. 7 Theorem Every interval (a, b), no matter how small, contains both rational and irrational numbers. Proof This is certainly true of the interval (0, 1) since it contains the numbers 1/2 and 1/л/2. For the general interval (a, b), think of a, b as cuts a = A\Af, b = B\Bf. The fact that a < b implies the set В \ A contains two distinct rational numbers, say r, s. Thus a < r < s < b. The transformation Τ : t \-^ r + (s — r)t  20 Real Numbers Chapter 1 sends the interval (0, 1) to the interval O, s).Sincer, stands—rare rational, Τ sends rationals to rationals and irrationals to irrationals. That is, (r, s) contains both rationals and irrationals, and so does the larger interval (a,b). D Theorem 7 expresses the fact that between any two rational numbers lies an irrational number; and between any two irrational numbers lies a rational number. This is a fact worth thinking about for it seems implausible at first. Spend some time trying to picture the situation, especially in light of the following related facts: (a) There is no first (i.e., smallest) rational number in the interval (0, 1). (b) There is no first irrational number in the interval (0, 1). (c) There are strictly more irrational numbers in the interval (0, 1) (in the cardinality sense explained in Section 4) than there are rational numbers. The transformation in the proof of Theorem 7 shows that the real line is like rubber: stretch it out and it never breaks. A somewhat obscure and trivial fact about IR is its Archimedean property: for each χ e R there is an integer η that is greater than x. In other words, there exist arbitrarily large integers. The Archimedean property is true for Q since p/q < \p\. It follows that it is true for M. Given χ = А\ВЧ just choose a rational number r e В and an integer η > r. Then η > χ. An equivalent way to state the Archimedean property is that there exist arbitrarily small reciprocals of integers. Mildly interesting is the existence of ordered fields for which the Archimedean property fails. One example is the field Щх) of rational functions with real coefficients. Each such function is of the form q(x) where ρ and q are polynomials with real coefficients and q is not the zero polynomial. (It does not matter that q(x) = 0 at a finite number of points.) Addition and multiplication are defined in the usual fashion of high school algebra, and it is easy to see that Ж(х) is a field. The order relation on Ж(х) is also easy to define. If R(x) > 0 for all sufficiently large χ then we say that R is positive in IR(x), and if R — S is positive then we write S < R. Since a nonzero rational function vanishes (has value zero) at only finitely many χ e R, we get trichotomy: either R = 5, R < 5, or S < R. (To be rigorous, we need to prove that the values of a rational function do not change sign for χ large enough.) The other order properties are equally easy to check, and Ш(х) is an ordered field.  Section 3 Euclidean Space 21 Is E(jc) Archimedean? That is, given R e Ш(х), does there exist a natural number η e Ш(х) such that R < nl (A number η is the rational function whose numerator is the constant polynomial p(x) = n, a polynomial of degree zero, and whose denominator is the constant polynomial q(x) = 1.) The answer is "no." Take R(x) = χ/I. The numerator is χ and the denominator is 1. Clearly, we have η < x, not the opposite, so Щх) fails to be Archimedean. The same remarks hold for any positive rational function R = p(x)/q (x) where the degree of ρ exceeds the degree of q. In Щх), R is never less than a natural number. (You might ask yourself: exactly which rational functions are less than nl) The e -principle Finally let us note a nearly trivial principle that turns out to be invaluable in deriving inequalities and equalities in Ш. 8 Theorem (^-principle) Ifa,b are real numbers and if for each 6 > 0, a < b + 6, then a < b. If x,y are real numbers and for each e > 0, I* — y\ < e, then x = y. Proof Trichotomy implies that either a < b or a > b. In the latter case we can choose €,0 < € < a — b and get the absurdity 6 < a — b < 6. Hence a < b. Similarly, if χ φ у then choosing 6,0<6<|x — y\ gives the contradiction 6 < \x — y\ < 6. Hence χ = j. See also Exercise 11. D 3 Euclidean Space Given sets A and B, the Cartesian product of A and Б is the set Α χ θ of all ordered pairs (a, b) such that a e A and b e B. (The name comes from Descartes who pioneered the idea of the (jc, y)-coordinate system in geometry.) See Figure 4. The Cartesian product of IR with itself m times is denoted W1. Elements of IRm are vectors, ordered m-tuples of real numbers, (x}, ..., xm). In this terminology, real numbers are called scalars and IR is called the scalar field. When vectors are added, subtracted, and multiplied by scalars according to the rules  22 Real Numbers Chapter 1 ь — в I A a Figure 4 The Cartesian product Α χ Β. (XU...,Xm) + (yU •••>Ут) = (Х\+Уи---,Хт+ Ут) Ol, ...,Xm) - (УЬ ■■-,Ут) = Ol - УЬ ...9Хт ~ Ут) С Οι, . . . ,Xm) = (СХи ...,СХт) then these operations obey the natural laws of linear algebra: commuta- tivity, associativity, etc. There is another operation defined on IRm, the dot product (also called the scalar product or inner product). The dot product of χ = Оь · · ·, xm) and у = Оь · · ·, Ут) is (X9y) = XXyi 4 УХтУт- Remember: the dot product of two vectors is a scalar, not a vector. The dot product operation is bilinear, symmetric, and positive definite; i.e., for any x,y,z e Rm and any с е Е, 0, y + cz) = {x, y) + c(x, z), (х,У) = (У,х), (x,x) > 0 and (x,x) = 0 if and only if χ is the zero vector. The length or magnitude of a vector χ e Rm is defined to be \x\ = V(X'X) = \Μί Η ^-xm. See Exercise 15 which legalizes taking roots. Expressed in coordinate-free language, the basic fact about the dot product is the 9 Cauchy-Schwarz Inequality For all χ, у e Mm, (jc, y) < |jc| \y\.  Section 3 Euclidean Space 23 Proof Tricky! For any vectors x, у consider the new vector w = χ + ty where t e Ш is a varying scalar. Then fit) = (w, w) = {x + ty, χ + ty) is a real-valued function of t. In fact, f(t)>0 since the dot product of any vector with itself is nonnegative. The bilinearity properties of the dot product imply that f(t) = (x, x) + Ъ(х, у) + t2{y, y) = c + bt+ at2 is a quadratic function of t. Nonnegative quadratic functions of f e Ш have nonpositive discriminants, b2 — 4ac < 0. For if b2 - Aac > 0 then f(t) has two real roots, between which f(t) is negative. See Figure 5. b2-4oc<0 b2-4ac = Q b2-4ac>0 Figure 5 Quadratic graphs. But b2 — Aac < 0 means that A(x,y)2 -A(x,x)(y,y) <0. Therefore (x, y) < y/{x,x)y/{y,y) = \x\ \y\. D The Cauchy-Schwarz inequality implies easily the Triangle Inequality for vectors: For all x, у е IRm, \x + y\ <\x\ + \y\- For \x + y\2 = (x + y, χ + y) = (χ, χ) + 2(x, y) + {y9 y). By Cauchy- Schwarz, 2(x, y) < 2 |jc| \y\. Thus, \x + >l2 < И2 4- 2 |jc| |y| + \y\2 = {\x\ + \y\)2. Taking the square root of both sides gives the result.  24 Real Numbers Chapter 1 The Euclidean distance between vectors x, у е Шт is defined as the length of their difference, \Х~У\ = \Л* - V, X-y) = y/(X\ - Vi)2 Η + (xm- Ут)2. From the Triangle Inequality for vectors follows the Triangle Inequality for distance. For all x, y, ζ e №.m, \x-z\< \x-y\ + \y-z\. To prove it, think of χ — ζ as a vector sum (x — y) + (у — ζ) and apply the Triangle Inequality for vectors. See Figure 6. Figure 6 How the Triangle Inequality gets its name. Geometric intuition in Euclidean space can carry you a long way in real analysis, especially in being able to forecast whether a given statement is true or not. Your geometric intuition will grow with experience and contemplation. We begin with some vocabulary. The 7th coordinate of the point (x\,..., xm) is the number Xj appearing in the 7th position. The 7th coordinate axis is the set of points χ e Rm whose k^1 coordinates are zero for all к ф j. The origin of IRm is the zero vector, (0 0). The first orthant of IRm is the set of points χ e Rm all of whose coordinates are nonnegative. When m = 2, the first orthant is the first quadrant. The integer lattice is the set ΊΓ С М.т of ordered m -tuples of integers. The integer lattice is also called the integer grid. See Figure 7. A box is a Cartesian product of intervals [aubx] χ ··· χ [am,bm] in IRm. (A box is also called a rectangular parallelpiped.) The unit cube in IRm is the box [0, \]m = [0, 1] χ · · · χ [0, 1]. See Figure 8. The unit ball and unit sphere in Rm are the sets Bm = {x eRm : \x\ < 1] Sm~l = {x eRm : |jc| = 1}.  Section 3 Euclidean Space 25 • · • · • · axis • · > ·· ...#.. -· ·■ . . . # . . ■ ■ · · first quadrant · ■ (4,1) origin χ j -axis • •i····· Figure 7 The integer lattice and first quadrant. box cube Figure 8 A box and a cube. The reason for the exponent m — 1 is that the sphere is (m — 1)-dimensional as an object in its own right, although it does live in m-space. In 3-space, the surface of a ball is a two-dimensional film, the 2-sphere S2. See Figure 9. A set Ε С Шт is convex if for each pair of points jc, у е £, the straight line segment between χ and у is also contained in E. The unit ball is an example of a convex set. To see this, take any two points in Bm and draw the segment between them. It obviously lies in Bm. See Figure 10.  26 Real Numbers Chapter 1 Figure 9 A 2-disc with its boundary circle, and a 2-sphere. Figure 10 Convexity of the ball. To give a mathematical proof, it is useful to describe the line segment between χ and у with a formula. The straight line determined by distinct points.*,)' e Шт is the set of all linear combinations sx+t у where s+1 = 1, and the line segment is the set of linear combinations where s and t are < 1. Such linear combinations sx + ty with s + t = 1 and 0 < s, t < 1 are called convex combinations. The line segment is denoted as [x, y]. (This notation is consistent with the interval notation [a, b]. See Exercise 25.) Now if jc, у e Bm and sx + ty = ζ is a convex combination of χ and у then, using the Cauchy-Schwarz inequality and the fact that 1st > 0, we get  Section 3 Euclidean Space 27 (z9 z) = s2{x, x) + 2st(x, y) + t2(y, y) Ss2M2 + 2st\x\\y\+t2\y\2 <s2 + 1st 4-12 = (s + t)2 = 1. Taking the square root of both sides gives \z\ < 1, which proves convexity of the ball. Inner product spaces An inner product on a vector space V is an operation ( , ) on pairs of vectors in V that satisfies the same conditions that the dot product in Euclidean space does, namely, bilinearity, symmetry, and positive definite- ness. A vector space equipped with an inner product is an inner product space. The discriminant proof of the Cauchy-Schwarz Inequality is valid for any inner product defined on any real vector space, even if the space is infinite-dimensional and the standard coordinate proof would make no sense. For the discriminant proof uses only the inner product properties, and not the particular definition of the dot product in Euclidean space. IRm has dimension m because it has a basis e\,..., em. Other vector spaces are more general. For example, let С ([a, fc], Ш) denote the set of all of continuous real valued functions defined on the interval [a,b]. (See Section 6 or your old calculus book for the definition of continuity.) It is a vector space in a natural way, the sum of continuous functions being continuous and the scalar multiple of a continuous function being continuous. The vector space, however, has no finite basis. It is infinite-dimensional. Even so, there is a natural inner product, </.*>= f f(x)g(x)dx. J a Cauchy-Schwarz applies to this inner product, just as to any inner product, and we infer a general integral inequality valid for any two continuous functions, j f(x)g(x)dx < J J f(x)4xJj g(x)2dx. It would be challenging to prove such an inequality from scratch, would it not? A norm on a vector space V is any function || || : V —> Ш with the three properties of vector length: namely, if υ, w e V and λ e Ε then  28 Real Numbers Chapter 1 ||υ|| > Oand ||v|| = 0 if and only if ν = 0, Ι|λυ|| = |λ| || ν И, l|i> + u;||<|N + ||u;||. An inner product ( , ) defines a norm as ||l>|| = */{υ, ν) , but not all norms come from inner products. The unit sphere {v e V : (v,v) = \] for every inner product is smooth (has no corners) while for the norm IMLax = max{|ui|, |υ2|} defined on ν = (v\, i?2> e M2, the unit sphere is the perimeter of the square {(ui, V2) e R2 : \v\\ < I and |i>2l < 1}· It has corners and so it does not arise from an inner product. See Exercises 43,44, and the Manhattan metric on page 72. The simplest Euclidean space beyond Μ is the plane IR2. Its xj-coordinates can be used to define a multiplication, O, y) · (*', /) = (**' - yy\ xyf + xy). The point (1,0) corresponds to the multiplicative unit element 1, while the point (0, 1) corresponds to i = V—T, which converts the plane to the field С of complex numbers. Complex analysis is the study of functions of a complex variable, i.e., functions f(z) where ζ and f(z) He in С Complex analysis is the good twin and real analysis the evil one: beautiful formulas and elegant theorems seem to blossom spontaneously in the complex domain, while toil and pathology rule the reals. Nevertheless, complex analysis relies more on real analysis than the other way around. 4 Cardinality Let A and В be sets. A function f : A -+ β is a rule or mechanism which, when presented with any element a e A, produces an element b = f(a) of β. It need not be defined by a formula. Think of a function as a device into which you feed elements of A and out of which pour elements of B. See Figure 11. We also call / a mapping or a map or a transformation. The set A is the domain of the function and В is the target. The range or image of / is the subset of the target, {b e В : there exists at least one element a e A with f(a) = b]. See Figure 12. Try to write / instead of f(x) to denote a function. The function is the device which when confronted with input χ produces output f(x). The function is the device, not the output.  Section 4 Cardinality 29 Figure 11 The function / as a machine. Figure 12 The domain, target, and range of a function. Think also of a function dynamically. At time zero all the elements of A are sitting peacefully in Λ. Then the function applies itself to them and throws them into B. At time one all the elements that were formerly in A are now transferred into B. Each a e A gets sent to some element f(a) e B. A mapping / : A -» В is an injection (or is one-to-one) if for each pair of distinct elements a, a e A, the elements f(a), f(d) are distinct in B. That is, α φ a' => f(a) φ f{a'). The mapping / is a surjection (or is onto) if for each b e В there is at least one a e A such that f(a) = b. That is, the range of / is B.  30 Real Numbers Chapter 1 A mapping is a bijection if it is both injective and surjective. It is one-to- one and onto. If / : A -» В is a bijection then the inverse map f~l : В —> Л is a bijection where f~l(b) is by definition the unique element a e A such that f(a) = b. The identity map of any set to itself is the bijection that takes each a e A and sends it to itself, id (я) —а. If / : A -» В and g : В -» С then the composite g о / : Л -» С is the function that sends a e Ato g(f(a)) e С If/ and g are injective then so is g о f, while if / and g are surjective then so is g о /. In particular the composite of bijections is a bijection. If there is a bijection from A onto В then Л and В are said to have equal cardinality,1 and we write A ^ B. The relation ~ is an equivalence relation. That is, (a) A ~ A. (b) Л ~ Б implies В ~ A. (c) A ~ β ~ С implies A ~ С (a) follows from the fact that the identity map bijects A to itself, (b) follows from the fact that the inverse of a bijection A —> Б is a bijection Z? -» A. (c) follows from the fact that the composite of bijections / and g is a bijection A set S is finite if it is empty or for some η e N, S ~ {1,..., n]. infinite if it is not finite. denumerable if S ~ N. countable if it is finite or denumerable. uncountable if it is not countable. We also write card A = card В and #A = #B when A, B have equal cardinality. * The word "cardinal" indicates the number of elements in the set. The cardinal numbers are 0, 1.2,... The first infinite cardinal number is aleph null, Ко- One says the N has Ко elements. A mystery of math is the Continuum Hypothesis which states that R has cardinality Ki, the second infinite cardinal. Equivalently, ifNc5cl, the Continuum Hypothesis asserts that S ~ N or S ~~ WL No intermediate cardinalities exist. You can pursue this issue in Paul Cohen's book, Set Theory and the Continuum Hypothesis.  Section 4 Cardinality 31 If S is denumerable then there is a bijection / : N —► S, and this gives a way to list the elements of S as si = /(1), ^2 = /(2), S3 = /(3), etc. Conversely, if a set 5 is presented as an infinite list (without repetition) S = {s\,S2,S3, ...} then it is denumerable: define f(k) = sk for к е N. In brief, denumerable = listable. Let's begin with a truly remarkable cardinality result, that although N and R are both infinite, R is more infinite than N. Namely, 10 Theorem Ш is uncountable. Proof There are other proofs of the uncountability of R, but none so beautiful as this one. It is due to Cantor. I assume that you accept the fact that each real number χ has a decimal expansion, χ = Ν.Χ1Χ2Χ3... , and it is uniquely determined by χ if one agrees never to terminate the expansion with an infinite string of 9's. (See also Exercise 16.) We want to prove that Ш is uncountable. Suppose it is not uncountable. It is countable and, being infinite, it must be denumerable. Accordingly let / : N —> Ш be a bijection. Using /, we list the elements of R along with their decimal expansions as an array, and consider the digits Хц that occur along the diagonal in this array. See Figure 13. /41) /42) /43) /44) /45) /46) /47) — = = = = = = "χ N2 Nl ^4 ^5 ^6 ^7 *li *2I *3I Хц ■*51 ■*61 *71 x\1 ΧΊΙ x3? A42 X52 -*62 *72 *13 *.гч %э л43 х53 хвз х73 л14 *24 *34 ХЛ& л54 -*64 *74 45 ■*J5 *35 *4.5 *» *65 *75 *16 х26 *36 ■*4б *56 Щб Х1Ь хх1 ХП Χ3Ί х47 *57 *67 %7 Figure 13 Cantor's diagonal method. For each 1, choose a digit yt such that уг ^ хц and у/ ^ 9. Where is the number у = 0.у\у2уз ... ? Is it /(1)? No, because the first digit in the decimal expansion of /(1) is xu and y\ φ xn. Is it /(2)? No, because the second digit in the decimal expansion of f(2) is x22 and y2 Φ x22. Is it /(£)? No, because the kth digit in the decimal expansion of f(k) is Xkk and ^ ^ хкк. Nowhere in the list do we find y. Nowhere! Therefore the list could not account for every real number, and R must have been uncountable. Π  32 Real Numbers Chapter 1 11 Corollary [a, b] and (a, b) are uncountable. Proof There are bijections from (a, b) onto (— 1, 1) onto the unit semicircle onto IR shown in Figure 14. Figure 14 Equicardinality of (a, b), (—1, 1), and IR. The composite / bijects (a, b) onto IR, so (a, b) is uncountable. Since [a, b] contains (a, b), it too is uncountable. D The remaining results in this section are of a more positive flavor. 12 Theorem Each infinite set S contains a denumerable subset. Proof Since S is infinite it is non-empty and contains an element s\. Since S is infinite the set S \ {s\} = {s e S : s φ s\} is non-empty and there exists s2 € S\ {si}. Since S is an infinite set, S \ {s\, s2] = {s e S : s φ s\, s2] is non-empty and there exists s^ e S\{s\, s2}. Continuing this way gives a list (sn) of distinct elements of S. The set of these elements forms a denumerable subset of S. D 13 Theorem An infinite subset A of a denumerable set В is denumerable. Proof There exists a bijection / : N -> B. Each element of Л appears exactly once in the list /(1), /(2), /(3),... of B. Define g(k) to be the kth element of A appearing in the list. Since Л is infinite, g(k) is defined for all к e N. Thus g : N -> A is a bijection and A is denumerable. D  Section 4 Cardinality 33 14 Corollary The sets of even integers and of prime integers are denumer- able. Proof They are infinite subsets of N, which is denumerable, D 15 Theorem ΝχΝίί denumerable. Proof Think ofNxNasanooxoo matrix and walk along the successive counter-diagonals. See Figure 15. This gives a list (1, 1), (2, 1), (1, 2), (3, I), (2, 2), (1, 3), (4, 1), (3, 2), (2, 3), (1,4), (5, 1),... of Ν χ Ν and proves that Ν χ Ν is denumerable. D Figure 15 Counter-diagonals in an oo χ oo matrix. 16 Corollary The Cartesian product of denumerable sets A and В is denumerable. Proof N - NxN - АхБ. D 17 Theorem If f : N —> В is a surjection and В is infinite then В is denumerable. Proof For each b e B, the set {k e N : f(k) = b} is non-empty and hence contains a smallest element, say h(b) —k is the smallest integer that is sent to b by /. Clearly, if b φ V then h(b) φ h{b'). That is, h : В -> N is an injection which bijects В to hВ С N. Since В is infinite, so is hB. By Theorem 13, hВ is denumerable and therefore so is В. D 18 Corollary The denumerable union of denumerable sets is denumerable.  34 Real Numbers Chapter I Proof Suppose that A\, A2, ... is a sequence of denumerable sets. List the elements of A, as щ \, ал,... and define /:NxN->A = (jAi (l, j) H> dij Clearly / is a surjection. According to Theorem 15, there is a bijection g : N —► Ν χ N. The composite / о g is a surjection N —► A. Since A is infinite, Theorem 17 implies it is denumerable. D 19 Corollary Q /л· denumerable. Proof Q is the denumerable union of the denumerable sets Aq = {p/q : ρ e Z} as g ranges over N. D 20 Corollary For each m e N, Qm /s denumerable. Proof Apply the induction principle. If m = 1, then the previous corollary states that Q1 is denumerable. Knowing inductively that Qm_1 is denumerable and Qm = Qm~] χ Q, the result follows from Corollary 16. D Combination laws for countable sets are similar to those for denumerable sets. As is easily checked, Every subset of a countable set is countable. A countable set that contains a denumerable subset is denumerable. The Cartesian product of finitely many countable sets is countable. The countable union of countable sets is countable. 5* Comparing Cardinalities The following result gives a way to conclude that two sets have the same cardinality. Roughly speaking the condition is that card A < card В and card В < card A. 21 Schroeder-Bernstein Theorem If А, В are sets and f : A —► B, g : В -> A are injections then there exists a bijection h : A —> B. Proof-sketch Consider the dynamic Venn diagram, Figure 16. The disc labeled gf A is the image of A under the map g о /. It is a subset of A. The ring between A and gf A divides into two subrings. A0 is the set of points in A that do not lie in the image of g, while A\ is the set points in the image of g that do not lie in gf A. Similarly, Bo is the set of points in В that do not lie in /A, while B\ is the set of points in f A that do not lie in fgB. There is a natural bijection h from the pair of rings A0 U A \ = A \ gf A to the pair of rings Bq U B\ = В \ fgB. It equals / on the outer ring A0 = A \ gB  Section 5* Comparing Cardinalities 35 Figure 16 Pictorial proof of the Schroeder-Bernstein Theorem. and it is g~l on the inner ring A\ = gB\ gfA. (The map g~l is not defined on all of A, but it is defined on the set gB.) In this notation, h sends Ao onto #ι and sends A\ onto Bq. It switches the indices. Repeat this on the next pair of rings for A and B. That is, look at gfA instead of A and fgB instead of B. The next two rings in Α, β are Μ = gfA \ gfgB A3 = gfgB \ gfgfA Bi = fgB \ fgfA B3 = fgfA \ fgfgB. Send A2 to Z?3 by / and A3 to B2 by g-1. The rings A, are disjoint, and so are the nogs /?,·, so repetition gives a bijection <p--\JAi ^ \JBi (LI indicates disjoint union) defined by If(x) if χ e Ai and / is even g (x) if x e Ai and / is odd Let A* = A \ (\jAi) and B* = B\ {\jBi) be the rest of A and B. Then / bijects A* to B*, and φ extends to a bijection h : A —>> В defined by \ф{х) if^eMA; [fix) ifjceA*. D A supplementary aid in understanding the Schroeder Bernstein proof is the following crossed ladder diagram, Figure 17. Exercise 33 asks you to show directly that (a, b) ~ [a,b\. This makes sense since (a,b) С [α, bJ С Ш and (a, fc) ~ Μ should certainly imply that (a, b) - [a, b] - R.  36 Real Numbers Chapter 1 \ /4 S-1 \ Уч g- A4 A5 A, X ■ i' B0 Bi B2 B* B4 B5 B* /\ /\ /\ ♦' L· R, Я, Д, R, Re A< B$ B4 B5 Bo B] Figure 17 Diagramatic proof of the Schroeder-Bernstein Theorem. The Schroeder-Bernstein theorem gives a quick, indirect solution to the exercise. The inclusion map i : (a,b) c-^ [a,b] sending χ to χ injects (a, b) into [a, b], while the function j (χ) = χ/2 + (a + b)/4 injects [a, fc] into (a,b). The existence of the two injections implies by the Schroeder- Bernstein Theorem that there is a bijection (a, b) ~ [a, b]. 6* The Skeleton of Calculus The behavior of a continuous function defined on an interval [a, b] is at the root of all calculus theory. Using solely the l.u.b. property of the real numbers we rigorously derive the basic properties of such functions. The function/ : [a, b] -» discontinuous if for each 6 > 0 and each χ e [a,b] there is a 8 > 0 such that t e [a, b] and \t — x\ < 8 See Figure 18. 2δ : 1/(0-/(*)!<€. Figure 18 The graph of a continuous function of a real variable.  Section 6* The Skeleton of Calculus 37 Continuous functions are found everywhere in analysis and topology. Theorems 22, 23, 24 present their simplest properties. Later we generalize these results to functions that are neither real valued nor dependent on a real variable. Although it is possible to give a combined proof of Theorems 22 and 23,1 prefer to highlight the l.u.b. property and keep them separate. 22 Theorem The values of a continuous function defined on an interval [a, b]form a bounded subset ofR. That is, there exist m, Μ e Ш such that for all χ e [a, b\ m < f{x) < M. Proof For χ € [a, fc], let Vx be the value set of f(t) as t varies from a tox, Vx = {y £ IR : for some t e [a, x]9 у = f(t)}. Set X = {x e [a, b\ : Vx is a bounded subset of IR}. We must prove that b e X. Clearly a e X and b is an upper bound for X. Since X is non-empty and bounded above, there exists in IR a least upper bound с < b for X. Take 6 = 1 in the definition of continuity. There exists a 8 > 0 such that \x — c\ < 8 implies \f(x) — /(c)| < 1. Since с is the least upper bound for X, there exists χ € X in the interval [c — <5, c]. (Otherwise с — 8 is a smaller upper bound for X.) Now as t varies from a to c, the value f(t) varies first in the bounded set Vx and then in the bounded set J = (/(c) - 1, /(c) 4- 1). See Figure 19. f(c)+\ Figure 19 The value set Vx and the interval /.  38 Real Numbers Chapter 1 The union of two bounded sets is a bounded set and it follows that Vc is bounded, so с e X. Besides, if с < b then f(t) continues to vary in the bounded set / for t > c, contrary to the fact that с is an upper bound for X. Thus, с = b,b e X, and the values of / form a bounded subset of JL D 23 Theorem A continuous function f defined on an interval [a,b] takes on absolute minimum and absolute maximum values: for some xq.xi £ [a, b] and for all χ € [a, b], f(X0) < fix) < /(*!)■ Proof Let Μ = 1. u. b. f(t) as t varies in [a, b\. By Theorem 22, Μ exists. Consider the set X = {x e [a, b] :l.u. b. V* < M} where, as above, Vx is the set of values of f(t) as / varies on [a, x]. Case 1. f(a) = M. Then / takes on a maximum at a and the theorem is proved. Case 2. f(a) < M. Then Χ φ 0 and we can consider the least upper bound of X, say с If /(c) < M, we choose 6 > 0 with 6 < Μ — /(c). By continuity, there exists a <S > 0 such that \t — c\ < 8 implies |/(r) — /(c)| < 6. Thus, 1. u. b. Vc < M. If с < b this implies that there exist points t to the right of с at which 1. u. b. Vt < M, contrary to the fact that с is an upper bound of such points. Therefore, с = h which implies that Μ < Μ, a contradiction. Having arrived at a contradiction from the supposition that/(c) < M, we duly conclude that/(c) = M, so /assumes a maximum at с The situation with minima is similar. D 24 Intermediate Value Theorem A continuous function defined on an interval [a, b] takes on (or "achieves," "assumes," or "attains") all intermediate values: if f(a) = a, f(b) — β, and У is given, a < Υ < β, then there is some с e \a, b] such that /(с) = У. The same conclusion holds if β <Y <a. The theorem is pictorially obvious. A continuous function has a graph that is a curve without break points. Such a graph can not jump from one height to another. It must pass through all intermediate heights. Proof Set X = {x e [a, b] : 1. u.b. Vx < Y] and с = l.u.b. X. Now с exists because X is non-empty (it contains a) and it is bounded above (by b). We claim that /(c) = Y, as shown in Figure 20. To prove it, we just eliminate the other two possibilities, /(c) < К and /(c) > Y, by showing that each leads to a contradiction. Suppose that /(c) < Υ and take € = Υ — /(c). Continuity gives 8 > 0 such that \t - c\ < 8 implies \f(t) - /(c)| < 6. That is, t € (С-Й,С + Й) => /(f) < У,  Section 6* The Skeleton of Calculus 39 β Г γ Г a * 0 '■ a '■ X с '■ b Figure 20 χ e X implies that f(x) < Y. so с + (5/2 e X, contrary to с being an upper bound of X. Suppose that f(c) > У and take € = f(c) — У. Continuity gives δ > 0 such that \t — c\ < 8 implies \f(t) — f(c)\ < e. That is, f € (c-5,c + 5)=> /(f) > K, so с — 8/2 is an upper bound for X, contrary to с being the least upper bound for X. Since /(c) is neither < У nor > K, we get f(c) = У. D A combination of Theorems 22, 23, 24 and Exercise 40 could well be called the Fundamental Theorem of Continuous Functions Every continuous real valued/unction of a real variable χ e [a4 b] is bounded, achieves minimum, intermediate, and maximum values, and is uniformly continuous.  40 Real Numbers Chapter 1 Exercises / have adopted Мое Hirsch ys star system for the exercises. One star is hard, two stars is very hard, and a three-star exercise is a question to which I do not know the answer. 0. Prove that for all sets А, В, С the formula Α Π (В U С) = (Α Π В) U (А П С) is true. Here is the solution written out in gory detail. Imitate this style in writing out proofs in this course. Hypothesis. А, В, С are sets. Conclusion. Α Π (Β U С) = (Α Π Β) U (А П С). Proof. To prove two sets are equal we must show that every element of the first set is an element of the second set and vice versa. Referring to Figure 21 Jet χ denote an element of the set Α Π (Β U С). It belongs ВС ВС Figure 21 A is ruled vertically, В and С are ruled horizontally, Α Π β is ruled diagonally, and А П С is ruled counter-diagonally. to A and it belongs to В or to C. Therefore χ belongs to Α Π Β or it belongs to Α Π С Thus χ belongs to the set (Α Π Β) U (А П С) and we have shown that every element of the first set Α Π (B U C) belongs to the second set (Α Π Β) U (А П С). On the other hand let у denote an element of the set (Α Π Β) U (А П С). It belongs to Α Π Б or it belongs to А П С Therefore it belongs to A and it belongs to В or to С Thus у belongs to А П (Б U С) and we have shown that every element of the second set (Α Π Β) U (А П С) belongs to the first set Α Π (Β U С). Since each element of the first set belongs to the second set and each element of the second belongs to the first, the two sets are equal, Α Π (В U С) = (А П В) U (А П С). QED  Exercises 41 1. Prove that for all sets A, #, С the formula A U (Β Π С) = (Л U В) П (Л U С) is true. 2. If several sets Л, Б, С, ... all are subsets of the same set X then the differences X \ A, X \ Z?, X \ C, ...are the complements of Α, β, С, ... in X and are denoted Ac, 5C, Cr, .... The symbol Ac is read "A complement." (a) Prove that (Ar)c = A. (b) Prove deMorgan's Law: (Α Π #)c = Ac U Bc and derive from it the law (A U £)c = Ac Π £c. (c) Draw Venn diagrams to illustrate the two laws. (d) Generalize these laws to more than two sets. 3. Recast the following English sentences in mathematics, using correct mathematical grammar. Preserve their meaning. (a) 2 is the smallest prime number. (b) The area of any bounded plane region is bisected by some line parallel to the jc-axis. *(c) "All that glitters is not gold." *4. What makes the following sentence ambiguous? "A death row prisoner can't have too much hope." 5. Negate the following sentences in English using correct mathematical grammar. (a) If roses are red, violets are blue. *(b) He will sink unless he swims. 6. Why is the square of an odd integer odd and the square of an even integer even? What is the situation for higher powers? [Hint: Prime factorization.] 7. (a) Why does 4 divide every even integer square? (b) Why does 8 divide every even integer cube? (c) Why can 8 never divide twice an odd cube? (d) Prove that the cube root of 2 is irrational. 8. Suppose that the integer к is not a perfect nth power. (a) Prove that l/k £ Q. (b) Infer that the n^ root of an integer is either an integer or it is irrational. It is never a fraction. 9. Let χ = A\B, x' = A'\B' be cuts in Q. We defined x + x' = (A + A') | rest of Q.  42 Real Numbers Chapter 1 (a) Show that although В + В' is disjoint from A + A\ it may happen in degenerate cases that Q is not the union of A + A' and В + В'. (b) Infer that the definition of χ + xf as (Λ + A')\(B + Bf) would be incorrect. (c) Why did we not define χ · xf = (A · A')|rest of Q? 10. A multiplicative inverse of a nonzero cut χ = A\B is a cut у = C\D such that χ · у = 1*. (a) If χ > 0*, what are С and £>? (b) If χ < 0*, what are they? (c) Prove that χ uniquely determines y. 11. Prove that there exists no smallest positive real number. Does there exist a smallest positive rational number? Given a real number jc, does there exist a smallest real number у > jc? 12. Let b = 1. u. b. S, where S is a bounded nonempty subset of M. (a) Given 6 > 0 show that there exists an s e S with Ь - € < s < b. (b) Can s e S always be found so that b — € < s < Ы (c) If χ = Л|Б is a cut in Q, show that χ = 1. u. b. Λ. 13. Prove that y/2 6 Μ by showing that χ - χ = 2 where χ = A\B is the cut in Q with A = {r = Q : r < 0 or r2 < 2}. [Hint: Use Exercise 12. See also Exercise 15, below.] 14. Given у e Μ, η 6 Ν, and 6 > 0, show that for some δ > 0, if |и — y\ < <5 then Iw71 — yn\ < 6. [Hint: Prove the inequality when η = 1, η = 2, and then do induction on η using the identity и» - yn = (u - y)(un-{ + un~2y + · · · + У1"1).] 15. Given χ > 0 and η 6 N, prove that there is a unique у > 0 such that yn — χ. That is, у = фс exists and is unique. [Hint: Consider у = l.u.b.{j eR:sn < jc}. Then use Exercise 14 to show that yn can be neither < χ nor > x.] 16. Prove that real numbers correspond bijectively to decimal expansions not terminating in an infinite strings of 9's, as follows. The decimal expansion of jc e Μ is N.x\x2 ... where N is the largest integer < x. x} is the largest integer < \0(x — N), x2 is the largest integer < 100(jc -(N+ jc, /10)), and so on.  Exercises 43 (a) Show that each xk is a digit between 0 and 9. (b) Show that for each к there is an i > к such that χι φ 9. (c) Conversely, show that for each such expansion N.x\X2 ... not terminating in an infinite string of 9's, the set X\ X\ Χί 10 10 100 ; is bounded and its least upper bound is a real number χ with decimal expansion N\x\X2 (d) Repeat the exercise with a general base in place of 10. 17. Formulate the definition of the greatest lower bound (g.l.b.) of a set of real numbers. State a g.l.b. property of Μ and show it is equivalent to the l.u.b. property of R. 18. Let / : A —* В be a function. That is, / is some rule or device which, when presented with any element α e Λ, produces an element b = / (a) of В. The graph of / is the set S of all pairs (a,b) e Αχ Β such that b = f(a). (a) If you are given a subset S С А χ Б, how can you tell if it is the graph of some function? (That is, what are the set theoretic properties of a graph?) (b) Letg : В -+ С be a second function and consider the composed function g о / : Л -> С. Assume that A = В = С = [0, I], draw Λ χ Β χ С as the unit cube in 3-space, and try to relate the graphs of /, g, and g о / in the cube. 19. A fixed point of a function / : Л —> A is a point я е Л such that f(a) = a. The diagonal of A x A is the set of all pairs (a, a) in Λ χ A. (a) Show that f : A —> A has a fixed point if and only if the graph of / intersects the diagonal. (b) Prove that every continuous function / : [0, 1] —> [0, 1] has at least one fixed point. (c) Ts the same true for continuous functions / : (0, 1) -* (0, l)?f (d) Is the same true for discontinuous functions? 20. Given a cube in Rm, what is the largest ball it contains? Given a ball in Rm, what is the largest cube it contains? What are the largest ball and cube contained in a given box in Шт ? ' A question posed in this manner means that, as well as answering the question with a "yes" or a "no," you should give a proof if your answer is "yes" or a specific counter-example if your answer is "no." Also, to do this exercise you should read Theorems 22, 23, 24.  44 Real Numbers Chapter 1 21. A rational number p/q is dyadic if q is a power of 2, g = 2* for some nonnegative integer k. For example 0, 3/8, 3/1, —3/256, are dyadic rationals, but 1/3, 5/12 are not. A dyadic interval is [a, b] where a = p/2* and b = (p + \)/2k. For example, [.75, 1] is a dyadic interval but [1, π], [0, 2], and [.25, .75] are not. A dyadic cube is the product of dyadic intervals having equal length. The set of dyadic rationals may be denoted as Q2 and the dyadic lattice as (Qg1. (a) Prove that any two dyadic squares (i.e., planar dyadic cubes) of the same size are either identical or intersect only along their edges. (b) Show that the same intersection property is true for dyadic cubes in Rm, when "edge" is interpreted as "(m — 1)- dimensional face." 22. (a) Given 6 > 0, show that the unit disc contains finitely many dyadic squares whose total area exceeds π — 6, and which intersect each other only along their boundaries. *(b) Show that the assertion is false for e < π/2 if we demand that the dyadic squares be disjoint. (c) Formulate (a) in dimension m = 3 and m > 4. *(d) Do the analysis with squares and discs interchanged. That is, given € > 0 prove that finitely many disjoint discs can be drawn inside the unit square so that the total area of the discs exceeds 1-6. *23. Let b(R) and s(R) be the number of integer unit cubes in Rm that intersect the ball and sphere of radius /?, centered at the origin. (a) Let m = 2 and calculate the limits s(R) s(R)2 lim and lim . tf^oo b(R) R-*oc b(R) (b) Take m > 3. What exponent к makes the limit r s(R)k lim д-ос b(R) interesting? (c) Let c(R) be the number of integer unit cubes that are contained in the ball of radius /?, centered at the origin. Calculate lim ——— R^oc b(R)  Exercises 45 (d) Shift the ball to a new, arbitrary center (not on the integer lattice) and re-calculate the limits. *24. Let f(k, m) be the number of ^-dimensional faces of the ra-cube. See Table 1. Jk = 0 1 k = ι 1k=2 1к=з 1k=A \ m = 1 2 1 0 0 0 m = 2 4 4 1 0 0 m = 3 8 12 6 1 0 m = 4 /(0,4) /0,4) /(2,4) /0,4) /(4,4) m = 5 /(0, 5) /(1,5) /(2, 5) /(3, 5) /(4, 5) m /(0,m) /0,m) /(2,m) /(3, m) /(4,m) m + 1 /(0,m+l) /U,m + 1) /(2,m + l) /(3,m+l) /(4,m + l) Table 1 /(^, m) is the number of ^-dimensional faces of the m-cube. (a) Verify the numbers in the first three columns. (b) Calculate the columns m = 4, m = 5, and give the formula for passing from the тш column to the (m + l)st. (c) What would anm = 0 column mean? (d) Prove that the alternating sum of the entries in any column is 1. That is, 2-1 = 1,4-4+ 1 = 1, 8 - 12 + 6 - 1 = 1, and in general X)(— l)k f(k. m) — 1. This alternating sum is called the Euler characteristic. Prove that the interval [a, b] in IR is the same as the segment [a, b] 25. in IR1. That is, {x e R : a < χ < b} ={y 6l:3i,fe[0,l], s + t = 1, and у = sa + tb}. [Hint: How do you prove that two sets are equal?] 26. A convex combination of w\,..., Wk e M™ is a vector sum w — s\VJ\ Л hSkWk such that s\ -\ h ty = 1 and 0 < s\, ..., s> < 1. (a) Prove that if a set Ε is convex then Ε contains the convex combination of any finite number of points in E. (b) Why is the converse obvious?  46 Real Numbers Chapter 1 27. (a) Prove that the ellipsoid 2 2 2 aL bL xL is convex. [Hint: Ε is the unit ball for a different dot product. What is it? Does the Cauchy-Schwarz inequality not apply to all dot products?] (b) Prove that all boxes in IRm are convex. 28. A function / : (a, b) —> Ж is a convex function if for all x, у е (a, b) and all s, t e [0. 1] with s + t = 1, f(sx + ty)<sf(x)+tf(y). (a) Prove that / is convex if and only if the set S of points above its graph is convex in IR2. The set S is {(x, y) : f(x) < y]. *(b) Prove that a convex function is continuous. (c) Suppose that / is convex and a < χ < и < b. The slope σ of the line through (jc, f(x)) and (w, f(u)) depends on χ and u, a = σ(Χ и). Prove that σ increases when χ increases, and σ increases when и increases. (d) Suppose that / is second-order differentiable. That is. / is differentiable and its derivative ff is also differentiable. As is standard, write (/')' = /"· Prove that / is convex if and only if/"(*) > Oforallx e (ащЬ). (e) Formulate a definition of convexity for a function / : Μ —> Ш where Μ с Шт is a convex set. [Hint: Start with m — 2.J *29. Suppose that Ε is a convex region in the plane bounded by a curve C. (a) Show that С has a tangent line except at a countable number of points. [For example, the circle has a tangent line at all its points. The triangle has a tangent line except at three points, and so on.] (b) Similarly, show that a convex function has a derivative except at a countable set of points. *30. Suppose that a function / : [a, b] —> Ш is monotone increasing: i.e.. (a) Prove that / is continuous except at a countable set of points. [Hint: Show that at each χ e (a4b), f has right limit f(x+) and a left limit / (x —). which are limits of / (x -\-h) as h tends to 0 through positive, and negative values respectively. The jump  Exercises 47 of / at χ is fix-l·) — fix—)- Show that / is continuous at χ if and only if it has zero jump at x. At how many points can / have jump > 1 ? At how many points can the jump be between 1/2 and 1? Between 1/3 and 1/2?1 (b) Is the same assertion true for a monotone function defined on all of E? 31. Find an exact formula for a bijection / : Ν χ Ν -> N. Is one /(,, Л _ Ж>+2+.. .+0ЧУ-2» _ /;+;;+iC2;-3)-;+2? 32. Prove that the union of denumerably many sets Bk, each of which is countable, is countable. How could it happen that the union is finite? 33. Without using the Schroeder-Bernstein Theorem, (a) Prove that [a, b] — ia,b] ~ (a, b). (b) More generally, prove that if С is countable then E\C - Ε ~ EUC. (c) Infer that the set of irrational numbers has the same cardinality as Ε, Ε \ Q - E. 34. Prove that E2 - E. [Hint: Think of shuffling two digit strings (αχα^α^ ... )&(7?ι/?2^3 ...)—> iaxbxa^b^a^b^ ...). In this way you could transform a pair of reals into a single real. Be sure to face the nines-termination issue.] 35. Let S be a set and let V = 7^(5) be the collection of all subsets of S. [V(S) is called the power set of S.] Let Τ be the set of functions /:S->{0,1}. (a) Prove that there is a natural bijection from Τ onto V defined by f^{seS:f(s) = \}. *(b) Prove that the cardinality of V is greater than the cardinality of 5, even when S is empty or finite. [Hints: The notation Yx is sometimes used for the set of all functions X -+ Y. In this notation, Τ = {0, l}5 and assertion (b) becomes #iS) < #({0, \}s). The empty set has one subset, itself, whereas it has no elements, so #(0) = 0, while #({0, 1 }0) = 1. Assume there is a bijection from S onto V. Then there is a bijection β : S —* J7, and for each s e S, Pis) is a function, say fs:S—> {0, I}. Think like Cantor and try to find a function which corresponds to no s. Infer that β could not have been onto.]  48 Real Numbers Chapter 1 36. A real number is algebraic if it is a root of a nonconstant polynomial with integer coefficients. (a) Prove that the set Λ of algebraic numbers is denumerable. [Hint: Each polynomial has how many roots? How many linear polynomials are there? How many quadratics? ...] (b) Repeat the exercise for roots of polynomials whose coefficients belong to some fixed, arbitrary denumerable set S. *(c) Repeat the exercise for roots of trigonometric polynomials with integer coefficients. 37. A finite word is a finite string of letters, say from the roman alphabet. (a) What is the cardinality of the set of all finite words, and thus of the set of all possible poems and mathematical proofs? (b) What if the alphabet had only two letters? (c) What if it had countably many letters? (d) Prove that the cardinality of the set Έη of all infinite words formed using a finite alphabet of η letters, η > 2, is equal to the cardinality of E. (e) Give a solution to Exercise 34 by justifying the equivalence chain Ε2 = Ε χ Ε - Σ2 χ Σ2 ~ Σ4 - Σ2 - Ε. (f) How many decimal expansions terminate in an infinite string of 9's? How many don't? 38. If ν is a value of a continuous function / : [a, b] —> Ε use the l.u.b. property to prove that there are smallest and largest χ e [a,b] such that f(x) = v. 39. A function defined on an interval [a. b] or (a, b) is uniformly continuous if for each e > 0 there exists a δ > 0 such that |jc — r| < δ implies that I/O) - /(f) I < e. (Note that this δ can not depend on x, it can only depend on 6. With ordinary continuity, the δ can depend on both χ and 6.) (a) Show that a uniformly continuous function is continuous but continuity does not imply uniform continuity. (For example, prove that sin(l/x) is continuous on the interval (0, 1) but is not uniformly continuous there. Graph it.) (b) Is the function 2x uniformly continuous on the unbounded interval (—oo, oo)? (c) What about jc2? *40. Prove that a continuous function defined on an interval [a, b] is uniformly continuous. [Hint: Let 6 > 0 be given. Think of 6 as fixed  Exercises 49 and consider the sets A(5) ={u e [a, b] : if jc, t e [a, u] and \x - t\ < 8 then \f(x) - f(t)\ < 6} A=(jA(S). <5>0 Using the least upper bound principle, prove that b e A. Infer that / is uniformly continuous. The fact that continuity on [a, b] implies uniform continuity is one of the important, fundamental principles of continuous functions.] *41. Define injections / : N -* N and g : N -* N by f(n) = In and g(n) = 2n. From / and g, the Schroeder-Bernstein Theorem produces a bijection N —> N. What is it? *42. Let (an) be a sequence of real numbers. It is bounded if the set A = {a\, a2,...} is bounded. The limit supremum. or lim sup. of (an) as η —> oo is lim sup an = lim ( sup a^) (a) If the sequence (an) is bounded, why does the lim sup exist? (b) If sup{an} = oo, what is lim sup αηΊ (c) If lim^oo an = — oo, how should we define lim sup anl (d) When is it true that lim sup(an + bn) < lim sup an + lim sup bn lim sup can = с lim sup aw ? (e) Define the limit iillinium, or lim inf, of a sequence of numbers, and find a formula relating it to the limit supremum. **43. The unit ball with respect to a norm || || on R2 is {i;eR2:|MI< I}. (a) Find necessary and sufficient geometric conditions on a subset of IR2 that it be the unit ball for some norm. (b) Give necessary and sufficient geometric conditions that a subset be the unit ball for a norm arising from an inner product. (c) Generalize to IRm. [You may find it useful to read about closed sets in the next chapter, and to consult Exercise 38 there.]  50 Real Numbers Chapter 1 44. Assume that V is an inner product space whose inner product induces a norm as \x\ = y/(x, x). (a) Show that | | obeys the parallelogram law \x + y\2 + \x-y\2 = 2\x\2 + 2\y\2 for all x, у е V. *(b) Show that any norm obeying the parallelogram law arises from a unique inner product. [Hints: Define the prospective inner product as Checking that ( , ) satisfies the inner product properties of symmetry and positive definiteness is easy. Also it is immediate that \x\2 = (jc, x), so ( , ) induces the given norm. Checking bilinearity is another story, (i) Let x9y,z £ V be arbitrary. Show that the parallelogram law implies (x + y,z) + {x- y, z) = 2(x, y), and infer that (2x, z) = 2(л\ ζ). For arbitrary w, υ e V set χ = ~(u + v), у = ^(u — υ), plug in to the previous equation, and deduce (u,z) + (v,z) = (u + υ,ζ)9 which is additive bilinearity in the first variable. Why does it now follow at once that ( , ) is also additively bilinear in the second variable? (ii) To check multiplicative bilinearity, prove by induction that if m e Ъ then m(x9 y) = (mx, y), and if η 6 N then i(jc, y) = (^x4 y). Infer that r(x, y) = (rx, y) when r is rational. Is λ н» (λχ4 у) — λ{χ, у) a continuous function of λ 6 К, and does this give multiplicative bilinearity?]  2 A Taste of Topology 1 Metric Space Concepts It may seem paradoxical at first, but a specific math problem can be harder to solve than some abstract generalization of it. For instance, if you want to know how many roots the equation t5 - 4t4 + t3 - t + 1 = 0 can have, then you could use calculus and figure it out. It would take a while. But thinking more abstractly, and with less work, you could show that any 77th degree polynomial has at most η roots. In the same way many general results about functions of a real variable are more easily grasped at an abstract level — the level of metric spaces. Metric space theory can be seen as a special case of general topology, and many books present it that way, explaining compactness primarily in terms of open coverings. In my opinion, however, the sequence/subsequence approach provides the easiest and simplest route to mastering the subject. Accordingly it gets top billing throughout this chapter. A metric space is a set Μ, the elements of which are referred to as points of M, together with a metric d having the three properties that distance has in Euclidean space. The metric d = J(jc, y) is a real number defined for all points x, у e Μ and d(x, y) is called the distance from the point χ to the point y. The three distance properties are: for all x, y, ζ £ Μ,  52 A Taste of Topology Chapter 2 (a) positive definiteness: d(x, y) > 0, and d(x, у) = 0 if and only if χ = y. (b) symmetry: d{x, y) = d(y, x). (c) triangle inequality: d(x,z) < d(x, y) +d(y, z). The function d is also called the distance function. Strictly speaking, it is the pair (M, d) which is a metric space, but we will follow the common practice of referring to "the metric space Μ," and leave to you the job of inferring the correct metric. The main examples of metric spaces are R, Rm, and their subsets. The metric on R is d{x, y) = \x — y\ where ijel and \x — y\ is the magnitude of χ — y. The metric on Rm is the Euclidean length of χ — у where χ, у are vectors in Rm. Namely, d(x, y) = y/(xi - yi)2 Η + (xm- Ут)2 for χ = (xi,..., xm) and у = (yu ..., ym). Since Euclidean length satisfies the three distance properties, d is a bona fide metric and it makes Rm into a metric space. A subset Μ С Rm becomes a metric space when we declare the distance between points of Μ to be their Euclidean distance apart as points in Rm. We say that Μ inherits its metric from Rm and is a subspace of Rm. Figure 22 shows a few subsets of R2 to suggest some interesting metric spaces. There is also one metric that is hard to picture but valuable as a source for counter-examples, the discrete metric. Given any set Μ define the distance between distinct points to be 1 and the distance between any point and itself to be 0. This is a metric. If Μ consists of three points, say Μ = {a, b, c}, you can think of the vertices of the unit equilateral triangle as a model for M. See Figure 23. They have mutual distance 1 from each other. If Μ consists of one, two, or four points can you think of a model for the discrete metric on M? More challenging is to imagine the discrete metric on R. All points, by definition of the discrete metric, lie at unit distance from each other. Convergent sequences and subsequences A sequence of points in a metric space Μ is a list pb /?2, - - - where the points pn belong to M. Repetition is allowed, and not all the points of Μ need to appear in the list. Good notation for a sequence is (/?„), or (Pn)neN· The notation {pn} is also used but it is too easily confused with the set of points making up the sequence. The difference between (pn)neN and [pn : η e N} is that in the former case the sequence prescribes an ordering of the points, while in the latter the points get jumbled together.  Section 1 Metric Space Concepts 53 Figure 22 Five metric spaces: a closed outward spiral, a Hawaiian earring, a topologist's sine circle, an infinite television antenna, and Zeno's maze. Figure 23 The vertices of the unit equilateral triangle form a discrete metric space. For example, the sequences 1,2,3,... and 1,2,1,3,2,1,4,3,2,1,... are different sequences but give the same set of points, namely N. Formally, a sequence is a function / : N -^ M. The nth term in the sequence is f(n) = pn. Clearly, every sequence defines a function / :  54 A Taste of Topology Chapter 2 N —> Μ and conversely, every function f :N —> Μ defines a sequence in M. The sequence (/?„) converges to the limit ρ in Μ if V6 > 0 3N e N such that η e N and π > N =* d(/?„, p) < 6. Limits are unique in the sense that if (рл) converges to ρ and if (pn) also converges to p' then ρ — ρ'. The reason is this. Given any 6 > 0, there are integers N, Nr such that if η > /V then d(/?„, /?) < 6, while ifn > Nf then d(/?„, //) < 6. Then for all л > max{7V, W}, dip. p') < d(p. /*„) + d(p„, p) < 6 + 6 = 2б. But 6 is arbitrary and so d(p, //) = 0 and ρ = /?'. (This is the 6-principle again.) We write pn —► p, or /?„ —> ρ as η —> oo, or lim рл = ρ и-» ου to indicate convergence. For example, in R the sequence pn = \/n converges to 0 as η -+ oo. In IR2 the sequence (1/w, sin η) does not converge as и -> oo. In the metric space Q (with the metric it inherits from Ж) the sequence 1, L.4, 1.41, 1.414, ... does not converge. Just as a set can have a subset, a sequence can have a subsequence. For example, the sequence 2, 4, 6, 8,... is a subsequence of 1, 2, 3, 4,... . The sequence 3, 5, 7, 11, 13, 17,... is a subsequence of 1, 3, 5, 7, 9 which in turn is a subsequence of 1, 2, 3, 4,... .In general, if (pn)nen and (qk)keN are sequences and if there is a sequence 1 < n\ < η-ι < n^ < ... of integers such that for each к eN ,qk = рщ then (q^) is a subsequence of ipn). Note that the terms in the subsequence occur in the same order as in the mother sequence. 1 Theorem Every subsequence of a convergent sequence converges and it converges to the same limit as does the mother sequence. Proof Let (qk) be a subsequence of (pn) q^ — рПк, where η\ < η2 < Assume that (p„) converges to ρ in M. Given 6 > 0, there is an N such that for all η > TV, d(pl2, ρ) < 6. Since n\, η>ι, ... are integers, к < η к for all к. Thus, if /r > N then nk > N and J(^, /7) < 6. Hence (#*) converges to p. D A common way to state Theorem 1 is that limits are unaffected when we pass to a subsequence.  Section 1 Metric Space Concepts 55 Continuity In linear algebra the objects of interest are linear transformations. In real analysis the objects of interest are functions, especially continuous functions. A function / from the metric space Μ to the metric space TV is just that; f : Μ —> N and / sends points ρ £ Μ to points fp e N. A function is also called a transformation, a mapping, or a map. The function maps Μ to N. The way you should think of functions — as devices, not formulas — is discussed in Section 4 of Chapter 1. The most common type of function maps Μ to IR. It is a real-valued function of the variable ρ £ Μ. Definition A function / : Μ -> N is continuous if it satisfies the e, 8 condition: V6 > 0 and V/7 £ Μ 38 > 0 such that q € Μ and d{p. q) < 8 => d(fp, fq) < 6. Here and in what follows, the notation fp is used as convenient shorthand for f(p). Consider the case of a real valued function of a real variable/ : (a,fc) —> Ш as in Chapter 1. There we defined / to be continuous when V6 > 0 and Vx e{a,b) 38 > 0 such that у £ (α, b) and \x — y\ < 8 => \fx — fy\ < 6. In case Μ = (a,b) and N = R, the two 6, 8 definitions are identical except in the second we write out explicitly the distance in IR as \x — y\ instead of d(x4 y). Thus, every continuous real function of a real variable is an example of a continuous mapping from the metric space (a, b) to the metric space IR, and conversely, every continuous map from the metric space (a, b) to the metric space IR is a continuous function of a real variable. How is continuity expressed using sequences? Nothing could be simpler or more natural. 2 Theorem f : Μ —± N is continuous if and only if it sends each convergent sequence in Μ to a convergent sequence in N, limits being sent to limits. Proof Suppose that / is continuous and (pn) is a convergent sequence in M, lim pn = p.  56 A Taste of Topology Chapter 2 Then (f(pn)) is a sequence in N. Continuity implies that given e > 0. there exists 8 > 0 such that d(x, ρ) < 8 implies d(fx, fp) < e. Convergence implies that there is an N such that for all и > N, d(pn, p) < 8. Then d(f(pn), fp) < e and lim f(pn) = fp. и-»ос We prove the converse in contrapositive form: if / is not continuous then it does not preserve convergence. / being not continuous means that for some ρ € Μ there is an 6 > 0 such that no matter how small we take <5, there will always be points χ e Μ with d(x, p) < 8 but d(fx, fp) > €. Take «i = l, «2 = 1/2, ... δη = \/η, ... For each 8n there is a point xn with d(xn, p) < 8n = \/n and d(f(xn), fp) > €· Thus lim xn — ρ «—►ос but /(*„) does not converge to fp. D See also Exercise 17. 3 Corollary Гйе composite of continuous functions is continuous. Proof Let f : Μ -+ N and g : Ν -+ Ρ be continuous and assume that lim pn = Ρ и—юс in Μ. Since / is continuous, Theorem 2 implies that lim f{pn) = /p. Since g is continuous, Theorem 2 implies that lim g(f(pn)) = g(fp) and «-►ОС therefore g о / : Μ —> Ρ is continuous. See Figure 24. D Figure 24 The composite function go/.  Section 1 Metric Space Concepts 57 Moral The sequence condition is the easy way to tell at a glance whether a function is continuous. Homeomorphism Vector spaces are isomorphic if there is a linear bijection from one to the other. When are metric spaces isomorphic? They should "look the same." The letters Υ and Τ look the same; and they look different from the letter O. If / : Μ -+ N is a bijection and / is continuous and the inverse bijection f~l:N-+Mis also continuous then / is a homeomorphism* (or a "homeo" for short) and Μ, Ν are homeomorphic. We write Μ = N to indicate that Μ and N are homeomorphic. = is an equivalence relation: Μ = Μ since the identity map is a homeomorphism Μ -> Μ; Μ = Ν clearly implies that Ν = Μ; and the previous corollary shows that the composite of homeomorphisms is a homeomorphism. Geometrically speaking, a homeomorphism is a bijection that can bend, twist, stretch, and wrinkle the space Μ to make it coincide with N, but it can not rip, puncture, shred, or pulverize Μ in the process. The basic questions to ask about metric spaces are: (a) Given Μ, Ν, are they homeomorphic? (b) What are the continuous functions from Μ to N? A major goal of this chapter is to show you how to answer these questions in many cases. For example, is the circle homeomorphic to the interval? To the sphere? etc. Figure 25 indicates that the circle and the (perimeter of the) triangle are homeomorphic, while Figure 14 shows that (a,b), the semicircle, and IR are homeomorphic. Figure 25 The circle and triangle are homeomorphic. ^ This is a rare case in mathematics in which spelling is important. Homeomorphism φ homomor- phism.  58 A Taste of Topology Chapter 2 A natural question that should occur to you is whether continuity of f~x is actually implied by continuity of a bijection /. It is not. Here is an instructive example. Consider the interval [0, 2π) = {χ £ IR : 0 < χ < 2π} and define / : [0, 2π) -+ Sl to be the mapping f(x) = (cosjc, shut) where S] is the unit circle in t

Real Mathematical Analysis Charles Chapman Pugh Pdf

Source: https://b-ok.asia/book/1300111/734914

Posted by: martinthews1997.blogspot.com

Share this post