# Abstract mathematics

lOMoARcPSD|5093418 MT2116 Abstract mathematics Examiners’ commentaries 2017 MT2116 Abstract mathematics Important note This commentary reflects the examination and assessment arrangements for this course in the academic year 2016–17. The format and structure of the examination may change in future years, and any such changes will be publicised on the virtual learning environment (VLE). Information about the subject guide and the Essential reading references Unless otherwise stated, all cross-references will be to the latest version of the subject guide (2011). You should always attempt to use the most recent edition of any Essential reading textbook, even if the commentary and/or online reading list and/or subject guide refer to an earlier edition. If different editions of Essential reading are listed, please check the VLE for reading supplements – if none are available, please use the contents list and index of the new edition to find the relevant section. Comments on specific questions – Zone A Candidates should answer SIX of the following EIGHT questions: THREE from Section A and THREE from Section B. If additional questions are answered, only your best THREE answers from Section A and your best THREE answers from Section B will count towards the final mark. All questions carry equal marks. Section A Answer any three questions from this section. Question 1 (a) Let p, q and r be statements. Prove, using a truth table or otherwise, that [(p ∨ r) ∨ (q ∨ r)] ∧ ¬ [(p ∨ r) ∧ (q ∨ r)] =⇒ ¬r. Reading for this question This question builds on the material of Chapter 1 of the subject guide. Approaching the question Let S1 denote the statement (p ∨ r) ∨ (q ∨ r), let S2 be ¬ [(p ∨ r) ∧ (q ∨ r)] and let S be S1 ∧ S2 . (So, S is the left-hand side of the implication given in the question.) Then we have the following truth table. 4 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 Examiners’ commentaries 2017 p T T T F T F F F q T T F T F T F F r T F T T F F T F p∨r T T T T T F T F q∨r T T T T F T T F S1 T T T T T T T F (p ∨ r) ∧ (q ∨ r) T T T T F F T F S2 F F F F T T F T S F F F F T T F T ¬r F T F F T T F T We need to verify that S =⇒ ¬r. What that means is that we need to verify that whenever S is true, so too is ¬r. This can be seen to be the case from the final two columns of the table. (b) Let S be the following statement: If an integer, n, is even, then its cube, n3 , is even. Prove that S is true. Write down the converse of S. Write down the contrapositive of the converse of S. Is the converse of S true or false? Justify your answer. Approaching the question If n is even, then n = 2k for some integer k, and so n3 = 8k 3 = 2(4k 3 ) is even. The converse is: ‘If n3 is even, then n is even.’ The contrapositive of the converse if: ‘If n is not even, then n3 is not even,’ That is, it is ‘If n is odd, then n3 is odd.’ The contrapositive of the converse is true: for, if n is odd, then n = 2k + 1 for some integer k, and so: n3 = (2k + 1)3 = 8k 3 + 12k 2 + 6k + 1 = 2(4k 3 + 6k 2 + 3k) + 1 which is odd. Since the contrapositive of the converse is logically equivalent to the converse, it follows that the converse is true. Question 2 (a) Use the method of induction to prove that the following statement is true for all natural numbers n: n X r(r + 2)(r + 4) = r=1 1 4 n(n + 1)(n + 4)(n + 5). Reading for this question Proof by induction is discussed in Chapter 3 of the subject guide. Approaching the question The base case n = 1 is easily seen to be true since both sides of the expression are 15 in this case. Suppose the result is true for a positive integer n, so that: n X r=1 r(r + 2)(r + 4) = 1 n(n + 1)(n + 4)(n + 5). 4 5 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 MT2116 Abstract mathematics Then: n+1 X r(r + 2)(r + 4) = (n + 1)(n + 3)(n + 5) + n X r(r + 2)(r + 4) r=1 r=1 = = = = = 1 (n + 1)(n + 3)(n + 5) + n(n + 1)(n + 4)(n + 5) 4 1 (n + 1)(n + 5) [4(n + 3) + n(n + 4)] 4 1 (n + 1)(n + 5)(n2 + 8n + 12) 4 1 (n + 1)(n + 5)(n + 2)(n + 6) 4 1 (n + 1)((n + 1) + 1)((n + 1) + 4)((n + 1) + 5) 4 which establishes that the result is true for n + 1. By induction, therefore, the result holds for all n. (b) The sequence x1 , x2 , . . . is defined as follows: x1 = 1, x2 = 2 and, for n ≥ 3, xn = 2xn−1 + xn−2 − 2. Prove by induction that: xn is even if and only if n is even. Approaching the question Since x1 = 1 and x2 = 2, the statement is true for n = 1, 2. Suppose it is true for all n ≤ k. Suppose first that k + 1 is even, so k is odd. Then xk is odd and xk−1 is even. Therefore, xk+1 = 2xk + xk−1 + 2 is even. If k + 1 is odd, then xk is even and xk−1 is odd. In this case, xk+1 = 2xk + xk−1 + 2 is odd. So the result holds. (c) Let X = R and let Y be the interval (−1, 1). Prove that the function f : X → Y given by x f (x) = 1 + |x| is a bijection from X to Y . Reading for this question Functions and their properties are dealt with in Chapter 4 of the subject guide. Approaching the question First, we show f in injective. Suppose f (x) = f (y). Then: y x = 1 + |x| 1 + |y| so: x(1 + |y|) = y(1 + |x|) which means: x + x|y| = y + y|x|. Now: x y = 1 + |x| 1 + |y| implies that x, y have the same sign (both are at most, or at least, 0). So x|y| = y|x|. We conclude (after cancellation) that x = y. 6 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 Examiners’ commentaries 2017 Now we show f is surjective. Given y ∈ (−1, 1), we want x such that: x = y. 1 + |x| If y ≥ 0, we want x ≥ 0, so we solve: x =y 1+x to get x = y/(1 − y). If y < 0, we want x < 0, so we solve: x =y 1−x to get x = y/(1 + y). Question 3 (a) Consider the following system of simultaneous equations in Z7 : 5x + 3y = 2 cx + 2y = 1, where c ∈ Z7 is a constant. Show that this system has no solution if c = 1. Suppose c 6= 1 and let a be the inverse of c − 1 in Z7 . Find all solutions of the system, expressing your answers in terms of a. Reading for this question Modular arithmetic is discussed in Chapter 7 of the subject guide. Approaching the question If c = 1, the system is: 5x + 3y = 2 x + 2y = 1. Multiplying the second equation by 5 gives 5x + 10y = 5, which, in Z7 , is 5x + 3y = 5. Then, given the first equation, this would mean 2 = 5, which is false. So there are no solutions. Suppose c 6= 1. Multiplying the first equation by 2 and the second by 3 and working modulo 7, we obtain 3x + 6y = 4 and 3cx + 6y = 3. Subtracting the first of these from the second, we obtain (3c − 3)x = −1 = 6 and hence (c − 1)x = 3−1 6 = 5.6 = 30 = 2 and x = 2(c − 1)−1 = 2a. Then, since 3y = 2 − 5x, we have 3y = 2 − 10a = 2 + 4a and hence: y = 3−1 (2 + 4a) = 5(2 + 4a) = 10 + 20a = 3 + 6a. So there is a unique solution: x = 2a, and y = 3 + 6a. (b) What does it mean to say that a relation R on a set X is an equivalence relation? Let R be the relation defined on the set of natural numbers N as follows: xRy ⇐⇒ gcd(x + 1, y + 1) ≥ 2. Is R reflexive? Is R symmetric? Is R transitive? 7 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 MT2116 Abstract mathematics Reading for this question Equivalence relations are discussed in Chapter 5 of the subject guide. Approaching the question R is an equivalence relation if: • R is reflexive: for all x ∈ A, x R x. • R is symmetric: for all x, y ∈ A, x R y implies y R x. • R is transitive: for all x, y, z ∈ A, x R y and y R z imply x R z. R is reflexive because for any x ∈ N, gcd(x + 1, x + 1) = x + 1 ≥ 2. R is symmetric because for any x, y, gcd(x + 1, y + 1) = gcd(y + 1, x + 1) ≥ 2 and therefore gcd(x + 1, y + 1) ≥ 2 if and only if gcd(y + 1, x + 1) ≥ 2, meaning x R y if and only if y R x. R is not transitive. For example, take x = 1, y = 5, z = 2. Then x R y and y R z because gcd(x + 1, y + 1) = gcd(2, 6) = 2 and gcd(y + 1, z + 1) = gcd(6, 3) = 3 ≥ 2, yet gcd(x + 1, z + 1) = gcd(2, 3) = 1. (c) Use the Euclidean algorithm to find the greatest common divisor, d, of 71 and 22. Use your answer to find integers x, y such that 71x + 22y = 1. Reading for this question This is a standard, easy, question. As directed, we use the Euclidean Algorithm (of Chapter 6 of the subject guide). Approaching the question We have: 71 = 3.22 + 5 22 = 4.5 + 2 5 = 2.2 + 1 where, for shorthand, the ‘.’ represents multiplication (×). It follows from this that gcd(71, 22) = 1. Furthermore: 1 = 5 − 2.2 = 5 − 2(22 − 4.5) = 9.5 − 2.22 = 9(71 − 3.22) − 2.22 = 9.71 − 29.22 so we may take x = 9 and y = −29. Question 4 (a) Let x be the real number x = 1.1248. Express x in the form p/q where p and q are integers. Reading for this question See Chapter 8 of the subject guide. 8 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 Examiners’ commentaries 2017 Approaching the question We have 1000x = 1124.8248 and so 1000x − x = 1124.8248 − 1.1248 = 1123.7. That is, 999x = 11237/10 and so: 11237 x= . 9990 (b) Suppose a is irrational. Prove that if x, y, z, t are rational numbers and x + ya = z + ta, then x = z and y = t. Reading for this question See Chapter 8 of the subject guide for a discussion of rational and irrational numbers. Approaching the question If y 6= t, then we have: x−z . t−y The numerator and denominator are both rational, so can be written, respectively, as r/s and m/n for some integers r, s, m, n. Then: a= a= r/s rn = m/n sm which is rational. This is a contradiction, since a is irrational. Therefore, y = t. The equation x + ya = z + ta then says x = z. (c) Find all solutions z ∈ C to the equation (z 2 + 1)(z 3 + z + 2) = 0. Reading for this question Complex numbers are discussed in Chapter 8 of the subject guide. Approaching the question z 2 + 1 has roots z = ±i. We look for a real solution to z 3 + z + 2 = 0. (There will be one since it is a cubic.) We see that z = −1 works. Dividing z 3 + z + 2 by the corresponding factor, z + 1, gives z 3 + z + 2 = (z + 1)(z 2 − z + 2) The remaining two solutions are the roots of the quadratic, which are: √ 1 7 1 1√ 1−8= ± z= ± i. 2 2 2 2 (d) For a complex number z, ℑ(z) denotes the imaginary part of z. Prove that for any z ∈ C, |z + iz|2 = 2|z|2 + 2 ℑ(z 2 ). Approaching the question We have: |z + iz|2 = (z + iz)(z + iz) = (z + iz)(z − iz) = zz + iz 2 − iz 2 + zz = 2|z|2 + i(z 2 − z 2 ). Now, for any w ∈ C, w − w = 2i ℑ(w), so (with w = z 2 , and noting that z 2 = (z)2 , the expression equals: 2|z|2 − i(2i ℑ(z 2 )) = 2|z|2 + 2 ℑ(z)2 . You could, alternatively, take an arbitrary z = a + bi and show that both expressions coincide. 9 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 MT2116 Abstract mathematics Section B Answer any three questions from this section. Question 5 (a) i. Let S be a non-empty set. What does it mean to say that a real number u is an upper bound for S? What does it mean to say that s is the supremum of S? ii. Let A and B be two non-empty sets of real numbers, both bounded above. Show that sup (A ∪ B) ≥ sup A. iii. For non-empty sets A and B of real numbers, we say that A dominates B if, for every b ∈ B, there is some a ∈ A with a ≥ b. Suppose that A dominates B. Show that s = sup A is an upper bound for A ∪ B, and deduce that sup (A ∪ B) = s. iv. Is it true that, if sup (A ∪ B) = sup A, then A dominates B ? Justify your answer by means of a proof or a counterexample. v. Is it true that, if sup A = sup B = s and s 6∈ B, then A dominates B ? Justify your answer by means of a proof or a counterexample. Reading for this question See Chapter 9 of the subject guide for the background material to this part of the question. Approaching the question i. To say that u is an upper bound for S means that s ≤ u for all s ∈ S. To say that s is the supremum of S means that: • s is an upper bound for S, and • for any t < s, t is not an upper bound for S. ii. Let u = sup (A ∪ B). We show that u is an upper bound on A. Hence, by the second property of supremum, sup A ≤ u. Indeed, if a ∈ A, then a ∈ A ∪ B, so a ≤ u. iii. Suppose that A dominates B, let s = sup A, and take any x ∈ A ∪ B. Either x ∈ A, in which case x ≤ s because s is an upper bound on A, or x ∈ B, in which case there is some a ∈ A such that x ≤ a ≤ s (because s is an upper bound on A). Thus, s is an upper bound for A ∪ B. Consequently, by the second property of supremum, sup (A ∪ B) ≤ s = sup A, and we have equality by (ii). iv. This is false. Consider A = (0, 1), B = (0, 1]. Then sup (A ∪ B) = sup A = 1, but there is no a ∈ A such that a ≥ 1 ∈ B, so A cannot dominate B. v. This is true. Take any b ∈ B. As s is an upper bound for B, but s 6∈ B, we have b < s. Now, as s is the supremum of A, b is not an upper bound for A, and so there is some a ∈ A with a > b. Hence A dominates B. (b) i. State the Intermediate Value Theorem. ii. Let f : [0, ∞) → R be a decreasing continuous function √ such that f (0) = 1. Show that there is exactly one x > 0 such that f (x) = x. Reading for this question See Chapter 11 of the subject guide for relevant background material. Approaching the question i. Intermediate Value Theorem (Theorem 11.6 in the subject guide): suppose g is a continuous function on the closed interval [a, b], and z lies between g(a) and g(b). Then there is some c ∈ [a, b] with g(c) = z. 10 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 Examiners’ commentaries 2017 √ ii. We apply the Intermediate Value Theorem with g(x) =√ x − f (x) and [a, b] = [0, 1]. Function g is continuous at every point x ≥ 0 because x and −f (x) are continuous. We have g(0) = −f (0) = −1, and g(1) = 1 − f (1) ≥ 1 − f (0) = 0 because f is decreasing. By √ the Intermediate Value Theorem there is x such that g(x) = 0, that is, f (x) = x. √ √ Suppose that x1 < x2 are two solutions. Then f (x1 ) = x1 < x2 = f (x2 ), which contradicts the fact that f is decreasing. Question 6 (a) Define what it means to say that a sequence (an ) converges to 1. Reading for this question See Chapter 10 of the subject guide for material related to this question. Approaching the question A sequence (an ) is convergent to 1 if, for every ǫ > 0, there exists N such that for all n > N we have |an − 1| < ǫ. (b) Suppose that a sequence (an ) converges to 1. i. Show, directly from the definition, that the sequence (a2n ) converges to 1. Let bn = max{an , a2n }, for n ∈ N. Here max{x, y} = x for x ≥ y, and max{x, y} = y for x < y. ii. Show that (bn ) converges to 1. Approaching the question i. Given ǫ > 0, we pick N such that for n > N we have |an − 1| < min{1, ǫ/3}. Then: |a2n − 1| = |an − 1||an + 1| < ǫ ǫ (|an − 1| + 2) < · 3 = ǫ. 3 3 ii. Given ǫ > 0, we pick N1 such that for n > N1 we have |an − 1| < ǫ, and we choose N2 such that for n > N2 we have |a2n − 1| < ǫ. Take N = max{N1 , N2 }. For n > N , we have an < 1 + ǫ and a2n < 1 + ǫ. Hence, bn < 1 + ǫ as well. We also have bn ≥ an > 1 − ǫ. So, for n > N , we have |bn − 1| < ǫ. (c) For each of the following sequences, find the limit of the sequence or show that the sequence does not converge. Justify your answers. (You may use any results from the course, provided they are clearly stated.) √ √ √ i. (cn ), where cn = n( n + 1 − n − 1); ii. (dn ), where dn = (−1)n 21/n . Approaching the question i. Observe that: √ n+1− √ √ √ √ √ ( n + 1 − n − 1)( n + 1 + n − 1) n + 1 − (n − 1) √ √ √ n−1= =√ . n+1+ n−1 n+1+ n−1 Hence: cn = √ √ n + 1 − (n − 1) 2 n 2 p √ √ n√ =√ =p n+1+ n−1 n+1+ n−1 1 + 1/n + 1 − 1/n and, by the algebra of limits (Theorem 10.5 in the subject guide): lim cn = lim p n→∞ n→∞ 2 1 + 1/n + p 1 − 1/n =√ Downloaded by lex lexus (localfocalpoint@gmail.com) 2 √ = 1. 1+0+ 1−0 11 lOMoARcPSD|5093418 MT2116 Abstract mathematics ii. We know that 21/n → 20 = 1 as n → ∞. So, using part a) with ǫ = 1/2, for some N , we have that 21/n > 1 − ǫ = 1/2 for n > N . Hence, for even n > N , dn > 1/2 and for odd n > N , dn < −1/2. This implies that (dn ) does not converge. Question 7 (a) Let (G, ⋆) be a group, and let a ∈ G. Give the definition of am , where m ∈ Z. Define the order of the element a of G. Reading for this question See Chapters 12, 13 and 14 of the subject guide for relevant reading for this question. Approaching the question If m > 0, then am = |a ∗ a ∗{z· · · ∗ a}, if m < 0, then am = (a−1 )−m , and a0 = e. m times The order of a is the smallest n ∈ N such that an = e. If no such n exists, we say that a has infinite order. (b) Let (G, ⋆) be any group. Show that, for every a, b ∈ G, the order of a is equal to the order of b ⋆ a ⋆ b−1 . Approaching the question Note that (b ⋆ a ⋆ b−1 )n = (b ⋆ a ⋆ b−1 ) ∗ (b ⋆ a ⋆ b−1 ) ∗ · · · ∗ (b ⋆ a ⋆ b−1 ) = b ⋆ a ⋆ (b−1 ∗ b) ⋆ a ⋆ (b−1 ⋆ b) ⋆ a . . . a ⋆ (b−1 ⋆ b) ⋆ a ⋆ b−1 = b ⋆ an ⋆ b−1 . From this, it follows that an = e if and only if (b ⋆ a ⋆ b−1 )n = e, hence their order must be the same. (c) Let C∗ = C \ {0} be the set of non-zero complex numbers, and let GL(2, R) denote the set of 2 × 2 invertible matrices with real entries. You may assume that C∗ with complex multiplication, and GL(2, R) with matrix multiplication, are both groups. i. Define φ : C∗ → GL(2, R) by φ(x + iy) = x y −y . x Show that φ is a homomorphism. ii. Show that H = a b −b a a, b ∈ R, a2 + b2 6= 0 is a subgroup of GL(2, R). iii. Show that C∗ is isomorphic to H. Approaching the question ∗ i. We need to show that, for all x + iy, a + bi ∈ C , we have φ(x + iy)φ(a + ib) = φ (x + iy)(a + ib) . Indeed: x −y a −b ax − yb φ(x + iy)φ(a + ib) = = y x b a bx + ya = 12 −bx − ya ax − yb φ(ax − yb + i(bx + ya)) = φ (x + iy)(a + ib) . Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 Examiners’ commentaries 2017 ii. We must check that H is non-empty and closed under multiplication and taking inverse. Since 12 + 02 6= 0, we have that: 1 0 1 −0 = ∈ H. 0 1 0 1 H is closed under multiplication: if a2 + b2 6= 0, and: x y −y x a b −b a x y = −y a , x b −b a −(bx + ya) ax − yb ax − yb bx + ya ∈ H, then x2 + y 2 6= 0, ∈H because (ax − yb)2 + (bx + ya)2 = (x2 + y 2 )(a2 + b2 ) 6= 0. x −y Finally, for ∈ H, we have: y x because: x y −y x −1 1 = 2 x + y2 x 2 x + y2 2 x −y + = 2 = −(−y) x −y 2 x + y2 x x2 +y 2 −y x2 +y 2 x2 − x2−y +y 2 ) x x2 +y 2 ! ∈H 1 6= 0. + y2 iii. To show that φ is an isomorphism, we must establish that φ is a bijective homomorphism. We know from (i) that φ is a homomorphism. φ is if also surjective: x −y x −y 2 2 . ∈ H, then x + y 6= 0 (so x + iy 6= 0) and φ(x + iy) = y x y x x −y a −b Furthermore, if φ(x + iy) = = = φ(a + ib), then x = a and y = b, so y x b a φ is injective. Question 8 (a) Let (G, ∗) and (G′ , ∗′ ) be groups, with identity elements e and e′ respectively. Suppose that φ : G → G′ is a homomorphism. i. Show that φ(e) = e′ . ii. Define the kernel ker(φ) of φ. iii. Show that ker(φ) is a subgroup of G. You may use without a proof that for a homomorphism φ and every a ∈ G, we have φ(a)−1 = φ(a−1 ). Reading for this question See Chapters 12, 13 and 14 of the subject guide for relevant reading for this question. Approaching the question i. Since φ is homomorphism, we have: φ(e) = φ(e ∗ e…

Purchase answer to see full attachment