Description

This is a course in calculus in several variables. The following is core material: Basic topology of n-dimensional Euclidian space; limits and continuity of functions; the derivative as a linear transformation; Taylor’s formula with remainder; the Inverse and Implicit Function Theorems, change of coordinates; integration (including transformation of integrals under changes of coordinates); Green’s Theorem.

7 attachmentsSlide 1 of 7attachment_1attachment_1attachment_2attachment_2attachment_3attachment_3attachment_4attachment_4attachment_5attachment_5attachment_6attachment_6attachment_7attachment_7

Unformatted Attachment Preview

QUIZ 9. ADVANCED MULTIVARIABLE CALCULUS,

SPRING 2021

1. (5 pts) Prove that every convergent sequence in Rn is a set of

volume zero.

2. (5 pts) Let E be a Jordan region in Rn , and c > 0. Let

F = cE = {cx : x ∈ E}.

Prove that F is a Jordan region, and Vol(F ) = cn Vol(E).

3. (5 pts) Prove that the area of the triangle with vertices (0, 0), (0, 1), (1, 0)

in R2 is 1/2. Use only facts from Section 12.1, integration is not allowed.

1

AN INTRODUCTION TO ANALYSIS

This page intentionally left blank

AN INTRODUCTION TO ANALYSIS

Fourth Edition

William R. Wade

University of Tennessee

Upper Saddle River, New Jersey 07458

Library of Congress Cataloging-in-Publication Data

Wade, W. R.

An introduction to analysis / William R. Wade. — 4th ed.

p. cm.

Includes bibliographical references and index.

ISBN 978-0-13-229638-0 (alk. paper)

1. Mathematical analysis—Textbooks. I. Title.

QA300.W25 2010

515—dc22

2009023698

Editor-in-Chief: Deirdre Lynch

Senior Acquisitions Editor: William Hoffman

Associate Editor: Caroline Celano

Project Manager, Production: Robert S. Merenoff

Associate Managing Editor: Bayani Mendoza de Leon

Senior Managing Editor: Linda Mihatov Behrens

Operations Specialists: Ilene Kahn/Carol Melville

Executive Marketing Manager: Jeff Weidenaar

Marketing Assistant: Kendra Bassi

Senior Design Supervisor: Andrea Nix

Art Director / Cover Designer: Barbara Atkinson

Compositor / Art studio: Integra Software Services, Pvt. Ltd, Pondicherry, India

Photographer: © Matt C. Jones

Cover image: 360 Bridge in Austin, TX

© 2010, 2004, 2000, 1995 by Pearson Education, Inc.

Pearson Prentice Hall

Pearson Education, Inc.

Upper Saddle River, NJ 07458

All rights reserved. No part of this book may be reproduced, in any

form or by any means, without permission in writing from the publisher.

Pearson Prentice Hall™ is a trademark of Pearson Education, Inc.

Printed in the United States of America

10 9 8 7 6 5 4 3 2 1

ISBN-13:

ISBN-10:

978-0-13-229638-0

0-13-229638-1

Pearson Education, Ltd., London

Pearson Education Australia PTY. Limited, Sydney

Pearson Education Singapore, Pte., Ltd

Pearson Education North Asia Ltd, Hong Kong

Pearson Education Canada, Ltd., Toronto

Pearson Educación de Mexico, S.A. de C.V.

Pearson Education – Japan, Tokyo

Pearson Education Malaysia, Pte. Ltd

Pearson Education Upper Saddle River, New Jersey

To Cherri, Peter, and Benjamin

This page intentionally left blank

Contents

Preface

PART I

x

ONE-DIMENSIONAL THEORY

1 The Real Number System

1.1 Introduction . . . . . . . . . . .

1.2 Ordered Field Axioms . . . . . .

1.3 Completeness Axiom . . . . . .

1.4 Mathematical Induction . . . . .

1.5 Inverse Functions and Images .

1.6 Countable and Uncountable Sets

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

1

1

5

16

23

29

35

2 Sequences in R

2.1 Limits of Sequences . . . . . .

2.2 Limit Theorems . . . . . . . .

2.3 Bolzano–Weierstrass Theorem

2.4 Cauchy Sequences . . . . . . .

∗ 2.5 Limits Supremum and Inﬁmum

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

41

41

46

53

58

61

.

.

.

.

.

3 Functions on R

3.1 Two-Sided Limits . . . . . . . . . . . . .

3.2 One-Sided Limits and Limits at Inﬁnity

3.3 Continuity . . . . . . . . . . . . . . . . .

3.4 Uniform Continuity . . . . . . . . . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

68

68

76

83

92

4 Differentiability on R

4.1 The Derivative . . . . . . . . . . . . . .

4.2 Differentiability Theorems . . . . . . .

4.3 The Mean Value Theorem . . . . . . . .

4.4 Taylor’s Theorem and l’Hôpital’s Rule .

4.5 Inverse Function Theorems . . . . . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

98

98

105

109

117

125

5 Integrability on R

5.1 The Riemann Integral . . . . . . . . . .

5.2 Riemann Sums . . . . . . . . . . . . . .

5.3 The Fundamental Theorem of Calculus

5.4 Improper Riemann Integration . . . . .

∗ 5.5 Functions of Bounded Variation . . . .

∗ 5.6 Convex Functions . . . . . . . . . . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

130

130

141

152

163

170

175

vii

viii

Contents

6 Inﬁnite Series of Real Numbers

6.1 Introduction . . . . . . . . . .

6.2 Series with Nonnegative Terms

6.3 Absolute Convergence . . . .

6.4 Alternating Series . . . . . . .

∗ 6.5 Estimation of Series . . . . . .

∗ 6.6 Additional Tests . . . . . . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

184

184

192

198

209

214

219

7 Inﬁnite Series of Functions

7.1 Uniform Convergence of Sequences

7.2 Uniform Convergence of Series . .

7.3 Power Series . . . . . . . . . . . . .

7.4 Analytic Functions . . . . . . . . . .

∗ 7.5 Applications . . . . . . . . . . . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

222

222

230

237

249

261

.

.

.

.

.

.

.

.

.

.

.

.

PART II MULTIDIMENSIONAL THEORY

8 Euclidean Spaces

8.1 Algebraic Structure . . . . . . . . .

8.2 Planes and Linear Transformations .

8.3 Topology of Rn . . . . . . . . . . . .

8.4 Interior, Closure, and Boundary . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

267

267

279

288

297

9 Convergence in Rn

9.1 Limits of Sequences .

9.2 Heine–Borel Theorem

9.3 Limits of Functions . .

9.4 Continuous Functions

∗ 9.5 Compact Sets . . . . .

∗ 9.6 Applications . . . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

303

303

307

312

321

327

330

10 Metric Spaces

10.1 Introduction . . . . . . . . . . .

10.2 Limits of Functions . . . . . . . .

10.3 Interior, Closure, and Boundary

10.4 Compact Sets . . . . . . . . . . .

10.5 Connected Sets . . . . . . . . . .

10.6 Continuous Functions . . . . . .

∗ 10.7 Stone–Weierstrass Theorem . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

342

342

350

355

361

367

372

377

11 Differentiability on Rn

11.1 Partial Derivatives and Partial Integrals . . . . .

11.2 The Deﬁnition of Differentiability . . . . . . . .

11.3 Derivatives, Differentials, and Tangent Planes .

11.4 The Chain Rule . . . . . . . . . . . . . . . . . . .

11.5 The Mean Value Theorem and Taylor’s Formula

11.6 The Inverse Function Theorem . . . . . . . . . .

∗ 11.7 Optimization . . . . . . . . . . . . . . . . . . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

383

383

394

403

412

416

424

435

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

Contents ix

12 Integration on Rn

12.1 Jordan Regions . . . . . . . . . . . . . . .

12.2 Riemann Integration on Jordan Regions

12.3 Iterated Integrals . . . . . . . . . . . . . .

12.4 Change of Variables . . . . . . . . . . . .

∗ 12.5 Partitions of Unity . . . . . . . . . . . . .

∗ 12.6 The Gamma Function and Volume . . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

449

449

462

476

490

503

514

13 Fundamental Theorems of Vector Calculus

13.1 Curves . . . . . . . . . . . . . . . . .

13.2 Oriented Curves . . . . . . . . . . .

13.3 Surfaces . . . . . . . . . . . . . . . .

13.4 Oriented Surfaces . . . . . . . . . .

13.5 Theorems of Green and Gauss . . .

13.6 Stokes’s Theorem . . . . . . . . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

523

523

536

544

555

565

575

14 Fourier Series

∗ 14.1 Introduction . . . . . . . . . .

∗ 14.2 Summability of Fourier Series

∗ 14.3 Growth of Fourier Coefﬁcients

∗ 14.4 Convergence of Fourier Series

∗ 14.5 Uniqueness . . . . . . . . . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

584

584

591

598

606

612

Appendices

A. Algebraic Laws . . . . . . . .

B. Trigonometry . . . . . . . . .

C. Matrices and Determinants .

D. Quadric Surfaces . . . . . . .

E. Vector Calculus and Physics .

F.

Equivalence Relations . . . .

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

619

619

624

629

637

641

644

.

.

.

.

.

.

References

646

Answers and Hints to Selected Exercises

647

Subject Index

667

Notation Index

679

Preface

This text provides a bridge from “sophomore” calculus to graduate courses

which use analytic ideas (e.g., real and complex analysis, partial and ordinary differential equations, numerical analysis, ﬂuid mechanics, and differential geometry). For a two-semester course, the ﬁrst semester should end with

Chapter 8. For a three-quarter course, the second quarter should begin in

Chapter 6 and end somewhere in the middle of Chapter 11.

Our presentation is divided into two parts. The ﬁrst half, Chapters 1 through

7 together with Appendices A and B, gradually introduces the central ideas of

analysis in a one-dimensional setting. The second half, Chapters 8 through 14

together with Appendices C through F, covers multidimensional theory.

More speciﬁcally, Chapter 1 introduces the real number system as a complete,

ordered ﬁeld; Chapters 2 through 5 cover calculus on the real line; and Chapters

6 and 7 discuss inﬁnite series, including uniform and absolute convergence. The

ﬁrst two sections of Chapter 8 give a short introduction to the algebraic structure

of Rn , including the connection between linear functions and matrices.

At that point instructors have two options. They can continue covering

Chapters 8 and 9 to explore topology and convergence in the concrete Euclidean

space setting, or they can cover these same concepts in the abstract metric space

setting (Chapter 10). Since either of these options provides the necessary foundation for the rest of the book, instructors are free to choose the approach they

feel best suits their aims.

With this background material out of the way, Chapters 11 through 13 develop

the machinery and theory of vector calculus. Chapter 14 gives a short introduction to Fourier series, including summability and convergence of Fourier series,

growth of Fourier coefﬁcients, and uniqueness of trigonometric series.

Separating the one-dimensional from the n-dimensional material is not the

most efﬁcient way to present the material, but it does have two advantages. The

more abstract, geometric concepts can be postponed until students have been

given a thorough introduction to analysis on the real line. And, students have

two chances to master some of the deeper ideas of analysis (e.g., convergence of

sequences, limits of functions, and uniform continuity).

We have made this text ﬂexible in another way by including core material and

enrichment material. The core material provides a foundation for the typical

one-year course in analysis. Besides making the book a better reference, the

enrichment material has been included for two other reasons: curious students

can use it to delve deeper into the core material or as a jumping off place to

pursue more general topics, and instructors can use it to supplement their course

or to add variety from year to year.

Enrichment and optional materials are marked with an asterisk. Exercises

which use enrichment material are also marked with an asterisk, and the

x

Preface xi

material needed to solve them is cited in the Answers and Hints section. To

make course planning easier, each enrichment section begins with a statement

which indicates whether that section uses material from any other enrichment

section. Since no core material depends on enrichment material, any of the

latter can be skipped without loss in the integrity of the course.

Most enrichment sections (5.5, 5.6, 6.5, 6.6, 7.5, 9.5, 11.6, 12.6, 14.1) are

independent and can be covered in any order after the core material which precedes them has been dealt with. Sections 9.6 and 12.5 require 9.5, Section 14.3

requires 5.5 only to establish Lemma 14.24. This result can easily be proved

for continuously differentiable functions, thereby avoiding mention of functions

of bounded variation. In particular, the key ideas in Section 14.3 can be covered without the background material from Section 5.5 anytime after ﬁnishing

Chapter 7.

Since for many students this is the last (for some the only) place to see

a rigorous development of vector calculus, we focus our attention on classical, nitty-gritty analysis. By avoiding abstract concepts such as vector spaces

and the Lebesgue integral, we have room for a thorough, comprehensive

introduction. We include sections on improper integration, the gamma function, Lagrange multipliers, the Inverse and Implicit Function Theorem, Green’s

Theorem, Gauss’s Theorem, Stokes’s Theorem, and a full account of the change

of variables formula for multiple Riemann integrals.

We assume the reader has completed a three-semester or four-quarter

sequence in elementary calculus. Because many of our students now take their

elementary calculus in high school (where theory may be almost nonexistent),

we assume that the reader is familiar only with the mechanics of calculus, i.e.,

can differentiate, integrate, and graph simple functions of the form y = f (x) or

z = f (x, y). We also assume the reader has had an introductory course in linear algebra, i.e., can add, multiply, and take determinants of matrices with real

entries, and are familiar with Cramer’s Rule. (Appendix C, which contains an

exposition of all deﬁnitions and theorems from linear algebra used in the text,

can be used as review if the instructor deems it necessary.)

Always we emphasize the fact that the concepts and results of analysis

are based on simple geometric considerations and on analogies with material

already known to the student. The aim is to keep the course from looking like

a collection of tricks and to share enough of the motivation behind the mathematics so that students are prepared to construct their own proofs when asked.

We begin complicated proofs with a short paragraph (marked STRATEGY:)

which shows why the proof works; for example, the Archimedean Principle (Theorem 1.16), Density of Rationals (Theorem 1.18), Cauchy’s Theorem

(Theorem 2.29), Change of Variables in R (Theorem 5.34), Riemann’s

Theorem about rearrangements (Theorem 6.29), the Implicit Function Theorem

(Theorem 11.47), the Borel Covering Lemma (Lemma 9.9), and the fact that a

curve is smooth when φ = 0 (Remark 13.10). We precede abstruse deﬁnitions or theorems with a short paragraph which describes, in simple terms, what

behavior we are examining, and why (e.g., Cauchy sequences, one-sided limits,

upper and lower Riemann sums, the Integral Test, Abel’s Formula, uniform convergence, the total derivative, compact sets, differentiable curves and surfaces,

xii Preface

smooth curves, and orientation equivalence). And we include examples to show

why each hypothesis of a major theorem is necessary (e.g., the Nested Interval Property, the Bolzano–Weierstrass Theorem, the Mean Value Theorem, the

Heine–Borel Theorem, the Inverse Function Theorem, the existence of exact

differentials, and Fubini’s Theorem).

Each section contains a collection of exercises which range from very elementary (to be sure the student understands the concepts introduced in that section) to more challenging (to give the student practice in using these concepts to

expand the theory). To minimize frustration, some of the more difﬁcult exercises have several parts which serve as an outline to a solution of the problem.

To keep from producing students who know theory but cannot apply it, each set

of exercises contains a mix of computational and theoretical assignments. (Exercises which play a prominent role later in the text are marked with a box. These

exercises are an integral part of the course and all of them should be assigned.)

Since many students have difﬁculty reading and understanding mathematics,

we have paid close attention to style and organization. We have consciously

limited the vocabulary, kept notation consistent from chapter to chapter, and

presented the proofs in a uniﬁed style. Individual sections are determined by

subject matter, not by length of lecture, so that students can comprehend related

results in a larger context. Examples and important remarks are numbered

and labeled so that students can read the text in small chunks. (Many of these,

included for the student’s beneﬁt, need not be covered in class.) Paragraphs are

short and focused so that students are not overwhelmed by long-winded explanations. To help students discern between central results and peripheral ones,

the word Theorem is used relatively sparingly; preliminary results and results

which are only used in one section are called Remarks, Lemmas, and Examples.

And we have broken with tradition by stating deﬁnitions explicitly with an “if

and only if.” (How can we chide our students for using the converse of a result

when it appears that we do so about half the time we apply a deﬁnition?)

NEW TO THIS EDITION

We have changed many of the computational exercises so that the answers

are simpler and easier to obtain. We have replaced most of the beginning

calculus–style exercises with slightly more conceptual exercises that emphasize

the same ideas, but at a higher level. We have added many theoretical exercises of medium difﬁculty. We have scattered true-false questions throughout

the ﬁrst six chapters. These are designed to confront common misconceptions

that some students tend to acquire at this level. We have gathered introductory material that was scattered over several sections into a new section entitled

Introduction. This section includes two accessible examples about why proof

is necessary and why we cannot always trust what we see. We have reduced

the number of axioms from four to three by introducing the Completeness Axiom ﬁrst, and using it to prove the Well-Ordering Principle and the Principle of

Mathematical Induction. We have moved Taylor’s Formula from Chapter 7 to

Chapter 4 to offer another example of the utility of the Mean Value Theorem.

We have given the Heine–Borel Theorem its own section and included several

Preface xiii

exercises designed to give students practice in making a local condition on

a compact set into a global one. We have reorganized Section 12.1 (Jordan

regions) to simplify the presentation and make it easier to teach. We have

omited Chapter 15, And we have corrected a number of misprints.

We wish to thank Mr. P. W. Wade and Professors S. Fridli, G. S. Jordan,

Mefharet Kocatepe, J. Long, M. E. Mays, M. S. Osborne, P. W. Schaefer, F. E.

Schroeck, and Ali Sinan Sertoz, who carefully read parts of the ﬁrst edition

and made many valuable suggestions and corrections. Also, I wish to express

my gratitude to Ms. C. K. Wade for several lively discussions of a pedagogical nature, which helped shape the organization and presentation of this material. I wish to thank Der-Chen Chang (Georgetown University), Wen D. Chang

(Alabama State), Patrick N. Dowling (Miami University), Jeffery Ehme

(Spelman College), Dana S. Fine (University of Massachusetts-Dartmouth),

Stephen Fisher (Northwestern University), Scott Fulton (Clarkson University),

Kevin Knudson (Mississippi State University), Maria Nogin (California State

University- Fresno), Gary Weiss (University of Cincinnati), Peter Wolfe (University of Maryland), and Mohammed Yahdi (Ursinus College) who looked at

the fourth edition while it was in manuscript form and did some pre-revision

reviews. I wish to thank Professor Stan Perrine (Charleston Southern University) for checking the penultimate version of the manuscript for accuracy

and typographical errors. Finally, I wish to make special mention of Professor

Lewis Lum, (Portland State University) who continues to make many careful

and perspicuous comments about style, elegance of presentation, and level of

rigor which have found their way into this fourth edition.

If there remain any typographical errors, I plan to keep an up-to-date list at

my Web site (http://www.math.utk.edu/∼wade). If you ﬁnd errors which are not

listed at that site, please contact me via e-mail at iwade@utk.edu.

William R. Wade

Mathematics Department

University of Tennessee

Knoxville, TN 37996-1300

This page intentionally left blank

C H A P T E R

1

The Real Number System

You have already had several calculus courses in which you evaluated limits,

differentiated functions, and computed integrals. You may even remember

some of the major results of calculus, such as the Chain Rule, the Mean Value

Theorem, and the Fundamental Theorem of Calculus. Although you are probably less familiar with multivariable calculus, you have taken partial derivatives,

computed gradients, and evaluated certain line and surface integrals.

In view of all this, you must be asking: Why another course in calculus? The

answer to this question is twofold. Although some proofs may have been presented in earlier courses, it is unlikely that the subtler points (e.g., completeness

of the real numbers, uniform continuity, and uniform convergence) were covered. Moreover, the skills you acquired were mostly computational; you were

rarely asked to prove anything yourself. This course develops the theory of calculus carefully and rigorously from basic principles and gives you a chance to

learn how to construct your own proofs. It also serves as an introduction to

analysis, an important branch of mathematics which provides a foundation for

numerical analysis, functional analysis, harmonic analysis, differential equations,

differential geometry, real analysis, complex analysis, and many other areas of

specialization within mathematics.

1.1

INTRODUCTION

Every rigorous study of mathematics begins with certain undeﬁned concepts,

primitive notions on which the theory is based, and certain postulates, properties

which are assumed to be true and given no proof. Our study will be based on

the primitive notions of real numbers and sets, which will be discussed in this

section.

We shall use standard notation for sets and real numbers. For example, R or

(−∞, ∞) represents the set of real numbers, ∅ represents the empty set (the set

with no elements), a ∈ A means that a is an element of A, and a ∈

/ A means that

a is not an element of A. We can represent a given ﬁnite set in two ways. We can

list its elements directly, or we can describe it using sentences or equations. For

example, the set of solutions to the equation x 2 = 1 can be written as

{1, −1} or

{x : x 2 = 1}.

A set A is said to be a subset of a set B (notation: A ⊆ B) if and only if every

element of A is also an element of B. If A is a subset of B but there is at least

one element b ∈ B that does not belong to A, we shall call A a proper subset of

B (notation: A ⊂ B). Two sets A and B are said to be equal (notation: A = B)

1

2 Chapter 1

The Real Number System

if and only if A ⊆ B and B ⊆ A. If A and B are not equal, we write A = B.

A set A is said to be nonempty if and only if A = ∅.

The union of two sets A and B (notation: A ∪ B) is the set of elements x such

that x belongs to A or B or both. The intersection of two sets A and B (notation:

A ∩ B) is the set of elements x such that x belongs to both A and B. The complement of B relative to A (notation: A B, sometimes B c if A is understood)

is the set of elements x such that x belongs to A but does not belong to B. For

example,

{−1, 0, 1} ∪ {1, 2} = {−1, 0, 1, 2},

{−1, 0, 1} ∩ {1, 2} = {1},

{1, 2} {−1, 0, 1} = {2} and {−1, 0, 1} {1, 2} = {−1, 0}.

Let X and Y be sets. The Cartesian product of X and Y is the set of ordered

pairs deﬁned by

X × Y := {(x, y) : x ∈ X, y ∈ Y }.

(The symbol := means “equal by deﬁnition” or “is deﬁned to be.”) Two points

(x, y), (z, w) ∈ X × Y are said to be equal if and only if x = z and y = w.

Let X and Y be sets. A relation on X × Y is any subset of X × Y . Let R be a

relation on X × Y . The domain of R is the collection of x ∈ X such that (x, y)

belongs to R for some y ∈ Y . The range of R is the collection of y ∈ Y such

that (x, y) belongs to R for some x ∈ X . When (x, y) ∈ R, we shall frequently

write x R y.

A function f from X into Y (notation: f : X → Y ) is a relation on X ×Y whose

domain is X (notation: Dom( f ) := X ) such that for each x ∈ X there is a unique

(one and only one) y ∈ Y that satisﬁes (x, y) ∈ f . If (x, y) ∈ f , we shall call y

the value of f at x (notation: y = f (x) or f : x −→ y) and call x a preimage

of y under f . We said a preimage because, in general, a point in the range

of f might have more than one preimage. For example, since sin(kπ) = 0 for

k = 0, ±1, ±2, . . . , the value 0 has inﬁnitely many preimages under f (x) = sin x.

If f is a function from X into Y , we will say that f is deﬁned on X and call Y

the codomain of f . The range of f is the collection of all values of f ; that is, the

set Ran( f ) := {y ∈ Y : f (x) = y for some x ∈ X }. In general, then, the range

of a function is a subset of its codomain and each y ∈ Ran( f ) has one or more

preimages. If Ran( f ) = Y and each y ∈ Y has exactly one preimage, x ∈ X ,

under f , then we shall say that f : X → Y has an inverse, and shall deﬁne the

inverse function f −1 : Y → X by f −1 (y) := x, where x ∈ X satisﬁes f (x) = y.

At this point it is important to notice a consequence of deﬁning a function

to be a set of ordered pairs. By the deﬁnition of equality of ordered pairs, two

functions f and g are equal if and only if they have the same domain, and same

values; that is, f, g : X → Y , and f (x) = g(x) for all x ∈ X . If they have

different domains, they are different functions.

For example, let f (x) = g(x) = x 2 . Then f : [0, 1) → [0, 1) and g : (−1, 1) →

[0, 1) are two different functions. They both have the same range, [0, 1), but each

√

y ∈ (0, 1) has exactly one preimage under f , namely y, and two preimages

√

√

under g, namely ± y. In particular, f has an inverse function, f −1 (x) = x,

Section 1.1

Introduction 3

but g does not. Making distinctions like this will actually make our life easier

later in the course.

For the ﬁrst half of this course, most of the concrete functions we consider

will be real-valued functions of a real variable (i.e., functions whose domains and

ranges are subsets of R). We shall often call such functions simply real functions.

You are already familiar with many real functions.

1) The exponential function e x : R → (0, ∞) and its inverse function, the natural logarithm

x

dt

,

log x :=

1 t

deﬁned and real-valued for each x ∈ (0, ∞). (Although this last function is

denoted by ln x in elementary calculus texts, most analysts denote it, as we

did just now, by log x. We will follow this practice throughout this text. For a

more constructive deﬁnition, see Exercise 4.5.5.)

2) The trigonometric functions (whose formulas are) represented by sin x, cos x,

tan x, cot x, sec x, and csc x, and the inverse trigonometric functions arcsin x,

arccos x, and arctan x whose ranges are, respectively, [−π/2, π/2], [0, π], and

(−π/2, π/2).

3) The power functions x α , which can be deﬁned constructively (see

Appendix A.10 and Exercise 3.3.11) or by using the exponential function:

x α := eα log x ,

x > 0,

α ∈ R.

We assume that you are familiar with the various algebraic laws and identities

that these functions satisfy. A list of the most widely used trigonometric identities can be found in Appendix B. The most widely used properties of the power

functions are x 0 = 1 for all x = 0; x n = x · . . . · x (there are n factors here) when

n = 1, 2, . . . and x ∈ R;

x α > 0, x α · x β = x α+β , and (x α )β = x α·β for all x > 0

√

α

m

and α, β ∈ R; x = x when α = 1/m for some m ∈ N and the indicated root

exists and is real; and 0α := 0 for all α > 0. (The symbol 00 is left undeﬁned

because it is indeterminate [see Example 4.31].)

We also assume that you can differentiate algebraic combinations of these

functions using the basic formulas (sin x) = cos x, (cos x) = − sin x, and (e x ) =

e x , for x ∈ R; (log x) = 1/x and (x α ) = αx α−1 , for x > 0 and α ∈ R; and

(tan x) = sec2 x

for x =

(2n + 1)π

,

2

n ∈ Z.

(You will have an opportunity to develop some of these rules in the exercises,

e.g., see Exercises 4.2.9, 4.4.6, 4.5.3, 5.3.7, and 5.3.8.) Even with these assumptions, we shall repeat some material from elementary calculus.

We mentioned postulates in the opening paragraph. In the next two sections,

we will introduce three postulates (containing a total of 13 different properties)

which characterize the set of real numbers. Although you are probably already

familiar with all but the last of these properties, we will use them to prove other

4 Chapter 1

The Real Number System

equally familiar properties (e.g., in Example 1.4 we will prove that if a = 0, then

a 2 > 0).

Why would we assume some properties and prove others? At one point,

mathematicians thought that all laws about real numbers were of equal weight.

Gradually, during the late 1800s, we discovered that many of the well-known

laws satisﬁed by R are in fact consequences of others. The net result of this

research is that the 13 properties listed below are considered to be fundamental

properties describing R. All other laws satisﬁed by real numbers are secondary

in the sense that they can be proved using these fundamental properties.

Why would we prove a law that is well known, perhaps even “obvious”? Why

not just assume all known properties about R and proceed from there? We

want this book to be reasonably self-contained, because this will make it easier

for you to begin to construct your own proofs. We want the ﬁrst proofs you

see to be easily understood, because they deal with familiar properties that are

unobscured by new concepts. But most importantly, we want to form a habit of

proving all statements, even seemingly “obvious” statements.

The reason for this hard-headed approach is that some “obvious” statements

are false. For example, divide an 8 × 8-inch square into triangles and trapezoids

as shown on the left side of Figure 1.1. Since the 3-inch sides of the triangles

perfectly match the 3-inch sides of the trapezoids, it is “obvious” that these triangles and trapezoids can be reassembled into a rectangle (see the right side of

Figure 1.1). Or is it? The area of the square is 8 × 8 = 64 square inches but the

area of the rectangle is 5 × 13 = 65 square inches. Since you cannot increase

area by reassembling pieces, what looked right was in fact wrong. By computing slopes, you can verify that the rising diagonal on the right side of Figure 1.1

is, in fact, four distinct line segments that form a long narrow diamond which

conceals that extra one square inch.

NOTE: Reading a mathematics book is different from reading any other kind

of book. When you see phrases like “you can verify” or “it is easy to see,” you

should use pencil and paper to do the calculations to be sure what we’ve said is

correct.

Here is another

√ example. Grab a calculator and graph the functions

√ y =

log x and y = 100 x. It is easy to see, using calculus, that log x and 100 x are

both increasing and concave downward on [0, ∞). Looking

√ at the graphs (see

Figure 1.2), it’s “obvious” that log x is much larger than 100 x no matter how big

1000 : log(e1000 ) = 1000 log e = 1000

x is. Or is it? Let’s evaluate

√ each function at e

√

100 1000

10

e

= e ≈ 22, 000. Evidently, the graph of y = 100 x

is much smaller than

5

5

5

3

3

3

8

8

FIGURE 1.1

5

Section 1.2

Ordered Field Axioms

5

y

3

y = log x

2

1

y = 100√ x

–

5

10

x

FIGURE 1.2

eventually

√crosses that of y = log x. With a little calculus, you can prove that

log x < 100 x forever after that (see Exercise 4.4.6a).
What can be learned from these examples? We cannot always trust what
we think we see. We must, as above, ﬁnd some mathematical way of testing
our perception, either verifying that it is correct, or rejecting it as wrong. This
type of phenomenon is not a rare occurrence. You will soon encounter several
other plausible statements that are, in fact, false. In particular, you must harbor
a skepticism that demands proofs of all statements not assumed in postulates,
even the “obvious” ones.
What, then, are you allowed to use when solving the √
exercises? You may use
any property of real numbers (e.g., 2 + 3 = 5, 2 < 7, or 2 is irrational) without
reference or proof. You may use any algebraic property of real numbers involving equal signs [e.g., (x + y)2 = x 2 + 2x y + y 2 or (x + y)(x − y) = x 2 − y 2 ]
and the techniques of calculus to ﬁnd local maxima or minima of a given function without reference or proof. After completing the exercises in Section 1.2,
you may also use any algebraic property of real numbers involving inequalities
(e.g., 0 < a < b implies 0 < a x < b x for all x > 0) without reference or proof.

1.2

ORDERED FIELD AXIOMS

In this section we explore the algebraic structure of the real number system. We

shall assume that the set of real numbers, R, is a ﬁeld (i.e., that R satisﬁes the

following postulate).

Postulate 1. [FIELD AXIOMS]. There are functions + and ·, deﬁned on R2 :=

R × R, which satisfy the following properties for every a, b, c ∈ R:

Closure Properties. a + b and a · b belong to R.

Associative Properties. a + (b + c) = (a + b) + c and a · (b · c) = (a · b) · c.

Commutative Properties. a + b = b + a and a · b = b · a.

Distributive Law. a · (b + c) = a · b + a · c.

6 Chapter 1

The Real Number System

Existence of the Additive Identity. There is a unique element 0 ∈ R such that

0 + a = a for all a ∈ R.

Existence of the Multiplicative Identity. There is a unique element 1 ∈ R such

that 1 = 0 and 1 · a = a for all a ∈ R.

Existence of Additive Inverses. For every x ∈ R there is a unique element

−x ∈ R such that

x + (−x) = 0.

Existence of Multiplicative Inverses. For every x ∈ R {0} there is a unique

element x −1 ∈ R such that

x · (x −1 ) = 1.

We note in passing that the word unique can be dropped from the statements

in Postulate 1 (see Appendix A).

We shall usually denote a + (−b) by a − b, a · b by ab, a −1 by a1 or 1/a, and

a · b−1 by ab or a/b. Notice that by the existence of additive and multiplicative

inverses, the equation x + a = 0 can be solved for each a ∈ R, and the equation

ax = 1 can be solved for each a ∈ R provided that a = 0.

From these few properties (i.e., from Postulate 1), we can derive all the usual

algebraic laws of real numbers, including the following:

(−1)2 = 1,

0 · a = 0, −a = (−1) · a, −(−a) = a,

−(a − b) = b − a,

a, b ∈ R,

a ∈ R,

(1)

(2)

(3)

or b = 0.

(4)

and

a, b ∈ R

and ab = 0 imply a = 0

We want to keep our attention sharply focused on analysis. Since the proofs

of algebraic laws like these lie more in algebra than analysis (see Appendix A),

we will not present them here. In fact, with the exception of the absolute value

and the Binomial Formula, we will assume all material usually presented in a

high school algebra course (including the quadratic formula and graphs of the

conic sections).

Postulate 1 is sufﬁcient to derive all algebraic laws of R, but it does not completely describe the real number system. The set of real numbers also has an

order relation (i.e., a concept of “less than”).

Postulate 2. [ORDER AXIOMS]. There is a relation < on R × R that has the
following properties:
Trichotomy Property. Given a, b ∈ R, one and only one of the following statements holds:
a < b,
b < a,
or a = b.
Transitive Property. For a, b, c ∈ R,
a 0.
Postulate 2 has a slightly simpler formulation using the set of positive elements
as a primitive concept (see Exercise 1.2.11). We have introduced Postulate 2 as
above because these are the properties we use most often.
The real number system R contains certain special subsets: the set of natural
numbers
N := {1, 2, . . . },
obtained by beginning with 1 and successively adding 1s to form 2 := 1 + 1, 3 :=
2 + 1, and so on; the set of integers
Z := {. . . , −2, −1, 0, 1, 2, . . . }
(Zahl is German for number); the set of rationals (or fractions or quotients)
Q :=
7m
n
8
: m, n ∈ Z and n = 0 ;
and the set of irrationals
Qc = R Q.
Equality in Q is deﬁned by
m
p
=
n
q
if and only if
mq = np.
8 Chapter 1
The Real Number System
Recall that each of the sets N, Z, Q, and R is a proper subset of the next; that is,
N ⊂ Z ⊂ Q ⊂ R.
For example, every rational √
is a real number (because m/n := mn −1 is a real
number by Postulate 1), but 2 is an irrational.
Since we did not really deﬁne N and Z, we must make certain assumptions
about them. If you are interested in the deﬁnitions and proofs, see Appendix A.
1.1 Remark. We will assume that the sets N and Z satisfy the following
properties.
i) If n, m ∈ Z, then n + m, n − m, and mn belong to Z.
ii) If n ∈ Z, then n ∈ N if and only if n ≥ 1.
iii) There is no n ∈ Z that satisﬁes 0 < n < 1.
Using these properties, we can prove that Q satisﬁes Postulate 1 (see Exercise 1.2.9).
We notice in passing that none of the other special subsets of R satisﬁes Postulate 1. N satisﬁes all but three of the properties in Postulate 1: N has no additive
identity (since 0 ∈
/ N), N has no additive inverses (e.g., −1 ∈
/ N), and only one
of the nonzero elements of N (namely, 1) has a multiplicative inverse. Z satisﬁes all but one of the properties in Postulate 1: Only two nonzero elements
of Z have multiplicative inverses (namely, 1 and −1). Qc satisﬁes all but four
of the properties in Postulate 1: Qc does not have an additive identity (since
0∈
/ R Q), does not have a multiplicative identity √
(since 1 ∈
/ R Q), and does
2
is
irrational,
the sum of
not satisfy either closure property.
Indeed,
since
√
√
irrationals may
√ be√rational ( 2 + (− 2) = 0) and the product of irrationals may
be rational ( 2 · 2 = 2).
Notice that any subset of R satisﬁes Postulate 2. Thus Q satisﬁes both Postulates 1 and 2. The remaining postulate, introduced in Section 1.3, identiﬁes a
property that Q does not possess. In particular, Postulates 1 through 3 distinguish R from each of its special subsets N, Z, Q, and Qc . These postulates actually characterize R; that is, R is the only set that satisﬁes Postulates 1 through 3.
(Such a set is called a complete Archimedean ordered ﬁeld. We may as well
admit a certain arbitrariness in choosing this approach. R has been developed
axiomatically in at least ﬁve other ways [e.g., as a one-dimensional continuum
or as a set of binary decimals with certain arithmetic operations]. The decision
to present R using Postulates 1 through 3 is based partly on economy and partly
on personal taste.)
Postulates 1 and 2 can be used to derive all identities and inequalities which
are true for real numbers [e.g., see implications (5) through (9) below]. Since
arguments based on inequalities are of fundamental importance to analysis, we
begin to supply details of proofs at this stage.
What is a proof? Every mathematical result (for us this includes examples,
remarks, lemmas, and theorems) has hypotheses and a conclusion. There are
three main methods of proof: mathematical induction, direct deduction, and
contradiction.
Section 1.2
Ordered Field Axioms
9
Mathematical induction, a special method for proving statements that depend
on positive integers, will be covered in Section 1.4.
To construct a deductive proof, we assume the hypotheses to be true and proceed step by step to the conclusion. Each step is justiﬁed by a hypothesis, a
deﬁnition, a postulate, or a mathematical result that has already been proved.
(Actually, this is usually the way we write a proof. When constructing your own
proofs, you may ﬁnd it helpful to work forward from the hypotheses as far as
you can and then work backward from the conclusion, trying to meet in the
middle.)
To construct a proof by contradiction, we assume the hypotheses to be true,
the conclusion to be false, and work step by step deductively until a contradiction occurs; that is, a statement that is obviously false or that is contrary to
the assumptions made. At this point the proof by contradiction is complete. The
phrase “suppose to the contrary” always indicates a proof by contradiction (e.g.,
see the proof of Theorem 1.9).
What about false statements? How do we “prove” that a statement is false?
We can show that a statement is false by producing a single, concrete example
(called a counterexample) that satisﬁes the hypotheses but not the conclusion
of that statement. For example, to show that the statement “x > 1 implies

x 2 − x − 2 = 0” is false, we need only observe that x = 2 is greater than 1 but

22 − 2 − 2 = 0.

Here are some examples of deductive proofs. (Note: The symbol indicates

that the proof or solution is complete.)

1.2 EXAMPLE.

If a ∈ R, prove that

a = 0

implies a 2 > 0.

(5)

In particular, −1 < 0 < 1.
Proof. Suppose that a = 0. By the Trichotomy Property, either a > 0 or

a < 0.
Case 1. a > 0. Multiply both sides of this inequality by a, using the First

Multiplicative Property. We obtain a 2 = a · a > 0 · a. Since (by (2)), 0 · a = 0

we conclude that a 2 > 0.

Case 2. a < 0. Multiply both sides of this inequality by a. Since a < 0, it
follows from the Second Multiplicative Property that a 2 = a · a > 0 · a = 0.

This proves that a 2 > 0 when a = 0.

Since 1 = 0, it follows that 1 = 12 > 0. Adding −1 to both sides of this

inequality, we conclude that 0 = 1 − 1 > 0 − 1 = −1.

1.3 EXAMPLE.

If a ∈ R, prove that

0 a.

(6)

10 Chapter 1

The Real Number System

Proof. Suppose that 0 < a < 1. Multiply both sides of this inequality by a
using the First Multiplicative Property. We obtain 0 = 0 · a < a 2 < 1 · a = a.
In particular, 0 < a 2 < a.
On the other hand, if a > 1, then a > 0 by Example 1.2 and the Transitive

Property. Multiplying a > 1 by a, we conclude that a 2 = a · a > 1 · a = a.

Similarly (see Exercise 1.2.2), we can prove that

0≤a 0 and b < 0, or, b > 0 and a < 0. By symmetry, we may
suppose that a > 0 and b < 0. (That is, if we can prove it for a > 0 and b < 0,
then by reversing the roles of a and b, we can prove it for a < 0 and b > 0.)

By the Second Multiplicative Property, ab < 0. Hence by Deﬁnition 1.4, (2),
associativity, and commutativity,
|ab| = −(ab) = (−1)(ab) = a((−1)b) = a(−b) = |a| |b|.
Section 1.2
Ordered Field Axioms
11
Case 4. a < 0 and b < 0. By the Second Multiplicative Property, ab > 0.

Hence by Deﬁnition 1.4,

|ab| = ab = (−1)2 (ab) = (−a)(−b) = |a| |b|.

We shall soon see that there are more efﬁcient ways to prove results about

absolute values than breaking the argument into cases.

The following result is useful when solving inequalities involving absolute

value signs.

1.6 Theorem. [FUNDAMENTAL THEOREM OF ABSOLUTE VALUES].

Let a ∈ R and M ≥ 0. Then |a| ≤ M if and only if −M ≤ a ≤ M.

Proof. Suppose ﬁrst that |a| ≤ M. Multiplying by –1, we also have −|a| ≥ −M.

Case 1. a ≥ 0. By Deﬁnition 1.4, |a| = a. Thus by hypothesis,

−M ≤ 0 ≤ a = |a| ≤ M.

Case 2. a < 0. By Deﬁnition 1.4, |a| = −a. Thus by hypothesis,
−M ≤ −|a| = a < 0 ≤ M.
This proves that −M ≤ a ≤ M in either case.
Conversely, if −M ≤ a ≤ M, then a ≤ M and −M ≤ a. Multiplying the
second inequality by −1, we have −a ≤ M. Consequently, |a| = a ≤ M if
a ≥ 0, and |a| = −a ≤ M if a < 0.
NOTE: In a similar way we can prove that |a| < M if and only if −M < a < M.
Here is another useful result about absolute values.
1.7 Theorem. The absolute value satisﬁes the following three properties.
i) [Positive Deﬁnite] For all a ∈ R, |a| ≥ 0 with |a| = 0 if and only if a = 0.
ii) [Symmetric] For all a, b ∈ R, |a − b| = |b − a|.
iii) [Triangle Inequalities] For all a, b ∈ R,
|a + b| ≤ |a| + |b|
and
|a| − |b| ≤ |a − b|.
Proof. i) If a ≥ 0, then |a| = a ≥ 0. If a < 0, then by Deﬁnition 1.4 and the
Second Multiplicative Property, |a| = −a = (−1)a > 0. Thus |a| ≥ 0 for all

a ∈ R.

If |a| = 0, then by deﬁnition a = |a| = 0 when a ≥ 0 and a = −|a| = 0

when a < 0. Thus |a| = 0 implies that a = 0. Conversely, |0| = 0 by deﬁnition.
ii) By Remark 1.5, |a − b| = | − 1| |b − a| = |b − a|.
12 Chapter 1
The Real Number System
iii) To prove the ﬁrst inequality, notice that |x| ≤ |x| holds for any x ∈ R.
Thus Theorem 1.6 implies that −|a| ≤ a ≤ |a| and −|b| ≤ b ≤ |b|. Adding
these inequalities (see Exercise 1.2.1), we obtain
−(|a| + |b|) ≤ a + b ≤ |a| + |b|.
Hence by Theorem 1.6 again, |a + b| ≤ |a| + |b|.
To prove the second inequality, apply the ﬁrst inequality to (a − b) + b. We
obtain
|a| − |b| = |a − b + b| − |b| ≤ |a − b| + |b| − |b| = |a − b|.
By reversing the roles of a and b and applying part ii), we also obtain
|b| − |a| ≤ |b − a| = |a − b|.
Multiplying this last inequality by −1 and combining it with the preceding one
veriﬁes
−|a − b| ≤ |a| − |b| ≤ |a − b|.
We conclude by Theorem 1.6 that |a| − |b| ≤ |a − b|.
Notice once and for all that this last inequality implies that |a| − |b| ≤ |a − b|
for all a, b ∈ R. We will use this inequality several times.
WARNING. Some students mistakenly mix absolute values and the Additive
Property to conclude that b < c implies |a + b| < |a + c|. It is important from the
beginning to recognize that this implication is false unless both a + b and a + c
are nonnegative. For example, if a = 1, b = −5, and c = −1, then b < c but
|a + b| = 4 is not less than |a + c| = 0.
A correct way to estimate using absolute value signs usually involves one of
the triangle inequalities.
1.8 EXAMPLE.
Prove that if −2 < x < 1, then |x 2 − x| < 6.
Proof. By hypothesis, |x| < 2.
Remark 1.5,
Hence by the triangle inequality and
|x 2 − x| ≤ |x|2 + |x| < 4 + 2 = 6.
The following result (which is equivalent to the Trichotomy Property) will be
used many times in this and subsequent chapters.
1.9 Theorem. Let x, y, a ∈ R.
i) x < y + ε for all ε > 0 if and only if x ≤ y.

ii) x > y − ε for all ε > 0 if and only if x ≥ y.

iii) |a| < ε for all ε > 0 if and only if a = 0.

Section 1.2

Ordered Field Axioms

13

Proof. i) Suppose to the contrary that x < y + ε for all ε > 0 but x > y.

Set ε0 = x − y > 0 and observe that y + ε0 = x. Hence by the Trichotomy

Property, y + ε0 cannot be greater than x. This contradicts the hypothesis for

ε = ε0 . Thus x ≤ y.

Conversely, suppose that x ≤ y and ε > 0 is given. Either x < y or x = y.
If x < y, then x + 0 < y + 0 < y + ε by the Additive and Transitive Properties.
If x = y, then x < y + ε by the Additive Property. Thus x < y + ε for all ε > 0

in either case. This completes the proof of part i).

ii) Suppose that x > y − ε for all ε > 0. By the Second Multiplicative

Property, this is equivalent to −x < −y + ε, hence by part i), equivalent to
−x ≤ −y. By the Second Multiplicative Property, this is equivalent to x ≥ y.
iii) Suppose that |a| < ε = 0 + ε for all ε > 0. By part i), this is equivalent to

|a| ≤ 0. Since it is always the case that |a| ≥ 0, we conclude by the Trichotomy

Property that |a| = 0. Therefore, a = 0 by Theorem 1.7i.

Let a and b be real numbers. A closed interval is a set of the form

[a, b] := {x ∈ R : a ≤ x ≤ b},

[a, ∞) := {x ∈ R : a ≤ x},

(−∞, b] := {x ∈ R : x ≤ b}, or (−∞, ∞) := R,

and an open interval is a set of the form

(a, b) := {x ∈ R : a < x < b}, (a, ∞) := {x ∈ R : a < x},
(−∞, b) := {x ∈ R : x < b}, or (−∞, ∞) := R.
By an interval we mean a closed interval, an open interval, or a set of the form
[a, b) := {x ∈ R : a ≤ x < b}
or
(a, b] := {x ∈ R : a < x ≤ b}.
Notice, then, that when a < b, the intervals [a, b], [a, b), (a, b], and (a, b) correspond to line segments on the real line, but when b < a, these “intervals” are
all the empty set.
An interval I is said to be bounded if and only if it has the form [a, b], (a, b),
[a, b), or (a, b] for some −∞ < a ≤ b < ∞, in which case the numbers a, b
will be called the endpoints of I . All other intervals will be called unbounded.
An interval with endpoints a, b is called degenerate if a = b and nondegenerate
if a < b. Thus a degenerate open interval is the empty set, and a degenerate
closed interval is a point.
Analysis has a strong geometric ﬂavor. Geometry enters the picture because
the real number system can be identiﬁed with the real line in such a way that
a < b if and only if a lies to the left of b (see Figures 1.2, 2.1, and 2.2). This
gives us a way of translating analytic results on R into geometric results on the
number line, and vice versa. We close with several examples.
The absolute value is closely linked to the idea of length. The length of a
bounded interval I with endpoints a, b is deﬁned to be |I | := |b − a|, and the
distance between any two points a, b ∈ R is deﬁned by |a − b|.
14 Chapter 1
The Real Number System
Inequalities can be interpreted as statements about intervals. By Theorem 1.6,
|a| ≤ M if and only if a belongs to the closed interval [−M, M]; and by Theorem 1.9, a belongs to the open interval (−ε, ε) for all ε > 0 if and only if a = 0.

We will use this point of view in Chapters 2 through 5 to give geometric interpretations to the calculus of functions deﬁned on R, and in Chapters 11 through 13 to extend this calculus to functions deﬁned on the Euclidean

spaces Rn .

EXERCISES

In each of the following exercises, verify the given statement carefully, proceeding

step by step. Validate each step that involves an inequality by using some statement

found in this section.

1.2.0 Let a, b, c, d ∈ R and consider each of the following statements. Decide

which are true and which are false. Prove the true ones and give counterexamples to the false ones.

a)

b)

c)

d)

If a

If a

If a

If a

< b and c < d < 0, then ac > bd.

≤ b and c > 1, then |a + c| ≤ |b + c|.

≤ b and b ≤ a + c, then |a − b| ≤ c.

< b − ε for all ε > 0, then a < 0.
1.2.1. Suppose that a, b, c ∈ R and a ≤ b.
a) Prove that a + c ≤ b + c.
b) If c ≥ 0, prove that a · c ≤ b · c.
1.2.2. Prove (7), (8), and (9). Show that each of these statements is false if the
hypothesis a ≥ 0 or a > 0 is removed.

1.2.3. This exercise is used in Section 6.3. The positive part of an a ∈ R is

deﬁned by

a + :=

|a| + a

2

a − :=

|a| − a

.

2

and the negative part by

a) Prove that a = a + − a − and |a| = a + + a − .

b) Prove that

a

a+ =

0

a≥0

a≤0

and a − =

0

−a

1.2.4. Solve each of the following inequalities for x ∈ R.

a) |2x + 1| < 7
b) |2 − x| < 2
a≥0
a ≤ 0.
Section 1.2
Ordered Field Axioms
15
c) |x 3 − 3x + 1| < x 3
x
2 and b = 1 + a −
√1, then 2 < b < a.
Prove that if 2 < a < 3 and b = 2 + √a − 2, then 0 < a < b.
Prove that if 0 < a < 1 and b = 1 − √1 − a, then 0 < b < a.
Prove that if 3 < a < 5 and b = 2 + a − 2, then 3 < b < a.
1.2.6. The arithmetic mean of a, b ∈ R is A(a,√b) = (a +b)/2, and the geometric
mean of a, b ∈ [0, ∞) is G(a, b) = ab. If 0 ≤ a ≤ b, prove that
a ≤ G(a, b) ≤ A(a, b) ≤ b. Prove that G(a, b) = A(a, b) if and only if
a = b.
1.2.7. Let x ∈ R.
a)
b)
c)
d)
Prove that |x| ≤ 2 implies |x 2 − 4| ≤ 4|x − 2|.
Prove that |x| ≤ 1 implies |x 2 + 2x − 3| ≤ 4|x − 1|.
Prove that −3 ≤ x ≤ 2 implies |x 2 + x − 6| ≤ 6|x − 2|.
Prove that −1 < x < 0 implies |x 3 − 2x + 1| < 1.25|x − 1|.
1.2.8. For each of the following, ﬁnd all values of n ∈ N that satisfy the given
inequality.
1−n
< 0.01
a)
1 − n2
n 2 + 2n + 3
< 0.025
b)
2n 3 + 5n 2 + 8n + 3
n−1
< 0.002
c)
3
n − n2 + n − 1
1.2.9. a) Interpreting a rational m/n as m · n −1 ∈ R, use Postulate 1 to
prove that
m
p
mq + np
+ =
,
n
q
nq
m p
mp
· =
,
n q
nq
m
−m
− =
, and
n
n
−1
n
=
n
for m, n, p, q, ∈ Z and n, q, = 0.
b) Using Remark 1.1, Prove that Postulate 1 holds with Q in place of R.
c) Prove that the sum of a rational and an irrational is always irrational.
What can you say about the product of a rational and an irrational?
d) Let m/n, p/q ∈ R with n, q > 0. Prove that

p

m

<
n
q
if and only if mq < np.
(Restricting this observation to Q gives a deﬁnition of “ 0 is any positive number, then there is a
point a ∈ E such that
sup E − ε < a ≤ sup E.
Proof. Suppose that the theorem is false. Then there is an ε0 > 0 such that no

element of E lies between s0 := sup E − ε0 and sup E. Since sup E is an upper

bound for E, it follows that a ≤ s0 for all a ∈ E; that is, s0 is an upper bound

of E. Thus, by Deﬁnition 1.10ii, sup E ≤ s0 = sup E − ε0 . Adding ε0 − sup E

to both sides of this inequality, we conclude that ε0 ≤ 0, a contradiction.

The Approximation Property can be used to show that the supremum of any

subset of integers is itself an integer.

18 Chapter 1

The Real Number System

1.15 Theorem. If E ⊂ Z has a supremum, then sup E ∈ E. In particular, if the

supremum of a set, which contains only integers, exists, that supremum must be

an integer.

Proof. Suppose that s := sup E and apply the Approximation Property to

choose an x0 ∈ E such that s − 1 < x0 ≤ s. If s = x0 , then s ∈ E, as promised.
Otherwise, s − 1 < x0 < s and we can apply the Approximation Property
again to choose x1 ∈ E such that x0 < x1 < s.
Subtract x0 from this last inequality to obtain 0 < x1 − x0 < s − x0 . Since
−x0 < 1−s, it follows that 0 < x1 −x0 < s+(1−s) = 1. Thus x1 −x0 ∈ Z∩(0, 1),
a contradiction by Remark 1.1iii. We conclude that s ∈ E.
The existence of suprema is the last assumption about R we make.
Postulate 3. [COMPLETENESS AXIOM]. If E is a nonempty subset of R that
is bounded above, then E has a ﬁnite supremum.
We shall use Completeness Axiom many times. Our ﬁrst two applications deal
with the distribution of integers (Theorem 1.16) and rationals (Theorem 1.18)
among real numbers.
1.16 Theorem. [ARCHIMEDEAN PRINCIPLE].
Given real numbers a and b, with a > 0, there is an integer n ∈ N such that

b < na.
Strategy: The idea behind the proof is simple. By the Completeness Axiom
and Theorem 1.15, any nonempty subset of integers that is bounded above has
a “largest” integer. If k0 is the largest integer that satisﬁes k0 a ≤ b, then n =
(k0 + 1) (which is larger than k0 ) must satisfy na > b. In order to justify this

application of the Completeness Axiom, we have two details to attend to: (1) Is

the set E := {k ∈ N : ka ≤ b} bounded above? (2) Is E nonempty? The

answer to the second question depends on whether b < a or not. Here are the
details.
Proof. If b < a, set n = 1. If a ≤ b, consider the set E = {k ∈ N : ka ≤ b}. E is
nonempty since 1 ∈ E. Let k ∈ E (i.e., ka ≤ b). Since a > 0, it follows from

the First Multiplicative Property that k ≤ b/a. This proves that E is bounded

above by b/a. Thus, by the Completeness Axiom and Theorem 1.15, E has a

ﬁnite supremum s that belongs to E, in particular, s ∈ N.

Set n = s + 1. Then n ∈ N and (since n is larger than s), n cannot belong to

E. Thus na > b.

Notice in Example 1.11 and Theorem 1.15 that the supremum of E belonged

to E. The following result shows that this is not always the case.

1.17 EXAMPLE.

Let A = {1, 12 , 14 , 18 , . . .} and B = { 12 , 23 , 34 , . . .}. Prove that sup A = sup B = 1.

Section 1.3

Completeness Axiom 19

Proof. It is clear that 1 is an upper bound of both sets. It remains to see that

1 is the smallest upper bound of both sets. For A, this is trivial. Indeed, if

M is any upper bound of A, then M ≥ 1 (since 1 ∈ A). On the other hand,

if M is an upper bound for B, but M < 1, then 1 − M > 0. In particular,

1/(1 − M) ∈ R.

Choose, by the Archimedean Principle, an n ∈ N such that n > 1/(1− M). It

follows (do the algebra) that x0 := 1−1/n > M. Since x0 ∈ B, this contradicts

the assumption that M is an upper bound of B (see Figure 1.3).

The next proof shows how the Archimedean Principle is used to establish

scale.

1.18 Theorem. [DENSITY OF RATIONALS].

If a, b ∈ R satisfy a < b, then there is a q ∈ Q such that a < q < b.
Strategy: To ﬁnd a fraction q = m/n such that a < q < b, we must specify
both numerator m and denominator n. Let’s suppose ﬁrst that a > 0 and that

the set E := {k ∈ N : k/n ≤ a} has a supremum, k0 . Then m := k0 + 1, being

greater than the supremum of E, cannot belong to E. Thus m/n > a. Is this the

fraction we look for? Is m/n < b? Not unless n is large enough. To see this, look
at a concrete example: a = 2/3 and b = 1. If n = 1, then E has no supremum,
When n = 2, k0 = 1 and when n = 3, k0 = 2. In both cases (k0 + 1)/n = 1 is
too big. However, when n = 4, k0 = 2 so (k0 + 1)/4 = 3/4 is smaller than b, as
required.
How can we prove that for each ﬁxed a < b there always is an n large enough
so that if k0 is chosen as above, then (k0 + 1)/n < b? By the choice of k0 , k0 /n ≤
a. Let’s look at the worst case scenario: a = k0 /n. Then b > (k0 + 1)/n means

b>

k0 + 1

k0

1

1

=

+ =a+

n

n

n

n

(i.e., b − a > 1/n). Such an n can always be chosen by the Archimedean Principle.

What about the assumption that sup E exists? This requires that E be

nonempty and bounded above. Once n is ﬁxed, E will be bounded above by

na. But the only way that E is nonempty is that at the very least, 1 ∈ E (i.e., that

1/n ≤ a). This requires a second restriction on n. We begin our formal proof at

this point.

Proof. Suppose ﬁrst that a > 0. Since b − a > 0, use the Archimedean

Principle to choose an n ∈ N that satisﬁes

1

1

,

,

n > max

a b−a

and observe that both 1/n < a and 1/n < b − a.
Consider the set E = {k ∈ N : k/n ≤ a}. Since 1 ∈ E, E is nonempty. Since
n > 0, E is bounded above by na. Hence, by Theorem 1.15, k0 := sup E exists

20 Chapter 1

The Real Number System

and belongs to E, in particular, to N. Set m = k0 + 1 and q = m/n. Since k0 is

the supremum of E, m ∈

/ E. Thus q > a. On the other hand, since k0 ∈ E, it

follows from the choice of n that

b = a + (b − a) ≥

k0

1

m

k0

+ (b − a) >

+ =

= q.

n

n

n

n

Now suppose that a ≤ 0. Choose, by the Archimedean Principle, an integer

k ∈ N such that k > −a. Then 0 < k + a < k + b, and by the case already
proved, there is an r ∈ Q such that k + a < r < k + b. Therefore, q := r − k
belongs to Q and satisﬁes the inequality a < q < b.
For some applications, we also need the following concepts.
1.19 Deﬁnition.
Let E ⊂ R be nonempty.
i) The set E is said to be bounded below if and only if there is an m ∈ R such
that a ≥ m for all a ∈ E, in which case m is called a lower bound of the
set E.
ii) A number t is called an inﬁmum of the set E if and only if t is a lower
bound of E and t ≥ m for all lower bounds m of E. In this case we shall say
that E has an inﬁmum t and write t = inf E.
iii) E is said to be bounded if and only if it is bounded both above and below.
When a set E contains its supremum (respectively, its inﬁmum) we shall frequently write max E for sup E (respectively, min E for inf E).
(Some authors call the supremum the least upper bound and the inﬁmum the
greatest lower bound. We will not use this terminology because it is somewhat
old fashioned and because it confuses some students, since the least upper bound
of a given set is always greater than or equal to the greatest lower bound.)
To relate suprema to inﬁma, we deﬁne the reﬂection of a set E ⊆ R by
−E := {x : x = −a for some a ∈ E }.
For example, −(1, 2] = [−2, −1).
The following result shows that the supremum of a set is the same as the
negative of its reﬂection’s inﬁmum. This can be used to prove an Approximation
Property and a Completeness Property for Inﬁma (see Exercise 1.3.6).
1.20 Theorem. [REFLECTION PRINCIPLE].
Let E ⊆ R be nonempty.
i) E has a supremum if and only if −E has an inﬁmum, in which case
inf(−E) = − sup E.
Section 1.3
Completeness Axiom 21
ii) E has an inﬁmum if and only if −E has a supremum, in which case
sup(−E) = − inf E.
Proof. The proofs of these statements are similar. We prove only the ﬁrst
statement.
Suppose that E has a supremum s and set t = −s. Since s is an upper bound
for E, s ≥ a for all a ∈ E, so −s ≤ −a for all a ∈ E. Therefore, t is a lower
bound of −E. Suppose that m is any lower bound of −E. Then m ≤ −a for
all a ∈ E, so −m is an upper bound of E. Since s is the supremum of E, it
follows that s ≤ −m (i.e., t = −s ≥ m). Thus t is the inﬁmum of −E and
sup E = s = −t = − inf(−E).
Conversely, suppose that −E has an inﬁmum t. By deﬁnition, t ≤ −a for
all a ∈ E. Thus −t is an upper bound for E. Since E is nonempty, E has a
supremum by the Completeness Axiom.
Theorem 1.20 allows us to obtain information about inﬁma from results about
suprema, and vice versa (see the proof of the next theorem).
We shall use the following result many times.
1.21 Theorem. [MONOTONE PROPERTY].
Suppose that A ⊆ B are nonempty subsets of R.
i) If B has a supremum, then sup A ≤ sup B.
ii) If B has an inﬁmum, then inf A ≥ inf B.
Proof. i) Since A ⊆ B, any upper bound of B is an upper bound of A. Therefore, sup B is an upper bound of A. It follows from the Completeness Axiom
that sup A exists, and from Deﬁnition 1.10ii that sup A ≤ sup B.
ii) Clearly, −A ⊆ −B. Thus by part i), Theorem 1.20, and the Second
Multiplicative Property,
inf A = − sup(−A) ≥ − sup(−B) = inf B.
It is convenient to extend the deﬁnition of suprema and inﬁma to all subsets
of R. To do this we expand the deﬁnition
of R as follows. The set of extended real
#
numbers is deﬁned to be R := R {±∞}. Thus x is an extended real number if
and only if either x ∈ R, x = +∞, or x = −∞.
Let E ⊆ R be nonempty. We shall deﬁne sup E = +∞ if E is unbounded
above and inf E = −∞ if E is unbounded below. Finally, we deﬁne sup ∅ = −∞
and inf ∅ = +∞. Notice, then, that the supremum of a subset E of R (respectively, the inﬁmum of E) is ﬁnite if and only if E is nonempty and bounded
above (respectively, nonempty and bounded below). Moreover, under the convention −∞ < a and a < ∞ for all a ∈ R, the Monotone Property still holds
for this extended deﬁnition; that is, if A and B are subsets of R and A ⊆ B, then
sup A ≤ sup B and inf A ≥ inf B, provided we use the convention that −∞ < ∞.
22 Chapter 1
The Real Number System
EXERCISES
1.3.0. Decide which of the following statements are true and which are false.
Prove the true ones and give counterexamples to the false ones.
a) If A and B are nonempty, bounded subsets of R, then sup(A ∩ B) ≤
sup A.
b) Let ε be a positive real number. If A is a nonempty, bounded subset
of R and B = {εx : x ∈ A}, then sup(B) = ε sup(A).
c) If A + B := {a + b : a ∈ A and b ∈ B}, where A and B are nonempty,
bounded subsets of R, then sup(A + B) = sup(A) + sup(B).
d) If A − B := {a − b : a ∈ A and b ∈ B}, where A and B are nonempty,
bounded subsets of R, then sup(A − B) = sup(A) − sup(B)
1.3.1. Find the inﬁmum and supremum of each of the following sets.
a)
b)
c)
d)
e)
f)
E
E
E
E
E
E
= {x ∈ R : x 2 + 2x = 3}
= {x ∈ R : x 2 − 2x + 3 > x 2 and x > 0}

= { p/q ∈ Q : p2 < 5q 2 and p, q > 0}

= {x ∈ R : x = 1 + (−1)n /n for n ∈ N}

= {x ∈ R : x = 1/n + (−1)n for n ∈ N}

= {2 − (−1)n /n 2 : n ∈ N}

1.3.2. Prove that for each a ∈ R and each n ∈ N there exists a rational rn such

that |a − rn | < 1/n.
1.3.3 . [Density of Irrationals] This exercise is used in Section 3.3. Prove
that if a < b are real numbers, then there is an irrational ξ ∈ R such that
a < ξ < b.
1.3.4. Prove that a lower bound of a set need not be unique but the inﬁmum
of a given set E is unique.
1.3.5. Show that if E is a nonempty bounded subset of Z, then inf E exists and
belongs to E.
1.3.6 . This exercise is used in many sections, including 2.2 and 5.1. Use the
Reﬂection Principle and analogous results about suprema to prove the
following results.
a) [Approximation Property for Inﬁma] Prove that if a set E ⊂ R has
a ﬁnite inﬁmum and ε > 0 is any positive number, then there is a

point a ∈ E such that inf E + ε > a ≥ inf E.

b) [Completeness Property for Inﬁma] If E ⊆ R is nonempty and

bounded below, then E has a (ﬁnite) inﬁmum.

1.3.7. a) Prove that if x is an upper bound of a set E ⊆ R and x ∈ E, then x is

the supremum of E.

b) Make and prove an analogous statement for the inﬁmum of E.

c) Show by example that the converse of each of these statements is

false.

1.3.8. Suppose that E, A, B ⊂ R and E = A ∪ B. Prove that if E has a supremum and both A and B are nonempty, then sup A and sup B both exist,

and sup E is one of the numbers sup A or sup B.

Section 1.4

Mathematical Induction 23

1.3.9. A dyadic rational is a number of the form k/2n for some k, n ∈ Z. Prove

that if a and b are real numbers and a < b, then there exists a dyadic
rational q such that a < q < b.
1.3.10. Let xn ∈ R and suppose that there is an M ∈ R such that |xn | ≤ M
for n ∈ N. Prove that sn = sup{xn , xn+1 , . . .} deﬁnes a real number for
each n ∈ N and that s1 ≥ s2 ≥ · · · . Prove an analogous result about
tn = inf{xn , xn+1 , . . .}.
1.3.11. If a, b ∈ R and b − a > 1, then there is at least one k ∈ Z such that

a < k < b.
1.4
MATHEMATICAL INDUCTION
In this section we introduce the method of Mathematical Induction and use it
to prove the Binomial Formula, a result that shows how to expand powers of a
binomial expression (i.e., an expression of the form a + b).
We begin by obtaining another consequence of the Completeness Axiom,
the Well-Ordering Principle, which is a statement about the existence of least
elements of subsets of N.
1.22 Theorem. [WELL-ORDERING PRINCIPLE].
If E is a nonempty subset of N, then E has a least element (i.e., E has a ﬁnite
inﬁmum and inf E ∈ E).
Proof. Suppose that E ⊆ N is nonempty. Then −E is bounded above, by
−1, so by the Completeness Axiom sup(−E) exists, and by Theorem 1.15,
sup(−E) ∈ −E. Hence by Theorem 1.20, inf E = − sup(−E) exists, and
inf E ∈ −(−E) = E.
Our ﬁrst application of the Well-Ordering Principle is called the Principle of
Mathematical Induction or the Axiom of Induction (which, under mild assumptions, is equivalent to the Well-Ordering Principle—see Appendix A).
1.23 Theorem. Suppose for each n ∈ N that A(n) is a proposition (i.e., a verbal
statement or formula) which satisﬁes the following two properties:
i) A(1) is true.
ii) For every n ∈ N for which A(n) is true, A(n + 1) is also true.
Then A(n) is true for all n ∈ N.
Proof. Suppose that the theorem is false. Then the set E = {n ∈ N : A(n)
is false} is nonempty. Hence by the Well-Ordering Principle, E has a least
element, say x.
Since x ∈ E ⊆ N ⊂ Z, we have by Remark 1.1ii that x ≥ 1. Since x ∈ E,
we have by hypothesis i) that x = 1. In particular, x − 1 > 0. Hence, by

Remark 1.1i and iii, x − 1 ≥ 1 and x − 1 ∈ N.

Since x − 1 < x and x is a least element of E, the statement A(x − 1) must
be true. Applying hypothesis ii) to n = x − 1, we see that A(x) = A(n + 1)
must also be true; that is, x ∈
/ E, a contradiction.
24 Chapter 1
The Real Number System
Recall that if x0 , x1 , . . . , xn are real numbers and 0 ≤ j ≤ n, then
n
xk := x j + x j+1 + · · · + xn
k= j
denotes the sum of the xk ’s as k ranges from j to n. The following examples
illustrate the fact that the Principle of Mathematical Induction can be used to
prove a variety of statements involving integers.
1.24 EXAMPLE.
Prove that
n
(3k − 1)(3k + 2) = 3n 3 + 6n 2 + n
k=1
for n ∈ N.
Proof. Let A(n) represent the statement
n
(3k − 1)(3k + 2) = 3n 3 + 6n 2 + n.
k=1
For n = 1 the left side of this equation is 2 · 5 and the right side is 3 + 6 + 1.
Therefore, A(1) is true. Suppose that A(n) is true for some n ≥ 1. Then
n+1
(3k − 1)(3k + 2) = (3n + 2)(3n + 5) +
k=1
n
(3k − 1)(3k + 2)
k=1
3
= (3n + 2)(3n + 5) + 3n + 6n 2 + n
= 3n 3 + 15n 2 + 22n +10.
On the other hand, a direct calculation reveals that
3(n + 1)3 + 6(n + 1)2 + (n + 1) = 3n 3 + 15n 2 + 22n + 10.
Therefore, A(n + 1) is true when A(n) is. We conclude by induction that A(n)
holds for all n ∈ N.
Two formulas encountered early in an algebra course are the perfect square
and cube formulas:
(a + b)2 = a 2 + 2ab + b2
and
(a + b)3 = a 3 + 3a 2 b + 3ab2 + b3 .
Our next application of the Principle of Mathematical Induction generalizes
these formulas from n = 2 and 3 to arbitrary n ∈ N.
Section 1.4
Mathematical Induction 25
Recall that Pascal’s triangle is the triangular array of integers whose rows
begin and end with 1s with the property that an interior entry on any row is
obtained by adding the two numbers in the preceding row immediately above
that entry. Thus the ﬁrst few rows of Pascal’s triangle are as below.
1
1 1
2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1
Notice that the third and fourth rows are precisely the coefﬁcients that appeared
in the perfect square and cube formulas above.
We can write down a formula for each entry in each row of the Pascal triangle.
The ﬁrst (and only) entry in the ﬁrst row is
0
:= 1.
0
Using the notation 0! := 1 and n! := 1 · 2 · · · (n − 1) · n for n ∈ N, deﬁne the
binomial coefﬁcient n choose k by
n
n!
:=
(n − k)!k!
k
for 0 ≤ k≤ n andn =
0, 1, . . . .
n
n
Since
=
= 1 for all n ∈ N, the following result shows that the
0
n
binomial coefﬁcient n over k does produce the (k + 1)st entry in the (n + 1)st
row of Pascal’s triangle.
1.25 Lemma.
If n, k ∈ N and 1 ≤ k ≤ n, then
n+1
n
n
=
+
.
k
k−1
k
Proof. By deﬁnition,
n
n!(n − k + 1)
n
n! k
+
+
=
k−1
(n − k + 1)!k! (n − k + 1)!k!
k
n!(n + 1)
n+1
=
=
.
(n − k + 1)!k!
k
26 Chapter 1
The Real Number System
Binomial coefﬁcients can be used to expand the nth power of a sum of
two terms.
1.26 Theorem. [BINOMIAL FORMULA].
If a, b ∈ R, n ∈ N, and 00 is interpreted to be 1, then
n
n n−k k
(a + b) =
a b .
k
n
k=0
Proof. The proof is by induction on n. The formula is obvious for n = 1.
Suppose that the formula is true for some n ∈ N. Then by the inductive
hypothesis and Postulate 1,
(a + b)n+1 = (a + b)(a + b)n
n
n
= (a + b)
a n−k bk
k
k=0
n
n
n
n
n−k+1 k
n−k k+1
b +
a
a b
=
k
k
k=0
k=0
n
n−1
n n−k+1 k
n n−k k+1
n+1
n+1
= a
+
b + b
+
a
a b
k
k
k=1
k=0
n
n
n
+
a n−k+1 bk + bn+1 .
= a n+1 +
k
k−1
k=1
Hence it follows from Lemma 1.25 that
(a + b)
n+1
=a
n+1
n
n+1
n + 1 n+1−k k
n + 1 n+1−k k
n+1
a
a
+
b +b
=
b ;
k
k
k=1
k=0
that is, the formula is true for n+1. We conclude by induction that the formula
holds for all n ∈ N.
We close this section with two optional, well-known results that further
demonstrate the power of the Completeness Axiom and its consequences.
∗ 1.27
n + 1.
Remark. If x > 1 and x ∈

/ N, then there is an n ∈ N such that n < x <
Proof. By the Archimedean Principle, the set E = {m ∈ N : x < m} is
nonempty. Hence by the Well-Ordering Principle, E has a least element,
say m 0 .
Set n = m 0 − 1. Since m 0 ∈ E, n + 1 = m 0 > x. Since m 0 is least,

/ N, we also have n = x. Therefore, n < x < n + 1.
n = m 0 − 1 ≤ x. Since x ∈
Section 1.4
Mathematical Induction 27
Using this last result, we can prove that the set of irrationals is nonempty.
∗ 1.28
Remark. If √
n ∈ N is not a perfect square (i.e., if there is no m ∈ N such
that n = m 2 ), then n is irrational.
√
Proof. Suppose
to the contrary that n ∈ N is not a perfect square but n ∈ Q;
√
that is, n = p/q for some p, q ∈ N. Choose by Remark 1.27 an integer
m 0 ∈ N such that
√
(10)
m 0 < n < m 0 + 1.
√
√
Consider the set E := {k ∈ N : k n ∈ Z}. Since q n = p, we know that E
is nonempty. Thus by the Well-Ordering Principle, E has a least element, say
n0.
√
√
Set x = n 0 ( n − m 0 ). By (10), 0 < n − m 0 < 1. Multiplying this inequality
by n 0 , we ﬁnd that
0 < x < n0.
(11)
Since n 0 is a least element of E, it follows from (11) that x ∈
/ E. On the
other hand,
√
√
√
√
x n = n0( n − m 0) n = n0n − m 0n0 n ∈ Z
√
since n 0 ∈ E. Moreover, since x > 0 and x = n 0 n − n 0 m 0 is the difference

of two integers, x ∈ N. Thus x ∈ E, a contradiction.

EXERCISES

1.4.0. Decide which of the following statements are true and which are false.

Prove the true ones and give counterexamples to the false ones.

a) If a ≥ 0 and b = 0, then (a + b)n ≥ bn for all n ∈ N.

b) If a < 0 < b, then (a + b)n ≤ bn for all n ∈ N.
c) If n ∈ N is even and both a and b are negative, then (a + b)n >

a n + na n−1 b.

d) If a = 0, then

n

n (a − 2)n−k

1

=

2n

a n 2n−k

k

k=0

for all n ∈ N.

√

1.4.1. a) Prove that if x1 > 2 and xn+1 = 1 + xn − 1 for n ∈ N, then 2 <
xn+1 < xn holds for all n ∈ N.
√
b) Prove that if 2 < x1 < 3 and xn+1 = 2 + xn − 2 for n ∈ N, then
0 < xn < xn+1 holds for all n ∈ N.
√
c) Prove that if 0 < x1 < 1 and xn+1 = 1 − 1 − xn for n ∈ N, then
0 < xn+1 < xn holds for all n ∈ N.
√
d) Prove that if 3 < x1 < 5 and xn+1 = 2 + xn − 2, then 3 < xn+1 < xn
holds for all n ∈ N.
28 Chapter 1
The Real Number System
1.4.2. Use the Binomial Formula or the Principle of Induction to prove each
of the following.
n
k n = 0 for all n ∈ N.
(−1)
a)
k=0
k
b) (a + b)n ≥ a n + bn for all n ∈ N and a, b ≥ 0.
n
c) (1 + 1/n)
≥ 2 for all n ∈ N.
n−1 k
n
n
d)
k=1 k =
k=0 2 for all n ∈ N.
1.4.3. Prove each of the following statements.
a)
b)
c)
d)
2n + 1 < 2n for n = 3, 4, . . . .
n < 2n for n = 1, 2, . . . .
n 2 ≤ 2n + 1 for n = 1, 2, . . . .
n 3 ≤ 3n for n = 1, 2, . . . .
1.4.4 . Parts a) and c) of this exercise are used in Sections 2.4 and 5.1.
Prove that the following formulas hold for all n ∈ N.
n
n(n + 1)
2
k=1
n
n(n
+ 1)(2n + 1)
k2 =
b)
6
k=1
n a−1
1
= 1 − n , a = 0
c)
k
a
k=1 a
2 − 1)
n
n(4n
d)
(2k − 1)2 =
3
k=1
a)
k=
1.4.5 . This exercise is used in Section 2.3. Prove that 0 ≤ a < b implies 0 ≤
√
√
a n < bn and 0 ≤ n a < n b for all n ∈ N.
1.4.6. Prove that 2n + 3n is a multiple of 5 for all odd n ∈ N.
1.4.7. Prove that 2n ≤ n! + 2 for n ∈ N.
1.4.8. Prove that
2n >

n(n − 1)(n − 2)

6

for n ∈ N.

1.4.9. a) Using Remark 1.28, prove that the square root of an integer m is

2

rational if and

√ only if m

√ = k for some k ∈ N.

b) Prove that n + 3 + n is rational for some n ∈ N if and only if

n = 1.

√

√

c) Find all n ∈ N such that n + 7 + n is rational.

1.4.10. Let a0 = 3, b0 = 4, and c0 = 5.

a) Let ak = ak−1 + 2, bk = 2ak−1 + bk−1 + 2, and ck = 2ak−1 + ck−1 + 2

for k ∈ N. Prove that ck − bk is constant for all k ∈ N.

Section 1.5

Inverse Functions and Images

29

b) Prove that the numbers deﬁned in part a) satisfy

ak2 + bk2 = ck2

for all k ∈ N.

1.5

INVERSE FUNCTIONS AND IMAGES

Let f : X → Y (i.e., suppose that f is a function from one set X to another

set Y ). In this section, we obtain simple conditions for when f has an inverse,

introduce images and inverse images induced by f , and explore how they interact with the algebra of sets.

First, recall from Section 1.1 that a function f : X → Y has an inverse function

if and only if Ran( f ) = Y and each y ∈ Y has a unique preimage x ∈ X , in

which case we deﬁne the inverse function f −1 by f −1 (y) := x. In particular, if

f : X → Y has an inverse function, then

f −1 ( f (x)) = x

and

f ( f −1 (y)) = y

(12)

for all x ∈ X and y ∈ Y .

We introduce the following concepts in order to answer the question, “Is there

an easy way to recognize when f has an inverse?”

1.29 Deﬁnition.

Let X and Y be sets and f : X → Y .

i) f is said to be 1–1 (one-to-one or an injection) if and only if

x1 , x2 ∈ X

and

f (x1 ) = f (x2 )

imply

x1 = x2 .

ii) f is said to be onto (or a surjection) if and only if for each y ∈ Y there is

an x ∈ X such that y = f (x).

iii) f is called a bijection if and only if it is both 1–1 and onto.

Sometimes, to emphasize the domain and range of f , we shall say that a

bijection f : X → Y is 1–1 from X onto Y .

For example, the function f (x) = x 2 is 1–1 from [0, ∞) onto [0, ∞) but not

1–1 on any open interval containing 0.

We shall now prove that bijections always have inverse functions and that (12)

characterizes those inverses.

1.30 Theorem. Let X and Y be sets and f : X → Y . Then the following three

statements are equivalent.

i) f has an inverse;

ii) f is 1–1 from X onto Y;

30 Chapter 1

The Real Number System

iii) There is a function g : Y → X such that

g( f (x)) = x

for all x ∈ X

(13)

f (g(y)) = y

for all y ∈ Y .

(14)

and

Moreover, for each f : X → Y , there is only one function g that satisﬁes (13) and

(14). It is the inverse function f −1 .

Proof. i) implies ii). By deﬁnition, if f has an inverse, then Ran( f ) = Y

(so f takes X onto Y ) and each y ∈ Y has a unique preimage in X [so, if

f (y1 ) = f (y2 ), then y1 = y2 , i.e., f is 1–1 on X ].

ii) implies iii). The proof that i) implies ii) also shows that if f : X → Y

is 1–1 and onto, then f has an inverse. In particular, g(y) := f −1 (y) satisﬁes

(13) and (14) by (12).

iii) implies i). Suppose that there is a function g : Y → X which satisﬁes

(13) and (14). If some y ∈ Y has two preimages, say x1 = x2 in X , then

f (x1 ) = y = f (x2 ). It follows from (13) that x1 = g( f (x1 )) = g( f (x2 )) = x2 ,

a contradiction. On the other hand, given y ∈ Y , set x = g(y). Then f (x) =

f (g(y)) = y by (14), so Ran( f ) = Y .

Finally, suppose that h is another function which satisﬁes (13) and (14), and

ﬁx y ∈ Y . By ii), there is an x ∈ X such that f (x) = y. Hence by (13),

h(y) = h( f (x)) = x = g( f (x)) = g(y);

that is, h = g on Y . It follows that the function g is unique.

There are two ways to show that a given function f is 1–1 on a set X . We can

suppose that f (x1 ) = f (x2 ) for some x1 , x2 ∈ X , and prove (using algebra, for

example) that x1 = x2 . If X is an interval in R and f is differentiable, there is an

easier way to prove that f is 1–1 on X .

1.31 Remark. Let I be an interval and let f : I → R. If the derivative of f is

either always positive on I, or always negative on I, then f is 1–1 on I.

Proof. By symmetry, we may suppose that the derivative f of f satisﬁes

f (x) > 0 for all x ∈ I . We will use a result that almost everyone who has

studied one variable calculus remembers (for a proof, see Theorem 4.17): If

f > 0 on an interval I , then f is strictly increasing on I ; that is, x1 , x2 ∈ I and

x1 < x2 imply that f (x1 ) < f (x2 ).
To see why this implies that f is 1–1, suppose that f (x1 ) = f (x2 ) for some
x1 , x2 in X . If x1 = x2 , then it follows from the trichotomy property that either
x1 < x2 or x2 < x1 . Since f is strictly increasing on I , either f (x1 ) < f (x2 )
or f (x2 ) < f (x1 ). Both of these conclusions contradict the assumption that
f (x1 ) = f (x2 ).
Section 1.5
Inverse Functions and Images
31
By Theorem 1.30, f : X → Y has an inverse function f −1 if and only if
= x for all x ∈ X and f ( f −1 (y)) = y for all y ∈ Y . This suggests that
we can ﬁnd a formula for f −1 if y = f (x) can be solved for x.
f −1 ( f (x))
∗ 1.32
EXAMPLE.
Prove that f (x) = e x − e−x is 1–1 on R and ﬁnd a formula for f −1 on Ran( f ).
Solution. Since f (x) = e x + e−x > 0 for all x ∈ R, f is 1–1 on R by

Remark 1.31.

Let y = e x − e−x . Multiplying this equation by e x and collecting all nonzero

terms on one side of the equation, we have

e2x − ye x − 1 = 0,

a quadratic in e x . By the quadratic formula,

y ± y2 + 4

x

e =

.

2

(15)

Since e x is always positive, the minus sign must

be discarded. Taking the logarithm of this last identity, we obtain x = log(y + y 2 + 4) − log 2. Therefore,

f −1 (x) = log(x + x 2 + 4) − log 2.

The following concepts greatly simplify the general theory of continuity (see

Theorem 9.26, for example).

1.33 Deﬁnition.

Let X and Y be sets and f : X → Y . The image of a set E ⊆ X under f is the

set

f (E) := {y ∈ Y : y = f (x) for some x ∈ E}.

The inverse image of a set E ⊆ Y under f is the set

f −1 (E) := {x ∈ X : f (x) = y for some y ∈ E}.

(16)

When E is an interval, we will sometimes drop the extra parentheses; for

example, write f (a, b] for f ((a, b]) and f −1 (a, b] for f −1 ((a, b]).

1.34 EXAMPLE.

Find the images and inverse images of the sets I = (−1, 0) and J = (0, 1] under

the function f (x) = x 2 + x.

Solution. Since “ﬁnd” doesn’t mean “prove,” we look at the graph y = x 2 + x.

By deﬁnition, f (I ) consists of the y-values of f (x) as x ranges over I = (−1, 0).

32 Chapter 1

The Real Number System

Since f has roots at x = 0, −1 and has a minimum of −0.25 at x = −0.5, it is

clear by looking at the graph that f (I ) = [−0.25, 0). Since f −1 (I ) consist of the

x-values whose images belong to I = (−1, 0), and the graph of f lies below the

x-axis only when −1 < x < 0, it is also clear that f −1 (I ) = (−1, 0). Similarly,
f (J ) = (0, 2] and
1
f
−1
(J ) =
−1 −
2
√
5
, −1
"
−1 +
0,
2
√ 4
5
.
(Be sure to look at the graph of y = x 2 + x and understand how these numbers
were obtained.)
WARNING. Unfortunately, there are now three meanings to f −1 : (1) f −1 (x) =
1/ f (x), the reciprocal of f which exists when f is real-valued and f (x) = 0;
(2) f −1 (x), the inverse function of f which exists when f is 1–1 and onto; (3)
f −1 (E), the inverse image of E under f , which always exists. Context will usually indicate which meaning we are using.
Notice that Deﬁnition 1.33 contains an asymmetry: y ∈ f (E) means that
y = f (x) for some x ∈ E, but x ∈ f −1 (E) does NOT mean that x = f −1 (y) for
some y ∈ E. For example, let f (x) = sin x. Since sin(kπ) = 0 for all k ∈ Z, the
inverse image of {0} under f is f −1 ({0}) = {kπ : k ∈ Z}, but since the range of
arcsin x is [−π/2, π/2], the image of {0} under f −1 is arcsin{0} = {0}.
Before we give an account of how images and inverse images interact with set
algebra (speciﬁcally, what the image and inverse image of a union, an intersection, and a complement of sets are), we need to expand the algebra of sets to
include unions and intersections of inﬁnitely many sets. We need these concepts
for some of the deeper results in the second half of this book because many of
the proofs involve associating a set E α with each α in a set A. With this end in
mind, we introduce the following terminology.
A collection of sets E is said to be indexed by a set A if and only if there is a
function F from A onto E (i.e., each α ∈ A is associated with one and only one
set in E ). In this case we shall call A the index set of E , say that E is indexed by A,
and represent F(α) by E α . In particular, E is indexed by A means E = {E α }α∈A .
1.35 Deﬁnition.
Let E = {E α }α∈A be a collection of sets.
i) The union of the collection E is the set
"
α∈A
E α := {x : x ∈ E α
for some α ∈ A}.
Section 1.5
Inverse Functions and Images
33
ii) The intersection of the collection E is the set
/
E α := {x : x ∈ E α
for all α ∈ A}.
α∈A
For example,
"
[0, x) = [0, 1)
/
and
x∈(0,1]
[0, x) = {0}.
x∈(0,1]
The following important, often used result shows that there is an easy way to
get from unions to intersections, and vice versa.
1.36 Theorem. [DEMORGAN’S LAWS].
Let X be a set and {E α }α∈A be a collection of subsets of X. If for each E ⊆ X
the symbol E c represents the set X E, then
c
"
/
=
Eα
α∈A
α∈A
E αc
(17)
E αc .
(18)
and
/
c
Eα
α∈A
"
=
α∈A
Proof.
# Suppose that x belongs to the left side of (17); that is, x ∈ X andc
/ E α for all α ∈ A. Hence, x ∈ E α
x ∈
/ α∈A E α . By deﬁnition, x ∈ X and x ∈
for all α ∈ A; that is, x belongs to the right side of (17). These steps are
reversible. This veriﬁes (17). A similar argument veriﬁes (18).
The following result, which plays a prominent role in Chapters 9 and 12,
describes images and inverse images of unions and intersections of sets.
1.37 Theorem. Let X and Y be sets and f : X → Y .
i) If {E α }α∈A is a collection of subsets of X, then
f
"
α∈A
Eα
=
"
α∈A
f (E α )
and
f
/
α∈A
Eα
⊆
/
α∈A
ii) If B and C are subsets of X, then f (CB) ⊇ f (C) f (B).
f (E α ).
34 Chapter 1
The Real Number System
iii) If {E α }α∈A is a collection of subsets of Y, then
f
"
−1
α∈A
Eα
=
"
f
−1
(E α )
and
f
−1
α∈A
/
Eα
α∈A
=
/
f −1 (E α ).
α∈A
iv) If B and C are subsets of Y, then f −1 (CB) = f −1 (C) f −1 (B).
v) If E ⊆ f (X ), then f ( f −1 (E)) = E, but if E ⊆ X , then f −1 ( f (E)) ⊇ E.
Proof. i) By deﬁnition, y ∈ f (∪α∈A E α ) if and only if y = f (x) for some x ∈
E α and α ∈ A. This is equivalent to y ∈ ∪α∈A f (E α ). Similarly, y ∈ f (∩α∈A E α )
if and only if y = f (x) for some x ∈ ∩α∈A E α . This implies that for all α ∈ A
there is an xα ∈ E α such that y = f (xα ). Therefore, y ∈ ∩α∈A f (E α ).
ii) If y ∈ f (C) f (B), then y = f (c) for some c ∈ C but y = f (b) for any
b ∈ B. It follows that y ∈ f (CB). Similar arguments prove parts iii), iv),
and v).
It is important to recognize that the set inequalities in parts i), ii), and v)
can be strict unless f is 1–1 (see Exercises 1.5.6 and 1.5.7). For example, if
f (x) = x 2 , E 1 = {1}, and E 2 = {−1}, then f (E 1 ∩ E 2 ) = ∅ is a proper subset of
f (E 1 ) ∩ f (E 2 ) = {1}.
EXERCISES
1.5.0. Decide which of the following statements are true and which are false.
Prove the true ones and give counterexamples to the false ones.
a) Let f (x) = sin x. Then the function
π 3π
,
f :
2 2
→ [−1, 1]
is a bijection, and its inverse function is arcsin x.
b) Suppose that A, B, and C are subsets of some set X and that f :
X → X . If A ∩ B = ∅, then f (A) ∩ f (B ∪ C) = ∅.
c) Suppose that A and B are subsets of some set X . Then (AB)c =
BA.
d) If f takes [−1, 1] onto [−1, 1], then f −1 ( f ({0})) = {0}.
1.5.1. a) For each of the following, prove that f is 1–1 on E and ﬁnd f (E).
α)
β)
γ)
δ)
ε)
ζ)
∗ b)
f (x) = 3x − 7, E = R
f (x) = e1/x , E = (0, ∞)
f (x) = tan x, E = (π/2, 3π/2)
f (x) = x 2 + 2x − 5, E = (−∞, −6]
f (x) = 3x − |x| + |x − 2|, E = R
f (x) = x/(x 2 + 1), E = [−1, 1]
Find an explicit formula for f −1 on f (E).
Section 1.6
Countable and Uncountable Sets
35
1.5.2. Find f (E) and f −1 (E) for each of the following.
a)
b)
c)
d)
e)
f (x) = 2 − 3x, E = (−1, 2)
f (x) = x 2 + 1, E = (−1, 2]
f (x) = 2x − x 2 , E = [−2, 2)
f (x) = log(x 2 − 2x + 2), E = (0, 3]
f (x) = cos x, E = [0, ∞)
1.5.3. Give a simple description of each of the following sets.
#
[x − 2, x + 1]
a)
x∈[0,1]
b)
(x − 1, x + 1]
x∈[0,1]
2
3
− k1 , k1
c)
k∈N 2
3
#
− k1 , 0
d)
k∈N 2
!
#
−k, k1
e)
k∈N 2
k−1 k+1 3
f)
k , k
k∈N
1.5.4. Prove (18).
1.5.5. Prove Theorem 1.37iii, iv, and v.
1.5.6. Let f (x) = x 2 .
a) Find subsets B and C of R such that f (CB) = f (C) f (B).
b) Find a subset E of R such that f −1 ( f (E)) = E.
1.5.7 . This exercise is used several times in Chapter 12. Let X, Y be sets and
f : X → Y . Prove that the following are equivalent.
a)
b)
c)
d)
1.6
f is 1–1 on X .
f (AB) = f (A) f (B) for all subsets A and B of X .
f −1 ( f (E)) = E for all subsets E of X .
f (A ∩ B) = f (A) ∩ f (B) for all subsets A and B of X .
COUNTABLE AND UNCOUNTABLE SETS
In this section we will show how to use bijections to “count” inﬁnite sets. We
begin by examining what it means to count a ﬁnite set. When we count a
ﬁnite set E, we assign consecutive numbers in N to the elements of E; that
is, we construct a function f from {1, 2, . . . , n} to E, where n is the number of elements in E. For example, if E has three objects, then the “counting” function, f , takes {1, 2, 3} to E. Now in order to count E properly,
we must be careful to avoid two pitfalls. We must not count any element of
E more than once (i.e., f must be 1–1), and we cannot miss any element of
E (i.e., f must take {1, 2, 3} onto E). Accordingly, we make the following
deﬁnition.
36 Chapter 1
The Real Number System
1.38 Deﬁnition.
Let E be a set.
i) E is said to be ﬁnite if and only if either E = ∅ or there exists a 1–1 function
which takes {1, 2, . . . , n} onto E, for some n ∈ N.
ii) E is said to be countable if and only if there exists a 1–1 function which
takes N onto E.
iii) E is said to be at most countable if and only if E is either ﬁnite or countable.
iv) E is said to be uncountable if and only if E is neither ﬁnite nor countable.
Loosely speaking, a set is countable if it has the same number of elements as
N, ﬁnite if it has less, and uncountable if it has more.
To show that a set E is countable, it sufﬁces to exhibit a 1–1 function f from
N onto E. For example, the set of even integers E = {2, 4, . . .} is countable
because f (k) := 2k is 1–1 from N onto E. Thus, two inﬁnite sets can have the
same number of elements even though one is a proper subset of the other. (In
fact, this property can be used as a deﬁnition of “inﬁnite set.”)
The following result shows that not every inﬁnite set is countable.
1.39 Remark. [CANTOR’S DIAGONALIZATION ARGUMENT].
interval (0, 1) is uncountable.
The open
Strategy: Suppose to the contrary that (0, 1) is countable. Then by definition, there is a function f on N such that f (1), f (2), . . . exhausts the elements of (0, 1). We could reach a contradiction if we could ﬁnd a new number
x ∈ (0, 1) that is different from all the f (k)’s. How can we determine whether
two numbers are different? One easy way is to look at their decimal expansions.
For example, 0.1234 = 0.1254 because they have different decimal expansions.
Thus, we could ﬁnd an x that has no preimage under f by making the decimal expansion of x different by at least one digit from the decimal expansion of
EVERY f (k).
There is a ﬂaw in this approach that we must ﬁx. Decimal expansions are
unique except for ﬁnite decimals, which always have an alternative expansion
that terminates in 9s (e.g., 0.5 = 0.4999 . . . and 0.24 = 0.23999 . . .) (see Exercise 2.2.10). Hence, when specifying the decimal expansion of x, we must avoid
decimals that terminate in 9s.
Proof. Suppose that there is a 1–1 function f that takes N onto the interval
(0, 1). Write the numbers f ( j), j ∈ N, in decimal notation, using the ﬁnite
expansion when possible, that is,
f (1) = 0.α11 α12 . . . ,
f (2) = 0.α21 α22 . . . ,
f (3) = 0.α31 α32 . . . ,
...,
Section 1.6
Countable and Uncountable Sets
37
where αi j represents the jth digit in the decimal expansion of f (i) and none
of these expansions terminates in 9s. Let x be the number whose decimal
expansion is given by 0.β1 β2 . . . , where
αkk + 1
if αkk ≤ 5
βk :=
if αkk > 5.

αkk − 1

Clearly, x is a number in (0, 1) whose decimal expansion does not contain

one 9, much less terminate in 9s. Since f is onto, there is a j ∈ N such that

f ( j) = x. Since we have avoided 9s, the decimal expansions of f ( j) and

x must be identical (e.g., α j j = β j := α j j ± 1). It follows that 0 = ±1, a

contradiction.

It is natural to ask about the countability of the sets Z, Q, and R. To answer

these questions, we prove several preliminary results. First, to show that a set

E is at most countable, we do not need to construct a ONE-TO-ONE function

which takes N onto E.

1.40 Lemma.

A nonempty set E is at most countable if and only if there is a function g from

N onto E.

Proof. If E is countable, then by Deﬁnition 1.38ii there is a (1–1) function f

from N onto E, so g := f takes N onto E. If E is ﬁnite, then there is an n ∈ N

and a 1–1 function f that takes {1, 2, . . . , n} onto E. Hence

f ( j)

j ≤n

g( j) :=

f (1)

j >n

takes N onto E.

Conversely, suppose that g takes N onto E. We need to construct a function

f that is 1–1 from some subset o…

Purchase answer to see full

attachment

Tags:

mathematics

linear transformation

Multivariable Calculus

Euclidian Space

limits and continuity of functions

User generated content is uploaded by users for the purposes of learning and should be used following Studypool’s honor code & terms of service.

## Reviews, comments, and love from our customers and community:

This page is having a slideshow that uses Javascript. Your browser either doesn't support Javascript or you have it turned off. To see this page as it is meant to appear please use a Javascript enabled browser.