Mathematical Logic and Sets Notes PDF

1 Mathematical Logic and Sets In this course we establish some of the important concepts and notation you will use throughout your maths degree. Here we introduce some basic mathematical logic and set theory. Pure mathematics is concerned with establishing axioms and definitions and then trying to prove that statements about these axioms and definitions are true. 1.1 Propositions and Predicates Definition 1.1. A Proposition is a statement that is True or False. Examples The following are all propositions. i. 1 + 1 = 2. ii. ⇡ = 3. iii. There exists a real number x such that x2 iv. All even integers greater than 2 can be written as the sum of two primes. We will use P and Q etc. to denote propositions. 1. Definition 1.2. A Predicate is a statement that depends on one or more vari ables and becomes a proposition when values are assigned to these variables. Examples i. n is a prime number. ii. n+m < 4. iii. x2 > y2 iv. x2 + 3x+ 2 = 0. We will use P (n), P (n,m), Q(x) etc. to denote predicates. When we refer to a statement we mean either a proposition or a predicate. Exercise Which of the following are propositions and which are predicates? i. There exists a real number x such that x2 = x. ii. x2 3x 4 = 0. iii. 25 iv. 31471 is a prime number. v. All natural numbers divisible by 2 are divisible by 4. 36. 1.2 Logical connectives We can make composite statements by using the logical connectives ‘OR’ and ‘AND’: Definition 1.3. Let P and Q be mathematical statements, The statement ‘P or Q’ is True precisely when one or both of P and Q are True. We use _ to denote ‘or’. We can summarise this in a Truth Table: P _Q P Q T T T F F T F F T T T F (Note that this di↵ers from the normal use of ‘or’ in the English language eg. ‘People travel to work by bus or train’ assumes they do one or the other, but not both. In mathematics we use ‘or’ to mean ‘inclusive or’. We can also define ‘exclusive or’ which is true when one of the two statements is true but false when both are true.) Definition 1.4. ‘P and Q’ is True precisely when both P and Q are True. We use ^ to denote ‘and’. The Truth Table is: P ^Q P Q T T T F F T F F T F F F Definition 1.5. The negation of a statement P, ‘not P ’, is True when P is False and vice versa. We use ¬P to denote ‘not P ’. ¬P P T F F T Examples i. ‘x = ±y’ is shorthand for ‘x = y or x = y’. ii. ‘3 < ⇡ < 4’ is shorthand for ‘3 < ⇡ and ⇡ < 4’. iii. ‘¬(x < 4)’ is the same as ‘x 4. (which is shorthand for ‘x > 4 or x = 4’). Two statements are said to be Logically Equivalent (or simply Equivalent) if they have the same truth tables. Example (¬P ) _ (¬Q) P Q T T T F F T F F F T T T ¬(P ^Q) F T T T Therefore ¬(P ^Q) is equivalent to (¬P ) _ (¬Q). Exercise Show that ¬(P _Q) is equivalent to (¬P ) ^ (¬Q). 1.3 Implications In Section 2 we are going to study di↵erent methods to prove statements are true. An important idea in proofs is that of ’implication’. Definition 1.6. Let P and Q be statements. Then ‘P implies Q’ is True in all cases except when P is True and Q is False. We use P ) Q to denote ‘P implies Q’. The Truth Table is P)QPQTTTFFTFFTFTT We sometimes call P the Hypothesis and Q the Conclusion. Exercise Consider the statement ‘n > 3 implies n > 0.0 What happens for di↵erent values of n? There are other ways of writing ‘P implies Q’: If P , then Q Q if P P only if Q P is su cient for Q Q is necessary for P What is the negation of P ) Q? Exercise Write out the Truth Tables for the following: i. P ) ¬Q ii. ¬P ) Q iii. ¬P ) ¬Q iv. Q ) P v. Q ) ¬P vi. ¬Q ) P vii. ¬Q ) ¬P We can see that none of these is equivalent to ¬(P ) Q). We can write P ; Q but this is not usually practical to work with. We call Q ) P the Converse of P ) Q. We call ¬Q ) ¬P the Contrapositive of P ) Q. Notice that the contrapos itive is logically equivalent to P ) Q. Consider P ^ (¬Q): P ^ (¬Q) P Q T T T F F T F F F T F F Therefore ¬(P ) Q) and P ^ (¬Q) are logically equivalent. We will use this fact when we look at Proof by Contradiction. Definition 1.7. We define ‘P if and only ifQ’ to mean ‘(P ) Q) and (Q ) P )’. We denote ‘if and only if’ by ,. We also use the shorthand ‘i↵’ for ‘if and only if’. The Truth Table is P,QPQTTTFFTFFTFFT (Check this is equivalent to (P ) Q) ^ (Q ) P ).) Exercise Write down the truth tables for the following and show they are logically equiv alent. (You wll need 8 rows for all the possible T or F values of P ,Q and R.) i. (P _Q) ) R ii. (P ) R) ^ (Q ) R). 1.4 Sets We now introduce some basic set notation and some of the standard number sets. We will return to look at sets in more detail later in the course. Set Theory underpins the whole of pure mathematics. Definition 1.8. A set is a collection of objects. The objects in a set A are called the elements of A. We use the notation x 2 A to denote ‘x is an element of A’ and x /2 A to denote that x is not an element of A. Elements of a set can be anything (including sets themselves). We consider both finite sets (with a finite number of elements) and infinite sets (where the number of elements is not finite). The empty set, denoted by ;, is the set with no elements. In this course and throughout your degree you will work with the standard number sets. The set of Natural Numbers, N, is the set {1, 2, 3,...}. (Here the dots mean the list continues ’forever’.) The set of Integers, Z, is the set {... , 2, 1, 0, 1, 2,...}. The set of Rational Numbers, Q, is the set of all numbers that can be represented as a/b for some integers a and b with b = 0. Note that a/1 2 Q for any integer a and so the integers are contained in the rationals. Also the expression a/b for a rational is not unique eg. 1/3 = 3/9 = 9. 27, The set of Real Numbers, R, can be thought of as all numbers that can be represented as a finite or infinite decimal expression. (This is not a formal definition but it will do for now!) but we can always cancel common factors and assume b > 0 to write the number in its lowest terms. Remark We sometimes write Z+ instead of N, Z for the set of non-negative integers and use R+ and R to denote the sets of positive and negative real numbers respectively. Real numbers that are not rational are called irrational numbers. We will return to look at properties of these sets later in the course. We will also define the set of complex numbers C in Section 3. We can write a set in three ways. i. As a LIST inside curly brackets: e. A = {1, 0, ⇡, {4}}, N = {1, 2, 3,...}. The order in which the elements is written does not matter and we exclude repetitions of elements. ii. Using CONDITIONS: {x 2 A |P (x)}, where P (x) is a predicate. e. B = {n 2 Z | 0 < n < 6} = {1, 2, 3, 4, 5}. iii. By CONSTRUCTION using a formula: e. {n2 |n 2 Z} = {0, 1, 4, 9,...}, Q = {a/b | a, b 2 Z, b = 0}. 1.5 Subsets Definition 1.9. We say that a set A is a subset of a set B, and write A ✓ B (or B ◆ A), if and only if x 2 A ) x 2 B. Note that A ✓ B includes the case when A = B. If A = B we write A ⇢ B or A $ B and we say that A is a proper subset of B. We write A * B if A is not a subset of B. Examples i. Z ✓ Q, in fact Z ⇢ Q. ii. Q ✓ R, in fact Q ⇢ R. iii. {x 2 R | x2 x = 2} = { 1, 2} ✓ Z. (iv) ; is a subset of every set. Two sets are equal if they contain exactly the same elements ie. A = B , A ✓ B and B ✓ A. In other words, A = B means ‘x 2 A i↵ x 2 B’. Exercise Which of these statements are true? i. 2 2 {1, 2, 3}. ii. {2} 2 {1, 2, 3}. iii. 2 ✓ {1, 2, 3}. iv. {2} ✓ {1, 2, 3}. v. {2} 2 {1, 2, {2}}. vi. {2} ✓ {1, 2, {2}}. 1.6 Operations on Sets A Universal Set, U , is a set for which all the sets we are considering in a particular example are subsets. In our examples this will often be Z or R. Definition 1.10. Let A and B be subsets of a universal set U. 1. The Intersection of A and B, denoted by A \B, is the set A \ B = {x 2 U | x 2 A and x 2 B}. We say two sets are disjoint if A \ B = ;. 2. The Union of A and B, denoted by A [ B, is the set A [ B = {x 2 U | x 2 A or x 2 B}. 3. The Di↵ erence of A and B, denoted by A\B (or sometimes A the set A\B = {x 2 U | x 2 A and x /2 B}. 4. The Complement of A, denoted by Ac , is the set Ac = {x 2 U | x /2 A}. Remarks. From the definitions the following properties hold for all sets A,B and C: B), is i. A \ (B \ C) = (A \ B) \ C and so we can write A \ B \ C without ambiguity. ii. A [ (B [ C) = (A [ B) [ C and so we can write A [ B [ C without ambiguity. iii. (Ac)c = A. iv. A\B = A \Bc. Let the universal set be Z. Let A = {1, 2, 3, 4}, B = {2k + 1 | k 2 Z} (the set of odd integers) and C = {n 2 Z | i. A \ B, A \ C, B \ C. ii. A [ B, A [ C. iii. A\B, B\C. iv. Bc , Cc. 1.7 Quantifiers 5 n 0}. Write out the following: Many mathematical statements include terms such as ’for all’, ’there exists’, ’for every’, ’there is some’ etc. These are known as quantifiers. They can be used to turn predicates into propositions. Let P (x) be a predicate where x is an element of a set A. There exists We write ‘9x 2 A,P (x)’ to mean ’there exists an element x of A such that P (x) is true’. Examples i. ‘9x 2 R, x2 x2 x 1 = 0’. ii. ‘9n 2 N, n2 + 3 is a prime number’ means ‘there exists a natural number n such that n2 + 3 is a prime number’. For all x 1 = 0’ means ‘there exists a real number x such that We write ‘8x 2 A,P (x)’ to mean ‘for all elements x of A, P (x) is true’. Examples i. ‘8x 2 R, x2 ii. ‘8n 2 Z, n2 > n’ means ‘for all integers n, we have n2 > n’. 0’ means ‘for all real numbers x, we have x2 0’. Statements can involve several quantifiers. The order is IMPORTANT. Examples i. 8x 2 R, 9y 2 R such that x > y. ii. 9y 2 R such that 8x 2 R, x > y. The proposition in (i) is True but the proposition in (ii) is False. Exercises Which of these statements is True? (i) 8n 2 Z, 9m 2 Z such that n+m = 0. (ii) 9n 2 Z such that 8m 2 Z, n+m = 0. (iii) 9x 2 R and 9y 2 R such that xy 0. (iv) 8x 2 R and 8y 2 R, xy 0. (v) 8m 2 Z, 9q 2 Q such that 8n 2 N, (m q)n = 0. Negating statements which contain quantifiers. The negation of the statement ‘All cats are black.’ is ‘There exists some cat that is not black.’ We can see that the ‘for all’ has changed to a ‘there exists’ and the predicate has been negated. We can generalise this as follows: The negation of ‘8x 2 A,P (x)’ is ‘9x 2 A such that ¬P (x)’. Similarly the negation of ‘9x 2 A such that P (x)’ is ‘8x 2 A,¬P (x)’. Examples i. The negation of ‘8x 2 R, x2 ii. The negation of ‘9m 2 Z such that 8n 2 Z, n+m = 0’ is ‘8m 2 Z, 9n 2 Z such that n+m = 0’. 0’ is ‘9x 2 R such that x2 < 0’. 11 Find the negation of (8x 2 R, 9y 2 R such that x+ y = 0) ^ (8x 2 R, x2 = 0 ) x = 0). Remark When we write down the converse or contrapositive of a statement with quanti fiers at the start we don’t change the quantifier. 2 Methods of Proof A proof of a mathematical statement is a clear, logical argument to establish the statement is true. A proof uses a series of implications, starting with some assumptions and ending with a conclusion. In this section we describe di↵erent methods of proof. Some proofs are short and simple, some are long and complex. There is no way of knowing from the statement how di cult the proof will be! In your maths courses you will see many proofs, some containing clever ’tricks’ that make you wonder ’how did they think of that?’. Constructing proofs is a creative process and many proofs take years to perfect. You will be expected to create your own simple proofs and construct proofs based on similar arguments to proofs you’ve seen in lectures. It’s important that you write out proofs clearly so that other people can understand them. The statements we prove will be given names like Theorem 3.4 and Lemma 2.6 etc. Here’s a quick guide to some of the terminology: A Theorem is an important statement for which a proof exists. A Proposition is a (less important) statement for which a proof exists. A Lemma is a proven statement that is not usually of interest in its own right but does a lot of the work required to prove a theorem. A Corollary is a statement that can be easily proved using a Theorem or Proposition. A Conjecture is a statement which is believed to be true but no proof has been found yet. Although there are no guaranteed rules for constructing proofs, there are some standard methods used to provide a structure for a proof. 2.1 Direct Proof A direct proof starts with some assumptions and uses a chain of implications to reach a conclusion. We start by looking at how to write a direct proof to show ‘P ) Q’ is true. We do this by assuming P is true and then show that Q is also true. Proposition 2.1. Let A,B and C be sets. If A ✓ B and B ✓ C, then A ✓ C. 13 Proof Assume that A ✓ B and B ✓ C. Let x 2 A. Then x 2 B because A ✓ B. Hence x 2 C because B ✓ C. We have shown that if x 2 A, then x 2 C. Therefore A ✓ C by definition. ⇤ Before proving the next statement we need some basic properties of the integers. Definition 2.2. Let a and b be integers. We say that a divides b if and only if there is an integer c with b = ac. We write a|b and also say that a is a factor of b or b is a multiple of a. Definition 2.3. An integer a is even if and only if 2 divides a. ie. there exists an integer k such that a = 2k. An integer is odd if and only if it is not even. If a is an odd integer, then it can be written as 2k + 1 for some integer k. Proposition 2.4. For all integers a, b and c, if a|b or a|c, then a|bc. Proof First assume that a|b. Then by definition b = pa for some integer p. Therefore bc = (pc)a and since pc is an integer, this means that a|bc by definition. Next assume that a|c. Then by definition c = qa for some integer q. Therefore bc = (bq)a and since bq is an integer, this means that a|bc by definition. ⇤ In this case the assumption involves an ’or’ and so we have to consider the two cases a|b and a|c separately. Note that ‘(P or Q) ) R’ is logically equivalent to ‘(P ) R) and (Q ) R)’ (see Section 1.3). Exercise Prove that for all integers a, b and c, a|b and a|c implies that a|(b+ c). Proof by contrapositive We know that P ) Q and its contrapositive ¬Q ) ¬P are logically equivalent. Therefore we can prove P ) Q is true by proving the contrapositive is true. This can sometimes be easier. Proposition 2.5. Let a, b, c 2 Z. If a - bc, then a - b and a - c. Proof The contrapositive of ‘If a - bc then a - b and a - c’ is ‘If a|b or a|c, then a|bc’. This is the statement we proved in Proposition 2.4. ⇤ If and only if proofs If we want to prove a statement P , Q, then we have to prove that P ) Q and Q ) P. Proposition 2.6. Let a, b 2 R. Then (a+ b)2 > 4ab if and only if a = b. ProofWe first show that (a+b)2 > 4ab implies a = b. The easiest way to do this is to prove the contrapositive statement a = b implies (a + b)2 4ab. Assume a = b. Then (a + b)2 = (2a)2 = 4a2 = 4ab 4ab. Therefore (a + b)2 > 4ab implies a = b as required. Next we show that a = b implies (a + b)2 > 4ab. Assume a = b. Then a b = 0 and since a, b 2 R we have (a and adding 4ab to both sides we have a2+2ab+b2 > 4ab. Hence (a+b)2 > 4ab, as required. ⇤ b)2 > 0. Therefore a2 Proving and disproving statements involving quantifiers 2ab+ b2 > 0 If we want to prove a statement of the form ‘For all x 2 A,P (x)’ is true, we have to produce a general argument that shows that P (x) is true for every x in the set A. To disprove the statement ie. show it is false, it is enough to find one value of x for which P (x) is false. This is known as a counterexample. On the other hand, to prove a statement of the form ‘There exists x 2 A,P (x)’ is true, it is enough to find a single value of x in A for which P (x) is true. To disprove the statement we have to show that for every x in A, P (x) is false (ie. the negation of P (x) is true). Exercise Prove that the following propositions are true. i. 8x 2 R, x2 + 2x+ 1 ii. 9x 2 R such that x2 + 2x+ 1 > 0. 0. Prove that the following propositions are false. iii. 8x 2 R, x2 + 2x+ 1 > 0. iv. 9x 2 R such that x2 + 2x+ 1 < 0. 15 2.2 Proof by Contradiction Let’s start with an example. Proposition 2.7. There do not exist integers m and n such that 14m+ 20n = 101. We can’t check all possible pairs of integers and there is no obvious way to construct a direct proof. Let’s assume the statement is false and see where that assumption takes us. Proof Assume there exist integers m and n with 14m + 20n = 101. Since 14m+20n = 2(7m+10n), then 14m+20n is an even integer. This means that 101 is an even integer. However we know that 101 = 2⇥50+1 is an odd integer and an integer can’t be both even and odd by definition. We have generated a contradiction. This means that our assumption that the statement was false was incorrect and therefore the statement must be true. ⇤ This method is known as Proof by Contradiction. We can generalise this as follows: To prove a statement P is true using proof by contradiction: i. Assume P is false. ii. Deduce from this assumption a statement that we know is false or that contradicts one of our assumptions. iii. Conclude that the assumption in (i) is false ie. the statement P must be true. Even though it seems a bit strange, proof by contradiction is widely used to prove theorems and there are many famous examples. Recall from section 1 the negation of P ) Q is equivalent to P ^ (¬Q). Lemma 2.8. For any integer n, if n2 is even, then n is even. Proof We use proof by contradiction. Assume that the statement is false ie. the negation is true. Therefore there exists an integer n such that n2 is even and n is odd. We can write n = 2k+1 for some integer k. Then n2 = 4k2+4k+1 = 2(2k2 +2k)+ 1 and this is odd because 2k2 +2k is an integer. This contradicts our assumption that n2 is even. Therefore we have proved that the statement is true. ⇤ Theorem 2.9. p 2 is not a rational number. Proof. We use proof by contradiction. Assume the statement is false, ie. assume p 2 is a rational number. Then we can write p 2 = a/b for some integers a and b, with b = 0. We also assume that we have cancelled all common factors, apart from ±1, from a and b. We can rearrange the expression above to get p 2b = a and squaring both sides gives 2b2 = a2. Since b2 is an integer, this means that 2|a2 and then 2|a by Lemma 2.8. There fore we can write a = 2k for some integer k. Substituting into 2b2 = a2, we get 2b2 = 4k2 and so b2 = 2k2. This means that 2|b2 and so 2|b by Lemma 2.8. However we assumed that a and b have no common factors and so we now have a contradiction. This means that p 2 is not a rational number. 2.3 Proof by Induction ⇤ We are often required to prove a statement about the natural numbers (or a subset of the natural numbers). e. For all n 2 N, 1 + 2 +...+ n = 2n(n+ 1 1). A technique known as Mathematical Induction can be useful in these cases. (Simple) Mathematical Induction Let P (n) be a statement about the natural number n. Suppose we can show that i. P (1) is true (called the Base Case), and ii. for each natural number k, if P (k) is true, then P (k + 1) is true (called the Inductive Step). f. Then P (n) is true for all natural numbers n. We call the assumption that P (k) is true in (ii) the Inductive Hypothesis. Theorem 2.10. For all n 2 N, 1 + 2 +...+ n = 2n(n+ 1 1). 17 Proof. We use proof by induction. Let P (n) be the statement ‘1 + 2 +...+ n = 2n(n+ 1 1)’. The base case is to show that P (1) is true. P (1) is the statement ‘1 = 2 1.1.2’ which is true. For the inductive step let k be any natural number and assume that P (k) is true ie. 1 + 2 +...+ k = 2 1 k(k + 1). We need to show that P (k+1) is true. We add k+1 to both sides of the above expression to get 1 + 2 +...+ k + (k + 1) = 2 1 k(k + 1) + (k + 1) = 2 1 (k + 1)(k + 2). Therefore P (k + 1) is true and we have proved that P (k) ) P (k + 1) for any natural number k. By induction, P (n) is true for all natural numbers n. Note we could have used the notation 1 + 2 +...+ n = nX i. i=1 Induction can be generalised to cases where the base case is greater than 1. Proposition 2.11. For all n 2 N with n ⇤ 4, n2 2n. Proof Using proof by induction, let P (n) be the statement ‘n2 2n’. The base case here is P (4) which is ‘42 24’ and this is true. 4 and assume that P (k) is true, ie. For the inductive step let k 2 N, with k k2 2k. Then (k + 1)2 = k2 + 2k + 1 k2 + 2k + k k2 + 3k k2 + k2 2k + 2k = 2k+1 because k n 4. Exercise 4. Therefore P (k + 1) is true. By induction P (n) is true for all ⇤ Prove that for all natural numbers n, nX i2 = 6n(n+ 1 1)(2n+ 1). i=1 Strong Mathematical Induction A variation on Simple Induction is Strong Induction. In this case we need to assume more than P (k) is true to show that P (k + 1) is true. Let P (n) be a statement about the natural number n. Suppose we can show that i. P (1) is true (and sometimes it is necessary to check P (t) is true for other small values of t); ii. for each k 2 N, if P (1), P (2),... , P (k) are true, then P (k + 1) is true. Then P (n) is true for all natural numbers n. The following example shows how this works. Example The Fibonacci numbers are a famous sequence of numbers which have many fascinating properties. They are defined as follows: a1 = 1, a2 = 1, an+1 = an 1 + an, for all n 2. The sequence starts 1, 1, 2, 3, 5, 8, 13, 21, 34,... Proposition 2.12. Let a1, a2,... be the Fibonacci sequence. For all n an = (↵n where ↵ = (1 +p 5)/2 and (Note that ↵ and ↵2 = ↵ + 1 and 2 = n)/p5, = (1 p 5)/2. are roots of the quadratic equation x2 + 1.) 1 x 1 = 0 and so Proof We use strong induction. For n 2 N, let P (n) be the statement an = (↵n a1 = (↵ n)/p5. For the base case we need to show P (1) is true. P (1) is )/p5 = 1 and this is true. 2)/p5 = 1 and so P (2) Since we know a2 = 1 we can also check a2 = (↵2 is true. For the (strong) inductive step let k 2 N with k 2 and assume that P (1), P (2),... P (k) are true. We have ak+1 = ak 1 + ak by definition and so ak+1 = (↵k 1 k 1)/p5+ (↵k = (↵k 1↵2 k)/p5 = (↵k 1(1+↵) k 1 2)/p5 = (↵k+1 k 1(1+ ))/p5 k+1)/p5. Therefore P (k + 1) is true and by strong induction P (n) is true for all n 2 N. ⇤ 3 Complex Numbers 3.1 Definition of the Complex Numbers In section 1 we defined the standard number sets N,Z,Q and R. We can do addition and multiplication in all these sets. Subtraction is not always defined in N and division is not always defined in Z. In Q and R we can define division apart from division by 0. The integers are an example of a ‘ring’ and the rationals and real numbers are examples of ‘fields’. You will learn more about these in later algebra course units. Let’s consider solutions of polynomial equations with real coe cients. How many solutions (or roots) are there? For a linear polynomial equation ax+ b = 0, where a, b 2 R and a = 0, there is a unique solution (or root) x = R. If a are b are rational numbers, then x will also be rational. However when we consider quadratic equations with rational coe cients the solutions may no longer lie in Q, for example x2 2 = 0, b/a in has roots x = ± p 2. For some quadratic equations there are also no solutions in R, for example x2 + 1 = 0. In this case we define a ‘new number’ i = p 1. This is not a real number but we do have i2 = 1. We call i an imaginary number. In general an imaginary number is any number of the form ia, where a 2 R. Note that x2 + 1 = 0 has two solutions, x = i and x = i. Exercise What are the values of in for any natural number n? We can now solve any quadratic equation ax2 + bx+ c = 0, where a, b, c 2 R and a = 0 using the root formula x= There are 3 cases: 1. If b2 2. If b2 3. If b2 4ac b± p b2 2a. 4ac > 0 we get 2 real roots. 4ac = 0 we get 1 real root (a repeated root). 4ac < 0 we get 2 complex roots. In case 3, the roots can be written as b± p b2 z= where x = 2a 4ac = b± i p 4ac b2 = x± iy b/2a, y = p 4ac 2a b2/2a are real numbers. Definition 3.1. Any number of the form a + ib, where a, b 2 R is called a Complex Number. We denote the set of all complex numbers by C, ie. C = {a+ ib | a, b 2 R}. For a complex number z = a+ib we call a the real part of z and b the imaginary part of z, denoted by Re(z) and Im(z), respectively. We call a+ib the standard form of the complex number. 3.2 Arithmetic of Complex Numbers We can do addition, subtraction and multiplication in C. Let a+ ib, c+ id 2 C. Addition: (a+ ib) + (c+ id) = (a+ c) + i(b+ d) Subtraction: (a+ ib) c. id) = (a c. + i(b d) Multiplication: (a+ ib)(c+ id) = ac+ aid+ ibc+ i2bd = (ac b. + i(ad+ bc) Example Consider z = 1 + 3i and w = 2 5i. Then z + w = (1 + 2) + (3 z w = (1 2) + (3 ( 5))i = 1 + 8i, zw = (1 + 3i)(2 5)i = 3 2i, 5i) = (2 + 15) + ( 5 + 6)i = 17 + i. We can also define division of complex numbers, apart from division by 0. For any complex number z = a+ ib, we define z = a of z. Notice that zz = (a+ ib)(a ib) = a2 + b2 + i(ab ib, called the conjugate ab) = a2 + b2. This enables us to define and simplify division in complex numbers by multiplying the numerator and denominator by the conjugate of the denominator. If a+ ib, c+ id 2 C and c+ id = 0 (ie. c and d are not both 0), we define a+ ib c+ id = (a+ ib)(c (c+ id)(c id) (ac+ bd) + i(bc ad) = id) c2 + d2. Notice that this is well defined because c2 + d2 = 0 and is in the standard form x+ iy for x, y 2 R. Proposition 3.2. Let z, w 2 C. Then i. z + w = z + w ii. zw = z w iii. z 1 = (z) 1. Proof Exercise. 3.3 Representing Complex Numbers We can think of the set of real numbers as being represented by an infinite horizontal line, called the real line. 0 We can represent the complex numbers graphically by extending the real line to the complex plane, ie. we represent z = x + iy by the point (x, y) in this plane. This representation is sometimes called the Argand diagram. We call the x- axis the real axis and the y-axis the imaginary axis. z = x+ iy = (x, y) Im(z) x Re(z) y 0 Using basic trigonometry (see diagram below) we can write z = x+ iy = r cos ✓ + ir sin ✓, where (r, ✓) are the polar co-ordinates of (x, y). We have r = p x2 + y2 (positive square root or 0) and tan ✓ = y/x (unless x = 0 in which case we have ✓ = ⇡ 2 or ✓ = ⇡ 2.) x+ iy x y 0 ✓ r Definition 3.3. We call z = r(cos ✓ + i sin ✓) the polar form of z, where r is the modulus of z and ✓ is the argument of z. We write r = |z| and ✓ = arg(z). Note that the argument of a complex number z is not unique because we can add any integer multiple of 2⇡ to ✓ and this gives the same value of the cosine and sine. We take the principal value of ✓ to be in the range ⇡ < ✓ ⇡ and denote this by Arg(z). Example Find the modulus and the principal value of the argument of a. 3 + 2i, a. |3 + 2i| = p 32 + 22 = p 13, Arg(3 + 2i) = tan 1(2/3) ⇡ 0.588 radians. b. |4i| = 4, Arg(4i) = ⇡/2. c. |p3 i| = p 3 + 1 = 2, Arg(p3 i. = tan 1( 1/p3) = ⇡/6. (b) 4i, (c) p3 i and (d) p 3 + i. (d) | the argument because we have that ⇡/2 < Arg( p 3 + i) < ⇡ and so Arg( p 3 + 1) = tan 1(1/( p 3)) + ⇡ = 5⇡/6. p 3 + i| = p 3 + 1 = 2. In this case we have to be careful with Proposition 3.4. Let z, w 2 C. Then i. |z| = |z| ii. |zw| = |z||w| and arg(zw) = arg(z) + arg(w) iii. |z + w| |z|+ |w| (Triangle Inequality for complex numbers). Proof i. Let z = a + ib. Then z = a p a2 + ( b)2 = |z|. ii. Let z = r(cos ✓ + i sin ✓) and w = s(cos + i sin ). Then zw = rs[cos ✓ cos ib. We have |z| = p a2 + b2 = sin ✓ sin +i(cos ✓ sin +sin ✓ cos )] = rs[cos(✓+ )+i sin(✓+ )]. By definition we have |zw| = rs = |z||w| and arg(zw) = ✓ + arg(z) + arg(w) (iii) Let z = a+ ib, w = c+ id. We have 0 (ad Therefore 2abcd a2d2 + b2c2. = bc)2 because a, b, c, d 2 R. Adding a2c2 + b2d2 to each side we get a2c2 + b2d2 + 2abcd a2c2 + b2d2 + a2d2 + b2c2 (ac+ bd)2 (a2 + b2)(c2 + d2). and hence Square rooting we get ac+ bd p a2 + b2 p c2 + d2. Then |z + w|2 = (a+ c)2 + (b+ d)2 = a2 + c2 + 2ac+ b2 + d2 + 2bd a2 + b2 + c2 + d2 + 2 p a2 + b2 p c2 + d2 = (|z|+ |w|)2. Square rooting and noting that the modulus is always non-negative we get |z + w| |z|+ |w| as required. 3.4 Powers ⇤ We start by looking at positive integer powers of a complex number. We have the following result. Theorem 3.5. (DeMoivre’s Theorem) Let z = r(cos ✓ + i sin ✓ ). For all n 2 N we have zn = rn(cos(n✓) + i sin(n✓)). Proof We use proof by induction. Let P (n) be the statement zn = rn(cos(n✓) + i sin(n✓)). The base case, n = 1 holds because z = r(cos ✓ + i sin ✓). Assume that k 2 N and that P (k) is true, ie. zk = rk(cos(k✓) + i sin(k✓)). Then zk+1 = zzk = [r(cos ✓ + i sin ✓)][rk(cos(k✓) + i sin(k✓))] = rk+1[cos ✓ cos(k✓) sin ✓ sin(k✓) + i(cos ✓ sin(k✓) + sin ✓ cos(k✓))] = rk+1[cos((k + 1)✓) + i sin((k + 1)✓)] using standard trigonometric identities. Therefore P (k + 1) is true and by in duction P (n) is true for all n 2 N. ⇤ Corollary 3.6. Let z = r(cos ✓ + i sin ✓ ). For all n 2 Z, zn = rn(cos(n✓) + i sin(n✓)). Proof. We have shown the statement is true for positive n by Theorem 3.5. The statement holds for n = 0 because 1 = z0 = r0(cos 0 + i sin 0). Assume n < 0 and let k = n. Then zn=z k = 1/zk and so zn = rk(cos(k✓) 1 + i sin(k✓)) = [rk(cos(k✓) + rk(cos(k✓) i sin(k✓))][rk(cos(k✓) i sin(k✓)) = r k(cos(k✓) i sin(k✓))] ⇤ i sin(k✓)) = rn(cos(n✓) + i sin(n✓)). We can extend this result to all real number powers by defining for any z = r(cos ✓ + i sin ✓) and any a 2 R, za = ra(cos(a✓) + i sin(a✓)). 3.5 Roots Let z, w 2 C be such that z = r(cos ✓+ i sin ✓) and let wn = z for some n 2 N. Then w =zn1=r n1 cos ✓ n ✓ ◆ + i sin ✓ n ✓ ◆. However w is not unique because for any complex number we can add any integer multiple of 2⇡ to the argument without changing its value ie. z = rn[cos(✓ + 2⇡k) + i sin(✓ + 2⇡k)] for any k 2 Z. Therefore w =r n1 cos ✓ ✓ + n 2⇡k ◆ + i sin ✓ ✓ + n 2⇡k ◆. This gives distinct values for k = 0, 1,..., n z n , ie. n distinct n-th roots of z. 1 Example Find the cube roots of 2i. We have 1 and so there are n solutions for 2i = 2 h cos ⇣⇡ 2 + 2⇡k ⌘ + i sin ⇣⇡ 2 + 2⇡k ⌘i for any k 2 Z. Therefore (2i) 3 1 = 2 3 1 cos ✓ ⇡ 6 + 2⇡k 3 ◆ + i sin ✓ ⇡ 6 + 2⇡k 3 ◆. Taking k = 0, 1, 2 we get 3 cube roots w1 = 2 3 1 h cos ⇣⇡ 6 ⌘ + i sin ⇣⇡ 6 ⌘i , w2 = 2 3 1 cos ✓ 5⇡ 6 ◆ + i sin ✓ 5⇡ 6 ◆ , w3 = 2 3 1 cos ✓ 3⇡ 2 ◆ + i sin ✓ 3⇡ 2 ◆. We can see that all the roots have the same modulus, 2 3 1 (the real cube root of 2) and on the Argand diagram they are positioned equidistant on the circle centre 0, radius 2 3 1. w2 0 w3 w1 231 Exercise Find the fifth roots of 3. Exponential Form and Euler’s Formula There is one more form of a complex number, called the exponential form. For this we need Euler’s formula: ei✓ = cos ✓ + i sin ✓, for any ✓ 2 R. We can’t prove this here because we need to use power series and these are not covered in this course. If we let ✓ = ⇡ we get the famous e. + 1 = 0, ne of the most beautiful expressions in mathematics. Using Euler’s formula we can write any complex number z as z = rei✓ where r = |z| and ✓ = arg(z). Example Find the roots of the quadratic equation iz2 + z We can use the quadratic root formula z= 2 + i = 0. b± p b2 2a 4ac 1± p 1 4i( 2 + i) = 2i = We need to find the square roots of 5 + 8i. We can write 5 + 8i = p 89ei(✓+2⇡k) where ✓ = tan 1(8/5) and k 2 Z. Then This gives 1± p 5 + 8i 2i z⇡. + 8i) 2 1 = 89 4 1 ei(✓/2+⇡k) ⇡ ±(2.69 + 1.49i). 1. (2.69 + 1.49i) i. (1.49 2.69i) 2i z ⇡ 0.75 = 2, 0.85i, 0.75 + 1.85i. We finish this section by stating one of the most important results about polyno mials, the Fundamental Theorem of Algebra. We are not in a position to prove this theorem yet but it answers the question we set out at the beginning of the section about finding roots of polynomials. Theorem 3.7. (The Fundamental Theorem of Algebra) Let n 2 N and let a0 + a1z + a2z 2 +...+ anz n be a polynomial of degree n where a0, a1, a2,...an 2 C and an = 0. Then this polynomial has exactly n complex roots, although some may be repeated. 4 Functions Before we define functions we return to some set theory. 4.1 Cartesian Products of Sets Definition 4.1. Let A and B be non-empty sets. The Cartesian Product of A and B, denoted by A⇥ B, is the set of ordered pairs, A⇥ B = {(a, b) | a 2 A, b 2 B}. If A or B is the empty set, then A⇥ B = ;. In an ordered pair, the order matters and so (a, b) = (b, a) unless a = b. We write A2 for A⇥ A. eg. R2 = {(x, y) | x, y 2 R} is the set of points in the Cartesian plane. Examples i. Let A = {1, 2} and B = {1, 2, 3}. Then A. B = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3)}. ii. {(x, y) 2 R2 | x2 + y2 = 1} is the set of points in the unit circle in R2. iii. (Z⇥ {3}) \ ({1}⇥ Z) = {(1, 3)} = {1}⇥ {3}. Remarks 1. We can identify R⇥R with the set of complex numbers C. We do this when we plot the complex number a+ ib on the Argand diagram at the point (a, b). 2. In general if n is any natural number with n 2 we can define An = A⇥...⇥ A = {(a1, a2,... , an) | a1, a2,... , an 2 A}. | {z } n Proposition 4.2. For all sets A,B,C and D, i. A⇥ (B [ C) = (A⇥ B) [ (A⇥ C), ii. (A⇥ B) [ (C ⇥D) ✓ (A [ C)⇥ (B [D). Proof. See Exercise Sheet 4. 4.2 Relations and Equivalence Relations Definition 4.3. Let A be a set. A relation on A is a subset R of A⇥ A. We write a ⇠ b to denote that (a, b) 2 R. An equivalence relation on A is a relation R with the following properties: i. Reflexive: 8a 2 A, a ⇠ a. ii. Symmetric: 8a, b 2 A, a ⇠ b ) b ⇠ a iii. Transitive: 8a, b, c 2 A, a ⇠ b and b ⇠ c ) a ⇠ c. Examples The following are relations on Z. (i) R = {(1, 1), (2, 2), (1, 2)} (ii) For all a, b 2 Z, a ⇠ b i↵ a < b. Then R = {(a, b) 2 Z⇥ Z | a < b}. (iii) Let n 2 N. For all a, b 2 Z, a ⇠ b i↵ n divides a b. The relations in (i) and (ii) are not equivalence relations. The relation in (iii) is an equivalence relation. If a ⇠ b we say that a is congruent to b modulo n and write a ⌘ b mod n. This relation is the basis of modular arithmetic. 4.3 Functions In this section we formalise the idea of a function. You will be used to seeing ‘functions’ given as formulas (eg. f(x) = x2 , g(x) = sin(x)), usually defined on the real numbers but functions are much more general than this. Definition 4.4. Let A and B be sets. A function f from A to B is a rule that assigns to each element of A a unique element of B. We write f : A ! B. A is called the Domain of the function and B is called the Codomain. For every a 2 A we let f(a) denote the unique element of B that f assigns to a. We call f(a) the image of a under f. Note: the domain and codomain are an essential part of the function. If we change either one of these we get a di↵erent function. Examples (i) Let A = {1, 2, 3, 4} and B = {5, 6, 7} and define f : A ! B by f(1) = 5, f(2) = 6, f(3) = 6, f(4) = 5. ii. Let A = B = R and define f : R ! R by f(x) = sin(x), for all x 2 R. iii. For any set A the Identity function on A is IA : A ! A defined by IA(a) = a, for all a 2 A. iv. The map f : R+ ! R defined by f(x) = x1/2 is not a function because for each x 2 R+ , x has two square roots. v. The map g : R ! R defined by g(x) = 1/x is not a function. However h : R\{0} ! R defined by h(x) = 1/x is a function. Definition 4.5. Let f : A ! B be a function. 1. If f : A ! B is a function and C is a subset of A we can define the restriction of f to C as f |C : C ! B, given by f |C(x) = f(x), for all x 2 C. 2. The Image of f , denoted by Imf (or sometimes f(A)), is the set Imf = {f(a) | a 2 A} ✓ B. 3. The Graph of f is the set Gf = {(x, y) 2 A⇥ B | y = f(x)}. (This is sometimes used as an alternative way to define a function.) Exercise Write down functions with the given domain and image. 1. The domain is Z and the image is N. 2. The domain is N and the image is {1, 2, 3, 4}. 4.4 Injective (or 1-1) Functions Definition 4.6. A function f : A ! B is injective if 8x, y 2 A, f(x) = f(y) ) x = y. Another name for an injective function is a 1-1 (one-to-one) function. So an injective function is one where the function values are all distinct. Examples (i) Let A = {1, 2, 3, 4} and B = {5, 6, 7} and define f : A ! B by f(1) = 5, f(2) = 6, f(3) = 6, f(4) = 5. This function is not injective because f(1) = f(4). (ii) Let g : Z ! Z be defined by g(x) = x+ 3, for all x 2 Z. This function is injective because if x, y 2 Z with g(x) = g(y) we have x+ 3 = y + 3 and so x = y. (iii) Let h : Z ! R be defined by h(x) = x/(x2 + 1), for all x 2 Z. Then h(x) = h(y) ) x2 x + 1 = y2 y + 1 ) x(y2 + 1) = y(x2 + 1) ) (xy Therefore either xy 1)(x y) = 0. 1 = 0 which means that x = y = 1 or x = y = 1, y = 0. Therefore in all cases x = y and we have shown that for all x, y 2 Z, h(x) = h(y) ) x = y. Therefore h is injective. or x Exercise Which of the following functions are injective? i. f : Z ! Z defined by f(n) = 2 ii. g : N ! N defined by g(n) = n2 for all n 2 N iii. h : C ! R defined by h(x) = |x| for all x 2 C. n for all n 2 Z 4.5 Surjective (or onto) Functions Definition 4.7. A function f : A ! B is surjective if Imf = B. This means that 8y 2 B, 9x 2 A, such that y = f(x). Another name for a surjective function is an onto function. Examples (i) Let A = {1, 2, 3, 4} and B = {5, 6, 7} and define f : A ! B by f(1) = 5, f(2) = 6, f(3) = 6, f(4) = 5. This function is not surjective because 7 is not in the image of f. ii. Let g : Z ! Z be defined by g(x) = x+ 3, for all x 2 Z. This function is surjective because if y 2 Z (codomain), then y = g(y 3. and y (domain). 32Z (iii) Let h : Z ! R be defined by h(x) = x/(x2 + 1), for all x 2 R. Since x2 + 1 > |x| for all x 2 Z we have |h(x)| < 1 for all x 2 Z. Therefore h is not surjective. 4.6 Bijections Definition 4.8. A function f is a bijection if it is both injective and surjective. If we have a bijection f : A ! B we say that there is a one-to-one corre spondence between A and B. This means we can pair up the elements of A with the elements of B, x $ f(x), 8x 2 A. Examples i. The function g above is a bijection. Each integer is paired with the integer 3 greater than it. ii. f : R ! R given by f(x) = x3 , 8x 2 R is a bijection. Exercise Which of the following functions are bijections? i. f : {1, 2, 3} ! {1, 2, 3} defined by f(1) = 2, f(2) = 3, f(3) = 1. ii. g : N ! Z defined by g(n) = n/2 if n is even and g(n) = n is odd. 4.7 Composition of Functions (n 1)/2 if Definition 4.9. Let f : A ! B and g : B ! C be functions. The composite function, g f , of g and f is such that g f(a) = g(f(a)) for all a 2 A. Note that g f : A ! C. Examples (i) Let A = {1, 2, 3}, B = {3, 4, 5}, C = {2, 4, 6} and define f : A ! B, g : B ! C by f(1) = 5, f(2) = 3, f(3) = 4 g(3) = 2, g(4) = 6, g(5) = 4. Then g f : A ! C is given by g f(1) = 4, g f(2) = 2, g f(3) = 6. (ii) Define f : R ! R by f(x) = x2 and g : R ! R by g(x) = 3x+ 1, for all x 2 R. Then we can define f f : R ! R, given by f f(x) = f(f(x)) = x4 , for all x 2 R, f g : R ! R, given by f g(x) g f : R ! R, given by g f(x) = g(f(x)) = 3x2 + 1, for all x 2 R, g g : R ! R, given by g g(x) = g(g(x)) = 3(3x+1)+ 1 = 9x+4, for all x 2 R. f(g(x)) = (3x+ 1)2, for all x 2 R, Theorem 4.10. Let f : A ! B and g : B ! C be functions. (i) If f and g are both injective, then g f is injective. ii. If f and g are both surjective, then g f is surjective. iii. If f and g are both bijections, then g f is a bijection. Proof. (i) Assume that f and g are injective. Assume that g f(x) = g f(y) for some x, y 2 A. Then g(f(x)) = g(f(y)) and since g is injective it follows from the definition that f(x) = f(y). Since f is injective, this implies that x = y. Therefore g f is injective by definition. ii. See Exercise Sheet 4. iii. This follows from (i) and (ii). Let f : A ! B, g : B ! C and h : C ! D be functions. Then h (g f)(x) = h(g f(x)) = h(g(f(x))) = (h g) f(x). ⇤ Hence composition of functions is associative and we can simply write h g f. 4.8 Inverse Functions Let f : A ! B be a function. We say that f is invertible if there exists a function f 1 : B ! A such that f 1 f is the identity function on A and f f 1 is the identity function on B. We call f 1 the inverse of f. Remarks i. An inverse function f 1 does not exist for all functions (see the next result). ii. For a given function f , if f 1 exists, then it is unique. iii. If f 1 exists, it is also invertible and (f 1) 1 = f. Theorem 4.11. A function f : A ! B is invertible if and only if f is a bijection. Proof. Assume that f is invertible with inverse f 1 : B ! A. Let f(a1) = f(a2) for some a1, a2 2 A. Then f 1(f(a1)) = f 1((f(a2)) and so a1 = a2. Therefore f is injective. Let b 2 B with a = f 1(b) 2 A. Then f(a) = b and so f is surjective. Therefore f is a bijection. Conversely assume that f is a bijection. Let b 2 B. Since f is surjective, there exists a 2 A with f(a) = b and since f is injective, a is unique. Therefore we can define f 1(b) = a. This defines the function f 1 : B ! A. For a 2 A, let f(a) = b. Then f 1 f(a) = f 1(b) = a. For b 2 B, let a be the unique element in A such that f(a) = b. Then f f 1(b) = f(a) = b. Therefore f 1 is the inverse of f. ⇤ Examples (i) Let A = {1, 2, 3}, B = {3, 4, 5} and define f : A ! B by f(1) = 5, f(2) = 3, f(3) = 4. Then f 1 : B ! A is defined by f 1(3) = 2, f 1(4) = 3, f 1(5) = 1. ii. Let g : Z ! Z be defined by g(x) = x+3, for all x 2 Z. Then g 1 : Z ! Z is defined by g 1(x) = x 3. for all x 2 Z. iii. Let h : R ! R given by h(x) = x3 , 8x 2 R. Then h 1 : R ! R is given by h 1(x) = x1/3 , the unique real cube root of x for all x 2 R. iv. The function f1 : R ! R defined by f1(x) = sin(x) is neither injective nor surjective and so it does not have an inverse. However if we consider the function f2 : [ ⇡/2, ⇡/2] ! [ 1, 1] defined by f2(x) = sin(x), this is a bijection and we can define the inverse function f 2 1 : [ 1, 1] ! [ ⇡/2, ⇡/2] by f 2 1 (x) = sin 1(x). Exercise Assume that f : A ! B and g : B ! C are bijections. What is the inverse of g f? 5 Cardinality of Sets 5.1 Finite Sets For finite sets it is relatively straightforward to define the cardinality as the number of elements in the set. However we introduce a rigorous definition of cardinality to allow us to generalize this to infinite sets. For any n 2 N define Nn = {1, 2, 3,... , n} = {k 2 N| 1 k n}. Definition 5.1. Let A be a set. We say that A has cardinality n if there exists a bijection f : Nn ! A and we write |A| = n. Define |;| = 0. Instead of directly counting the elements in A we are pairing them up with the elements of Nn. Alternatively we can think of this as a labelling of the elements in A as a1, a2,... , an, where f(i) = ai for all i = 1,..., n. Example Let A = {3, ⇡, 1.4, p 2} and define f : N4 ! A by f(1) = 3, f(2) = ⇡, f(3) = 1.4, f(4) = p 2. Then f is a bijection and |A| = 4. Notice that f is not the only bijection between the two sets. In the definition of cardinality, the bijection f is not unique and so we need to check that cardinality is well-defined ie. we need to exclude the possibility that there is some other bijection g : Nm ! A with m = n. Lemma 5.2. Let m,n 2 N. If there is an injective function f : Nm ! Nn, then m n. Proof (not examinable) We use induction on m. For m 2 N let P (m) be the statement ’8n 2 N, if there is an injective function f : Nm ! Nn, then m n.’ For m = 1 we have m n for all n 2 N and so P (1) is true. Let k 2 N and suppose P (k) is true. Let n 2 N and assume we have an injective 2 (otherwise n = 1 function f : Nk+1 ! Nn. Then n 2 because k + 1 would mean f(1) = f(2) = 1 and then f is not injective). Let b = f(k + 1) and define f1 : Nk ! Nn\{b} by f1(x) = f(x). Since f is 2 we can define g : Nn\{b} ! Nn 1 injective, then f1 will be injective. Since n by g(x) = ⇢ x x 1 if x b if x 1 b+ 1. Then g is a bijection because its inverse is g 1 : Nn 1 ! Nn\{b} defined by g 1(x) = ⇢ x+ x 1 if x b if x 1 b. In particular g is injective. Hence g f1 : Nk ! Nn 1 is injective by Theorem 4.9. By the inductive hypothesis we must have k n 1. Hence k+1 n and P (k + 1) is true. By induction P (m) is true for all m 2 N. ⇤ Theorem 5.3. Let A be a set and suppose that m,n 2 N. If there are bijections f : Nm ! A and g : Nn ! A, then m = n. Proof (not examinable) Assume there are bijections f : Nm ! A and g : Nn ! A. Then g 1 f : Nm ! Nn is a bijection and therefore is injective. By Lemma 5.2 m n. By the same argument, f 1 g : Nn ! Nm is injective and so n m. Hence m = n as required. ⇤ Corollary 5.4. Let A and B be finite sets. If there exists an injection f : A ! B, then |A| |B|. Further, if f is a bijection, then |A| = |B|. Proof. Assume there exists an injection f : A ! B. If A = ;, then the result is true because |A| = 0 |B| for any set B. Assume A = ; and so B = ;. Let |A| = m, |B| = n for somem,n 2 N. Therefore there are bijections g : Nm ! A and h : Nn ! B. Then h 1 f g : Nm ! Nn is injective by Theorem 4.9. By Lemma 5.2, m n. If f is a bijection we can apply a similar argument to f 1 : B ! A to show that n m. The contrapositive of Corollary 5.4 is Theorem 5.5. (The Pigeonhole Principle) Let A,B be finite sets. If f : A ! B and |A| > |B|, then f is not injective. ⇤ The Pigeonhole Principle means that if |A| > |B|, then for any function f : A ! B there exist a1, a2 2 A with a1 = a2 and f(a1) = f(a2). For example, if there are more than 12 people in a room there will be two people who have their birthday in the same month. Exercise Suppose that a room contains n people where n two people with the same number of friends in the room (we assume that if a is friends with b, then b is friends with a). 2. Then there are at least Theorem 5.6. Let A and B be disjoint, finite sets (ie. A \B = ;). Then |A [B| = |A|+ |B|. Proof. If |A| = 0, then A = ; and A [ B = B, so the result holds. Similarly if |B| = 0. Suppose that |A| = m > 0 and |B| = n > 0. Then there exist bijections f : Nm ! A and g : Nn ! B. Define h : Nm+n ! A [B by h(i) = ⇢ g(i f(i) m) if 1 i m if m+ 1 i m+ n Then h is a bijection because it has an inverse h 1 : A [B ! Nm+n defined by h 1(x) = ⇢ g f 1(x) 1(x) +m if x 2 A if x 2 B. This is well-defined because A \ B = ;. Therefore |A [ B| = |A| + |B| as required. Corollary 5.7. Let A1, A2,... , An be pairwise disjoint, finite sets. Then |A1 [... [ An| = nX |Ai|. i=1 ⇤ Proof Use induction and Theorem 5.6. ⇤ Theorem 5.8. (Inclusion-exclusion principle) Let A and B be finite sets. Then |A [ B| = |A|+ |B| |A \ B|. Proof. We can write A [ B = (A\B) [ (B\A) [ (A \ B), a union of pairwise disjoint sets. By Corollary 5.7, |A [ B| = |A\B|+ |B\A|+ |A \ B|. Since A = (A\B) [ (A \ B), a union of disjoint sets, Theorem 5.6 gives |A| = |A\B|+ |A \B|. Similarly we have |B| = |B\A|+ |A \ B|. Putting this all together we get |A [ B| = |A| |A \B|+ |B| |A \B|+ |A \ B| = |A|+ |B| |A \B|. ⇤. We can extend this result to the union of more than two sets. For three sets we get |A [B [ C| = |A|+ |B|+ |C| (See Exercise Sheet 5.) 5.2 Infinite Sets |A \B| |A \ C| |B \ C|+ |A \B \ C|. Definition 5.9. Two sets A and B are said to be Equipotent if there exists a bijection between A and B. So two finite sets A and B are equipotent i↵ |A| = |B|. Example The open intervals (0, 1) and (0, 2) are equipotent because f : (0, 1) ! (0, 2) defined by f(x) = 2x is a bijection. Definition 5.10. A set A is said to be Denumerable if and only if there exists a bijection f : N ! A. In this case we write |A| = @0 (Aleph-zero). We say a set A is Countable if and only if A is finite or denumerable. A set A is denumerable if and only if we can write the elements of A as an infinite list, ie. A = {a1, a2,...}. (Here the bijection f : N ! A is defined by f(i) = ai for all i 2 N.) Any subset of a denumerable set will be countable because we can list the elements of the subset which defines a bijection with N or Nn for some n 2 N. Examples i. The set A = {2k | k 2 N} of even positive integers is denumerable. The function f : N ! A defined by f(k) = 2k for all k 2 N, is a bijection. ii. The set B = {k2 | k 2 N} of squares is denumerable. The function f : N ! B defined by f(k) = k2 for all k 2 N is a bijection. iii. Z is denumerable. The function f : N ! Z defined by f(n) = n/2 if n is even and f(n) = (n 1)/2 if n is odd, is a bijection. Theorem 5.11. (Dedekind) A set A is infinite if and only if it is equipotent to a proper subset of itself.(ie. equipotent to B with B $ A). Proof Omitted. Proposition 5.12. Let A,B be countable sets. Then A [ B and A ⇥ B are countable. Proof Let A and B be countable sets. Then they are finite or denumerable. We can write A = {a1, a2,... }, B = {b1, b2,...} (finite or infinite list of elements). Then A [ B = {a1, b1, a2, b2,...} and if we delete any repetitions of elements this gives the elements of A [ B as a list. Therefore A [B is countable. Write the elements of A⇥ B in an array: (a1, b1) (a2, b1) (a3, b1)... (a1, b2) (a2, b2) (a3, b2)... (a1, b3) (a2, b3) (a3, b3)............... By moving diagonally through the array we can list the elements of A⇥ B and so A⇥ B is countable. Corollary 5.13. If A1, A2,... , An are countable, then A1 [... [ An and A1 ⇥...⇥ An are countable. Proof Omitted (use induction and Proposition 5.12). Theorem 5.14. (Cantor 1874) Q is denumerable. ⇤ Proof Since Z is denumerable, then Z ⇥ Z is countable by Proposition 5.12. However Q = {a/b | a, b 2 Z, b > 0, a, b are coprime} is in one-to-one correspon dence with the set {(a, b) | a, b 2 Z, b > 0, a, b are coprime}. This is a subset of Z⇥ Z and so Q is countable. Since Q is infinite it is denumerable. ⇤. 5.3 Cardinality of the Real Numbers Recall from section 1 that we defined the set of real numbers R as the set of all finite and infinite decimal expressions. Note that these representations are not unique eg. 0.999... = 1.000... Theorem 5.15. (Cantor 1874) R is uncountable. Proof We will show that the closed interval [0, 1] = {x 2 R | 0 x 1} is uncountable. The result will then follow because any subset of a countable set is countable. Write each x 2 [0, 1] as a decimal 0.↵1↵2... where ↵i 2 {0, 1,... , 9}, for all i 2 N. We use proof by contradiction. Assume that [0, 1] is countable. It cannot be finite because it contains the infinite subset {1/2, 1/3, 1/4,...} and so we may assume that [0, 1] is denumerable. Therefore there exists a bijection f : N ! [0, 1] and we can list all the elements in [0, 1] as follows a1 = 0.a11a12a13... a2 = 0.a21a22a23... a3 = 0.a31a32a33....... Choose b 2 [0, 1] with b = 0.b1b2... such that bn = 2 if ann = 1 and bn = 1 if ann = 1. Then b = an for all n 2 N because bn = ann. Hence b is not in our list and we have a contradiction. Therefore [0, 1] and R are uncountable. ⇤ Since N ⇢ R, Theorem 5.15 tells us that the cardinality of R is greater than @0. We have shown that @0 = |N| = |Z| = |Q| < |R|. The cardinality of R is usually denoted by c (c for the continuum). This raises many new questions. What is the cardinality of R ⇥ R? Are there any sets with cardinality between @0 and c? Are there any sets A with |A| > c? Cantor answered the first question. Theorem 5.16. |R ⇥ R| = c Cantor conjectured that there were no sets A with @0 < |A| < c but could not find a proof. In 1963 Paul Cohen showed that this question was undecidable ie. a proof could not be found. However Cantor was able to answer the third question using the power set, P(A), of a set A. Definition 5.17. For any set A, the power set P(A) is the set of all subsets of A. P(A) = {B | B ✓ A}. Example If A = {1, 2}, then P(A) = {;, {1}, {2}, {1, 2}}. Theorem 5.18. For any set A, |P(A)| > |A|. Proof See Exercise Sheet 5 question 10. This means that |P(R)| > |R| and there are greater infinities than c. Using power sets we can find infinitely many infinities. 6. Introduction to analysis §6.1 How this part of the course will be taught As with the first part of this course, there are 4 lectures per week and some additional videos on the course Blackboard page. Each week has an Exercise Sheet with: (i) Homework that you should do and hand in to be marked by your supervisor, (ii) supervision work that will be discussed in the supervisions, (iii) extra exercises to be done in your own time or as part of your revision. As you will see, Analysis contains a lot of theory. It will be important for you to have lots of examples to hand which will help you understand the theory. There is an important distinc tion here in how the term ‘example’ is used in university-level mathematics, particularly in pure mathematics, and how it is used at A-level or high school. At A-level or high school, you are often taught a method for working something out (maybe how to use the quadratic formula or how to differentiate using the chain rule); you then see lots of ‘examples’ of using this method. At university, you will see lots of very formal definitions and precisely formulated theorems. An ‘example’ is then ‘a thing that satisfies (or not) this definition’ or ‘something to which this theorem applies (or not)’. In university-level mathematics, and certainly in pure maths, the emphasis is far more on developing theory and knowing that you can apply it rather than on practising methods. It is normal in mathematics to write in the first person plural (you will have seen this in other courses as ’We now prove...’ or ’We will define...’, etc). In these notes we continue with this convention (and you should do it in the work you hand in for supervisions too!). But there are also times where it says ‘you’, and these are places where you are explicitly encouraged to try to do something yourself. There are also some places where it says ‘I’, and these are places where I am giving you my own personal opinion (and other mathematicians, including yourselves, may have different opinions—and that is absolutely fine!) The end of a proof is denoted, as normal, by 2. Some of the examples we study are quite long; to make it clear that we have finished discussing an example we denote the end of an example by ⋄. In a definition I have bolded the term or terms being defined. §6.2 What is Analysis? In the first part of this course, you’ve seen the basics of how mathematicians think, do, and talk about mathematics. The goal of this part of the course is to put all of the things that you’ve learned so far into practice in the area of mathematics called Analysis. When you studied mathematics before University you will have become familiar with cal culus, i.e. how to differentiate and integrate functions. Analysis provides the theoretical underpinnings of why calculus works. Many students find Analysis difficult. It often seems to involve spending an extremely long time proving things that you already intuitively know. You will often feel lost and stuck. This is normal! I very strongly encourage you to read the book ‘How to think about Analysis’ by Lara Alcock, which goes into far more detail about students’ experiences with Analysis. Analysis is also very ‘hands-on’: as well as studying the material presented in the classes, etc, you must do the exercises and work in the supervision groups. Just sitting passively in the classes (or, worse, just passively reading these notes) will not work (and there is a lot of empirical evidence to support this!). We said that Analysis is the theoretical underpinning of calculus. Analysis is really the theoretical underpinning of ‘limiting behaviour’ or ‘taking limits’. For example, suppose we want to differentiate f(x) = x2 from first principles. We want to calculate the gradient of the function f at the point x0. So we look at a point close x0, call it x0 + h where we think of h as being very small. We then draw in the straight line between (x0, f(x0)) and (x0 + h, f(x0 + h)) and think of this as an approximation to the tangent at x0. (x0, f(x0)) (x0 + h, f(x0 + h)) Figure : 6.1 We can calculate the slope of this straight line as: f(x0 + h)− f(x0) (x0 + h)− x0 = = (x0 + h)2 − x20 h x20 + 2x0h+ h2 − x20 h = 2x0 + h. As the point x0 + h gets closer and closer to x0, we get a better and better approximation to the tangent at the point x0. We are ‘taking the limit as h tends to 0’. We define the derivative of f at x0 to be this limit. Indeed, we define f ′(x0) := h→0 lim f(x0 (x0 + + h)− h)− f(x0) x0 = lim 2x0 + h h→0 = 2x0. (2.1) (2.2) (2.3) We’ve now rediscovered that the derivative of x2 is 2x, which I hope is not a surprise! A crucial step in understanding Analysis is to realise that in taking the limit (going from (2.2) to (2.3)) we are not just setting h = 0. We’re asking instead: what is the limiting behaviour of (2.2) as we let h become smaller and smaller? We will formulate what taking the limit of a function means later (and you’ll see how to apply it to differentiation next semester). We will come back to limits of functions later in the course when we study continuous functions in Week 10. Before we do that, we will study something that is a bit easier than functions, but is incredibly important: namely, asking whether a sequence of numbers converges. A sequence is a infinite list of numbers (which could be real numbers or complex numbers). Earlier in the course you met different notions of what it means to be ‘infinite’; here we mean a denumerable list of numbers. For example, the following are sequences: i. 1, 1/2, 1/3, 1/4,... , 1/n,... , ii. 1,−1, 1,−1, 1,−1, 1,... , (−1)n,... , iii. 1, 2, 4, 8, 16,... , 2n,.... In Sections 8, 9 and 10 we will discuss sequences, and what it means for a sequence to converge, in far more detail. Intuitively, which of the above sequences do you think converges and what do you think the limit of that sequence is? Before we talk about sequences and continuous functions, we need two digressions, the first a reminder about inequalities and the second about bounds on sets. §6.3 Inequalities In Analysis we will use inequalities a lot! You should know that for real numbers x, y and c i. if c > 0 we have x < y implies cx < cy; ii. if x < y then −y < −x; iii. if 0 < x < y then 1/y < 1/x. iv. ⌊y⌋ denotes the greatest integer less than or equal to y. We call ⌊y⌋ the floor of y and we have ⌊y⌋ ≤ y < ⌊y⌋+ 1. v. You should also know the Triangle Inequality, which we state below for completeness. (You saw the proof of this (for real numbers) on Exercise Sheet 2, question 4.) Proposition 6.3.1 (The Triangle Inequality) Let z, w ∈ C. Then |z + w| ≤ |z|+ |w|. We will also use the following result. (3.1) Proposition 6.3.2 (The Reverse Triangle Inequality) Let z, w ∈ C. Then ||z| − |w|| ≤ |z − w|. (3.2) Remark. Of course, the Triangle Inequality and Reverse Triangle Inequality also hold if z, w are real numbers (because real numbers are a subset of the complex numbers). Proof of Proposition 6.3.2. (Not Examinable) Let z, w ∈ C. Then Hence We also have Hence z. = |(z − w) + w| ≤ |z − w|+ |w| by the Triangle Inequality z. − |w| ≤ |z − w|. w. = |(w − z) + z| ≤ |w − z|+ |z| by the Triangle Inequality = |z − w|+ |z| as |w − z| = | − (z − w)| = |z − w|. |w| − |z| ≤ |z − w|. −|z − w| ≤ |z| − |w|. We can rearrange (3.4) as From (3.3) and (3.5) we have −|z − w| ≤ |z| − |w| ≤ |z − w|. (3.3) (3.4) (3.5) (3.6) Recall that for real numbers x, y, we have that −y ≤ x ≤ y is equivalent to |x| ≤ y. Hence we can write (3.6) as ||z| − |w|| ≤ |z − w|. 2 Remark. In the Triangle Inequality and in the Reverse Triangle Inequality in the context of complex numbers, we have relationships such as |z| ≤ |w|. Note that |z| and |w| are real numbers and it makes sense to say if one real number is greater than or less than another. You might ask if we could write expressions such as z ≤ w for complex numbers z, w ∈ C. This is not possible; see the optional video in the Week 5 folder for details. 7. Bounds on sets In this section we define what it means for a set of real numbers or complex numbers to be bounded. We will also define the supremum and infimum of a subset of the real numbers, generalising the idea of the maximum and minimum of a set in a mathematically precise way. §7.1 Number systems Here is a quick reminder of the different number systems that you have seen so far. i. The set of natural numbers, denoted by N, is the set {1, 2, 3,...}. ii. The set of integers, denoted by Z, is the set {... ,−2,−1, 0, 1, 2,...}. iii. The set of real numbers, denoted by R, can be thought of as all numbers that can be represented as a finite or infinite decimal expression. (This is not a formal definition, but it will be sufficient for the moment.) The real line is the usual way of representing the set of all real numbers by a straight line. iv. The set of complex numbers, denoted by C, is the set {x + iy | x, y ∈ R}. The Argand diagram is a way of representing C graphically by extending the real line vertically and regarding the element x+ iy ∈ C as the point (x, y). The following proposition will be useful later. Proposition 7.1.1 Let a, b ∈ R and suppose that a < b. Then the following hold. i. There exists x ∈ Q such that a < x < b. ii. There exists x ∈ R\Q such that a < x < b. Proof. Not examinable. The proof follows from the axioms of the real numbers which we do not discuss in full in this course (see the optional video on Blackboard to learn more about these). The proof is given in an optional video in the Week 5 folder on Blackboard. 2 §7.2 Bounded subsets §7.2.1 Subsets that are bounded above and the supremum We begin with the following definition. Example 7.2.2 i. An upper bound for A = [0, 1] is M = 1. But there are plenty of other upper bounds. For example, M = 1.5, M = 2, M = 100.3, M = 299 792 458,..., or indeed any ther real number M ≥ 1 are also all perfectly good upper bounds. ii. An upper bound for A = (−∞, 5) is M = 17. Or you could have chosen any real number M ≥ 5. iii. An upper bound for A = {x ∈ Q | x2 ≤ 2} is M = 42. If you had wanted to find the least (or smallest) upper bound then you would need to take M = √ 2. Any M ≥ √ 2 will be an upper bound. iv. The subset A = {x ∈ R | x = 2n, n ∈ N}, the set of positive even integers, is not bounded above. Suppose for a contradiction that A is bounded above. Then there would exist M ∈ R such that 2n ≤ M for all n ∈ N, i.e. all even integers are no more than M. This is clearly a contradiction: one of ⌊M⌋ + 1 or ⌊M⌋ + 2 must be even and is greater than M. (Here ⌊y⌋ is the largest integer less than y.) v. The subset A = {p ∈ N | p, p+2 are prime} comprises all twin primes, that is primes p such that p+2 is also prime. If there are finitely many twin primes then the set A is bounded above. If there are infinitely many twin primes then the set A is not bounded above. It is a major unsolved problem in mathematics as to whether there are infinitely many twin primes or not (see https://en.wikipedia.org/wiki/Twin_prime). ⋄ Notice that we say that M is an upper bound, not the upper bound. In particular, there could be more than one upper bound. Often, however, the least upper bound plays a special role in Analysis which motivates the following definition. Definition 7.2.3 Let A ⊆ R be bounded above. The supremum of A, also known as the least upper bound of A, is the real number K such that i. K is an upper bound for A ii. if M is an upper bound for A then K ≤ M. We often write supA for the supremum of A. Remark. If A is not bounded above, then it often makes sense to define supA to be +∞ and we normally define sup ∅ = −∞. These are notational tricks rather than definitions that give any deep significance to what +∞ and −∞ might mean. Let us go back to the examples above, at least the ones that are bounded above, and look at their suprema. Example 7.2.4 i. Let A = [0, 1]. We have already seen that any M ≥ 1 is an upper bound for A. If M < 1 then clearly M is not an upper bound for A; this is because 1 ∈ A. By Definition 7.2.3 it follows that supA = 1. ii. Let A = (−∞, 5). We have already seen that any M ≥ 5 is an upper bound for A. We claim that 5 is the least upper bound. Suppose for a contradiction that M < 5 is an upper bound for A. Then (M + 5)/2 < 5 and so (M + 5)/2 ∈ A. But we also have M < (M + 5)/2 (see Figure 7.1). Hence M is not an upper bound for A, a contradiction. By Definition 7.2.3 it follows that supA = 5. M M+5 2 5 ) Figure : 7.1 (iii) A = {x ∈ R | x ∈ Q, x2 ≤ 2}. We have already seen that any M ≥ √ 2 is an upper bound for A. We claim that √ 2 is the least upper bound. Suppose for a contradiction that M < √ 2 is an upper bound for A. By question 9 on Exercise Sheet 7 we can always find x ∈ Q such that M < x < √ 2. But then x ∈ A as x2 < 2. This contradicts the assumption that M is an upper bound. Hence √ 2 is indeed the least upper bound of A. ⋄ There is a very subtle and important point about the structure of the real line hidden in example (iii). There are several, equivalent, ways of constructing R. One way is to specify a set of axioms for the real numbers (see the optional video in the Week 7 folder on Blackboard). One of the axioms for the real numbers is the following: Axiom 7.2.5 Every non-empty subset of R that is bounded above has a supremum in R. Note that Axiom 7.2.5 is not satisfied by Q, that is, not every non-empty subset of Q that is bounded above has a least upper bound in Q. Indeed, the set A = {x ∈ R | x ∈ Q, x2 ≤ 2} from (iii) is a set of rational numbers which is bounded above, but the supremum is √ 2, which is not a rational number! §7.2.2 Subsets that are bounded below and the infimum In Section 7.2.1 we defined what it means for a subset A ⊆ R to be bounded above and what the supremum (the least upper bound) of such a set is. There are, of course, corresponding notions of what it means for a subset to be bounded below and of the greatest lower bound (also known as the infimum). You will develop this in the supervisions. We have the following analogue of Definition 7.2.1. Remark. If a subset A ⊆ R is bounded below, then it has an infimum or greatest lower bound which we denote by inf A. The definition of inf A will be given in the Week 8 supervision class. §7.2.3 Bounded subsets of the set of real numbers Definition 7.2.7 A subset A ⊆ R is bounded if and only if there exists M ∈ R such that for all x ∈ A we have |x| ≤ M. Remark. If a subset A ⊆ R is not bounded, that is it satisfies the negation of Definition 7.2.7, then we say that it is unbounded. Proposition 7.2.8 Let A ⊆ R. Then the following are equivalent: i. A is bounded; ii. A is bounded above and is bounded below. Proof of Proposition 7.2.8. We prove that (i) implies (ii). Suppose that A is bounded. We want to prove that A is bounded above and that A is bounded below. As A is bounded we know that there exists M ∈ R such that for all x ∈ A we have |x| ≤ M. Note that |x| ≤ M is equivalent to −M ≤ x ≤ M. Hence x ≤ M for all x ∈ A so that M is an upper bound for A. Similarly, −M ≤ x for all x ∈ A so that −M is a lower bound for A. We prove that (ii) implies (i). Suppose that A is bounded above. Then there exists M1 ∈ R such that for all x ∈ A we have x ≤ M1. Suppose that A is bounded below. Then there exists M2 ∈ R such that for all x ∈ A we have M2 ≤ x. Let M = max{|M1|, |M2|}. Let x ∈ A. Then We also have x ≤ M1 ≤ |M1| ≤ max{|M1|, |M2|} = M. −M = −max{|M1|, |M2|} ≤ −|M2| ≤ M2 ≤ x. Combining (2.1) and (2.2) we have −M ≤ x ≤ M. Hence |x| ≤ M. §7.2.4 Bounded subsets of the set of complex numbers We can also define what is meant for a subset of complex numbers to be bounded. Definition 7.2.9 (2.1) (2.2) 2 Let A ⊆ C be a subset of complex numbers. We say that A is bounded if and only if there exists M ∈ R such that for all z ∈ A we have |z| ≤ M. Remark. Another way of thinking about Definition 7.2.9 is that all points z ∈ A are distance at most M away from the origin. This is illustrated in Figure 7.2. A M Figure : 7.2 If A ⊆ C is not bounded, we say that A is unbounded. Example 7.2.10 Fix z0 ∈ C. The set A = {z ∈ C | |z−z0| < 1} is bounded. This is illustrated in Figure 7.3. 1 + |z0| z0 Figure : 7.3 We show that A is bounded. Let z ∈ A. Then |z| = |(z − z0) + z0| ≤ |z − z0|+ |z0| by the Triangle Inequality ≤ 1 + |z0|. Hence we can take M = 1 + |z0| in Definition 7.2.9 for this set. ⋄ Example 7.2.11 The set A = {z ∈ C | Re(z) ≤ 1} is an unbounded subset of C. This is illustrated in Figure 7.4. 1 Figure : 7.4 We show that A is unbounded. Suppose, for a contradiction, that A is bounded. Suppose that there exists M ∈ R such that for all z ∈ A we have |z| ≤ M. Without loss of generality we can assume that M > 0. Take z = −(M + 1). Then Re(z) = −(M + 1) < 0 < 1. Hence z ∈ A. But |z| = | − (M + 1)| = M + 1 > M , a contradiction. Hence A is unbounded. ⋄ 8. Sequences In this section we will introduce the concept of a sequence and how to represent a sequence. We will then consider increasing, decreasing and bounded sequences. §8.1 The definition of a sequence For the moment, we give the following definition of a sequence. We will give a more formal definition later. Definition. A sequence is an infinite list of numbers. The terms in the sequence could be real numbers or complex numbers. Here are some examples of sequences: i. 2, 4, 6, 8, 10,... ii. 1, 1/3, 1/9, 1/27, 1/81, 1/243,... iii. 1, 0, 1, 0, 1,... iv. 1, i,−1,−i, 1, i,−1, i,... v. 7,7,7,7,... vi. 0, -19, 203, 4, 5, 6, -99, π, 143,... Note that a sequence may or may not be given by a nice formula. The first 5 examples above follow an obvious pattern, but there is no nice formula (that I can think of!) that generates the final example though! If we are doing computations with sequences then it is often easier to do so when there is a nice formula involved. But general theorems about sequences will apply to all sequences, whether they have a nice formula or not. §8.2 Representing a sequence We might denote the sequence a1, a2, a3,... , an,.... by (an), (an)∞n=1 or (an)n∈N. We call an the nth term of the sequence. If a sequence is given by a nice formula then we will sometimes incorporate this into the notation. For example, we could write: Let (an) be the sequence defined by an = 2n for all n ∈ N Let (an) be the sequence (2n)n∈N. or: We can use the above idea to give a formal definition of a sequence. Definition 8.2.1 A sequence of real numbers is a function a : N → R. A sequence of complex numbers is a function a : N → C. We write an for a(n). We call an the nth term in the sequence. However, we will not normally need to use this definition of a sequence and the idea in Definition 8.1 will be sufficient. We can also represent sequences graphically. For a sequence of real numbers, one standard way to do this is on the real line. An example is given in Figure 8.1: ···1154 1132 1 Figure : 8.1 Of course, this kind of representation makes us assume that the terms in the sequence appear in the obvious order: 1, 1/2, 1/3, 1/4,.... If we want to indicate which is the first term, which is the second term, and so on, then we might instead draw a picture as in Figure 8.2. ··· a3 = 3 1 a2 = 2 1 a1 = 1 Figure : 8.2 Here is another example. Consider the sequence 1, 0, 1, 0, 1, 0, 1,... given by (an) where an = { 0 1 if if n n is is odd, even. We can draw this as in Figure 8.3. a2, a4, a6,... = 0 a1, a3, a5,... = 1 Figure : 8.3 Note that in this kind of representation we would have to say which point on the real line is an. If we have a sequence of complex numbers then we can sketch the sequence in the same way, but this time in the Argand diagram rather than on the real line. For example, we can plot the sequence an = (1 + i)n as in Figure 8.4. (1 + i)7 (1 + i)3 (1 + i)4 (1 + i)5 (1 + i)6 (1 + i)2 1 + i Figure : 8.4 Here is another way of representing a sequence in a diagram. We add in another dimension and plot an against n. For example, we can plot an = 1/n for n ∈ N as in Figure 8.5. an 1 12345678 Figure : 8.5 n Here is another example. Take an = 1 if n is odd and an = 0 is n is even. Then we can represent this as in Figure 8.6. an 1 12345678 n Figure : 8.6 This is (in my opinion) usually clearer than the picture in Figure 8.3. In general, it does not normally matter which type of picture you use (if any picture at all). Drawing pictures can help you understand things better, but you cannot prove things by drawing pictures! Use whichever way of representing a sequence pictorially works best for you for the situation you are in! Note that if (an) is a sequence of complex numbers then it is much harder to plot an against n. For each n we would need a copy of the complex plane resulting in a picture as in Figure 8.7. an a2 a1 a3 1 n 2 3 Figure : 8.7 Whilst there is nothing wrong with the kind of picture in Figure 8.7, in my experience I’ve never personally found this to be useful. Instead, if I need to visually represent a sequence of complex numbers, I would plot them in the Argand diagram as in Figure 8.4. 9. Monotonic, bounded and convergent sequences Our goal for the immediate future is to understand and define what it means for a sequence to converge to a limit. You will likely have an intuitive idea as to what it might mean for a sequence to converge. The formal definition is quite technical and involves being very careful with quantifiers. We will build up to this. First, we define what it means for a sequence of real numbers to be increasing, decreasing or bounded. §9.1 Monotonic Sequences Here are the definitions of what it means for a sequence of real numbers to be increasing or decreasing. Definition 9.1.1 Let (an) be a sequence of real numbers. We say that (an) is increasing if and only if an+1 ≥ an for all n ∈ N. We say that (an) is decreasing if and only if an+1 ≤ an for all n ∈ N. Examples. i. The sequence 2, 4, 6, 8, 10,... is clearly increasing. ii. The sequence 1, 1, 3, 3, 5, 5, 7, 7, 9, 9,... is increasing: remember that the definition for (an) to be increasing is that an ≤ an+1 and this includes the possibility that an = an+1 for some of the terms. iii. The sequence 7, 7, 7, 7, 7,... is both increasing and decreasing. iv. The sequence 0, 1, 0, 2, 0, 3, 0, 4,... is neither increasing nor decreasing. v. The sequence −1,−2,−3,−4,... is decreasing. Occasionally, we might want to talk about sequences where all of the terms do strictly increase or decrease. We can make the following definitions. Definition 9.1.2 Let (an) be a sequence of real numbers. We say that (an) is strictly increasing if and nly if an+1 > an for all n ∈ N. We say that (an) is strictly decreasing if and only if an+1 < an for all n ∈ N. In the above examples, Example (i) is strictly increasing. Example (v) is strictly decreasing. Examples (ii), (iii), and (iv) are neither strictly increasing nor strictly decreasing. Sometimes we will want to work with an abstract sequence that could be either increasing r decreasing. Definition 9.1.3 Let (an) be a sequence of real numbers. We say that (an) is monotonic (or monotone) if and only if (an) is either increasing or decreasing. In the above examples, Examples (i), (ii), (iii), (v) are monotonic. Example (iv) is not monotonic. Note that these definitions only apply to sequences of real numbers as we cannot do in equalities with complex numbers. §9.2 Bounded Sequences In this section we will discuss what it means for a sequence to be bounded above, bounded below, and bounded. Definition 9.2.1 Let (an) be a sequence of real numbers. We say that (an) is bounded above if and only if there exists M ∈ R such that for all n ∈ N we have an ≤ M. We can illustrate this in Figure 9.1. All terms in the sequence are below M an M 1 2 3 4 5 6 7 8 a1 a8 a2 a3 a7 a6 a4 a5 n Figure : 9.1 The definition of bounded below should come as no surprise to you: Definition 9.2.2 Let (an) be a sequence of real numbers. We say that (an) is bounded below if and only if there exists M ∈ R such that for all n ∈ N we have an ≥ M. Again, this corresponds to our intuition, as illustrated in Figure 9.2. an All terms in the sequence are above M M 1 2 3 4 5 6 7 8 a8 a1 a2 a7 a3 a6 a4 a5 n Figure : 9.2 Example 9.2.3 Let an = −n. Then (an) is bounded above but is not bounded below. Clearly (an) is bounded above because an ≤ 0 for all n ∈ N. It should be clear to you that (an) is not bounded below, but let us prove it. We argue by contradiction. Suppose that an is bounded below. Then there exists M ∈ R such that for all n ∈ N we have M ≤ an. Take n = ⌊|M |⌋ + 1. Then an = −(⌊|M |⌋ + 1) < M , a contradiction. Next, we define what it means for a sequence of real numbers to be bounded. Definition 9.2.4 ⋄ Let (an) be a sequence of real numbers. We say that (an) is bounded if and only if there exists M ∈ R such that for all n ∈ N we have |an| ≤ M. We can illustrate Definition 9.2.4 in a diagram as in Figure 9.3. −M M All terms in the sequence are between M and −M 0 a1 1 2 3 4 5 6 7 8 a2 a3 a4 a5 a6 a7 a8 an Figure : 9.3 Here are some examples of bounded sequences. Example 9.2.5 Let an = 1/n. Then (an) is a bounded sequence. n This is clear: we have 0 < an ≤ 1 for all n ∈ N. Therefore |an| ≤ 1 for all n ∈ N. Hence (an) satisfies Definition 9.2.4 and so is bounded. ⋄ Let (an) be a sequence of real numbers. On Exercise Sheet 8 you will prove that the following statements are equivalent. i. The sequence (an) is bounded. ii. The sequence (an) is bounded above and bounded below. We introduce the following definition. Definition 9.2.6 Let (an) be a sequence of real numbers. We say that (an) is unbounded if and only if (an) is not bounded, that is, for all M ∈ R there exists n ∈ N such that |an| > M. As the statements (i) and (ii) given above are equivalent, their negations are also equivalent. It follows that a sequence is unbounded if and only if it is not both bounded above and bounded below. We must be careful with the logic here. If P is the statement ‘(an) is bounded above’ and Q is the statement ‘(an) is bounded below’, then (ii) is P ∧ Q. The negation of (ii) is ¬(P ∧ Q) which is logically equivalent to (¬P ) ∨ (¬Q). So a sequence of real numbers (an) is unbounded if and only if it is not bounded above or it is not bounded below. This should fits in with your intuition of what is means for a sequence to be unbounded. Example 9.2.7 In the last example we showed that the sequence (an) with an = −n is bounded above, but not bounded below. As (an) is not bounded below, we can conclude that (an) is not bounded. ⋄ We cannot say what it means for a sequence (an) of complex numbers to be bounded above or bounded below because, if an is a complex number, then we cannot make sense of inequalities such as an ≤ M. However, the modulus of an, |an|, is a real number—and we can do inequalities with real numbers. Therefore Definition 9.2.4 does make sense for a sequence (an) of complex numbers. Definition 9.2.8 Let (an) be a sequence of complex numbers. We say that (an) is bounded if and only if there exists M ∈ R such that for all n ∈ N we have |an| ≤ M. We can illustrate this as in Figure 9.4. M a1 a4 a5 a3 a2 Figure : 9.4 §9.3 Convergent sequences In this section we will define what it means for a sequence to be convergent. You might already have an intuitive idea what this might mean. For example, it might seem reasonable to you that the sequence 1, 1/2, 1/3,... , 1/n,... converges to 0 as n → ∞. How could you formulate your idea of what it means for a sequence to converge in terms of formal mathematics? §9.3.1 Convergent sequences: the intuitive idea We will give the formal definition of what it means for a sequence to converge in the next section. We start with the intuitive informal idea that we are trying to capture. For the moment, and for simplicity, we only consider sequences of real numbers. Informal definition. Let (an) be a sequence. We want to say that (an) converges to a limit a as n → ∞ if, by going down the sequence sufficiently far, we can make an as close as we like to a. We specify a desired small distance away from the limit a. Then, provided we look sufficiently far down the sequence, we have that the terms in the sequence are within that desired small distance of a. In Analysis, the usual letter to use for a ‘very small distance’ is ε, the Greek letter epsilon. If we want a number an that is within distance ε of a, then we want a− ε < an < a+ ε. This is equivalent to requiring that |a − an| < ε. You can read |an − a| < ε out aloud as ‘the absolute value of an minus a is less than ε’. But I always read it out as ‘the distance between an and a is less than ε’. Now suppose that we want the sequence (an) to have the property that, provided we go down the sequence sufficiently far, we can make all the terms an beyond that point within distance ε of a. This is illustrated in Figure 9.5. an a+ ε a a− ε N n Figure : 9.5 We can turn this into symbols and quantifiers as follows: ∃N ∈ N such that ∀n ∈ N, if n ≥ N then |an − a| < ε. This captures the idea that, beyond a certain point (the N th) in the sequence, all the terms in the sequence are within distance ε of a. We want to be able to do this for any value of ε > 0. This suggests that we need a definition along the following lines: given any ε > 0 then, provided we look sufficiently far down the sequence, we can make the terms an be within distance ε of a. We are now ready to formalise this. §9.3.2 Convergent sequences: the definition In this section we turn our intuitive informal definition of what it means for a sequence (an) of real numbers to converge into a formal mathematical definition, explore what it means, and see how to prove that a given sequence is convergent (or not). We begin with the following definition. Definition 9.3.1 Let (an) be a sequence of real numbers. We say that (an) converges to a as n → ∞ if and only if for all ε > 0 there exists N ∈ N such that for all n ∈ N, if n ≥ N then |an − a| < ε. We write an → a as n → ∞, lim an = a or (an) → a. n→∞ We can read Definition 9.3.1 as ∀ε > 0 given any distance ε (no matter how small) ∃N ∈ N we can find a point in the sequence (which is allowed to depend on ε) such that ∀n ∈ N, n ≥ N such all terms that of the sequence beyond the N th ⇒ |an − a| < ε are within distance ε of a. Remark. Here ∀ε > 0 is short for ∀ε ∈ R with ε > 0. Since in Analysis ε is commonly used to represent a ‘very small distance’, the fact that ε represents a real number is left implicit. In a similar way, we might leave the fact that n is a natural numbers as implicit and write ∀ε > 0 ∃N ∈ N such that ∀n ≥ N we have |an − a| < ε. §9.3.3 Sequences of complex numbers If you look at Definition 9.3.1 then you should notice that everything in that definition continues to make sense if an and a are complex numbers. Here |an − a| becomes the modulus of an − a and |an − a| being small again corresponds to our intuitive idea of the distance in the Argand diagram between an and a being small. This means that we can use the same definition to define what it means for a sequence of complex numbers to converge. Definition 9.3.2 Let (an) be a sequence of complex numbers. We say that (an) converges to a as n → ∞ if and only if for all ε > 0 there exists N ∈ N such that for all n ∈ N, if n ≥ N then |an − a| < ε. Note that if (an) is a sequence of complex numbers then Re(an) and Im(an) are sequences of real numbers. We have the following result. Proposition 9.3.3 Let (an) be a sequence of complex numbers. Let (xn) = (Re(an)) and let (yn) = (Im(an)) be the sequences of real and imaginary parts of an, respectively. Then (an) converges if, and only if, (xn) and (yn) converge. More specifically, i. Suppose that an → a as n → ∞. Let x = Re(a) and y = Im(a). Then xn → x and yn → y as n → ∞. ii. Suppose that xn → x and yn → y as n → ∞. Then an → x+ iy as n → ∞. Remark. We prove (i) below. Proving (ii) will be an exercise for you to do once we have developed a bit more theory in Section 10. Proof. (i) Suppose that an → a as n → ∞. We prove that xn → x as n → ∞. Let ε > 0. Choose N ∈ N such that if n ≥ N then |an − a| < ε. Then |xn − x| = √|xn − x|2 ≤ √|xn − x|2 + |yn − y|2 = |an − a| < ε. (3.1) (3.2) Here (3.1) follows from the fact that |yn − y|2 ≥ 0 and (3.2) follows from the definition of the modulus of a complex number. Hence xn → x as n → ∞. The proof that yn → y as n → ∞ is very similar. In Definitions 9.3.1 and 9.3.2 we have defined what it means for a sequence (an) to converge to the limit a. It is often useful to say that a sequence converges but not specify what the limit is. We can capture this in the following definition. Definition 9.3.4 2 Let (an) be a sequence of real numbers. We say that (an) converges as n → ∞ if and only if there exists a ∈ R such that (an) converges to a as n → ∞. (There is, of course, an obvious analogue of this for sequences of complex numbers.) Some times, instead of saying that (an) converges as n → ∞ we will say that (an) is convergent. Remark. In terms of quantifiers, we can rewrite Definition 9.3.4 as follows. Let (an) be a sequence of real numbers. Then (an) converges as n → ∞ if and only if ∃a ∈ R such that ∀ε > 0 ∃N ∈ N such that ∀n ∈ N, n ≥ N ⇒ |an − a| < ε. §9.4 Examples of Convergent Sequences In this section, we give some examples to show how to prove that a given sequence is convergent by showing that it satisfies the definition. We also give some examples to show that a sequence is not convergent by showing that it does not satisfy the definition. Example 9.4.1 Prove that limn→∞ 1/n = 0. We will set this out as a formal proof (remember from earlier in the course that you need to write your arguments in complete sentences and make the logical structure clear). We want to prove that limn→∞ 1/n = 0. Let ε > 0. We want to show that there exists N ∈ N such that for all n ∈ N if n ≥ N then |1/n| < ε. Choose N = ⌊1/ε⌋+ 1. Suppose that n ∈ N and n ≥ N. Then 0< 1 1 n ≤ N = ⌊1/ε⌋+ 1 < 1/ε = ε. 11 (Recall that ⌊x⌋ is the floor function: it gives the largest integer m for which m ≤ x.) So how did I construct this proof? When I wrote this proof down, I did not know in advance what the formula for N would be: I had to work it out. Here’s what I actually did. Firstly, I drew the following picture to convince myself that I believed that 1/n does converge to 0. I’ve drawn in a horizontal line at height ε. And now I want to calculate N , as illustrated in Figure 9.6. an 1 ε N−1NN+1123 n Figure : 9.6 I need to calculate an explicit formula for N. I am going to use the fact that the sequence 1/n is decreasing. To make calculating an N easier, I am going to find the first N for which 1/N < ε; as 1/n is decreasing, it then follows that 1/n < ε for all n ≥ N. (Of course, I could choose N to be any integer bigger than this first N and the argument will still work.) Given ε > 0, I want to find N such that 11 N−1≥ε>N. (4.1) I now want to re-arrange this to find a formula for N in terms of ε. Re-arranging (4.1) we have N − 1 ≤ 1 < N. ε (4.2) From (4.2) we have that N − 1 = ⌊1/ε⌋ is the largest integer less than 1/ε. Re- arranging this gives N = ⌊1/ε⌋+ 1. I now need to check that my formula for N works in Definition 9.3.1. Suppose n ≥ N. Then 1 1 n ≤ N = ⌊1/ε⌋+ 1 < 1/ε = ε 11 where the second inequality follows from (4.1). Having now found my formula for N and checked that it works in the definition of conver gence, I can now go back and write out a formal proof as above. ⋄ Here’s another example Example 9.4.2 Prove that 1/2n → 0 as n → ∞. This time, we will do the rough work first and then set it out as a formal proof. We can sketch 1/2n as in Figure 9.7. 1/2 an 12345 an 1 2N−1 1 2N 1 n 2N+1 ε N−1NN+1 Figure : 9.7 Let ε > 0 be arbitrary. I want to construct N such that if n ≥ N then 1/2n < ε. From the picture, it looks like choosing N such that 11 2N−1 > ε > 2N (4.3) will work. Recall that log is an strictly increasing function; this means that if x < y then log x < log y. Taking logs in (4.3) and being very careful with minus signs we can re-arrange (4.3) to obtain N − 1 < log log 1/ε 2 < N. This suggests taking N = ⌊ log log 1/ε 2 ⌋ + 1. Note that if ε > 1 then 1/ε < 1 and therefore log 1/ε < 0. As we require N ∈ N we choose N = max {⌊ log log 1/ε 2 ⌋ + 1, 1 }. We can now use these ideas to write down a formal proof that 1/2n → 0 as n → ∞. Let ε > 0 be arbitrary. We want to find N ∈ N such that for all n ∈ N if n ≥ N then |1/2n| < ε. Choose N = max {⌊ log log 1/ε 2 ⌋ + 1, 1 }. Let n ∈ N and assume n ≥ N. Then n ≥ ⌊ log log 1/ε 2 ⌋ + 1 > log log 1/ε 2. Re-arranging this we see that log 2n = n log 2 > log 1/ε. As log is an increasing function, it follows that 2n > 1/ε. Taking the reciprocal then gives that 0 < 1/2n < ε. Hence |1/2n| < ε. n ⋄ Remark. In Example 9.4.2 we saw that 1/2n → 0 as n → ∞. This argument generalises to show that rn → 0 as n → ∞ whenever |r| < 1 (in fact here r could be real or complex). See the optional video in the Week 8 folder on Blackboard. Example 9.4.3 Let a ∈ R. Let (an) be the constant sequence where an = a for all n ∈ N. Then an → a as n → ∞. Let ε > 0 be given. We want to show that an → a as n → ∞. Choose N = 1. Then for all n ∈ N, if n ≥ N we have |an − a| = |a − a| = 0 < ε. Hence we have shown that an → a as n → ∞. §9.5 Proving that a sequence does not converge ⋄ As well as seeing examples of sequences that do converge, it is equally as important to see examples of sequences that do not converge. This way we can convince ourselves that the formal definition in Definition 9.3.1 does correspond to our intuition. an = { 0 1 if if n n is is odd, even. Example 9.5.1 Define Then the sequence (an) does not converge to 0. We will do this using proof by contradiction. An alternative method would be to directly show that the sequence satisfies the negation of the definition of convergence. Suppose for a contradiction that (an) does converge to 0. Then ∀ε > 0, ∃N ∈ N such that ∀n ∈ N if n ≥ N then |an| < ε. Take ε = 1/2. Then there exists some N ∈ N such that for all n ≥ N we have |an − 0| < 1/2. But if we take n={ NN+1 if N is odd if N is even then n ≥ N and |an| = 1 ≥ ε, giving a contradiction. Hence the sequence (an) does not tend to 0. See Figure 9.8. an 1 ε −ε NN+112345 n Figure : 9.8 ⋄ In Example 9.5.1, we showed that the sequence (an) given by an = { 0 1 if if n n is is odd, even. does not converge to 0. On Exercise Sheet 8 you will be asked to prove that (an) does not converge (that is, for all a ∈ R, (an) does not converge to a). Here is another example of a sequence that does not converge. Example 9.5.2 Let an = n2. It should be clear from Figure 9.9 that the sequence (an) does not converge to any limit. an 12345678 Figure : 9.9 n To prove this formally, however, we must go back to the definition. Recall from Defini tion 9.3.4 that the sequence (an) converges if and only if: ∃a ∈ R such that ∀ε > 0, ∃N ∈ N such that ∀n ∈ N, n ≥ N⇒ |an − a| < ε. Taking the negation, we have the following definition of what it means for (an) to not converge: ∀a ∈ R, ∃ε > 0, such that ∀N ∈ N, ∃n ∈ N such that n ≥ N and |an − a| ≥ ε. (5.1) We prove that the sequence an = n2 satisfies (5.1). Let a ∈ R be arbitrary. Choose ε = 1. Let N ∈ N be arbitrary. First let us consider the case a < 0. We can take n = N and we have |an − a| = n2 − a ≥ n2 ≥ 1 = ε. Now suppose a ≥ 0. Choose n = max{⌊√a+ 1 ⌋ + 1, N}. Then n ≥ N and n ≥ √ a+ 1. Therefore an = n2 ≥ a+1 and we have |an−a| = an−a ≥ 1 = ε. Hence we have shown that the sequence (an) with an = n2 does not converge. §9.6 Uniqueness of limits ⋄ In Sections 9.3 and 9.4, when a sequence was convergent, we talked about the limit (rather than a limit). But there is nothing in the definition of what it means for a sequence to converge that requires the limit to be unique. In this sections we prove that, if a sequence converges, then the limit is unique. Theorem 9.6.1 Suppose that the sequence (an) converges. Then the limit is unique. Before writing out the rigorous proof, we start with some rough work. We will use proof by contradiction. Suppose that the sequence (an) converges to two different limits, say a and a′. Because an → a as n → ∞, provided we look sufficiently far down the sequence, all the terms in the sequence will be close to a. Similarly, because an → a′ as n → ∞, all terms sufficiently far down the sequence will be close to a′. This is illustrated in Figure 9.10 below. It should be clear from Figure 9.10 that this is impossible, and this is how we will get our contradiction. ( a ) ( a′ ) If n is sufficiently large then all terms are close a If n is sufficiently large then all terms are close a′ Figure : 9.10 To turn this into rigorous mathematics, we will have to work from Definition 9.3.1. We start by assuming, for a contradiction, that a = a′ and: i. for all ε > 0 there exists N ∈ N such that for all n ∈ N if n ≥ N then |an − a| < ε, and ii. for all ε > 0 there exists N ∈ N such that for all n ∈ N if n ≥ N then |an − a′| < ε. Therefore, for a fixed value of ε > 0, there exists N1 ∈ N such that if n ≥ N1 then |an − a| < ε and there exists N2 ∈ N such that if n ≥ N2 then |an − a′| < ε. If we want to use that both |an − a| < ε and |an − a′| < ε then we will need take n to be bigger than both N1 and N2. A convenient way of doing this is to let N = max{N1, N2}. Looking at Figure 9.10, it looks like we should get a contradiction provided that there is a ‘gap’ between the two indicated intervals. We can make this happen by choosing, for example, ε = |a− a′|/3. Thus we have the picture as illustrated in Figure 9.11). εε εε ( a′ ) ( a ) If n ≥ N1 then |an − a| < ε If n ≥ N2 then |an − a| < ε Figure : 9.11 This should give you the idea of how we will rigorously prove Theorem 9.6.1. Note that we cannot prove things by drawing pictures. Instead of using the picture in Figure 9.11, we will need to play around with some inequalities to deduce the final contradiction. Proof of Theorem 9.6.1. Suppose that an → a and an → a′ as n → ∞. We show that a = a′. To see this, suppose for a contradiction that a = a′. Let ε = (|a − a′|/3). Then ε > 0. As an → a as n → ∞, we know that there exists N1 ∈ N such that if n ≥ N1 then |an− a| < ε. Similarly, as an → a′ as n → ∞, we know that there exists N2 ∈ N such that if n ≥ N2 then |an − a′| < ε. Let N = max{N1, N2}. Then |a− a′| = |(a− aN ) + (aN − a′)| ≤ |a− aN |+ |aN − a′| by the Triangle Inequality < 3 1 |a− a′|+ 3 1 |a− a′| = 3 |a− a′|. 2 This shows that |a − a′| < 3 2 |a − a′|, which is clearly impossible. Hence our assumption that a = a′ must be false. Hence a = a′. §9.7 Relationships between different types of sequence 2 Let (an) be a sequence of real numbers. We have seen definitions of what it means for (an) to be monotone, to be bounded, and to be convergent. What are the relationships between these concepts? Which of the following statements do you think are true and which do you think are false? For those that are false, can you find a counter-example? For those that are true, can you find a proof? In each case, let (an) be a sequence of real numbers. i. Suppose that (an) is bounded. Then (an) is convergent. ii. Suppose that (an) is convergent. Then (an) is bounded. iii. Suppose that (an) is monotone. Then (an) is convergent. iv. Suppose that (an) is convergent. Then (an) is monotone. v. Suppose that (an) is bounded. Then (an) is monotone. vi. Suppose that (an) is monotone. Then (an) is bounded. vii. Suppose that (an) is monotone and bounded. Then (an) is convergent. Statement (i) is false. A counter-example is given by the sequence (an) defined by an = { 0 1 if if n n is is odd, even. Clear

Mathematical Logic and Sets Notes PDF

Document Details

Tags

Related

Summary

Full Transcript

Upgrade to continue