- February 9, 2021

The University of Melbourne School of Mathematics and Statistics MAST20026 Real Analysis Semester 2, 2020 Partial Lecture Slides Some things to be aware of: I These notes are not intended as a textbook. Rather they are an accompaniment to the lectures. You will need to take notes during the lectures. I You are expected to watch all lectures in the week they are published in order to keep up with tutorials and homework assignments. I You are expected also to utilise textbooks from the library (or elsewhere). This compilation has been made in accordance with the provisions of Part VB of the copyright act for teaching purposes at the University. For the use of students of the University of Melbourne enrolled in the subject MAST20026 Real Analysis. Main Topics Topic 1 Logic and Proof 9 Topic 2 Sequences 162 Topic 3 Limits and Continuity 223 Topic 4 Differentiability 284 Topic 5 Integration 296 Topic 6 Series 325 1 Introduction In your previous subjects, you will have seen some simple proofs and constructed some yourselves. For example, in Linear Algebra, showing that a particular set is (or is not) a vector subspace of a bigger vector space. This subject is more about developing your skills in proof writing rather than about calculation! To do this we need to have a thorough understanding of how mathematical arguments work. This involves starting with logic and the way it is used in mathematics. This subject has two main aims: I To study how to write mathematical proofs I To study Real Analysis 2 Consider as a motivating example, Euler’s number e. How do we understand this number? You might have been taught e ∼ 2.718281828 or the deceptive expression e = 2.718281828… The first is an approximation while the latter is not even a precise statement. 3 Hopefully you were told one of the rigorous definitions. Here are two of them e = lim n→∞ ( 1 + 1 n )n or e = ∞∑ n=0 1 n! = 1 + 1 1 + 1 1 · 2 + 1 1 · 2 · 3 + · · · Both of these definitions involve letting some value (in both cases “n”) tend to infinity. Moreover, they are equivalent, in the sense that they define the same real number. We mean to make this process mathematically precise. This is not so much about making the idea of infinity precise. It is more about understanding the rigorous definition of convergence. 4 e = ∞∑ n=0 1 n! = 1 + 1 1 + 1 1 · 2 + 1 1 · 2 · 3 + · · · (1) To make this expression (and the other definition above) precise took a long time. Cauchy first did it in 1821, which in mathematics is recent history. This used what is sometimes called the (, δ) or the (,N) definition of convergence. I You will learn this rigorous definition and apply it in all sorts of contexts to understand the concept of convergence I You will learn rigorous algebraic properties of numbers; for example e is a real number but not a rational number. (More on ‘rational vs real’ later.) 5 The definition in (1) is best for us because it readily generalizes to give us the powers of e: ex = ∞∑ n=0 xn n! = 1 + x 1 + x2 1 · 2 + x3 1 · 2 · 3 + · · · This is probably the most important function in mathematics. In particular it solves the important differential equation: d(ex) dx = ex Perhaps you can show this is true formally, but proving it rigorously is another matter. Making rigorous such precise properties of functions is also a central part of this subject. 6 Thus what we seek are Definitions: precise definitions of the objects we are working with. Proofs: to be able to prove statements based on the definitions as well as statements based on axioms. (axioms are statements assumed to be true) 7 Without precision in reasoning it is easy to make (erroneous) arguments which lead to ridiculous conclusions. For example consider the sum 1− 1 + 1− 1 + 1− 1 + 1− 1 + · · · · · · By grouping one way we argue that the (infinite) sum is 0, while by grouping another way we argue it is 1. Have we proved that 1 = 0? No! We have not proven anything. Now consider the sum 1 2 + 1 4 + 1 8 + 1 16 + 1 32 + 1 64 + · · · · · · 8 Logic and Proof We want 1. A precise way to write mathematical definitions. 2. A precise notion of what constitutes a mathematical proof. 3. A precise notion of what constitutes a theorem. 4. Some methods of proof. Need two forms of logic 1. Propositional logic 2. First order logic 9 Propositional Logic Logic is about how to infer true things from known or assumed things. Propositional logic is about two valued variables and two valued functions of those variables. These two values will be called “true” and “false” or sometimes 0 and 1. Definition 2.1 (Statement) A statement is a “sentence” or “expression” that is either true or false. The statement takes on the role of a logical variable (the variables are true or false). We will generally use lower case letters p, q, r , . . . to represent statements. Some books use the word proposition rather than statement. 10 Examples Example 2.1 (Which of these are statements?) I All maths lecturers are named Paul. I 2 + 3 = 7 I 1 + 1 = 2 I potato I x > 2 I For all x ∈ Z, x2 ≥ 0 I Every even number greater than 2 is the sum of two primes. 11 Connectives We can combine statements to give new statements. Such statements are called compound statements (or logical formulae). They are constructed from: 1. primitive statements (that is, logical variables) 2. connectives 3. parentheses (to remove ambiguity) Generally, we use upper case letters A,B,C , . . . to denote compound statements. The connectives we will consider are: I negation I disjunction I conjunction I implication I equivalence 12 Definition 2.2 (Negation) If p is a statement, the negation of p is the statement “not p” and is denoted by ∼p. Its logical value is the opposite of p (ie., if p is true then ∼p is false). It can also be denoted by ∼ p. p ∼ p T F F T Example 2.2 If p is the statement “the grass is green” then ∼p is the statement “not [the case that] the grass is green”. (We would usually say “the grass is not green”.) Example 2.3 If p is the statement “5 > 0” then ∼ p is the statement “5 is not > 0” which is the same as “5 ≤ 0”. Example 2.4 If q is the statement “1 + 1 = 7” then “∼ q” is the statement “1 + 1 6= 7”. 13 In the English language, there are two different usages of the word ‘or’. The exclusive use of “or”: I will ride my bike or catch the train. usually means that one or the other of these modes of transportation will be used, but not both. This is not the mathematical usage of “or”. Definition 2.3 (Disjunction) If p and q are statements, the disjunction of p and q is the statement “p or q” and is denoted by p ∨ q. It is True if one or both of p and q are True. It is False if both p and q are False. p q p ∨ q T T T F F T F F The disjunction is an inclusive use of “or”, that is; it allows for the possibility that both statements are true. 14 Example 2.5 If p is the statement “2 + 5 = 7” and q is the statement “1 + 1 = 2”, then p ∨ q is the statement “2 + 5 = 7 or 1 + 1 = 2”. Example 2.6 If p is the statement “2 + 5 = 7” and q is the statement “1 + 1 = 0”, then p ∨ q is the statement “2 + 5 = 7 or 1 + 1 = 0”. 15 When defining the above connectives we gave their Truth Tables. p ∼ p T F p q p ∨ q T T T F F T F F We will use truth tables to define some other connectives. 16 Definition 2.4 (Conjunction) If p and q are statements, the conjunction of p and q is the statement “p and q”, denoted p ∧ q. p q p ∧ q T T T F F T F F Conjunction accords with the natural language use of the word “and”. Example 2.7 If p is the statement “2 + 5 = 7” and q is the statement “1 + 1 = 2” then the conjunction of p and q is the statement “2 + 5 = 7 and 1 + 1 = 2”. Example 2.8 If p is the statement “2 + 5 = 7” and q is the statement “1 + 1 = 0” then the conjunction of p and q is the statement “2 + 5 = 7 and 1 + 1 = 0”. 17 Example 2.9 Note that p ∧ q has the same truth table as q ∧ p, and p ∨ q has the same truth table as q ∨ p; that is, conjunction and disjunction are commutative. 18 Definition 2.5 (Implication) A statement of the form “if p then q”is called an implication (or a conditional statement). It is written as p ⇒ q. p q p ⇒ q T T T F F T F F The statement p is called the antecedent and the statement q is called the consequent. 19 Example 2.10 p : 1 + 1 = 2 q : 22 = 4 r : pi = 3 p ⇒ q is True p ⇒ r is r ⇒ p is True 20 There are many natural language equivalent statements: I If p then q I p only if q I q follows from p I q is necessary for p I q provided that p I q is a necessary condition for p I there are others……… 21 Example 2.11 p q p ⇒ q ∼ p (∼ p) ∨ q 22 Definition 2.6 (equivalence) A statement of the form“p if and only if q” is called an equivalence (or a biconditional statement). It is written as p ⇔ q. p q p ⇔ q Note that p if and only if q is the same as (ie., “logically equivalent to”) (p ⇒ q) ∧ (q ⇒ p). 23 Definition 2.7 (Compound statement) Statements constructed from several primitives are called compound statements. Usually they are written with capital letters, P,Q,R, . . . . A compound statement is also either true or false. Another way to look at it is, if you combine statements with connectives in a valid way then you have a compound statement which is either true or false, and its truth value depends on the truth values of the statements comprising it. Example 2.12 Let p, q, r be primitive statements, then I p ∧ q I (∼ p) ∧ (∼ q) I (p ⇒ q) ∧ (q ⇒ p) are all compound statements. 24 Negating Compound Statements Example 2.13 Since p ∧ q is a statement, we can negate it, giving, ∼ (p ∧ q). The truth table is p q p ∧ q ∼ (p ∧ q) Be careful with your use of brackets. They should be used to remove any ambiguity. If I write ∼ p ∧ q do I mean (∼ p) ∧ q or ∼ (p ∧ q)? They are not the same. 25 Example 2.14 Now consider the truth table for (∼ p) ∨ (∼ q) p q ∼ p ∼ q (∼ p) ∨ (∼ q) Notice that (∼ p) ∨ (∼ q) always gives the same truth value as ∼ (p ∧ q) 26 Logical Equivalence Definition 2.8 (Logically equivalent) Statements which have the same truth table are said to be logically equivalent. That is, p and q are logically equivalent if the statement p ⇔ q is a tautology. It is denoted p ≡ q. 1. p ∧ q ≡ q ∧ p 2. p ∨ q ≡ q ∨ p 3. ∼ (p ∧ q) ≡ (∼ p) ∨ (∼ q) 4. ∼ (p ∨ q) ≡ (∼ p) ∧ (∼ q) 27 Example 2.15 We show number 4 from above p q p ∨ q ∼ (p ∨ q) ∼ p ∼ q (∼ p) ∧ (∼ q) ∼ (p ∨ q)⇔ (∼ p) ∧ (∼ q) 28 First Order Logic Mathematical theories have several ingredients that propositional logic cannot easily represent (for example, sets, functions and mathematical operations). We use mathematical variables x , y , z , . . . to represent elements of the set of objects U (called the universal set). We also have equations and inequalities containing variables: I x > 0 I x2 − 3x + 2 = 0. These two formulae are not statements. They are neither true nor false, because their truth depends on the value of x . Formulae which depend on (free) variables are called conditions (or predicates) 29 Conditions on x are written as p(x), q(x), . . . . Example 2.16 Some conditions on x are: I p(x) : x > 0 I q(x) : x2 − 3x + 2 = 0. They are neither True nor False. Some statements are: I p(2) : 2 > 0 I p(−5) : −5 > 0 I q(3) : 32 − 32 + 2 = 0. They can be seen as True or False. 30 If x is replaced by a particular value (or element of a set), then the formulae become statements. There are (at least) two ways to convert formulae containing mathematical variables into logical statements. 1. Substitution Pick any element of U and substitute into the formula: Thus, if U is Z, then I (x = 2) I (x = −5) I (x = 3) 31 2. Using quantifiers Thus, if U is still Z, then I for all x ∈ Z, x > 0 I for all x ∈ Z, x2 − 3x + 2 = 0 I there exists an x ∈ Z such that x > 0 I there exists an x ∈ Z such that x2 − 3x + 2 = 0 The phrases “for all” and “there exists” are quantifiers. 32 Expressions like p(x) ∧ q(x) and p(x)⇒q(x) are compound conditions (or predicates). Example 2.17 I p(x) ∧ q(x) is the condition “p(x) and q(x)”. I p(x) ∨ q(x) is the condition “p(x) or q(x)”. I p(x)⇒q(x) is the condition “if p(x) then q(x)”. These all become valid logic statements when a particular value for x is substituted. 33 Quantifiers As we have seen, we can turn conditions on x into statements. Consider the condition p(x) : x2 ≥ 3. We can turn this into a statement in various ways: Definition 2.9 (Universal Quantifier) The phrase “for all” is called the universal quantifier and is written as ∀. 34 Now consider the condition p(x) : x2 − 1 = 0. Definition 2.10 (Existential Quantifier) The phrase “there exists” is called the Existential Quantifier and is written as ∃. 35 Proving and Disproving Quantified Statements If Q is the statement “∀x ∈ D p(x)”, where D is a set and p(x) is a condition on x , then Q is true only if p(x) is be true for every member of D (this might be difficult to show). However if at least one instance is false (say p(c)) then p(a) ∧ p(b) ∧ p(c) · · · is false. So Q can be disproved if at least one false case can be found. This is called a counterexample. 36 Example 2.18 ∀x ∈ R, (x − 1)2 > 0 37 Similarly, if R is the statement “∃x ∈ D p(x)”, then R is true if there is one true instance of p(x). So R can be proved true if at least one primitive statement is true. This is called an example. 38 Example 2.19 ∃x ∈ R (x − 1)2 > 0 In general I Disprove a universal statement with a counterexample. I Prove an existential statement with an example. 39 Writing theorems using First Order Logic We can use First Order Logic to write theorems in a precise way. 1. Any real number has the property that its square is not negative. 2. For every even integer m, 3m5 will also be an even integer. 40 3. If x and y are real numbers, the absolute value of their sum is no greater than the sum of their absolute values. 4. √ 2 is irrational. 5. If n is an integer greater than or equal to 5, then 2n is greater than n2. 41 Negation of ∀ Since quantified conditions are statements their negation is well defined. For example: ∼ [ ∀x ∈ D p(x) ] and ∼ [ ∃x ∈ D p(x) ] Are these logically equivalent to anything else? Theorem 2.1 (Negation of ∀) ∼( ∀x ∈ D p(x)) ≡ ∃x ∈ D ∼p(x) 42 Negation of ∃ Theorem 2.2 (Negation of ∃) ∼( ∃x ∈ D p(x) ) ≡ ∀x ∈ D ∼p(x) Example 2.20 No positive real number satisfies x3 = −1. This is the same as: 43 Tautologies and Contradictions Definition 2.11 (Tautology) If the truth table of a compound statement P(p1, . . . , pn) is true for all values of p1, . . . , pn then it is called a tautology. Example 2.21 p ∼p (∼p) ∨ p Thus (∼p) ∨ p is a tautology. 44 Example 2.22 P(p, q) : p ⇒ p ∨ q p q p ∨ q p ⇒ (p ∨ q) Thus P is a tautology. 45 Example 2.23 Show [p ∧ (p ⇒ q)]⇒ q is a tautology. p q p ⇒ q p ∧ (p ⇒ q) [p ∧ (p ⇒ q)]⇒ q 46 Definition 2.12 (Contradiction) If the truth table of a compound statement P(p1, . . . , pn) is false for all values of p1, . . . , pn then it is called a contradiction. Example 2.24 P(p) : (∼p) ∧ p p ∼p (∼p) ∧ p Thus P is a contradiction. Note: There is a second type of contradiction associated with inference rules — see later. 47 Converse and Contrapositive Definition 2.13 (Converse) The converse of p ⇒ q is the statement q ⇒ p. A conditional statement is not logically equivalent to its converse. Example 2.25 p q p ⇒ q q ⇒ p 48 Definition 2.14 (Contrapositive) The contrapositive of p ⇒ q is the statement (∼q)⇒ (∼p). (ie., switch and negate p and q) The following theorem says that the contrapositive of a conditional statement is logically equivalent to the original statement. This is very useful! Theorem 2.3 (Conditional and Contrapositive) If p and q are statements, then p ⇒ q ≡ (∼q)⇒ (∼p) 49 Proof. p q ∼p ∼q p ⇒ q (∼q)⇒ (∼p) This means that a conditional statement is logically equivalent to its contrapositive. 50 The following is a very useful form of the biconditional. Theorem 2.4 (Biconditional and Conditional) If p and q are statements, then [p ⇔ q] ≡ [(p ⇒ q) ∧ (q ⇒ p)]. Proof. p q p ⇔ q p ⇒ q q ⇒ p (p ⇒ q) ∧ (q ⇒ p) Columns 3 and 6 are the same thus the statements are logically equivalent. 51 For proof writing if we need to show p ⇔ q is true, then we can use Theorem 2.4. In general we show: 1. p ⇒ q is true, and 2. q ⇒ p is true (that is, the converse is true). Thus (p ⇒ q) ∧ (q ⇒ p) is true (T − T row of truth table). Thus p ⇔ q is true. Conversely, if we know p ⇔ q is true then Theorem 2.4 tells us that p ⇒ q is true and that q ⇒ p is true 52 Example 2.26 An even number x is a number that can be written in the form x = 2k, k ∈ Z. Written as a definition: x ∈ Z is even ⇔ ∃k ∈ Z such that x = 2k. 53 Logic, Theorems, and Mathematical Proofs We will now begin our discussion of proofs in depth. We start with an example: Theorem 2.5 If x is an even integer, then x2 is an even integer. 54 Let p : x is an even integer and q : x2 is an even integer. The theorem states, “If p then q” is true; that is, the conditional “p ⇒ q” is true. Method: To prove the theorem, we assume that p is true (i.e. that x is an even integer) and use this together with valid rules of inference to conclude that q is true (i.e. that x2 is an even integer. 55 Many theorems can be written as P(p1, . . . , pn)⇒ Q(p1, . . . , pn). To say that P(p1, . . . , pn)⇒ Q(p1, . . . , pn) is a theorem, means that P(p1, . . . , pn)⇒ Q(p1, . . . , pn) is a tautology; it is always true. From the truth table for P ⇒ Q, we see that it is true in all cases except when P is TRUE and Q is FALSE. So to prove the theorem, all we need to do is show that this can’t happen; that is, If p is true then q is true. 56 Using theorems: When we use the theorem we usually take p as true (ie., choose an even integer) and then use the theorem to infer q is true (ie., the square of an even integer is even). This is justified by the truth table for the conditional: p q p ⇒ q Assuming p is true and having the theorem true puts us on row 1 and hence q must be true. 57 Thus we get p true and (p ⇒ q) true allows us to infer q In logic this is usually written {p, p ⇒ q} q where is read“infers”. This is a famous “rule of inference” called Modus Ponens1 or the Law of Detachment – q has been detached from p ⇒ q. It is valid as long as p and (p ⇒ q) are assumed (or known) to be true. 1 From Latin: “The method that affirms the consequent by affirming the antecedent” 58 To emphasize the structure of mathematical proofs, let us prove the following simple statement: the sum two odd numbers is an even number. First let’s write this in a form where the logic is clear. If (m, n are odd integers), then (m + n is an even integer). Assumed true Inferred steps Conclusion 59 True statements that can be used as steps in a proof without inference come in various flavours. I Premises – statements assumed true for the purposes of a proof. I Axioms – very simple statements assumed true for the purposes of building an area of mathematics. I Tautologies – always true. I Theorems – already proved true. I Definitions I etc… 60 Thus a proof is a finite sequence of statements A1,A2, . . . . . . ,An such that each Ai is either I known or assumed true or I can be inferred from a known or assumed true statement Aj , with j < i (ie., a previous statement). The last statement, An, is usually called the conclusion and so a proof is sometimes written A1,A2, . . . . . . ,An−1 proves An 61 Indirect Proofs Up until now we have used “direct proofs”: • Start with true premises and infer a true conclusion using valid arguments. Indirect proofs are different. We will consider two types: • Proof using the contrapositive. • Proof by contradiction. 62 Contrapositive Proofs Instead of proving P ⇒ Q we use the logical equivalence (Theorem 2.3) (P ⇒ Q) ≡ ((∼Q)⇒ (∼P)) and prove (∼Q)⇒ (∼P) using any method of proof. 63 Theorem 2.6 (∀x ∈ Z), x2 is even iff x is even. 64 Example 2.27 Prove that there are infinitely many prime numbers. (You may take as axiomatic the rules or arithmetic and the factorization of integers into prime numbers.) 65 Proof by Contradiction If a theorem is in the form of a conditional: Theorem: If P then Q that is, we need to prove P ⇒ Q is true, then a proof by contradiction generally takes the form: Proof (by contradiction): P Premise (ie. assume P true) ∼Q Contradiction premise (ie. assume ∼Q true) Main steps of proof ... Negation of some previous statement (ie. a contradiction) Thus Q is true Contradiction Inference Thus P ⇒ Q Deduction Inference. QED. 66 Example 2.28 Prove by contradiction that, Theorem: If x is a rational number and y is an irrational number, then x + y is irrational. First place theorem into logic form: Proof (by contradiction): 67 There are many methods of proof: I Direct proofs I Indirect proofs I proof by contradiction, I contrapositive proof I Proof by cases I Others... All these methods of proof are shown to be valid methods using theorems from logic. The previous “sum of even integers is even” proof is an example of a direct proof. 68 Naive Set Theory We are going to spend a little time thinking about the basics of set theory. Although fundamental to the way we think and write mathematics today, surprisingly, formal set theory has only been around since the late 1800’s when Georg Cantor formulated the basic definitions and axioms. The most basic of these notions is that of set, which Cantor described simply as any collection of objects. But this quickly became problematic, giving rise for example, to Russell’s Paradox. In the early 1900’s, axiomatic set theory was developed, by Von Neumann and others, in an attempt to iron out some of the crinkles in early set theory. Recommended if you want to go beyond this subject: “Naive Set Theory” by P Halmos. See Wikipedia (ZF set theory) for the logic forms of these axioms. 69 Russell’s Paradox 70 In this subject, we will try to get to some understanding of sets, with a little logic as its foundation. The fundamental relation in set theory is that of belonging, written x ∈ A read “x belongs to A” or “x is contained in A” or “x is a member of A”. There are several ways to build up the mathematics of sets. Currently most mathematicians start with the ZFC axioms: Zermelo-Fraenkel axioms + axiom of choice.2 This is a list of ten axioms. To give you some idea of what is required to start building mathematics here is an informal list (for interest only): 2see Srivastava p12 if interested. 71 Axioms of Set Theory (simplified) 1. Existence. There exists a set. 2. Equality. Two set are the same (ie. equal) if they have the same elements. 3. Specification – defining subsets using conditions. 4. Pairing – For any two sets there exists a set that they both belong to. 5. Union – for any collection of sets there exists a set that contains all the elements that belong to at least one set in the collection. 6. Power set – for each set there exists a set that contains all its subsets. 7. Replacement – the range of a function defined on a set falls inside some set. 8. Inductive set – there exists a set A such that if x ∈ A then the set x ∪ {x} is also in A. Required to prove that a set like the natural numbers exists. 9. Foundation – required to prevent Russell’s paradox (there is no set of all sets). 10. Axiom of choice – from a collection of sets I can always choose one element from each to make a new set. 72 The primary thing we do is build new sets from given sets. First, in more detail, our most useful axiom: Axiom of Specification For every non-empty set E and every condition p(x) on its elements there is a set A which contains those elements of E for which p(x) is true. We write A = { x ∈ E : p(x) } Note: This is essentially saying certain subsets of E exist: those containing the elements of E for which p(x) is true. 73 Example 3.1 I If A is a set then the set {x ∈ A : x 6= x} exists (separation axiom). It is called the I {x ∈ R : x2 = 2} = I {x ∈ Z : x > 0} = I {x ∈ R : (x < 0) ∨ (x = 0) ∨ (x > 0)} = 74 Recall that the Axiom of Specification says that if p(x) is a condition on the elements of some set E then there always exists a set A which contains those elements of E for which p(x) is true. But what if p(x) is false for all elements of E? Definition 3.1 (Empty Set) We define the empty set (or nullset), denoted ∅, to be the set {x ∈ U : p(x)} where U is any set and p(x) is any condition that is false for all elements in U. The axiom of specification tells us such a set exists. 75 Relations between sets Definition 3.2 (Equality) Let A and B be sets. We say that A = B if A and B contain the same elements. Logic: A = B ⇔ ∀x ∈ U (x ∈ A ⇔ x ∈ B) Assuming some universal set U. Example 3.2 A = {1, 2},B = {1, 2},C = {1, 3} and U = {1, 2, 3, 4}. x x ∈ A x ∈ B x ∈ A⇔ x ∈ B 1 T T 2 T T 3 F F 4 F F x x ∈ A x ∈ C x ∈ A⇔ x ∈ C 1 T T 2 T F 3 F T 4 F F 76 Definition 3.3 (Subsets) Let A and B be sets. We say that A is a subset of B if every element of A is also an element of B. This is written A ⊆ B. Logic: A ⊆ B ⇔ ∀x ∈ U (x ∈ A⇒ x ∈ B) If A is a subset of B and there is an element of B which is not an element of A then we say A is a proper subset of B. Assuming some universal set U. Also useful for showing A is not a subset of B is the negation: A 6⊆ B ⇔ ∃x ∈ U s.t. (x ∈ A) ∧ (x 6∈ B) 77 Example 3.3 Let A = {1},B = {1, 2}, E = {1, 2, 3, 4} x x ∈ A x ∈ B (x ∈ A)⇒ (x ∈ B) (x ∈ B)⇒ (x ∈ A) 1 T T 2 F T 3 F F 4 F F 78 Theorem 3.1 Let A be a set. Then ∅ ⊆ A. Logic form: “Proof”. 79 Theorem 3.2 (Equality and Subsets) If A and B are sets then A = B if and only if A ⊆ B and B ⊆ A. Logic: A = B ⇔ (A ⊆ B) ∧ (B ⊆ A) How do we prove a biconditional statement? We use p ⇔ q ≡ (p ⇒ q) ∧ (q ⇒ p) and write two proofs: First the “Forward proof” showing (p ⇒ q) is true then the “Converse proof” showing (q ⇒ p) is true. Since (p ⇒ q) and (q ⇒ p) are both true so is p ⇔ q is true. This is a method of proof – justified by the logical equivalence. 80 Proof 81 82 New sets from old Given two known sets A and B we can define new sets in many ways. Definition 3.4 (Union) Let A and B be sets. We define the union of A and B, denoted A ∪ B, to be the set that contains all elements of A and all elements of B. A ∪ B = {x ∈ U : (x ∈ A) ∨ (x ∈ B)} Definition 3.5 (Intersection) Let A and B be sets. We define the intersection of A and B, denoted by A∩B, to be the set that contains only those elements of A which are also all elements of B. If A ∩ B = ∅ we say that A and B are disjoint. A ∩ B = {x ∈ U : (x ∈ A) ∧ (x ∈ B)} 83 Definition 3.6 (Complement) Let A and B be sets. We define the complement of B in A, denoted by A\B, to be the set that contains only those elements of A which are not elements of B. A \B = {x ∈ U : (x ∈ A) ∧ (x 6∈ B)} 84 Theorem 3.3 Let A,B and C be subsets of some set E . Then A \ (B ∪ C ) = (A \ B) ∩ (A \ C ). We usually prove set equality using Theorem 3.2 Proof. 85 86 More notation Definition 3.7 (Indexed Family) Let i be an element of some nonempty set I . If for each i ∈ I there is a corresponding set Ai , then A = {Ai : i ∈ I} is called an indexed family of sets and I is called an indexing set. The union of the elements in A is denoted by⋃ i∈I Ai and the intersection of the elements of I is denoted by ⋂ i∈I Ai . Similarly, if N = {Ni : i ∈ I} is set of objects Ni that can be multiplied (eg. real numbers, algebraic expressions etc.), then∏ i∈I Ni denotes the product (multiplication) of all the elements of N. 87 Example 3.4 88 Ordered Pairs and Cartesian Products Definition 3.8 (Ordered Pairs) Let A and B be sets. An ordered pair is an object (a, b) where a ∈ A and b ∈ B. Two ordered pairs (a, b) and (c , d) are equal iff a = c and b = d . Definition 3.9 (Cartesian Product) Given sets A and B, the Cartesian product of A and B, written A× B is the set of all ordered pairs: A× B = {(a, b) : a ∈ A and b ∈ B} Proposition 3.1 Let A be a set. If (a1, a2) ∈ A× A and a1 6= a2 then (a1, a2) 6= (a2, a1). 89 Rational Numbers Definition 3.10 (Rational Numbers) The set of rational numbers, denoted Q, is the set of ratios of integers, Q = { r s | r , s ∈ Z, s 6= 0 } We will investigate below the way in which the real numbers can be constructed from the rationals. Aside: A rational number is actually an equivalence class of ordered pairs of integers (k, l), l 6= 0. Two pairs (m, n) and (k , l) represent the same rational number iff ml = nk. Addition and multiplication of rational numbers is defined as (k, l) + (m, n) = (kn + lm, ln) (k , l) · (m, n) = (km, ln) 90 Example 3.5 There is no rational number q satisfying q2 = 2 91 92 Example 3.6 Let A and B be subsets of Q given by A = {q ∈ Q : q < 0 or q2 < 2} B = {q ∈ Q : q > 0 and q2 > 2} Then A contains no largest element and B contains no smallest element. 93 Ordered sets and bounds You are familiar with many basic properties properties of the real numbers. We want to build up a list of properties that uniquely determine the real number system and see how they are related to Q. A familiar property of Q and R is that they are ‘ordered’. Definition 3.11 (ordered set) Let S be a set. An order on S is a relation, denoted < , satisfying 1. If x ∈ S and y ∈ S , then exactly one of the following holds: x < y x = y y < x 2. If x , y , z ∈ S satisfy x < y and y < z , then x < z An ordered set is a set equipped with an order. The notation x ≤ y is used to mean that x < y or x = y . We sometimes write y > x in place of x < y . 94 Example 3.7 The set Q of rational numbers equipped with the usual order (in which x < y is defined to mean that y − x is positive) is an ordered set. Definition 3.12 (bounded above) Let S be an ordered set and A ⊆ S a subset. If there exists β ∈ S such that ∀x ∈ A, x ≤ β then we say that A is bounded above and call β an upper bound for A. Example 3.8 The set A from Example 3.6 is bounded above and any element of B is an upper bound for A. 95 Definition 3.13 (least upper bound) Let S be an ordered set and A ⊆ S a subset that is bounded above. An element α ∈ S is called a least upper bound (or supremum) of A if it has the following properties: 1. α is an upper bound for A 2. If γ is an upper bound for A, then α ≤ γ It is clear from the definition that there can be at most one least upper bound for a given set A. We denote it by supA. Example 3.9 1. {q ∈ Q : q ≤ 12} ⊆ Q has least upper bound 12 2. {q ∈ Q : q < 12} ⊆ Q has least upper bound 12 3. The set A ⊆ Q as in Example 3.6 is bounded above but has no least upper bound 96 The defintions of lower bound and greatest lower bound (or infimum) are defined in exactly the same manner, but with ≤ replaced by ≥. Definition 3.14 Let S be an ordered set and A ⊆ S a subset. If there exists β ∈ S such that ∀x ∈ A, x ≥ β then we say that A is bounded below and call β a lower bound for A. An element α ∈ S is called a greatest lower bound (or infimum) of A if it has the following properties: 1. α is a lower bound for A 2. If γ is a lower bound for A, then α ≥ γ It is clear from the definition that there can be at most one greatest lower bound for a given set A. We denote it by inf A. 97 Example 3.10 1. E = { 1n : n = 1, 2, 3, . . . } ⊂ Q is bounded above and bounded below. We have supE = 1 and inf E = 0. Notice that, in this example, the infimum is not itself an element of E . 2. The set B ⊆ Q of Example 3.6 is bounded below but has no greatest lower bound 98 Definition 3.15 An ordered set S is said to have the least-upper-bound property if the following holds: If A ⊆ S is not empty and is bounded above, then A has a least upper bound in S . We have seen in the examples above that Q does not have the least-upper-bound property. 99 Fields Definition 3.16 (Field) A field is a set F equipped with two binary operations called addition (denoted +) and multiplication (denoted using × or simply by concatenation) that satisfy the following axioms (A1– A5, M1–M5, D): Field axioms for addition (A1) ∀x , y ∈ F , x + y ∈ F (closure) (A2) ∀x , y ∈ F , x + y = y + x (commutivity) (A3) ∀x , y , z ∈ F , (x + y) + z = x + (y + z) (associativity) (A4) ∃0 ∈ F ,∀x ∈ F , x + 0 = x (additive identity) (A5) ∀x ∈ F ,∃ y ∈ F , x + y = 0 (additive inverse) 100 Definition (Field, continued) Field axioms for multiplication (M1) ∀x , y ∈ F , xy ∈ F (closure) (M2) ∀x , y ∈ F , xy = yx (commutivity) (M3) ∀x , y , z ∈ F , (xy)z = x(yz) (associativity) (M4) ∃1 ∈ F \ {0}, (∀x ∈ F , 1x = x) (multiplicative identity) (M5) ∀x ∈ F \ {0}, (∃y ∈ F , s.t. xy = 1) (multiplicative inverse) Distributive law (D) ∀x , y , z ∈ F , x(y + z) = xy + xz Example 3.11 1. Q equipped with the usual operations (defined above) forms a field. 2. Z (with the usual operations) is not a field. 101 Definition 3.17 (Ordered Field) An ordered field is a field F that is also an ordered set and satisfies: 1. ∀x , y , z ∈ F , (y < z ⇒ x + y < x + z) 2. ∀x , y ∈ F , ((x > 0) ∧ (y > 0)⇒ xy > 0) Example 3.12 Q is an ordered field 102 The real field We have seen that Q is an ordered field but does not have the least-upper-bound property. Theorem 3.4 There exists an ordered field R that has the least-upper-bound property. Moreover, R contains Q as a subfield. The proof of this theorem constructs R from Q using ‘Dedekind cuts’. In fact, R is the unique field that satisfies the axioms of an ordered field having the least-upper-bound property. 103 Axioms for the reals The real numbers R consist of a set equipped with two binary operations called addition (+) and multiplication (×), and a relation < that satisfy the following axioms (A1– A5, M1–M5, D,O1,O2,AO,MO,C): (A1) ∀x , y ∈ R, x + y ∈ R (closure) (A2) ∀x , y ∈ R, x + y = y + x (commutivity) (A3) ∀x , y , z ∈ R, (x + y) + z = x + (y + z) (associativity) (A4) ∃0 ∈ R,∀x ∈ R, x + 0 = x (additive identity) (A5) ∀x ∈ R,∃ y ∈ R, x + y = 0 (additive inverse) (M1) ∀x , y ∈ R, xy ∈ R (closure) (M2) ∀x , y ∈ R, xy = yx (commutivity) (M3) ∀x , y , z ∈ R, (xy)z = x(yz) (associativity) (M4) ∃1 ∈ R \ {0}, (∀x ∈ R, 1x = x) (multiplicative identity) (M5) ∀x ∈ F \ {0}, (∃y ∈ F , s.t. xy = 1) (multiplicative inverse) 104 (D) ∀x , y , z ∈ R, x(y + z) = xy + xz (distributivity) (O1) ∀x , y ∈ R exactly one of the following hold: x < y , x = y , y < x (O2) ∀x , y , z ∈ R, (x < y ∧ y < z)⇒ x < z (AO) ∀x , y , z ∈ R, (y < z ⇒ x + y < x + z) (MO ∀x , y ∈ R, (0 < x) ∧ (0 < y)⇒ 0 < xy (C) Every non-empty subset of R that is bounded above has a least upper bound. 105 Dedekind Cuts Definition A subset A ⊆ Q is called a cut if it satisfies the following: 1. A 6= ∅ and A 6= Q 2. ∀a, b ∈ Q, (a ∈ A) ∧ (b < a)⇒ (b ∈ A) 3. ∀a ∈ A ∃b ∈ A, a < b Example 3.13 A√2 = {q ∈ Q | a < 0 ∨ a2 < 2} A2 = {q ∈ Q | q < 2} Let R = {A ⊂ Q | A is a cut}. Our goal is to define an order on R and operations (+ and ×) in such a way that R satisfies all the axioms for R. 106 Defining an order on R Each element of R is a subset of Q, so we can ask if one is a subset of another. We define an order on R by declaring that A < B precisely when A ( B. Of course, we then need to check that this does gives an order on R. (i.e., that axioms O1 and O2 are satisfied.) Exercise Check that O1 and O2 are satisfied. Example 3.14 With A√2 and A2 as above, we have A√2 < A2 since a ∈ A√2 ⇒ (a < 0) ∨ (a2 < 2)⇒ a < 2⇒ a ∈ A2 107 R has the least upper bound property Claim The ordered set R satisfies axiom C (the completeness axiom). Let E ⊆ R and suppose that E is bounded above by some element B ∈ R. Define α ⊂ Q by α = ⋃ A∈E A Then α is a cut, and is the least upper bound of E . To see that α is an upper bound for E note that: A ∈ E ⇒ A ⊆ ⋃ A∈E A⇒ A ≤ α It is the least upper bound because: β an upper bound ⇒ ∀A ∈ E ,A ⊆ β ⇒ ⋃ A∈E A ⊆ β ⇒ α ≤ β 108 Addition in R We define addition on R as follows A + B = {a + b | a ∈ A, b ∈ B} Exercise Show that A + B is a cut (given that A and B are cuts). Let 0R be the cut given by 0R = {q ∈ Q | q < 0} Exercise Show that 0R is the addition identity in R, and that the additive inverse of A ∈ R is given by −A = {q − a | q ∈ Q, q < 0, q ∈ Q \ A} 109 Multiplication in R Defining multiplication is a little more involved. We first define it for A,B ∈ R satisfying 0R ≤ A and 0R ≤ B A× B = {ab | a ∈ A, b ∈ B, 0 ≤ a, 0 ≤ b} ∪ {q ∈ Q | q < 0} Example 3.15 Noting that 0 ≤ A√2, we have A√2 × A√2 = {ab | (a < 0 ∨ a2 < 2) ∧ (0 ≤ a) ∧ (b < 0 ∨ b2 < 2) ∧ (0 ≤ b)} ∪ {q ∈ Q | q < 0} = {ab | (a2 < 2) ∧ (0 ≤ a) ∧ (b2 < 2) ∧ (0 ≤ b)} ∪ {q ∈ Q | q < 0} = {q ∈ Q | (q < 2) ∧ (0 ≤ q)} ∪ {q ∈ Q | q < 0} = A2 110 To define A× B when one or both of A and B are less than 0R, we can use the definitions already given to define A× B = −(A× (−B)) if 0R ≤ A and B < 0R A× B = (−A)× (−B) if A < 0R and B < 0R It is possible to show that R with the operations defined above satisfies all the axioms listed required for R. 111 Positive and negative numbers Notation: I The set R+ = {x ∈ R : 0 < x} is called the set of positive real numbers. I The set R− = {x ∈ R : x < 0} is called the set of negative real numbers. I Note, zero is in neither of these sets. I Less common is the notation: R+0 = R+ ∪ {0} and R−0 = R− ∪ {0}. 112 Addition and Cancellation Theorem 3.5 (Addition and Cancellation) ∀a, b, c ∈ R, (a = b) ⇔ (a + c = b + c). 113 114 Inequalities Theorem 3.6 ∀x ∈ R, (0 < x)⇒ (−x < 0). 115 116 Absolute value and inequalities The absolute value will be used extensively in the subject so we need to know how to use it in proofs. It is an example of a situation where it may be easier to prove a “p ⇒ q” theorem by special cases rather than all cases at once. Definition 3.18 The modulus or absolute value of x ∈ R, denoted |x |, is defined as |x | = { x , if x ≥ 0 −x , if x < 0. Geometrically, |x | is the distance from x to the origin on the real line. 117 The following theorem gives us a way of avoiding using |x | in some cases (or vice versa). Theorem 3.7 (Absolute-Interval) Let x ∈ R and a ∈ R+. Then |x | ≤ a if and only if −a ≤ x ≤ a. 118 119 The following of results are useful when using absolute value in proofs. Theorem 3.8 1. ∀x ∈ R 0 ≤ |x | 2. ∀x ∈ R x ≤ |x | 3. ∀x ∈ R − x ≤ |x | 120 The triangle inequality Another useful result about inequalities (which you should remember from Linear Algebra) is: Theorem 3.9 (Triangle Inequality) ∀x , y ∈ R |x + y | ≤ |x |+ |y | Corollary 3.1 (reverse triangle inequality) ∀x , y ∈ R ∣∣|x | − |y |∣∣ ≤ |x − y | 121 122 Bounded sets in R Geometrically, we would expect that any number bigger than an upper bound, is also an upper bound of the set E . Theorem 3.10 Let s, t ∈ R and E ⊆ R. If s is an upper bound of E and s < t then t is an upper bound of E . Proof: 123 How do we show w is not an upper bound of E ⊆ R? Proposition 3.2 (Not an Upper Bound) Let w ∈ R and E ⊆ R. Then w is not an upper bound of E if and only if there exists x ∈ E such that x > w . Thus to prove a number, w , is not an upper bound of a subset, we need to find at least one number in the subset that is greater than w . 124 Definition 3.19 (i) If a < b then the subset [a, b] = {x ∈ R : a ≤ x ≤ b} is called a closed interval. (ii) If a < b then the subset (a, b) = {x ∈ R : a < x < b} is called an open interval. Note that: the intervals [a, b) = {x ∈ R : a ≤ x < b} and (a, b] = {x ∈ R : a < x ≤ b} are neither open nor closed. Both of the sets [a, b] and (a, b) are bounded above, however there is a fundamental difference between them. 125 126 Question Does there exist s ∈ (a, b) such that s is an upper bound of (a, b)? More generally, do all subsets E which are bounded above contain an upper bound of themselves? To answer this we will need the following theorem: Theorem 3.11 ∀x , y ∈ R x < y ⇒ x < x + y 2 < y . Geometrically: This theorem states that between any two real numbers, there exists at least one other real number. Note: This statement is also true in Q but not in Z! 127 Proof: 128 Proposition 3.3 Let w ∈ R. Then w is an upper bound of (a, b) if and only if w ≥ b. Thus the subset (a, b) does not contain an upper bound of itself. Proof: 129 130 Exercise 1. Let s, t ∈ R. If s is a lower bound of E and t < s then t is a lower bound of E . 2. If a, b ∈ R with a < b, then a is a lower bound of (a, b) 3. If a, b ∈ R with a < b, then a is a lower bound of [a, b] 4. ∀s ∈ R (s is not a lower bound of E ) ⇔ ∃w ∈ E s.t. w < s Note: a /∈ (a, b) and a ∈ [a, b]. 131 We now combine the idea of upper and lower bounds: Definition 3.20 (Bounded) If E ⊆ R and E is bounded above and below, we say that E is a bounded set. If E is not bounded it is called an unbounded set. The subsets R+ and R− are important examples of unbounded subsets. Proposition 3.4 1. R = R− ∪ {0} ∪ R+. 2. If x ∈ R− and y ∈ R+ then x < y . Proof: - exercise - 132 Recall that b is an upper bound of (a, b) and [a, b] but b /∈ (a, b) and b ∈ [a, b]. The situation in which a set contains its upper bound is special. Definition 3.21 (Greatest element) Let E ⊆ R. If γ ∈ E and γ is an upper bound of E , then γ is called the greatest element of E . Definition 3.22 (Least element) Let E ⊆ R. If λ ∈ E and λ is a lower bound of E , then λ is called the least element of E . 133 Example 3.16 E1 = {1, 2, 3, 4} Note: The greatest element and least element, if they exist, are unique. That is, a set can have at most one greatest element and can have at most one least element. 134 Example 3.17 E2 = (a, b) Example 3.18 E3 = [a, b] 135 Example 3.19 E4 = { −1 n : n ∈ N } 136 Summary: Subset Least Element Greatest Element So, some subsets have greatest elements or least elements and some don’t. However, consider the following two subsets: Definition 3.23 (Set of Upper/Lower bounds) Let E ⊆ R. UE = {x ∈ R : x is an upper bound of E} LE = {x ∈ R : x is a lower bound of E} 137 That every nonempty subset of R that is bounded above (below) has a supremum (infimum) is ensured by the least-upper-bound property. This is sometimes referred to as the completeness axiom and stated in the following form: Axiom (Completeness). Let E be a non-empty subset of R. Every non-empty set of upper bounds of E has a least element. 138 The following result is sometimes useful when establishing suprema. Proposition 3.5 γ is the supremum of the set E if and only if for any > 0 no element of E is greater than γ + and there is an element of E greater than γ − . Logic: γ = supE ⇔ ∀ > 0 ((∀x ∈ E x ≤ γ + ) ∧ (∃x ∈ E s.t. x > γ − )) 139 Example: If A = {− 1n s.t. n ∈ N} then supA = 0. 140 Since we expect to add two real numbers to get another real, or multiply two reals to get a real, we should be able to add and multiply sup’s to get new sup’s (since all reals are sup’s of some set). In fact sup’s should satisfy all the axioms of reals. How adding sup’s works is seen from the following theorem: Theorem 3.12 (Sup Addition) Let A and B be nonempty subsets of R and C = {x + y ∈ R : x ∈ A and y ∈ B}. If A and B have suprema, then C has a supremum and supC = supA + supB. 141 Proof: 142 Mathematical Induction We now consider our last method of proof – Induction. Denote the set of positive integers by N = {1, 2, 3 . . .}. Suppose p(n) is a condition on n ∈ N and that we wish to prove theorems such as ∀n ∈ N, p(n). That is, we want to prove that p(n) is true for all n ∈ N. For example, 1. p(n) : 1 + 2 + 3 + . . .+ n = 12n(n + 1) 2. p(n) : 2n > n 3. p(n) : (1 + x)n ≥ 1 + nx , x ∈ R, x > −1 To do this we use the Principle of Mathematical Induction. 143 Mathematical Induction The following inference rule allows us to replace showing p(n) is true (for all n) with showing a conditional, p(n)⇒ p(n + 1) is true (for all n) – generally much easier. Theorem 3.13 (Principle of Mathematical Induction) If p(n), n ∈ N are statements such that: I p(1) is true, and I ∀k ∈ N (p(k)⇒ p(k + 1)) is true then, ∀n ∈ N p(n) is true This means that all the statements p(1), p(2), . . . are true. The proof relies on the well ordering, or least element, property of N. 144 Theorem 3.14 Any non-empty subset of the natural numbers has a least element. We use this theorem to prove Theorem 3.13. Given a proposition P(n), let S = {n ∈ N | P(n) is false}. If we can prove S is empty, then we have proven P(n) is true for all n ∈ N. If P(1) is true then S is not all of N. If S is non-empty then it possesses a least element m, say. Thus m − 1 /∈ S so P(m − 1) is true. If we know P(k)⇒ P(k + 1) then P(m − 1) is true implies P(m) is true, but this contradicts m ∈ S! We conclude that S has no least element, hence it is empty. 145 To use Theorem 3.13, we need to I Show p(1) is true. I Show that, if we assume p(k) true then we can deduce p(k + 1) is true. I Then, the deduction principle tells us that p(k)⇒ p(k + 1) is true. I Then the Induction principle tells us that p(1), p(2), . . . are all true 146 Example 3.20 p(n) : 1 + 2 + 3 + . . .+ n = 12n(n + 1) 147 Example 3.21 p(n) : 2n > n 148 149 150 Generalisations Some more general forms of induction exist. I Shift from n ≥ 1 to n ≥ −m (m > 0); that is, p(−4), p(−3), p(−2), . . .. Show p(−4) is true then p(k)⇒ p(k + 1) I Another form of induction (Strong Mathematical Induction) allows you to assume all of p(k), p(k + 1), . . . p(n) are true in order to prove p(n + 1) I Show p(k) is true for k ≤ n ∈ N I Show p(k), p(k + 1), . . . p(n)⇒ p(n + 1) I Conclude p(n) is true for all integers n ≥ k . 151 The Archimedean Property An important consequence of the Completeness Axiom is called the Archimedean Property. Theorem 3.15 (Archimedean Property – Form I) The set N of natural numbers is unbounded above in R Proof. 152 153 The two other theorems equivalent to the Archimedean Property are: Theorem 3.16 (Archimedean Property – Form II) If x ∈ R+ then ∃n ∈ N s.t. n − 1 < x ≤ n This gives us the picture that their is always an integer to the left and to the right of any real number. Theorem 3.17 (Archimedean Property - Form III) If x , y ∈ R+ then ∃n ∈ N s.t. y < nx This is usually paraphrased as: “No matter how small a measuring stick it is always possible to place it end-to-end to extend beyond any distance”. 154 Density of the Rationals Theorem 3.18 If x and y are real numbers with x < y , then there exists a rational number r such that x < r < y . Proof. 155 An easy consequence of Theorem 3.18 tells us that we can also find an irrational number between any two reals. This means that wherever you look along the real line - every interval, no matter how small, contains a rational number and an irrational number. 156 Functions Recall the informal definition of a function: A function (or map) f : A→ B from the set A, called the domain, to the set B called the codomain, is a “rule” that assigns to every x ∈ A, a unique element y ∈ B, called the image of x . The subset of all images is called the range of f . Example 4.1 157 This informal definition is not quite precise enough for our purposes, since the question of when something is, or isn’t, a rule is not easy to answer. To help us get a handle on the precise idea of a function, we use the concept of a relation. Definition 4.1 (Relation) A relation R between two sets A and B, is a subset of the Cartesian product A× B. Thus the “rule” is defined by the pairs. Example 4.2 158 Definition 4.2 (Function) A function f : A→ B is a triple (A,B, f ), where f ⊆ A× B is a relation, such that 1. if (x , y1) ∈ f and (x , y2) ∈ f then y1 = y2, 2. if x ∈ A then ∃z ∈ B such that (x , z) ∈ f . 159 Example 4.3 If A = {−1, 0, 1}, B = {T ,F} then 160 Special types of functions Injective: Surjective: Bijective: We will discuss functions again later in the subject. For now we are interested in functions with domain A = N. 161 Sequences Consider a function whose domain is N (or sometimes a subset of N). 162 Definition 4.3 (Sequence) A sequence is a function f : N→ B (usually B = R) and is written f (1), f (2), f (3), . . . or f1, f2, f3, . . . or {fn} or {fn}n≥1, or (fn) or (fn)n≥1, where the image of n, f (n), is called the nth term of f. 163 Convergence of Sequences In real analysis we are mostly interested in how the terms of a sequence approximate some real number, L. Question: As n gets larger are the terms fn a better approximation to L than previous terms? Think of decimal approximations to pi. Terminating the expansion gives a rational number: f1 = 3.1, f2 = 3.14, f3 = 3.142, f4 = 3.1416, f5 = 3.14159, . . . or f1 = 31 10 , f2 = 314 100 , f3 = 3142 1000 , f4 = 31416 10000 , . . . Is each successive rational a better approximation to pi? Those that do we will end up calling: convergent 164 Possible long-term behaviours of a sequence 165 Definition of Convergence of a Sequence Definition 4.4 (Sequence Limit) Let L ∈ R and f : N→ R (denoted n 7→ fn) be a sequence. We say that L is the limit of the sequence fn, if for all > 0 there exists an M ∈ N such that for all n > M, we have |fn − L| < This is written lim n→∞ fn = L If so, we say that the sequence fn converges to L 166 If we write this using logic symbols, we have ∀ > 0 ∃M ∈ N s.t. ∀n > M, |fn − L| < Thinking geometrically, this says: fn converges to L if: 1. for any distance > 0 we choose, 2. we can always find an M ∈ N, 3. such that for all n > M, 4. the distance of every fn to L is smaller than . 167 Definition 4.5 (Sequence Convergence) If there is some L such that lim n→∞ = L (i.e., if such an L exists) then we say that the sequence fn converges. If there is no such L then we say that the sequence fn diverges. 168 For the previous example, fn = 1− 1/n: Question: Given > 0 what value of M do we need? 169 The previous calculation gives us a candidate for M (which depends on ). We now need to prove that it “does the job”, that is, it will enable us to prove that ∀ > 0 (∃M ∈ N s.t. (∀n > M, |fn − L| < )) is true? Proof 170 Note the following notation: I The phrase “For all > 0 p()” will be written: ∀ > 0 p() where p() is some condition on n. This is an abbreviation for the logic statement: ∀ ∈ R+ p(). I Similarly, the phrase “For all n > M p(n)” will be written: ∀n > M p(n) where p(n) is some condition on n. This is an abbreviation for the logic statement: ∀n ∈ {M + 1,M + 2, . . .} p(n) 171 Example 4.4 f : N→ R, fn = 2 n − 1 2n 172 173 174 Example 4.5 g : N→ R, gn = 1 + (−1 2 )n 175 176 177 Note: Not all sequences behave like fn and gn ie. “get closer to some number”. Example 4.6 an = (−1)n 178 Luckily the proof that a sequence converges to L is almost always of the same form. We have a simple template: 179 The integer M does not have to be the smallest integer that works. The difficult part is finding M (which depends on ) and then filling in the middle. Usually this is done before writing the proof. In the proof you have to work out how to get from your already computed M to |fn − L| < . Sometimes the previous calculation can be “reversed”. Other times a different route is required. 180 For proofs about convergence of sequences, we often need to use the ceiling function. Definition 4.6 (Ceiling) Let x ∈ R. We define the ceiling of x , dxe, to be the smallest integer greater than or equal to x . Equivalently, dxe = inf{k ∈ Z : x ≤ k}. Geometrically dxe it is the closest integer to the right (or equal to) of x . Note, inf is only defined for non-empty sets. The fact that {k ∈ Z : x ≤ k} is non-empty is a consequence of the Archimedean Property (Form II). Example 4.7 181 Example 4.8 Show that the sequence ( n 2n + 1 ) n∈N converges to 12 . 182 183 184 Example 4.9 For the sequence fn = 1 n2 + 6n + 4 which converges to L ∈ R, find an M ∈ N such that, if > 0, and n ∈ N with n > M, then |fn − L| < . 185 186 187 188 Chain of inequalities Chain of inequalities to simplify expressions. 189 Notes: I Most books use “N” in place of “M”, in which case the proof of the existence of a limit is called an “− N proof”. I Many books use a “challenge-response” explanation of the idea convergence. Consider a two player game: Player A chooses any > 0 and then challenges player B to find a natural number M such that (∀n > M), |fn − L| < . If player B can do this for any > 0 then B wins and L is the limit of the sequence. 190 Written as a proof, player B needs M() – hence producing an M for any > 0 – and also needs the calculation starting from M() and showing that |fn − L| is indeed less than for all n > M. The proof shows that no matter what > 0 is, for the subset M = {n ∈ N : n > M} it is true that there exists an L ∈ R such that |fn − L| < . Note: This approach appears to put time into the proof ie. if the the challenge-response goes on “forever” then the theorem is proved - this is not the case. The logic statement only requires showing existence of integer (M) for every positive real number () such that a certain condition is satisfied (|fn − L| < ) - this has nothing to do with some process going on forever. 191 Divergent Sequences To show that (fn) does not converge to L, we need to show that ∼ [ lim n→∞ fn = L ] is true. That is, ∼ [∀ > 0 (∃M ∈ N s.t. (∀n > M, |fn − L| < ))] (2) ≡ ∃ > 0 s.t. (∀M ∈ N (∃n > M, s.t. |fn − L| ≥ )) (3) This is equivalent to saying that: we can find an example of > 0 so that, for any M ∈ N, we can always find some n > M such that |fn − L| ≥ . 192 Note: I We only need to find one such > 0, since the statement is now a “there exists” statement. I We only need to find one term (ie. there exists n) such that |fn − L| ≥ , for some n > M. Example 4.10 Show that (−1)n does not converge to L = 1. Proof: 193 Example 4.11 Show that 1n does not converge to L = 1, but it does converge to L = 0. Proof: 194 Not convergent Beware the distinction between “not convergent to L” and “not convergent”. To prove (fn) is not convergent, we need to prove that, for any L ∈ R, lim n→∞ fn 6= L. This can usually be done by cases on L: choose ranges of L where lim n→∞ fn 6= L is easier to prove. 195 There is a theorem for proving divergence that generally gives a simpler proofs. To use the theorem we need the idea of “subsequences”. A subsequence of the sequence {fn}n≥1 is a sequence fn1 , fn2 , fn3 , fn4 , . . . where n1 < n2 < n3 < . . . ie. pick a subset (without changing the order) of the terms of {fn}n≥1. The subsequence is usually written in the form {fnk}k≥1. Example 4.12 The following are subsequences of {1/n}: Theorem 4.1 (Divergence Criteria for Sequences) A sequence {fn}n≥1 is divergent if any of the following hold: 1. {fn}n≥1 has two subsequences {fnk}k≥1 and {fnp}p≥1 that converge to two different limits. 2. {fn}n≥1 has a subsequence that is divergent. 3. {fn}n≥1 is unbounded. 196 Example 4.13 The sequence fn = (−1)n is divergent. Proof: 197 Special Types of Sequences For certain types of sequences we do not need full −M proofs to show convergence. Definition 4.7 The following sequences are called monotonic sequences. A sequence (fn) is: I Increasing if: ∀n ∈ N fn+1 > fn I Non-Decreasing if: ∀n ∈ N fn+1 ≥ fn I Decreasing if: ∀n ∈ N fn+1 < fn I Non-Increasing if: ∀n ∈ N fn+1 ≤ fn 198 Example 4.14 199 200 Bounded Sequences Definition 4.8 ((Un)Bounded Above) I A sequence (fn) is bounded above if there exists an s ∈ R such that for all n ∈ N, fn ≤ s. I A sequence (fn) is unbounded above if no such s exists. Similarly, Definition 4.9 ((Un)Bounded Below) I A sequence (fn) is bounded below if there exists an s ∈ R such that for all n ∈ N, fn ≥ s. I A sequence (fn) is unbounded below if no such s exists. Note it can be proved (do it as an exercise) that unbounded sequences do not converge and so sometimes also called divergent. 201 Definition 4.10 (Bounded) A sequence is called bounded if it is both bounded above and bounded below. Example 4.15 Prove that the sequence (2n) is not bounded. Proof: 202 203 Combining the ideas of bounded and monotonic gives a very useful theorem: Theorem 4.2 (Non-decreasing and convergence) Let (fn) be a non-decreasing sequence. If (fn) is bounded above, then it is convergent. Note: This theorem tells us that (fn) has a limit, but not what that limit is. (The limit is actually supA, where A is a set containing all the terms of (fn)). 204 205 206 There is a similar theorem for non-increasing, bounded below sequences. When we combine the two, we get: Theorem 4.3 (Bounded monotonic sequence) Every bounded, monotonic sequence is convergent. To use this theorem we need to show: I The sequence is bounded above. I The sequence is bounded below. I The sequence is monotonic. If Lu and Ll are the upper and lower bounds, then Ll ≤ lim fn ≤ Lu that is, the bounds give an estimate of the limit. The better the bounds, the better the estimate. 207 Algebra of Limits Now that we have precise definitions of convergence, we can prove some limit laws. Theorem 4.4 If fn → α and gn → β then: 1. (fn + gn)→ α + β. 2. (fn · gn)→ α · β. 3. fn gn → α β , for β 6= 0. 4. k · fn → k · α, for any k ∈ R. 208 Many of these (and other) algebra theorems use the following: Recall “∀ > 0” is an abbreviation for “∀ ∈ R+”. It does not matter how the elements of R+ are “represented” so long as they give all of R+. This allows us to change the to some other function, g(), so long as the following condition holds: {g() : > 0} = R+ Examples of valid functions: 1. g1() = /2 2. g2() = 2 3. g3() = log(+ 1) Examples of invalid functions: 1. g4() = 1 + 2. g5() = 2 − 1 3. g6() = log() If g() is valid then we get logical equivalence. For example, all the statements below are logically equivalent. 1. ∀ > 0 ∃M ∈ N s.t. ∀n > M |fn − L| < 2. ∀ > 0 ∃M ∈ N s.t. ∀n > M |fn − L| < /2 3. ∀ > 0 ∃M ∈ N s.t. ∀n > M |fn − L| < 2 In the above three examples |fn − L| still has to be less than some positive real number. What will in general change is M(). 209 Proof of (fn + gn)→ α + β 210 211 The downside of the convergence definition is that you need to know the limit. Can we get around this for an arbitrary (convergent) sequence? Geometrically, we have This suggests that if (fn) converges, then |fn − fm| → 0. What we would like is the converse: “if |fn − fm| → 0 then (fn) converges”. 212 Cauchy Sequences Definition 4.11 (Cauchy Sequence) A sequence fn of real numbers is called a Cauchy Sequence if for each ε > 0 there exists an M ∈ N such that whenever n,m > M we have |fn − fm| < ε. Example 4.16 213 Lemma 4.1 (Convergent-Cauchy) Every convergent sequence is a Cauchy sequence. Proof. 214 Theorem 4.5 (Cauchy-Bounded) Every Cauchy sequence is bounded. Proof: Omitted - it’s rather long – see just about any real analysis text book. 215 Cauchy’s Convergence Criterion Theorem 4.6 (Cauchy’s Convergence Criterion) A sequence (fn) converges if and only if for every > 0 there exists M ∈ N such that for all n,m > M, |fn − fm| < . This is known as Cauchy’s Convergence Criterion. Proof: 216 Limit Points We now generalise the idea of a point γ being supE . Definition 5.1 (Limit Points) Let E ⊆ R and ` ∈ R. Then ` is called a limit point of E if, given any real number δ > 0 there is a point x ∈ E such that 0 < |x − `| < δ. Logic: (` a limit point of E ) ⇔ ∀δ > 0 ∃x ∈ E s.t. 0 < |x − `| < δ Note that: 1. The condition 0 < |x − `| excludes x = `. 2. E may or may not contain the limit point. 3. Limit points are also called accumulation points or cluster points in some books. 217 218 Example 5.1 If E = { x ∈ R : sin ( 1x ) = ±1} then ` = 0 is a limit point of E (and 0 /∈ E ). 219 220 Definition 5.2 (Deleted neighbourhood) Let ` ∈ R and δ > 0. The set defined as N0(`, δ) = {x ∈ R : 0 < |x − l | < δ} is called a deleted neighbourhood of `. 221 We can extend Definition 5.1 to allow ±∞ to be limit points. Definition 5.3 (Limit point at Infinity) Let E ⊆ R. Then if, given any α > 0, there is an element x ∈ E such that x > α, we say that E has a limit point at ∞ (or if x < α, E has a limit point at −∞). This is equivalent to saying that E is unbounded above (respectively unbounded below). Note that; 1. “±∞” are not elements of R, but are limit points of R. 2. The only limit point of N is ∞. 222 Continuous Functions We would like to generalise the idea of convergence of sequences to convergence of functions to some limit L. That is, we will think about functions with domain E ⊆ R where E is not N. This means we want to know what happens to f (x) as x gets close to some point `. 1. n→∞ becomes x → ` ∈ R. 2. fn → L becomes f (x)→ L. 223 Similarly for functions 1. ` is not generally in E , 2. f may not be defined at x = ` . So we would like to define f → L without assuming that ` is in the domain of f . This requires us to think about what “gets close to” means. • ` /∈ E requires us to define the deleted neighbourhood. • f not defined at x = ` will be avoided by using |f (x)− L| < ε with x 6= `. 224 Example 5.2 225 We can now generalise the idea of sequence limits to function limits: Definition 5.4 (Limits of Functions) Let f be the function f : E → R. Let ` be a limit point of E and f be defined on a deleted neighbourhood of ` (that is, N0(`, δ) ⊆ E ). We say that the limit of f as x tends to ` is L ∈ R, if: for any > 0 there is a δ > 0 such that for all x satisfying 0 < |x − l | < δ we have that |f (x)− L| < . We write this as lim x→` f = L or f → L as x → `. We also say that f converges to L as x tends to `. Logic Form: ∀ > 0 (∃δ > 0 s.t. (∀x ∈ E (0 < |x − `| < δ ⇒ |f (x)− L| < ) )) . 226 To motivate the conditional (0 < |x − `| < δ) ⇒ (|f (x)− L| < ) consider the following example: f : R \ {2} → R ; f (x) = x 2 − 4 x − 2 . How does the value of f (x) change as the value of x gets closer to x = 2? 227 228 Logic Form: ∀ > 0 (∃δ > 0 s.t. (∀x ∈ E (0 < |x − `| < δ ⇒ |f (x)− L| < ) )) . It might be easier to read when written in the form: ∀ > 0 ∃δ > 0 s.t. ∀x ∈ E p(x , δ, ) where p(x , δ, ) : (0 < |x − `| < δ) ⇒ (|f (x)− L| < ). Thus: for every > 0 we need to show there exists a δ > 0 such that p(x , δ, ) is true. p(x , δ, ) is true if: whenever x is in the deleted neighbourhood, (ie. 0 < |x − `| < δ) it is the case that f (x) is within the strip (ie. |f (x)− L| < ). 229 Recall the logical equivalence: If A ⊂ B then, ∀x ∈ B (x ∈ A⇒ p(x)) ≡ ∀x ∈ A p(x) . This enables us to rewrite the limit definition as ∀ > 0 ( ∃δ > 0 s.t. (∀x ∈ N0(`, δ) |f (x)− L| < ) )) where N0(`, δ) is the subset 0 < |x − `| < δ. This form of the logic then reads as: For every > 0 we need to show there exists a δ > 0 such that for every x in the deleted neighbourhood it is the case that |f (x)− L| < . 230 Notes: I f is never evaluated at x = ` so it does not matter if ` /∈ E . I N0(`, δ) ⊆ E is a strong restriction on the domain of E . I The definition requires ` ∈ R but can be extended to allow for limit points at ±∞. I We specify first and then find the deleted neighbourhood of ` such that f (x) is always within of L. 231 Note the similarity with the −M convergence definition: 232 I Thus a proof that f → L as x → ` has a very similar template to the one we used for sequences. I Before the proof (in the strategy section) we use |f (x)− L| < to find a suitable δ(). That is, we start with |f (x)− L| < and try to get to 0 < |x − l | < δ(). I In the proof we start with 0 < |x − l | < δ() and try to get to |f (x)− L| < . Proof Template: 233 Geometrically we have the picture: 234 Example 5.3 If f : R→ R, x 7→ x2, prove that lim x→2 f (x) = 4 235 We will need: Lemma 5.1 Let a, x , y ∈ R. If a < min(x , y) then a < x and a < y . Proof of previous example: 236 237 Beware bad points Functions which are not defined near limit points or are unbounded near limit points need special care. Choosing δ small enough can help to avoid these points. Example 5.4 Prove that lim x→1 x2 − 1 2x − 1 = 0 238 239 Proof: 240 241 One-sided limits The definition of one-sided limits is the same as limits, except the deleted neighbourhood N0(`, δ) is replaced by left or right deleted neighbourhoods. 242 Left and Right Limits The left limit is written: lim x→`− f (x) = L “x approaches ` from below (or from the left)”. The right limit is written: lim x→`+ f (x) = L “x approaches ` from above (or from the right)”. 243 The following theorem is useful for showing a limit does not exist. Theorem 5.1 (Left-Right Limits) Let f : E → R be a function. Then lim x→` f (x) = L if and only if lim x→`− f (x) = L and lim x→`+ f (x) = L. 244 Example 5.5 Prove that f (x) = { x − 1 x ≤ 2 x + 1 x > 2 does not have a limit as x → 2. 245 246 The limit points ±∞ We can now think about what happens to a function as: 1. “x → ±∞” 2. x → ` but “f (x)→ ±∞”. f bounded. In the first case, as with sequences, we are really asking, what happens to f as x gets arbitrarily large (positive or negative)? That is, what values can f take in the neighbourhood N∞(δ) = {x ∈ R : x > δ} or similarly in the neighbourhood N−∞(δ) = {x ∈ R : x < δ}? So we are looking at what happens on an unbounded subset of R. 247 Thus the logic form of the definition of lim x→∞ f (x) = L is: ∀ > 0 (∃δ > 0 s.t. (∀x ∈ E (x > δ ⇒ |f (x)− L| < ))). where E is the domain of f . Note, E must be unbounded above for lim x→∞ f (x) to be defined. This is logically equivalent to: ∀ > 0 (∃δ > 0 s.t. (∀x ∈ N∞(δ) |f (x)− L| < )). Geometrically this gives: 248 f unbounded. In the second case, if f is unbounded as x → ` ∈ R we say, lim x→` f (x) = +∞ if ∀α > 0 (∃δ > 0 s.t. (∀x ∈ E (0 < |x − l | < δ ⇒ f (x) > α))). where E is the domain of f . We also say that f is divergent to ∞. Note that there are analogous results for −∞. Remember that: ∞ is not a real number, but a convenient notation for unbounded subsets of R or as limit points. 249 Example 5.6 250 Limit Laws Now that we have a precise definition of a limit, we can prove the standard limit laws. Theorem 5.2 If f → α and g → β as x → ` where α, β ∈ R, then 1. f + g → α + β 2. f · g → α · β 3. f g → α β , β 6= 0 These are proved in a very similar way to the sequence limit laws and are left as an exercise. 251 When a limit does not exist at x = `. There are generally two ways to show that a function has no limit as x → `. 1. Prove the negation of the limit definition is true. 2. Use some theorems, for example left and right limits must both exist and be equal. Example 5.7 252 Continuity Question: When is lim x→` f (x) = f (`)? That is, when can we just substitute to get the value of a limit? Consider the following functions at x = 0: 253 254 Definition 5.5 (Continuous) Let f be a real valued function with domain E ⊆ R. Suppose ` ∈ E and E contains a neighbourhood of `. Then f is said to be continuous at x = `, if lim x→` f (x) = f (`). If D ⊆ E and f is continuous at all ` ∈ D, then f is said to be continuous on D. A very useful consequence of this is that, if we know a function is continuous at x = ` then we immediately know the value of the limit as x → `. We get the value of the limit by substituting x = `, that is f (`). 255 So continuity at x = ` requires: 1. limx→` f (x) ∈ R 2. f (`) is defined (that is, ` ∈ E ) 3. the limit equals the value of f at `. The definition requires N(`, δ) ⊆ E , so that x = ` is in the domain of f (so f (`) must be defined). Thus if f is not defined at x = ` it cannot be continuous at x = `. 256 Definition 5.6 A neighbourhood of x = ` is the open interval N(`, δ) = {x ∈ R : |x − l | < δ} for some δ > 0. Note the difference between a neighbourhood and a deleted neighbourhood. Here, x = ` is included. Thus the answer to the original question is: If f is continuous at x = ` then its limit as x → ` equals the value of the function. This is only really useful if we know a function is continuous at x = ` without proving the limit exists (via − δ) – which is where the continuity laws come in. 257 Theorem 5.3 Let f and g be continuous at x = `. Then the following functions are continuous at x = `. 1. f + g 2. fg 3. f g , as long as g(`) 6= 0 4. f ◦ g , as long as f is continuous at x = g(`). These can all be proved using the modified − δ Definition 5.7, or using the limit laws. 258 We also have the following theorem: Theorem 5.4 The following functions are all continuous on the stated domains: I Polynomials: m∑ n=0 anx n; D = R, an ∈ R I ex , cos(x), sin(x); D = R I log(x); D = R+ I x1/p; D = R+, p ∈ N (that is, pth root). 259 Since the limit point ` is required to be in the domain of f , a deleted neighbourhood is not required in the − δ definition, which gives the following equivalent definition: Definition 5.7 (Continuity at a point) Let f be a real valued function with domain E and ` ∈ E . Then f is continuous at x = ` if: for any > 0 there exists δ() > 0 such that for all x satisfying |x − l | < δ() we have |f (x)− f (`)| < . Note: The original − δ definition of a limit requires a deleted neighbourhood, but Definition 5.7 does not. 260 Example 5.8 Show that f : R→ R is continuous at x = 0, where f (x) = { x sin ( 1 x ) , x 6= 0 0, x = 0. 261 262 263 Bounded and Monotonic Functions As with sequences, (where E = N) we have similar bounded and monotonic properties for functions. Assume that E ,D ⊆ R. Definition 5.8 (Bounded Functions) Let f : E → D. 1. f is bounded above if ∃α ∈ R such that (∀x ∈E f (x) ≤ α). 2. f is bounded below if ∃α ∈ R such that (∀x ∈E f (x) ≥ α). 3. f is bounded above and bounded below (on E ) if and only if f is bounded on E . 264 Definition 5.9 (Monotonic Functions) Let f : E → D. Then f is monotonic on E if and only if it satisfies one of the following conditions: (i) f is increasing; that is, (∀x , y ∈ E x < y ⇒ f (x) < f (y)). (ii) f is non-decreasing; that is, (∀x , y ∈ E x < y ⇒ f (x) ≤ f (y)). (iii) f is decreasing; that is, (∀x , y ∈ E x < y ⇒ f (x) > f (y)). (iv) f is non-increasing; that is, (∀x , y ∈ E x < y ⇒ f (x) ≥ f (y)). If either (i) or (iii) apply, then we say f is strictly monotonic. Monotonicity is very useful for the existence of inverse functions. Question: If f : E → D when can we define g : D → E such that f (g(x)) = x? 265 Theorem 5.5 (Injectivity, Continuity & Monotinicity) Let f be a continuous, real-valued, injective function on an interval I . Then f is either increasing or decreasing on I . The theorem leads to the following useful relationship between continuity and inverse functions. Theorem 5.6 ( Continuity, Injectivity & Inverse,) Let f be a continuous, real-valued, injective function on an interval I . Then an inverse function f −1 exists on I and is a continuous function. Note that I can be [a, b], [a, b), (a, b] or (a, b). 266 Example 5.9 The sine function. The existence of an inverse depends on the domain. 267 Bounded and Continuous Functions Boundedness and continuity are related as shown in the following theorem. Theorem 5.7 (Bounded and Continuous) Let f : E → R, E ⊆ R, be a continuous function on [a, b]. Then f is bounded on [a, b]. 268 The following example shows why the interval [a, b] of the Bounded and Continuous theorem must be closed. 269 To account for continuity at points were the domain of the function only contains half of any deleted neighbourhood, the definition of continuity can be weakened to left and right continuity. Definition 5.10 (One sided Continuity) A function f : A→ B is left continuous at x = ` if lim x→`− f (x) = f (`) and is right continuous at x = ` if lim x→`+ f (x) = f (`) Example 5.10 270 Continuity and Solving Polynomials Question: How do I know that 5x6 − 3x4 + 2x3 − 2 = 0 has at least one real solution? 271 Example 5.11 272 Intermediate Value Theorem We now come to a classic theorem of real analysis. Theorem 5.8 Let g be a continuous real valued function on the closed interval I = [a, b]. Then g takes on every value in the interval J = [inf Ig , supIg ]. Conventionally, this is stated in a weaker form. Theorem 5.9 (Intermediate Value Theorem) Let f : [a, b]→ R be a continuous function and let y ∈ R such that f (a) < y < f (b) or f (a) > y > f (b). Then there exists c ∈ (a, b) such that f (c) = y . 273 274 275 Open and closed subsets of R Recall that N(x , ) = {y | d(x , y) < }. Definition 5.11 A subset E ⊂ R is called open if for all x ∈ E there exists an > 0 such that N(x , ) ⊆ E . A subset if called closed is its complement is open. The union of any collection of open sets is open. Proposition 5.1 Let A = {Ai | i ∈ I} be a collection of sets. If all the Ai are open, then ∪i∈IAi is open. 276 Example 5.12 The intersection of a collection of open sets need not be open. For i ∈ N define Ai = (−1/i , 1/i) ⊂ R. Then ∩i∈NAi = {0} and is not open. However, the intersection of a finite number of open sets is open. Proposition 5.2 Let A1,A2, . . .An ⊂ R be a finite collection of open sets. Then A1 ∩ A2 ∩ · · · ∩ An is open. Corollary 5.1 Let C = {Ci | i ∈ I} be a collection of closed sets. Then ∩i∈ICi is closed. Let C′ = {C1, . . . ,CN} be a finite collection of closed sets. Then ∪Ni=1Ci is closed. 277 Compact subsets Definition 5.12 A subset K ⊂ R is compact if every infinite sequence (xi )i∈N with xi ∈ K has a convergent subsequence which converges to a point in K . (This is in fact what is called ‘sequential compactness’.) Example 5.13 Let a ∈ R be positive. I [0, a) is not compact. (We’ll show this now.) I [0, a] is compact. (This is the Heine-Borel theorem below.) Example 5.14 [0,∞) is closed but not compact. 278 Theorem 5.10 (Heine-Borel) Let E be a subset of R. Then E is compact iff E is both closed and bounded. Proof: Suppose first that E ⊂ R is compact. To see that E is bounded 279 Now to show that E is closed. Suppose that it were not. Then R \ E is not open, therefore there exists x ∈ R \ E such that for all > 0, (x − , x + ) ∩ E 6= ∅. 280 For the converse, suppose now that E ⊂ R is closed and bounded. We must show that E is compact. 281 One of the central features of compact sets is that a continuous function on a compact set has a maximum value. Lemma 5.2 Let K ⊂ R be compact. Then supK ∈ K . Proof: Lemma 5.3 Let f : → R be a contiuous function, and let O ⊂ R be open. Then the set f −1(O) = {a ∈ R : f (a) ∈ O} is open. 282 Proposition 5.3 Let f be a continuous function and K ⊂ R a compact set. Then there is an a ∈ K such that f (a) ≥ f (b) for all b ∈ K . Proof: By the previous lemma it suffices to show that f (K ) is compact. 283 Differentiability In this topic, I represents any of the intervals [a, b], (a, b), [a, b), (−∞, a), (−∞, a], etc, where a < b. Refresher: Let f : I → R. The chord function 284 Since we now have an − δ definition of a limit, we can prove that f ′(x0) exists (as a real number). Definition 6.1 (Differentiability) Let I be an interval of R and f : I → R. The derivative of f at x0 denoted f ′(x0), is defined as f ′(x0) = lim h→0 f (x0 + h)− f (x0) h If f ′(x0) ∈ R (that is, exists) we say that f is differentiable at x0. If f is differentiable for all x ∈ I we say that f is differentiable. If f is differentiable we can define the function f ′ : I → R, x 7→ f ′(x). 285 Note: I f ′(x0) is the limiting value of the chord function, Cx0(h) as h→ 0. Thus if Cx0(h) is not defined in a deleted neighbourhood N0(x0, δ), then the limit defining f ′(x0) cannot exist. In particular f (x0) must be defined. 286 What is the relationship between continuity and differentiability? Theorem 6.1 (Differentiability and Continuity) If f : I → R is differentiable at x0 ∈ I then f is continuous at x0. Proof: Uses the trick f (x0 + h)− f (x0) = h · f (x0 + h)− f (x0) h , h 6= 0. Also, if f ′(x0) exists then Cx0(h) exists in some deleted neighbourhood (N0(0, δ)) so f (x0) is defined. 287 Note: Since lim f = lim g 6⇒ f = g , the converse of the theorem is not true. That is, continuity does not imply differentiability. Example 6.1 The function f (x) = |x | is continuous for all x ∈ R but not differentiable at x = 0. 288 Relationship between differentiability and monotonicity If f is differentiable at x0 we can get some information about the “local” monotonicity properties of f . That is, if we are close enough to x0 then we have the following result: Theorem 6.2 (Differentiability and Monotonicity) Let f be differentiable at x0. Then if f ′(x0) > 0 we have: I ∃ > 0 such that ∀h, (0 < h < )⇒ f (x0 + h) > f (x0). I ∃ > 0 such that ∀h, (− < h < 0)⇒ f (x0) > f (x0 + h). with similar statements for f ′(x0) < 0. 289 Rolle’s Theorem We now come to another classic theorem of real analysis. Theorem 6.3 (Rolle’s Theorem) Let f be continuous on [a, b], differentiable on (a, b) and suppose f (a) = f (b) = 0. Then there exists a point c ∈ (a, b) such that f ′(c) = 0. That is, there must exist at least one point of (a, b) where the tangent is horizontal. If f goes upwards somewhere after x = a it must “turn around” to get back down to x = b. Note carefully the conditions on the intervals. It must be continuous on the closed interval, differentiable on the open interval and c must be in the open interval. 290 Proof: 291 Mean Value Theorem The primary application is to prove another classic theorem, the Mean Value theorem, which in turn is used to prove results for Taylor polynomials - see later. Rolle’s theorem can be generalised to remove the condition f (a) = f (b) = 0, in which case the slope becomes non-zero, as given by: Theorem 6.4 (Mean Value Theorem) Let f be continuous on [a, b], differentiable on (a, b). Then there exists c ∈ (a, b) such that f ′(c) = f (b)− f (a) b − a . Note that, f ′(c) is the slope of the chord through f (a), f (b). 292 Thus the Mean Value theorem says The proof uses a trick to define a function g(x) that can be used with Rolle’s theorem: g(x) = f (x)− f (a)− ( f (b)− f (a) b − a ) · (x − a). Note that g(a) = g(b) = 0. 293 Proof: 294 Notes: I You may use all the usual rules for differentiating functions: I The sum rule, difference rule, scalar multiple rule. I The product rule, quotient rule, chain rule. I Standard derivatives for polynomials, sin, cos, log, etc. These are all straightforward to prove, and are left as an exercise. I The main use of the MVT is for proving things about Taylor polynomials. 295 Riemann Integration (There is a more general form of integration, called Lebesgue Integration, but this requires Measure Theory.) Recall: Integration has two ideas I The idea of an antiderivative, the opposite operation to differentiation. I The area under a curve. The two ideas are linked via the Fundamental Theorem of Calculus. We want a precise definition of: ∫ b a f (x) dx Generalising the first idea is too restrictive, some functions are not differentiable, but can be integrated. So we will try to make the second idea precise. 296 To do this we will show that for some functions, approximating the area under the curve by rectangles can be a very good approximation to the actual area. 297 There are two considerations: I How do we divide up [a, b]? I What height do we use for each rectangle? In the first instance, we allow arbitrary positions: Definition 7.1 (Partition) A partition P of [a, b] is a finite ordered set, written P = {a = x0 < x1 < . . . < xn−1 < xn = b}. 298 Thus, the partition fixes the widths of the rectangles, but what height should we use? There are many possibilities But there is a natural choice: 299 Definition 7.2 (Riemann Sums) Let f : [a, b]→ R be a bounded function. For each subinterval [xk−1, xk ] of the partition P = {a = x0 < x1 < . . . < xn−1 < xn = b}, define mk = inf{f (x) : x ∈ [xk−1, xk ]} Mk = sup{f (x) : x ∈ [xk−1, xk ]} and then define two approximations to the area: the Lower Riemann Sum L(f ,P) = n∑ k=1 mk(xk − xk−1) and the Upper Riemann Sum: U(f ,P) = n∑ k=1 Mk(xk − xk−1). 300 Informally, I U(f ,P) uses the maximum value of f on each subinterval. I L(f ,P) uses the minimum value of f on each subinterval. 301 Note: 1. We only assume f is bounded (so we can ensure that sup and inf exist), not continuous. 2. Riemann sums depend on P. Changing the number of points, or the position of points will change the sum. The useful property of sup and inf is that mk ≤ Mk for all subintervals, thus we have: Theorem 7.1 (Sum ordering: same partition) L(f ,P) ≤ U(f ,P) for all partitions of [a, b]. Thus, L(f ,P) is always a lower bound and U(f ,P) is always an upper bound on the “area”. 302 Question How do L and U change as we add new points to the partition P? That is, what if we keep the current n points fixed, but add new points between the existing ones to give a new partition Pˆ so that P ⊆ Pˆ? For example, P = { 1, 32 , 2 } and Pˆ = { 1, 54 , 3 2 , 2 } . 303 Definition 7.3 (Refinement) If P ⊆ Pˆ then Pˆ is called a refinement of P (that is, Pˆ has the same points and more). How L and U change under refinement is given by the following theorem: Theorem 7.2 (Sum ordering: refinement) If Pˆ is a refinement of P then L(f ,P) ≤ L(f , Pˆ) and U(f , Pˆ) ≤ U(f ,P). So increasing the number of subintervals increases L and decreases U. Hence, it improves the estimates. 304 Intuitively we can see this from the geometry: 305 The proof relies on the following theorem: Theorem 7.3 (Subintervals and Sup’s/Inf’s) Let f : [a, b]→ R be bounded on [a, b], with c ∈ (a, b). Then 1. sup[a,c] f ≤ sup[a,b] f 2. sup[c,b] f ≤ sup[a,b] f with similar (reversed) inequalities for infimum. The proof is left as an easy exercise. 306 We now prove Theorem 7.2. 307 308 309 What happens as we change the position of the points in P? If we compare U and L (rather than U and U) then we have: Theorem 7.4 (Sum Ordering: different partitions) If P and Q are any partitions of [a, b], then L(f ,P) ≤ U(f ,Q). Note this is a generalisation of Theorem 7.1. Proof: 310 Thus as we refine the partition (that is, increase points), L is non-decreasing and U is non-increasing. Question: Do they meet in the middle somewhere? Answer: Sometimes... it depends on f . 311 Riemann Integrable In the special case that L and U are equal in the limit, we define Definition 7.4 (Riemann Integrable) Let P˜ be the set of all possible partitions of [a, b]. Define the Lower Riemann Integral of f on [a, b] as: L(f ) = sup{L(f ,P) : P ∈ P˜} and the Upper Riemann Integral of f on [a, b] as: U(f ) = inf{U(f ,P) : P ∈ P˜}. We say that f is Riemann integrable on [a, b] if U(f ) = L(f ) 312 In this case we define the integral of f by∫ b a f = U(f ) = L(f ). Example 7.1 Here is a bounded function that is not integrable. 313 314 Question: Is it possible to determine if f is integrable without testing all partitions? Answered by Riemann: Theorem 7.5 (Integrability and Boundedness) Let f : [a, b]→ R be bounded. Then f is integrable if and only if, for all > 0 there exists a partition P of [a, b] such that, U(f ,P)− L(f ,P) < . This is similar to an − δ definition except finding δ() is replaced by finding P(). 315 316 317 In the special case when f is continuous, we can say more (without considering any partitions at all). Theorem 7.6 (Integrability and Continuity) If f : [a, b]→ R is continuous on [a, b], then f is integrable on [a, b]. Notes 1. The converse is NOT true: Integrable 6⇒ Continuous. 2. Functions which are not continuous on [a, b] may still be integrable, for example, f : R→ [−1, 1] f (x) = { 1, x ≥ 0 −1, x < 0. 3. The proof is not difficult but requires “uniform continuity” which is not in this subject. 318 Theorem 7.7 (Fundamental Theorem of Calculus) I If f : [a, b]→ R is integrable and F : [a, b]→ R satisfies F ′(x) = f (x) for all x ∈ [a, b] then ∫ b a f (x) dx = F (b)− F (a) I Let g : [a, b]→ R be integrable and define G : [a, b]→ R by G (x) = ∫ x a g(u) du, G (a) = 0. Then G is continuous on [a, b]. If g is continuous at c ∈ [a, b] then G is differentiable at c and G ′(c) = g(c). 319 The theorem says: 1. If f has an antiderivative, then we can evaluate ∫ b a f (x) dx . 2. If we can evaluate ∫ x a f (u) du, then we get the antiderivative (which is also continuous). 320 Algebraic Properties of the Integral All these usual properties can be proved from the definition: Theorem 7.8 (Algebra of Integrals) If f and g are integrable on [a, b] and c ∈ [a, b] then: 1. ∫ c a f and ∫ b c f exist 2. ∫ b a f = ∫ c a f + ∫ b c f 3. ∫ b a (f + g) = ∫ b a f + ∫ b a g 4. ∫ b a λf = λ ∫ b a f , λ ∈ R 321 Improper Integrals Question: What if f is unbounded at some point c ∈ [a, b]? Without loss of generality, we can take c = a or b since we can use Theorem 7.8 part 3. As with all things that might be unbounded, we consider the limit of finite things! Definition 7.5 (Improper Integral: unbounded integrand) Let f : (a, b]→ R be such that f is integrable on [c , b] for all c ∈ (a, b). If the limit lim c→a+ ∫ b c f exists we call it the improper integral of f on (a, b]. 322 Beware: the same notation ∫ b a f is generally used . You need to check the function f carefully to see if lim c→a+ ∫ b c f is meant. That is, check to see if a is actually in the domain of f . 323 We can make a similar definition for unbounded intervals: Definition 7.6 (Improper integral: unbounded interval) Let f : [a,∞)→ R be integrable on [a, c] for every c > a. If the limit lim c→∞ ∫ c a f exists we call it an improper integral, written∫ ∞ a f . Note: there is a similar definition for ∫ a −∞ f = lim c→−∞ ∫ a c f . See practice class sheets for examples. 324 Series For this topic the focus is on applying theorems rather than proving them. Consider the following methodof approximating the area under the parabola y = 1− x2 325 The (finite) partial sums Ak = 1 + 1 4 + · · ·+ 1 4k provide an increasingly better approximation to the area. 326 This example shows very clearly that: I LHS is an increasingly better approximation to the area I The approximation is always less than 43 Ak < 4 3 , ∀k ∈ N and so is bounded above I Less obviously, if I choose any number less than 4 3 , I can always find a k ∈ N such that Ak is larger than it, that is, 4 3 = sup{Ak : k ∈ N}. Sound familiar? ∀ > 0 ∃k0 ∈ N s.t. ∀k > k0 ∣∣∣∣Ak − 43 ∣∣∣∣ < . 327 Recall the definition of the convergence of a sequence fn: ∀ > 0 ∃M ∈ N s.t. ∀n > M, |fn − L| < . Thus the partial sums behave like the terms of a sequence A1,A2,A3, . . . . So we say that, Ak converges to 4 3 and write it as 1 + 1 4 + 1 16 + . . . = 4 3 . This is NOT the addition of an “infinite” number of terms: it is a convenient notation for saying the partial sums converge to 4 3 . That is, the approximations have a finite limit. 328 Question: Why can’t we think of it as the sum of an infinite number of terms? Clearly Ak is a sum of terms! If it were a summation, it would need to have all the properties of the binary operation “+”, that is: I Associative (1 + 2) + (3 + 4) = 1 + (2 + 3) + 4 I Commutative 1 + 2 + 3 = 3 + 2 + 1 I etc. 329 Example 8.1 Consider 1− 1 + 1− 1 + 1− 1 + . . . = ? 330 331 332 333 The essential idea is to consider the partial sums, Ak , as defining a sequence (Ak) and then consider the convergence of the sequence (Ak). Note: Historically things happened the other way around: Problems with “Infinite sums” (particularly those from Fourier series) were finally resolved once convergence was understood. Beware: “a1 + a2 + a3 + . . .” is not the same mathematical object as “a1 + a2 + . . .+ ak” (ie. a finite sum). The notation is, however, convenient as sometimes a1 + a2 + a3 + . . . has some of the properties of a finite sum. 334 Definition 8.1 (Series) The expression “a1 + a2 + a3 + . . .” is called a series and is usually written as ∞∑ n=1 an or ∑ n>0 an. The number an is called the n-th term of the series. Furthermore, Ak = a1 + a2 + . . .+ ak is called the k-th partial sum of the series and (Ak) the sequence of partial sums. 335 Thus we have a1 + a2 + a3 . . . Since the partial sums give a sequence of approximations to the series, in the sense of Archimedes, we are motivated to define: 336 Definition 8.2 (Convergent series) The series ∞∑ n=1 an is said to be convergent if the sequence (Ak) Ak = k∑ n=1 an is convergent. If lim k→∞ Ak = L, we call L the sum (or value) of the series and write: a1 + a2 + . . . = L, or ∑ n>0 an = L. The series is divergent if (Ak) is divergent. 337 Again we have the standard algebra: Theorem 8.1 (Algebra of Series) If ∑ n>0 an = α and ∑ n>0 bn = β then ∞∑ n=1 (an + bn) = α + β and ∞∑ n=1 (λan) = λα, λ ∈ R. Proof: Follows from the algebra of sequences. 338 Warning: Do not confuse the sequence of terms (an) with the sequence of partial sums (Ak). Given any sequence (an) we can define a series via its partial sums: The convergence of (Ak) (and hence the value of the series “a1 + a2 + . . . ”) is related to the sequence of terms in an important way: 339 Theorem 8.2 (Series and Term convergence) If ∞∑ n=1 an converges then lim n→∞ an = 0. The converse is false: lim n→∞ an = 0 does not imply that ∞∑ n=1 an converges. The classic counterexample is the Harmonic Series: ∞∑ n=1 1 n which diverges, even though 1 n → 0. 340 The Harmonic series is the s = 1 case of the famous Riemann Zeta Function: ζ(s) = ∞∑ n=1 1 ns which is the function of the famous Riemann Hypothesis. Proof of Theorem 8.2: 341 Even though the converse is false, the contrapositive (which is necessarily true) is very useful: ∼ ( lim n→∞ an = 0)⇒ ∼ (∑ n>0 an converges ) which gives the equivalent theorem: Theorem 8.3 (Terms & Series Divergence) If lim n→∞ an 6= 0 then ∑ n>0 an diverges. This is sometimes called the divergence test. 342 Example 8.2 1. ∑ n>0 2n diverges. 2. ∑ n>0 n3 n2 + 4 diverges. 3. ∑ n>0 (−1)n+1 diverges. 343 Back to the original problem: Question: How do we know when the series a1 + a2 + a3 + . . . behaves like a finite sum, that is, we can commute or associate the terms without changing its value? Theorem 8.4 (Associativity) If ∑ n>0 an converges then any series obtained by grouping the terms without changing their order converges to the same value. That is; convergence ⇒ associative (regrouping) of terms is allowed. Again the converse is false. If you split the terms of a1 + a2 + . . . into parts, then the series may or may not converge. 344 But the contrapositive of Theorem 8.4 is still useful. Informally: Theorem 8.5 (Associativity and Divergence) Regrouped ∑ n>0 an diverges ⇒ ∑ n>0 an diverges. We can use this to show that the harmonic series diverges. 345 346 What about the convergence of ∞∑ n=1 1 n2 or ∞∑ n=1 1 np etc? Previous contrapositive theorems relate one divergent series to another divergent series. For convergence, do we always have to use the definition? That is, show the sequence of partial sums converges via −M? The answer depends on the type of series (that is, the properties of its terms). 347 Don’t get lost (summary of some of the tests) 348 Positive Series Series with all positive terms are generally easier to test for convergence. Definition 8.3 (Positive series) A series ∑ n>0 an is positive if an ≥ 0 for all n ∈ N. Theorem 8.6 (Positive Bounded Series) A positive series ∑ n>0 an converges if and only if there exists K > 0 such that ∀n ∈ N An ≤ K , where An = n∑ m=1 am Note: 1. if all an ≤ 0 then you can factor out −1 to get a positive series 2. if some of the terms equal zero then ‘re-indexing’ changes it to the case an > 0 for all n.349 Example 8.3 Show that ∑ n>0 1 n2 converges. 350 Comparison Test Theorem 8.6 still requires knowledge of the partial sums {Ak}. Question: Can we determine the convergence of a series using only the terms an? Answer: If we can compare the series with some other series known to converge, then, yes: 351 Theorem 8.7 (Comparison Test) Let ∑ n>0 an be a series and ∑ n>0 bn a series convergent to L. If there exists K > 0 such that an and bn satisfy 0 ≤ an ≤ K bn, for all n ∈ N, then ∑ n>0 an converges and ∑ n>0 an ≤ KL. Conditions: The theorem is similar to the sandwich theorem for limits. If the terms of a positive series ∑∞ n=1 an are always bounded above by the terms of a convergent positive series (and bounded below by zero) then we get the convergence of ∑∞ n=1 an. 352 We also have the contrapositive of the theorem Theorem 8.8 (Comparison test – divergence) If there exists K > 0 such that for all n ∈ N, 0 ≤ bn ≤ Kan and ∑ n>0 bn diverges, then ∑ n>0 an diverges. Example 8.4 Does ∑ n>0 2 n2 + 1 converge? 353 Ratio Test A test that does not rely on the convergence of another series is: Theorem 8.9 (Ratio Test – Non-limit form) Let ∑ n>0 an be a positive series. Let r and R be real numbers with 0 < r < 1 and R > 1. Then 1. If there exists M1 ∈ N such that for all n > M1, an+1 an < r , then ∑ n>0 an converges. 2. If there exists M2 ∈ N such that for all n > M2, R < an+1 an , then ∑ n>0 an diverges. Conditions: 354 Thus, if the ratio of consecutive terms is bounded by a positive constant, we can determine if ∑ n>0 bn converges. On occasion it is easier to use the limit form of the Ratio Test. Theorem 8.10 (Ratio Test – Limit Form) Let ∑ n>0 an be a series such that the sequence ∣∣∣∣an+1an ∣∣∣∣ converges to a limit r . 1. If r < 1 then ∑ n>0 |an| converges (as does ∑ n>0 an). 2. If r > 1 then ∑ n>0 an diverges. Conditions: 355 Example 8.5 Does ∑ n>0 1 5n converge? 356 Example 8.6 More generally, when does ∑ n≥0 rn converge? 357 Example 8.7 Show that ∑ n>0 n2 2n converges. 358 What happens when ∣∣∣∣an+1an ∣∣∣∣ −→ 1 as n→∞? 359 There are many convergence tests. A few more are given below (without proof). You many use any of them to prove convergence. Theorem 8.11 (The Integral Test) Let f be a continuous function defined on [N,∞), N ∈ N, which is positive and decreasing. Then the series ∞∑ n=N f (n) converges if and only if lim n→∞ (∫ n N f (x)dx ) exists. Conditions: 360 Theorem 8.12 (p-series) The p-series is the series ∑ n>0 1 np where p > 0. 1. If p > 1, then the series converges. 2. If 0 < p ≤ 1 then the series diverges. p-series can be used to test convergence by using it as part of other tests eg. comparison test. 361 Theorem 8.13 (The Limit Comparison Test) Let ∑∞ n=1 an and ∑∞ n=1 bn be series with positive terms. Consider lim k→∞ ak bk . 1. If the limit is a positive number, then ∑∞ n=1 an converges if and only if ∑∞ n=1 bn converges. 2. If the limit is 0 and ∑∞ n=1 bn converges then ∑∞ n=1 an converges. 3. If the limit is ∞ (ie. unbounded) and ∑∞n=1 bn diverges then ∑∞n=1 an diverges. Conditions: 362 Alternating Series What about series that have some negative terms? The simplest type in this class are those with terms whose signs alternate. Definition 8.4 Alternating series are those of the form ∞∑ n=1 an where an = (−1)n+1bn and bn > 0. We use (−1)n+1 rather than (−1)n so that the first term is positive. For example, 1− 1 2 + 1 3 − 1 4 + 1 5 − 1 6 + . . . = ∞∑ n=1 (−1)n+1 n . 363 Alternating series have a very special relationship between (Ak) and (an): Theorem 8.14 (Alternating Series Test) Let (bn) be a non-increasing sequence with bn > 0 and bn → 0. Then the alternating series ∞∑ n=1 (−1)n+1bn converges. Conditions: Thus for alternating series it is necessary and sufficient for convergence, that bn → 0 (see Theorem 6.3). 364 Example 8.8 The series ∑ n>0 (−1)n+1 n converges. 365 Absolute Convergence We have seen that “convergence implies regrouping is ok” but what about commutativity – rearranging the order of terms? This depends on the following property: Definition 8.5 (Absolute Convergence) The series ∑ n>0 an is called absolutely convergent if ∑ n>0 |an| converges. Absolute Convergence allows us the arbitrarily change the signs of the terms: Theorem 8.15 (The Absolute Convergence Test) If ∑ n>0 an is absolutely convergent, then ∑ n>0 an converges. Conditions: 366 The converse is false. Note: Series for which ∑ n>0 an converges, but ∑ n>0 |an| does not, are called conditionally convergent. For example, ∑ n>0 (−1)n+1 n converges, but ∑ n>0 1 n does not. 367 Example 8.9 Does the series ∞∑ n=1 sin n n2 converge? 368 We can now finally state the rearrangement condition: Theorem 8.16 (Rearrangement) Let ∑ n>0 an be an absolutely convergent series. Then every rearrangement of∑ n>0 an converges absolutely to the same value. This says that, absolute convergence ⇒ the terms commute. So we have “Absolute convergence ⇒ rearranging is allowed” and “Convergence ⇒ regrouping is allowed” Since “Absolute convergence ⇒ convergence” then Absolutely convergent series can be both rearranged and regrouped! 369 Aside We need to define “rearrangement”. Let σ : N→ N be a bijection. If ∑ n>0 an and ∑ n>0 bn are two series such that ∀n ∈ N an = bσ(n), then ∑ n>0 an is a rearrangement (or permutation) of ∑ n>0 bn. 370 Power Series A power series is an infinite polynomial. These series can be added, subtracted, multiplied, differentiated and integrated to give new power series. We will study some of these series with a particular interest on if and when they converge. Consider the geometric series 1 + r + r2 + r3 + . . . , r ∈ R. Example 8.10 What does it converge to? 371 Theorem 8.17 (Geometric Series) The geometric series ∑ n≥0 rn converges if |r | < 1 and 1 + r + r2 + r3 + . . . = 1 1− r . If |r | ≥ 1 then the geometric series diverges. 372 We can generalise the geometric series by changing the coefficients of each term: Definition 8.6 (Power Series) A (real) power series, (about r = 0), is a series of the form a0 + a1r + a2r 2 + a3r 3 + . . . , an, r ∈ R. The sequence (an)n≥0 is the sequence of coefficients. Note, a power series conventionally starts with a0 as then the coefficient index is the same as the exponent of r : ∞∑ n=0 anr n. 373 Question: The geometric series (an = 1, ∀n ∈ N) converges for |r | < 1. How do the coefficients change this? Obviously convergence depends on (an). Thus we refine the question: Given the coeffcients (an) how does the convergence depend on r? Notice that the partial sums are polynomials Ak = a0 + a1r + a2r 2 + . . .+ ak r k , thus we can think of the partial sums as polynomial functions of r : Pk : R→ R, r 7→ a0 + a1r + . . .+ ak rk . 374 So we can think of the sequence of partial sums (Ak) = (Pk(r)) as a sequence of functions and hence the power series f (r) = lim k→∞ Pk(r) as a function obtained as a “limit of polynomial functions”. Question: How does the convergence of (Pk(r)) depend on r? Question: Polynomials are continuous and differentiable for all r ∈ R. What about f (r)? Question: Can known functions (for example, sin, log) be expressed as power series? 375 First some examples. f1(r) = r − r 2 2 + r3 3 − r 4 4 + . . . an = (−1)n+1 n f3(r) = 1 + r + 1 2! r2 + 1 3! r3 + . . . an = 1 n! f2(r) = r − 1 3! r3 + 1 5! r5 + . . . an = { (−1)k n! n = 2k + 1 (ie. odd) 0 n even Given the coefficients (an)n≥0, how does the convergence of the series change with r? 376 Consider the set of all values of r for which f (r) = ∞∑ n=0 anr n converges: Let S(f ) = {r ∈ R : f (r) converges } . I Since ∞∑ n=0 anr n converges if r = 0 the set S is non-empty. I If ∞∑ n=0 anr n converges absolutely for some r = s (ie. ∞∑ n=0 |ansn| converges) then for all r satisfying 0 ≤ |r | ≤ |s| it must also converge. Why? 377 Thus we can consider the “largest possible |s|”: ρ(f ) = sup { |s| : s ∈ S(f )}. • If ∞∑ n=0 anr n converges for all |r | then of course ρ does not exist, but if not, then ρ certainly exists as S contains s = 0. Thus we define: Definition 8.7 (Radius of convergence) Let S(f ) be the set of all r ∈ R for which f (r) = ∞∑ n=0 anr n converges. I If S is unbounded then the series is said to have infinite radius of convergence. I If S is bounded, then let ρ(f ) = sup { |s| : s ∈ S(f )}. and ρ(f ) is called the radius of convergence of the power series f (r). 378 Note: 1. ρ is the sup of the absolute values |s| so therefore ρ ≥ 0. 2. It is called the radius as r can be generalised to a complex number and then ρ is the radius of a circle in the complex plane (and ∑∞ n=0 anr n converges for all values inside the circle). 3. If |r | > ρ, then by definition of ρ, the power series diverges. 4. The set S(f ) may or may not contain ±ρ. Thus is is always necessary to check if f (r) converges when r = ±ρ. For example the power series g(r) = ∑n≥0 rn has ρ = 1 but g(1) does not converge. 5. S(f ) unbounded means the series converges for all r ∈ R. 379 The radius of convergence marks the divide between values of r for which ∞∑ n=0 anr n certainly converges and does not converge: Theorem 8.18 (Power series convergence) Let ρ be the radius of convergence of the power series ∞∑ n=0 anr n. Then if |r | < ρ the series is absolutely convergent; if |r | > ρ it is divergent. Proof: 380 Example 8.11 For what values of x does ∑ n≥0 xn n! converge? 381 Example 8.12 For what values of x does ∑ n≥0 (−1)n+1 n xn converge? 382 Example 8.13 For what values of x does ∑ n≥0 xn 5n converge? 383 Note that Power Series are easily generalised to the form: ∞∑ n=0 an(x − b)n, b ∈ R, in which case the convergence condition for |r | is replaced by one for |x − b|. Example 8.14 ∑ n≥0 (x − 2)n 5n 384 We first define a series related to f (x) and then consider if the series converges to f . The idea is to match the derivatives of f to those of the partial sums. Assume f is infinitely differentiable (that is, all derivatives exist). Then, if Ak = k∑ n=0 akx k we require dnAk dxn ∣∣∣ x=0 = dnf dxn ∣∣∣ x=0 for 0 < n ≤ k . This will give unique values to the coefficients of ∑ n≥0 akx n. 385 Example 8.15 Let f (x) = ex , then 386 387 Thus we get the series∑ n≥0 anx n = 1 + x + 12!x 2 + 13!x 3 + 14!x 4 + . . . Question: Does this series converge to ex , and if so, what is the radius of convergence? We generalise this to an arbitrary point x = b rather than x = 0. 388 Definition 8.8 (Taylor Series) Let b ∈ R and J be an open interval centred on x = b. Let f : J → R be infinitely differentiable at x = b. The Taylor Series of f about x = b is the series ∞∑ n=0 f (n)(b) n! (x − b)n. The partial sums Ak(x) = k∑ n=0 f (n)(b) n! (x − b)n are called the Taylor Polynomials of f about x = b. 389 Example 8.16 The Taylor polynomials for ex are 390 But, does ∑ n≥0 1 n! xn converge to ex for x ∈ (−ρ, ρ)? In other words, does lim k→∞ Ak(x) = e x? To prove convergence (which has to be done every time we change f ) we need to look at the error in the approximation |f (x)− Ak(x)|. That is, ∀ > 0, ∃M such that ∀n > M |f (x)− An| < . To help with this it would be useful if Ak , or better, f (x)− Ak could be bounded: 391 Theorem 8.19 (Taylor’s Theorem) Let f : (−ρ+ b, b + ρ)→ R be a k + 1 times differentiable function on (−ρ+ b, b + ρ) and let Ak(x) = k∑ n=0 f (n)(b) n! (x − b)n be the kth partial sum of the Taylor Series of f . Then for any x ∈ (−ρ+ b, b + ρ) there exists a real number c between b and x such that f (x)− Ak(x) = f (k+1)(c) (k + 1)! (x − b)k+1. 392 Notes: 1. Instead of having to work with f (x)− k∑ n=0 f (n)(b) n! (x − b)n we only need to know the (n + 1)th derivative of f . 2. f (x)− Ak(x) is a measure of how well Ak(x) approximates f (x) - compare with the Archimedes parabola area. 3. For fixed k the approximation gets worse as x moves away from b. 4. The only requirement is that f is k + 1 times differentiable in an open neighbourhood of x = b. 393 It is sometimes possible to estimate the remainder Rn(x). This is a very useful result. Theorem 8.20 (The Remainder Estimation Theorem) If there is a positive constant M such that |f (k+1)(t)| ≤ M for all t between x and b, then the remainder term Rk(x) in Taylor’s Theorem satisfies |Rk(x)| ≤ M |x − b| (k+1) (k + 1)! . If this condition holds for every k ∈ N and all conditions of Taylor’s Theorem are satisfied by f , then the series converges to f (x). 394 We have seen how Taylor series can be used to approximate functions, locally, by polynomials. We now turn our attention to Fourier series, which are useful for approximating functions on a wider interval, and can sometimes be used for discontinuous functions. Partial Sums In this case, our partial sums look like Fk(x) = k∑ n=0 (an cos(nx) + bn sin(nx)). 395 Thus if lim k→∞ Fk(x) exists (for x ∈ J) then so does the series ∑ n≥0 (an cos(nx) + bn sin(nx)). Note: The function sin(x) is an odd function: sin(−x) = − sin(x) and cos(x) is an even function: cos(−x) = cos(x). Thus k∑ n=0 an cos(nx) is even and k∑ n=0 bn sin(nx) is odd. 396 Historically: Early 1800’s, Fourier proposed a solution to heat flow in a thin infinite slab: as a solution to the heat equation - a partial differential equation for the temperature in the x − y plane: T (t; x , y). 397 The boundary conditions are: T (x , 0) = f (x), where f is an even function. T (−1, y) = T (1, y) = 0; that is, constant temperature on left and right sides. The simplest case is f (x) = 1. Fourier proposed the time independent solution T (x , y) = ∑ n≥0 ane −(2n−1)piy 2 cos ( (2n − 1)pi 2 x ) where the an’s depend on f (x). 398 Thus, along the x-axis, he proposed a solution of the form: f (x) = ∑ n≥0 an cos (npi 2 x ) and for f (x) = 1, his method gave 1 = 4 pi ∞∑ n=0 (−1)n−1 2n − 1 cos ( (2n − 1)pi 2 x ) , −1 ≤ x ≤ 1 or pi 4 = ∞∑ n=0 (−1)n−1 2n − 1 cos ( (2n − 1)pi 2 x ) . 399 Let’s check the partial sums: Fk(x) = k∑ n=0 (−1)n−1 2n − 1 cos ( (2n − 1)pi 2 x ) . 400 Note: Fk(±1) does fit with the temperature of the plate on the two sides, however, mathematically we are trying to find an infinite series that converges to 1 for x ∈ [−1, 1], perhaps this is not possible (with a Fourier series) and it only converges to 1 for x ∈ (−1, 1)? Let’s use the computer to plot the partial sums; that is, the approximations to f (x) = 1. Fk(x) = 4 pi [ cos (pix 2 ) − 1 3 cos ( 3pix 2 ) + . . . · · ·+ (−1) n−1 2n − 1 cos ( (2n − 1)pi 2 x )] 401 Computing the coefficients was given by Fourier: Definition 8.9 Let f : [−pi, pi]→ R be a function. Then the Fourier Coefficients are defined as: a0 = 1 2pi ∫ pi −pi f (x) dx an = 1 pi ∫ pi −pi f (x) cos(nx) dx bn = 1 pi ∫ pi −pi f (x) sin(nx) dx and the Fourier Series as a0 + ∞∑ n=1 (an cos(nx) + bn sin(nx)). 402 Note: The assumed property of f is that all the integrals ∫ pi −pi f (x) sin(nx) dx , ∫ pi −pi f (x) cos(nx) dx exist; that is, f (x) sin(nx) and f (x) cos(nx) are integrable. Some books replace a0 with a0 2 and then all the integrals have a 1 pi factor. The big question is what does the series converge to? 403 The answer was given by Dirichlet: Theorem 8.21 Let f : [−pi, pi]→ R be a bounded, piecewise continuous and piecewise monotonic function. Furthermore, assume that f is periodic with period 2pi and that f (x) = 1 2 ( lim h→0+ f (x + h) + lim h→0− f (x + h) ) for every value of x . Then f (x) = a0 + ∞∑ k=1 (an cos(nx) + bn sin(nx)) where (an) and (bn) are given by Definition 8.9. 404 There are several assumptions for f : 1. f is integrable on [−pi, pi] 2. f is periodic with period 2pi 3. If f has a discontinuity its value must be the average of the left and right limits. 4. Piecewise continuous (can be discontinuous at isolated points) 5. Piecewise monotonic The rather strange condition f (x) = 1 2 ( lim h→0+ f (x + h) + lim h→0− f (x + h) ) is only important where the function is discontinuous. If the function is continuous at x , then the left and right limits are equal: lim h→0+ f (x + h) = lim h→0− f (x + h) = f (x). and the equation is redundant. 405 Note: There is a more general version (where item 5 is relaxed and only requires that f is a bounded variation; that is, there exists increasing functions, g and h such that f (x) = g(x)− h(x) for all x ∈ [−pi, pi]). Thus Dirichlet’s Theorem explains Fourier’s solution with f (x) = 1. 406 Example 8.17 407 408 Example 8.18 409 410 欢迎咨询51作业君