Advanced Calculus

Pearson New International Edition

International_PCL_TP.indd 1 7/29/13 11:23 AM

Analysis with an Introduction to Proof Steven R. Lay Fifth Edition

Pearson Education Limited Edinburgh Gate Harlow Essex CM20 2JE England and Associated Companies throughout the world

Visit us on the World Wide Web at: www.pearsoned.co.uk

© Pearson Education Limited 2014

All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, without either the prior written permission of the publisher or a licence permitting restricted copying in the United Kingdom issued by the Copyright Licensing Agency Ltd, Saffron House, 6–10 Kirby Street, London EC1N 8TS.

All trademarks used herein are the property of their respective owners. The use of any trademark in this text does not vest in the author or publisher any trademark ownership rights in such trademarks, nor does the use of such trademarks imply any affi liation with or endorsement of this book by such owners.

ISBN 10: 1-269-37450-8 ISBN 13: 978-1-269-37450-7

British Library Cataloguing-in-Publication Data A catalogue record for this book is available from the British Library

Printed in the United States of America

Copyright_Pg_7_24.indd 1 7/29/13 11:28 AM

ISBN 10: 1-292-04024-6 ISBN 13: 978-1-292-04024-0

ISBN 10: 1-292-04024-6 ISBN 13: 978-1-292-04024-0

Table of Contents

P E A R S O N C U S T O M L I B R A R Y

I

1. Logic and Proof

1

1Steven R. Lay

2. Sets and Functions

41

41Steven R. Lay

3. The Real Numbers

111

111Steven R. Lay

4. Sequences

171

171Steven R. Lay

5. Limits and Continuity

207

207Steven R. Lay

6. Differentiation

251

251Steven R. Lay

7. Integration

291

291Steven R. Lay

8. Infinite Series

319

319Steven R. Lay

Glossary of Key Terms

345

345Steven R. Lay

359

359Index

Logic and Proof

To understand mathematics and mathematical arguments, it is necessary to have a solid understanding of logic and the way in which known facts can be combined to prove new facts. Although many people consider themselves to be logical thinkers, the thought patterns developed in everyday living are only suggestive of and not totally adequate for the precision required in mathematics. In this chapter we take a careful look at the rules of logic and the way in which mathematical arguments are constructed. Section 1 presents the logical connectives that enable us to build compound statements from simpler ones. Section 2 discusses the role of quantifiers. Sections 3 and 4 analyze the structure of mathematical proofs and illustrate the various proof techniques by means of examples.

Section 1 LOGICAL CONNECTIVES The language of mathematics consists primarily of declarative sentences. If a sentence can be classified as true or false, it is called a statement. The truth or falsity of a statement is known as its truth value. For a sentence to be a statement, it is not necessary that we actually know whether it is true or false, but it must clearly be the case that it is one or the other.

From Chapter 1 of Analysis with an Introduction to Proof, Fifth Edition. Steven R. Lay. Copyright © 2014 by Pearson Education, Inc. All rights reserved.

1

Logic and Proof

1.1 EXAMPLE Consider the following sentences.

(a) Two plus two equals four. (b) Every continuous function is differentiable. (c) x2 – 5x + 6 = 0. (d) A circle is the only convex set in the plane that has the same width in

each direction. (e) Every even number greater than 2 is the sum of two primes.

Sentences (a) and (b) are statements since (a) is true and (b) is false. Sentence (c), on the other hand, is true for some x and false for others. If we have a particular context in mind, then (c) will be a statement. In Section 2 we shall see how to remove this ambiguity. Sentences (d) and (e) are more difficult. You may or may not know whether they are true or false, but it is certain that each sentence must be one or the other. Thus (d) and (e) are both statements. [It turns out that (d) can be shown to be false, and the truth value of (e) has not yet been established.†]

1.2 PRACTICE Which of the sentences are statements?

(a) If x is a real number, then x2 ≥ 0. (b) Seven is a prime number. (c) Seven is an even number. (d) This sentence is false.

In studying mathematical logic we shall not be concerned with the truth value of any particular simple statement. To be a statement, it must be either true or false (and not both), but it is immaterial which condition applies. What will be important is how the truth value of a compound statement is determined by the truth values of its simpler parts. In everyday English conversation we have a variety of ways to change or combine statements. A simple statement‡ like

It is windy. can be negated to form the statement

It is not windy.

† Sentence (e) is known as the Goldbach conjecture after the Prussian mathematician Christian Goldbach, who made this conjecture in a letter to Leonhard Euler in 1742. Using computers it has been verified for all even numbers up to 1014 but has not yet been proved for every even number. For a good discussion of the history of this problem, see Hofstadter (1979). Recent results are reported in Deshouillers et al. (1998).

‡ It may be questioned whether or not the sentence “It is windy” is a statement, since the term “windy” is so vague. If we assume that “windy” is given a precise definition, then in a particular place at a particular time, “It is windy” will be a statement. It is customary to assume precise definitions when we use descriptive language in an example. This problem does not arise in a mathematical context because the definitions are precise.

2

Logic and Proof

The compound statement

It is windy and the waves are high.

is made up of two parts: “It is windy” and “The waves are high.” These two parts can also be combined in other ways. For example,

It is windy or the waves are high. If it is windy, then the waves are high. It is windy if and only if the waves are high.

The italicized words above (not, and, or, if . . . then, if and only if ) are called sentential connectives. Their use in mathematical writing is similar to (but not identical with) their everyday usage. To remove any possible ambi- guity, we shall look carefully at each and specify its precise mathematical meaning. Let p stand for a given statement. Then ~ p (read not p) represents the logical opposite (negation) of p. When p is true, ~ p is false; when p is false, ~ p is true. This can be summarized in a truth table:

p ~ p

T F F T

where T stands for true and F stands for false.

1.3 EXAMPLE Let p, q, and r be given as follows: p : Today is Monday. q : Five is an even number. r : The set of integers is countable.

Then their negations can be written as

~ p : Today is not Monday. ~ q : Five is not an even number. or Five is an odd number. ~ r : The set of integers is not countable. or The set of integers is uncountable. The connective and is used in logic in the same way as it is in ordinary language. If p and q are statements, then the statement p and q (called the conjunction of p and q and denoted by p ∧ q) is true only when both p and q are true, and it is false otherwise.

3

Logic and Proof

1.4 PRACTICE Complete the truth table for p ∧ q. Note that we have to use four lines in this table to include all possible combinations of truth values of p and q.

p q p ∧ q

T T T F F T F F

The connective or is used to form a compound statement known as a disjunction. In common English the word or can have two meanings. In the sentence

We are going to paint our house yellow or green.

the intended meaning is yellow or green, but not both. This is known as the exclusive meaning of or. On the other hand, in the sentence

Do you want cake or ice cream for dessert?

the intended meaning may include the possibility of having both. This inclusive meaning is the only way the word or is used in logic. Thus, if we denote the disjunction p or q by p ∨ q, we have the following truth table:

p q p ∨ q

T T T T F T F T T F F F

A statement of the form

If p, then q. is called an implication or a conditional statement. The if-statement p in the implication is called the antecedent and the then-statement q is called the consequent. To decide on an appropriate truth table for implication, let us consider the following sentence:

If it stops raining by Saturday, then I will go to the football game.

If a friend made a statement like this, under what circumstances could you call him a liar? Certainly, if the rain stops and he doesn’t go, then he did not tell the truth. But what if the rain doesn’t stop? He hasn’t said what he will do then, so whether he goes or not, either is all right.

4

Logic and Proof

Although it might be argued that other interpretations make equally good sense, mathematicians have agreed that an implication will be called false only when the antecedent is true and the consequent is false. If we denote the implication “if p, then q” by p ⇒ q, we obtain the following table:

p q p ⇒ q

T T T T F F F T T F F T

It is important to recognize that in mathematical writing the conditional statement can be disguised in several equivalent forms. Thus the following expressions all mean exactly the same thing:

if p, then q q provided that p p implies q q whenever p p only if q p is a sufficient condition for q q if p q is a necessary condition for p

1.5 PRACTICE Identify the antecedent and the consequent in each of the following statements.

(a) If n is an integer, then 2n is an even number. (b) You can work here only if you have a college degree. (c) The car will not run whenever you are out of gas. (d) Continuity is a necessary condition for differentiability.

One way to visualize an implication R ⇒ S is to picture two sets R and S, with R inside S. Figure 1 shows several objects of different shapes. Some are round and some are not round. Some are solid and some are not solid. Objects that are round are in set R and objects that are solid are in set S.

Figure 1 R ⇒ S

S

R • •

•

▲

■

♦

♦

▼

□

5

Logic and Proof

We see that the relationship between R and S in Figure 1 can be stated in several equivalent ways:

• If an object is round (R), then it is solid (S). • An object is solid (S) whenever it is round (R). • An object is solid (S) provided that it is round (R). • Being round (R) is a sufficient condition for an object to be solid (S).

(It is sufficient to know that an object is round to conclude that it is solid.)

• Being solid (S) is a necessary condition for an object to be round (R). (It is necessary for an item to be solid in order for it to be round.)

1.6 PRACTICE In Figure 1, which of the following is correct?

(a) An object is solid (S) only if it is round (R). (b) An object is round (R) only if it is solid (S). The statement “p if and only if q” is the conjunction of the two con- ditional statements p ⇒ q and q ⇒ p. A statement in this form is called a biconditional and is denoted by p ⇔ q. In written form the abbreviation “iff ” is sometimes used instead of “if and only if.” The truth table for the biconditional can be obtained by analyzing the compound statement ( p ⇒ q) ∧ ( q ⇒ p) a step at a time.

p q p ⇒ q q ⇒ p ( p ⇒ q) ∧ ( q ⇒ p)

T T T T T T F F T F F T T F F F F T T T

Thus we see that p ⇔ q is true precisely when p and q have the same truth values.

1.7 PRACTICE Construct a truth table for each of the following compound statements.

(a) ~ ( p ∧ q) ⇔ [(~ p) ∨ (~ q)] (b) ~ ( p ∨ q) ⇔ [(~ p) ∧ (~ q)] (c) ~ ( p ⇒ q) ⇔ [ p ∧ (~ q)]

In Practice 1.7 we find that each of the compound statements is true in all cases. Such a statement is called a tautology. When a biconditional statement is a tautology, it shows that the two parts of the biconditional are

6

Logic and Proof

logically equivalent. That is, the two component statements have the same truth tables. We shall encounter many more tautologies in the next few sections. They are very useful in changing a statement from one form into an equivalent statement in a different (one hopes simpler) form. In 1.7(a) we see that the negation of a conjunction is logically equivalent to the disjunction of the negations. Similarly, in 1.7(b) we learn that the negation of a disjunction is the conjunction of the negations. In 1.7(c) we find that the negation of an implication is not another implication, but rather it is the conjunction of the antecedent and the negation of the consequent.

1.8 EXAMPLE Using Practice 1.7(a), we see that the negation of

The set S is compact and convex. can be written as

The set S is not compact or it is not convex. This example also illustrates that using equivalent forms in logic does not depend on knowing the meaning of the terms involved. It is the form of the statement that is important. Whether or not we happen to know the definition of “compact” and “convex” is of no consequence in forming the negation above.

1.9 PRACTICE Use the tautologies in Practice 1.7 to write out a negation of each of the following statements.

(a) Seven is prime or 2 + 2 = 4. (b) If M is bounded, then M is compact. (c) If roses are red and violets are blue, then I love you.

Review of Key Terms in Section 1

Statement Implication Biconditional Negation Conditional Tautology Conjunction Antecedent Disjunction Consequent

ANSWERS TO PRACTICE PROBLEMS

1.2 (a), (b), and (c)

7

Logic and Proof

1.4 p q p ∧ q

T T T T F F F T F F F F

1.5 (a) Antecedent: n is an integer Consequent: 2n is an even number (b) Antecedent: you can work here Consequent: you have a college degree (c) Antecedent: you are out of gas Consequent: the car will not run (d) Antecedent: differentiability Consequent: continuity

1.6 Statement (b) is correct. If one of the objects is not solid, then it cannot possibly be round.

1.7 Sometimes we condense a truth table by writing the truth values under the part of a compound expression to which they apply.

(a) p q ~ ( p ∧ q) ⇔ [(~ p) ∨ (~ q)]

T T F T T F F F T F T F T F T T F T T F T T T F F F T F T T T T

(b) p q ~ ( p ∨ q) ⇔ [(~ p) ∧ (~ q)]

T T F T T F F F T F F T T F F T F T F T T T F F F F T F T T T T

(c) p q ~ ( p ⇒ q) ⇔ [ p ∧ (~ q)]

T T F T T T F F T F T F T T T T F T F T T F F F F F F T T F F T

8

Logic and Proof

1.9 (a) Seven is not prime and 2 + 2 ≠ 4. (b) M is bounded and M is not compact. (c) Roses are red and violets are blue, but I do not love you.

1 EXERCISES

Exercises marked with * are used in later sections, and exercises marked with have hints or solutions in the back of the chapter. 1. Mark each statement True or False. Justify each answer.

(a) In order to be classified as a statement, a sentence must be true. (b) Some statements are both true and false. (c) When statement p is true, its negation ~p is false. (d) A statement and its negation may both be false. (e) In mathematical logic, the word “or” has an inclusive meaning.

2. Mark each statement True or False. Justify each answer. (a) In an implication p ⇒ q, statement p is referred to as the proposition. (b) The only case where p ⇒ q is false is when p is true and q is false. (c) “If p, then q” is equivalent to “p whenever q.” (d) The negation of a conjunction is the disjunction of the negations of the

individual parts. (e) The negation of p ⇒ q is q ⇒ p.

3. Write the negation of each statement. (a) The 3 × 3 identity matrix is singular. (b) The function f (x) = sin x is bounded on R. (c) The functions f and g are linear. (d) Six is prime or seven is odd. (e) If x is in D, then f (x) < 5. (f ) If (an) is monotone and bounded, then (an) is convergent. (g) If f is injective, then S is finite or denumerable.

4. Write the negation of each statement. (a) The function f (x) = x2 – 9 is continuous at x = 3. (b) The relation R is reflexive or symmetric. (c) Four and nine are relatively prime. (d) x is in A or x is not in B. (e) If x < 7, then f (x) is not in C. (f ) If (an) is convergent, then (an) is monotone and bounded. (g) If f is continuous and A is open, then f – 1(A) is open.

9

Logic and Proof

5. Identify the antecedent and the consequent in each statement. (a) M has a zero eigenvalue whenever M is singular. (b) Linearity is a sufficient condition for continuity. (c) A sequence is Cauchy only if it is bounded. (d) x < 3 provided that y > 5.

6. Identify the antecedent and the consequent in each statement. (a) A sequence is convergent if it is Cauchy. (b) Convergence is a necessary condition for boundedness. (c) Orthogonality implies invertability. (d) K is closed and bounded only if K is compact.

7. Construct a truth table for each statement. (a) p ⇒ ~ q (b) [ p ∧ ( p ⇒ q)] ⇒ q (c) [ p ⇒ ( q ∧ ~ q)] ⇔ ~ p

8. Construct a truth table for each statement. (a) p ∨ ~ q (b) p ∧ ~ p (c) [(~ q) ∧ ( p ⇒ q)] ⇒ ~ p

9. Indicate whether each statement is True or False. (a) 3 ≤ 5 and 11 is odd. (b) 32 = 8 or 2 + 3 = 5. (c) 5 > 8 or 3 is even. (d) If 6 is even, then 9 is odd. (e) If 8 < 3, then 22 = 5. (f ) If 7 is odd, then 10 is prime. (g) If 8 is even and 5 is not prime, then 4 < 7. (h) If 3 is odd or 4 > 6, then 9 ≤ 5. ( i ) If both 5 – 3 = 2 and 5 + 3 = 2, then 9 = 4. ( j ) It is not the case that 5 is even or 7 is prime.

10. Indicate whether each statement is True or False. (a) 2 + 3 = 5 and 5 is even. (b) 3 + 4 = 5 or 4 + 5 = 6. (c) 7 is even or 6 is not prime. (d) If 4 + 4 = 8, then 9 is prime. (e) If 6 is prime, then 8 < 6. (f) If 6 < 2, then 4 + 4 = 8. (g) If 8 is prime or 7 is odd, then 9 is even. (h) If 2 + 5 = 7 only if 3 + 4 = 8, then 32 = 9. ( i ) If both 5 – 3 = 2 and 5 + 3 = 8, then 8 – 3 = 4. ( j) It is not the case that 5 is not prime and 3 is odd.

10

Logic and Proof

11. Let p be the statement “The figure is a polygon,” and let q be the statement “The figure is a circle.” Express each of the following statements in symbols. (a) The figure is a polygon, but it is not a circle. (b) The figure is a polygon or a circle, but not both. (c) If the figure is not a circle, then it is a polygon. (d) The figure is a circle whenever it is not a polygon. (e) The figure is a polygon iff it is not a circle.

12. Let m be the statement “x is perpendicular to M,” and let n be the statement “x is perpendicular to N.” Express each of the following statements in symbols. (a) x is perpendicular to N but not perpendicular to M. (b) x is not perpendicular to M, nor is it perpendicular to N. (c) x is perpendicular to N only if x is perpendicular to M. (d) x is not perpendicular to N provided it is perpendicular to M. (e) It is not the case that x is perpendicular to M and perpendicular to N.

13. Define a new sentential connective ∇, called nor, by the following truth table.