Logic Integers Sets Functions Prime Numbers & Relations Questions

Description

Topics: Logic, integers, sets and functions, prime numbers, relations, real and complex

numbers, greatest common divisor and modular arithmetic, infimum and supremum, sequences,

limits of sequences, functions and limits of functions, continuity, groups.

4 attachmentsSlide 1 of 4attachment_1attachment_1attachment_2attachment_2attachment_3attachment_3attachment_4attachment_4

Unformatted Attachment Preview

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) = φ(e) ∗′ φ(e). Multiplying both sides by φ(e)−1 , we get φ(e) = e′ . ii. The kernel of φ is ker(φ) = {a ∈ G | φ(a) = e′ }. 13 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 MT2116 Abstract mathematics iii. To see that ker(φ) is a subgroup of (G, ∗), we have three conditions to check: • If a, b ∈ ker(φ), then φ(a ∗ b) = φ(a) ∗′ φ(b) = e′ ∗ e′ = e′ , hence a ∗ b ∈ ker(φ). • We have φ(e) = e′ , so e ∈ ker(φ). • If a ∈ ker(φ), then φ(a−1 ) = φ(a)−1 = (e′ )−1 = e′ and hence a−1 ∈ ker(φ). (b) Let φ : G → G′ be a homomorphism. Suppose that h ∈ im(φ), and let g ∈ G be such that φ(g) = h. i. Show that the set Sh = {x ∈ G | φ(x) = h} is equal to the left coset g ∗ ker(φ). ii. Deduce that, if G is a finite group, φ : G → G′ is a homomorphism and h is any element of im(φ), then the set Sh has size | ker(φ)|. Hence, deduce that |G| = | ker(φ)| · |im(φ)|. Approaching the question i. We show first that g ∗ ker(φ) ⊆ Sh . If x ∈ g ∗ ker(φ), then x = g ∗ a for some a ∈ ker(φ). Hence, φ(x) = φ(g ∗ a) = φ(g) ∗′ φ(a) = h ∗′ e′ = h, so we have x ∈ Sh . Now we show that Sh ⊆ g ∗ ker(φ). Every x ∈ Sh can be written as x = g ∗ (g −1 ∗ x), so we only need to show that g −1 ∗ x ∈ ker(φ). Indeed, φ(g −1 ∗ x) = φ(g −1 ) ∗′ φ(x) = φ(g)−1 ∗′ h = h−1 ∗′ h = e′ . ii. We know that all left cosets of ker(φ) have size | ker(φ)|, and there is one coset for each element of im(φ). As the cosets (or indeed the inverse images of elements of im(φ)) partition the group, we have that |G| is equal to the number of cosets times the size of each coset, as given. (c) Let (G, ∗) be a group. Let θ : G → G be defined by θ(g) = g ∗ g. Show that θ is a homomorphism if and only if G is Abelian. Approaching the question The function φ is a homomorphism if and only if φ(a ∗ b) = φ(a) ∗′ φ(b) for all a, b ∈ G, that is, (a ∗ b) ∗ (a ∗ b) = (a ∗ a) ∗ (b ∗ b) for all a, b ∈ G. This is true if G is Abelian: we have a ∗ b = b ∗ a, hence (a ∗ b) ∗ (a ∗ b) = a ∗ (b ∗ a) ∗ b = a ∗ (a ∗ b) ∗ b = (a ∗ a) ∗ (b ∗ b). On the other hand, if (a ∗ b) ∗ (a ∗ b) = (a ∗ a) ∗ (b ∗ b), then a−1 ∗ (a ∗ b) ∗ (a ∗ b) ∗ b−1 = a−1 ∗ (a ∗ a) ∗ (b ∗ b) ∗ b−1 , from which b ∗ a = a ∗ b follows. (d) If (G, ∗) is a finite Abelian group with identity e, use parts (b) and (c) to show that |G| = | {a ∈ G | a = g ∗ g for some g ∈ G} | · | {g ∈ G | g ⋆ g = e} |. Approaching the question If G is Abelian, then the function θ is a homomorphism by c). Its kernel is {g ∈ G | g ⋆ g = e}, and its image is {a ∈ G | a = g ∗ g for some g ∈ G}. The result now follows from (b). 14 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 Examiners’ commentaries 2017 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 B 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. 15 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 MT2116 Abstract mathematics 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 odd, then its cube, n3 , is odd. 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 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. The converse is: ‘If n3 is odd, then n is odd.’ The contrapositive of the converse if: ‘If n is not odd, then n3 is not odd,’ That is, it is ‘If n is even, then n3 is even.’ This is true: if n is even, then n = 2k for some integer k, and so n3 = 8k 3 = 2(4k 3 ) is even. 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 + 1)2 = r=1 1 12 n(n + 1)(n + 2)(3n + 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 16 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 Examiners’ commentaries 2017 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) Functions f : R → R and g : R → R are defined by 2x + 1 if x ≥ 0 f (x) = x if x < 0. 2x if x ≥ 0 g(x) = x + 2 if x < 0. Find a formula for the composition h(x) = f (g(x)). Is h a bijection? (Justify your answer.) Reading for this question Functions and their properties are dealt with in Chapter 4 of the subject guide. Approaching the question Suppose x ≥ 0. Then g(x) = 2x and 2x ≥ 0, so: h(x) = f (g(x)) = f (2x) = 2(2x) + 1 = 4x + 1. Now suppose x < 0. Then g(x) = x + 2. If x ≥ −2, x + 2 ≥ 0 and hence: h(x) = f (x + 2) = 2(x + 2) + 1 = 2x + 5. If x < −2, then x + 2 < 0 and then h(x) = f (x + 2) = x + 2. So:   4x + 1 if x ≥ 0 4x + 5 if −2 ≤ x < 0 h(x) =  x+2 if x < −2. h is not a bijection because, for example, h(0) = 1 = h(−1), so it is not injective. 17 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 MT2116 Abstract mathematics 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? The relation R is defined on Z by: a R b if and only if 3 divides a + 2b. Prove that R is an equivalence relation. 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, x + 2x = 3x is divisible by 3. R is symmetric because for any x, y, if x + 2y is divisible by 3, then so is y + 2x = 2(x + 2y) − 3y. R is transitive. For example, if x + 2y and y + 2z are divisible by 3, so too is x + 2z = (x + 2y) + (y + 2z) − 3y. 18 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 Examiners’ commentaries 2017 (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.2138. Express x in the form p/q where p and q are integers. Reading for this question See Chapter 8 of the subject guide. Approaching the question We have 1000x = 1213.8138 and so 1000x − x = 1213.8138 − 1.2138 = 1212.6. That is, 999x = 12126/10 and so: 12126 . 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: a= x−z . t−y 19 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 MT2116 Abstract mathematics 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= 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: √ 7 −1 −1 1 √ 1−8= ± ± i. z= 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. 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 ℓ is a lower bound for S? What does it mean to say that t is the infimum of S? ii. Let A and B be two non-empty sets of real numbers, both bounded below. Show that inf (A ∪ B) ≤ inf A. 20 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 Examiners’ commentaries 2017 iii. For non-empty sets A and B of real numbers, we say that A minorizes B if, for every b ∈ B, there is some a ∈ A with a ≤ b. Suppose that A minorizes B. Show that t = inf A is a lower bound for A ∪ B, and deduce that inf (A ∪ B) = t. iv. Is it true that, if inf (A ∪ B) = inf A, then A minorizes B ? Justify your answer by means of a proof or a counterexample. v. Is it true that, if inf A = inf B = t and t 6∈ B, then A minorizes 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 ℓ is a lower bound for S means that s ≥ ℓ for all s ∈ S. To say that t is the infimum of S means that: • t is a lower bound for S, and • for any ℓ > t, ℓ is not a lower bound for S.
ii. Let ℓ = inf (A ∪ B). We show that ℓ is a lower bound on A. Hence, by the second
property of infimum, inf A ≥ ℓ. Indeed, if a ∈ A, then a ∈ A ∪ B, so a ≥ ℓ.
iii. Suppose that A minorizes B, let t = inf A, and take any x ∈ A ∪ B. Either x ∈ A, in
which case x ≥ t because t is a lower bound on A, or x ∈ B, in which case there is some
a ∈ A such that x ≥ a ≥ t (because t is a lower bound on A). Thus, t is a lower bound
for A ∪ B.
Consequently, by the second property of infimum, inf (A ∪ B) ≥ t = inf A, and we have
equality by i.
iv. This is false. Consider A = (0, 1), B = [0, 1). Then inf (A ∪ B) = inf A = 0, but there is
no a ∈ A such that a ≤ 0 ∈ B, so A cannot minorize B.
v. This is true. Take any b ∈ B. As t is a lower bound for B, but t 6∈ B, we have b > t.
Now, as t is the infimum of A, b is not a lower bound for A, and so there is some a ∈ A
with a < b. Hence A minorizes 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) = x2 .
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.
ii. We apply the Intermediate Value Theorem with g(x) = x2 − f (x) and [a, b] = [0, 1].
Function g is continuous at every point x ≥ 0 because x2 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) = x2 .
Suppose that x1 < x2 are two solutions. Then f (x1 ) = x21 < x22 = f (x2 ), which contradicts the fact that f is decreasing. 21 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 MT2116 Abstract mathematics 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 = min{an , a2n }, for n ∈ N. Here min{x, y} = y for x ≥ y, and min{x, y} = x 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( n2 + 1 − n2 − 1); ii. (dn ), where dn = cos(πn)21/n . Approaching the question i. Observe that: p n2 + 1 − Hence: p n2 − 1 = √ √ √ √ ( n2 + 1 − n2 − 1)( n2 + 1 + n2 − 1) n2 + 1 − (n2 − 1) √ √ √ =√ . n2 + 1 + n2 − 1 n2 + 1 + n2 − 1 2n 2 n2 + 1 − (n2 − 1) p √ √ =√ =p cn = n √ 2 n2 + 1 + n2 − 1 n2 + 1 + n2 − 1 1 + 1/n + 1 − 1/n2 and, by the algebra of limits (Theorem 10.5 in the subject guide): lim cn = lim p n→∞ n→∞ 2 1 + 1/n2 + p 1 − 1/n2 =√ 2 √ = 1. 1+0+ 1−0 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 , we have cos(πn) = 1 and dn > 1/2 and, for odd n > N , we have
cos(πn) = −1 and dn < −1/2. This implies that (dn ) does not converge. 22 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 Examiners’ commentaries 2017 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 m −1 −m 0 If m > 0, then am = a
| ∗ a ∗{z· · · ∗ a}, if m < 0, then a = (a ) , and a = 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−1 ⋆ a ⋆ b. Approaching the question Note that (b−1 ⋆ a ⋆ b)n = (b−1 ⋆ a ⋆ b) ⋆ (b−1 ⋆ a ⋆ b) ⋆ · · · ⋆ (b−1 ⋆ a ⋆ b) = b−1 ⋆ a ⋆ (b ⋆ b−1 ) ⋆ a ⋆ (b ⋆ b−1 ) ⋆ a . . . a ⋆ (b ⋆ b−1 ) ⋆ a ⋆ b = b−1 ⋆ an ⋆ b. From this, it follows that an = e if and only if (b−1 ⋆ a ⋆ b)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 + iy)φ(a + ib) = = x y −y x a b −b a = ax − yb bx + ya −bx − ya ax − yb φ(ax − yb + i(bx + ya)) = φ (x + iy)(a + ib) . 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 23 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 MT2116 Abstract mathematics H is closed under multiplication: if a2 + b2 6= 0, and: x y −y x a b −b a −y a , x b x y = −b a ∈ H, then x2 + y 2 6= 0, ax − yb −(bx + ya) bx + ya ax − yb ∈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 x2 + y 2 2 x −y + = 2 = −(−y) x −y x2 + y 2 x x2 +y 2 −y x2 +y 2 − x2−y +y 2 ) x x2 +y 2 ! ∈H 1 6= 0. x2 + y 2 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 ∈ H, then x2 + y 2 6= 0 (so x + iy 6= 0) and φ(x + iy) = . y x y x a −b x −y = φ(a + ib), then x = a and y = b, so = Furthermore, if φ(x + iy) = b a y x φ 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 image im(φ) of φ. iii. Show that im(φ) 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) = φ(e) ∗′ φ(e). Multiplying both sides by φ(e)−1 , we get φ(e) = e′ . ii. The image of φ is im(φ) = {a′ ∈ G′ | φ(a) = a′ for some a ∈ G}. iii. To see that im(φ) is a subgroup of (G′ , ∗′ ), we have three conditions to check: • If a′ , b′ ∈ im(φ), then a′ = φ(a) and b′ = φ(b) for some a, b ∈ G. Hence a′ ∗′ b′ = φ(a) ∗′ φ(b) = φ(a ∗ b), and a′ ∗′ b′ ∈ im(φ). • We have φ(e) = e′ , so e′ ∈ im(φ). • If a′ ∈ im(φ), then a′ = φ(a) for some a ∈ G. Hence a′−1 = φ(a)−1 = φ(a−1 ), and so a′−1 ∈ im(φ). 24 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 Examiners’ commentaries 2017 (b) Let φ : G → G′ be a homomorphism. Suppose that h ∈ im(φ), and let g ∈ G be such that φ(g) = h. i. Show that the set Sh = {x ∈ G | φ(x) = h} is equal to the left coset g ∗ ker(φ). ii. Deduce that, if G is a finite group, φ : G → G′ is a homomorphism and h is any element of im(φ), then the set Sh has size | ker(φ)|. Hence, deduce that |G| = | ker(φ)| · |im(φ)|. Approaching the question i. We show first that g ∗ ker(φ) ⊆ Sh . If x ∈ g ∗ ker(φ), then x = g ∗ a for some a ∈ ker(φ). Hence, φ(x) = φ(g ∗ a) = φ(g) ∗′ φ(a) = h ∗′ e′ = h, so we have x ∈ Sh . Now we show that Sh ⊆ g ∗ ker(φ). Every x ∈ Sh can be written as x = g ∗ (g −1 ∗ x), so we only need to show that g −1 ∗ x ∈ ker(φ). Indeed, φ(g −1 ∗ x) = φ(g −1 ) ∗′ φ(x) = φ(g)−1 ∗′ h = h−1 ∗′ h = e′ . ii. We know that all left cosets of ker(φ) have size | ker(φ)|, and there is one coset for each element of im(φ). As the cosets (or indeed the inverse images of elements of im(φ)) partition the group, we have that |G| is equal to the number of cosets times the size of each coset, as given. (c) Let (G, ∗) be a group. Let θ : G → G be defined by θ(g) = g ∗ g. Show that θ is a homomorphism if and only if G is Abelian. Approaching the question The function φ is a homomorphism if and only if φ(a ∗ b) = φ(a) ∗′ φ(b) for all a, b ∈ G, that is, (a ∗ b) ∗ (a ∗ b) = (a ∗ a) ∗ (b ∗ b) for all a, b ∈ G. This is true if G is Abelian: we have a ∗ b = b ∗ a, hence (a ∗ b) ∗ (a ∗ b) = a ∗ (b ∗ a) ∗ b = a ∗ (a ∗ b) ∗ b = (a ∗ a) ∗ (b ∗ b). On the other hand, if (a ∗ b) ∗ (a ∗ b) = (a ∗ a) ∗ (b ∗ b), then a−1 ∗ (a ∗ b) ∗ (a ∗ b) ∗ b−1 = a−1 ∗ (a ∗ a) ∗ (b ∗ b) ∗ b−1 , from which b ∗ a = a ∗ b follows. (d) If (G, ∗) is a finite Abelian group with identity e, use parts (b) and (c) to show that |G| = | {a ∈ G | a = g ∗ g for some g ∈ G} | · | {g ∈ G | g ⋆ g = e} |. Approaching the question If G is Abelian, then the function θ is a homomorphism by c). Its kernel is {g ∈ G | g ⋆ g = e}, and its image is {a ∈ G | a = g ∗ g for some g ∈ G}. The result now follows from (b). 25 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 Notes - qqqqqqqqqq Abstract mathematics (University of London) StuDocu is not sponsored or endorsed by any college or university Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 Math 13 — An Introduction to Abstract Mathematics Neil Donaldson & Alessandra Pantano January 21, 2020 Contents 1 Introduction 2 Logic and the Language of Proofs 2.1 Propositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Methods of Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Quantifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 9 21 36 3 Divisibility and the Euclidean Algorithm 3.1 Remainders and Congruence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Greatest Common Divisors and the Euclidean Algorithm . . . . . . . . . . . . . . . . . 46 46 53 4 Sets and Functions 4.1 Set Notation and Describing a Set . . . . . 4.2 Subsets . . . . . . . . . . . . . . . . . . . . 4.3 Unions, Intersections, and Complements 4.4 Introduction to Functions . . . . . . . . . . . . . 59 59 66 69 75 . . . . 86 86 90 96 105 5 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Mathematical Induction and Well-ordering 5.1 Investigating Recursive Processes . . . . . . . . . . . . . . . 5.2 Proof by Induction . . . . . . . . . . . . . . . . . . . . . . . 5.3 Well-ordering and the Principle of Mathematical Induction 5.4 Strong Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 Set Theory, Part II 110 6.1 Cartesian Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 6.2 Power Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 6.3 Indexed Collections of Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 7 Relations and Partitions 7.1 Relations . . . . . . . . . . . . . . . . . . 7.2 Functions revisited . . . . . . . . . . . . 7.3 Equivalence Relations . . . . . . . . . . 7.4 Partitions . . . . . . . . . . . . . . . . . . 7.5 Well-definition, Rings and Congruence . 7.6 Functions and Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Downloaded by lex lexus (localfocalpoint@gmail.com) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 131 136 142 148 156 160 lOMoARcPSD|5093418 8 Cardinalities of Infinite Sets 165 8.1 Cantor’s Notion of Cardinality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165 8.2 Uncountable Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 Useful Texts • Book of Proof, Richard Hammack, 2nd ed 2013. Available free online! Very good on the basics: if you’re having trouble with reading set notation or how to construct a proof, this book’s for you! These notes are deliberately pitched at a high level relative to this textbook to provide contrast. • Mathematical Reasoning, Ted Sundstrom, 2nd ed 2014. Available free online! Excellent resource. If you would like to buy the actual book, you can purchase it on Amazon at a really cheap price. • Mathematical Proofs: A Transition to Advanced Mathematics, Chartrand/Polimeni/Zhang, 3rd Ed 2013, Pearson. The most recent course text. Has many, many exercises; the first half is fairly straightforward while the second half is much more complex and dauntingly detailed. • The Elements of Advanced Mathematics, Steven G. Krantz, 2nd ed 2002, Chapman & Hall and Foundations of Higher Mathematics, Peter Fletcher and C. Wayne Patty, 3th ed 2000, Brooks–Cole are old course textbooks for Math 13. Both are readable and concise with good exercises. Learning Outcomes 1. Developing the skills necessary to read and practice abstract mathematics. 2. Understanding the concept of proof, and becoming acquainted with several proof techniques. 3. Learning what sort of questions mathematicians ask, what excites them, and what they are looking for. 4. Introducing upper-division mathematics by giving a taste of what is covered in several areas of the subject. Along the way you will learn new techniques and concepts. For example: Number Theory Five people each take the same number of candies from a jar. Then a group of seven does the same. The, now empty, jar originally contained 239 candies. Can you decide how much candy each person took? Geometry and Topology How can we visualize and compute with objects like the Mobius strip? Fractals How to use sequences of sets to produce objects that appear the same at all scales. To Infinity and Beyond! Why are some infinities greater than others? Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 1 Introduction What is Mathematics? For many students this course is a game-changer. A crucial part of the course is the acceptance that upper-division mathematics is very different from what is presented at grade-school and in the calculus sequence. Some students will resist this fact and spend much of the term progressing through the various stages of grief (denial, anger, bargaining, depression, acceptance) as they discover that what they thought they excelled at isn’t really what the subject is about. Thus we should start at the beginning, with an attempt to place the mathematics you’ve learned within the greater context of the subject. The original Greek meaning of the word mathemata is the supremely unhelpful, “That which is to be known/learned.” There is no perfect answer to our question, but a simplistic starting point might be to think of your mathematics education as a progression. Arithmetic College Calculus Abstract Mathematics In elementary school you largely learn arithmetic and the basic notions of shape. This is the mathematics all of us need in order to function in the real world. If you don’t know the difference between 15,000 and 150,000, you probably shouldn’t try to buy a new car! For the vast majority of people, arithmetic is the only mathematics they’ll ever need. Learn to count, add, and work with percentages and you are thoroughly equipped for most things life will throw at you. Calculus discusses the relationship between a quantity and its rate of change, the applications of which are manifold: distance/velocity, charge/current, population/birth-rate, etc. Elementary calculus is all about solving problems: What is the area under the curve? How far has the projectile traveled? How much charge is in the capacitor? By now you will likely have computed many integrals and derivatives, but perhaps you have not looked beyond such computations. A mathematician explores the theory behind the calculations. From an abstract standpoint, calculus is the beautiful structure of the Riemann integral and the Fundamental Theorem, understanding why we can use anti-derivatives to compute area. To an engineer, the fact that integrals can be used to model the bending of steel beams is crucial, while this might be of only incidental interest to a mathematician. Perhaps the essential difference between college calculus and abstract mathematics is that the former is primarily interested in the utility of a technique, while the latter focuses on structure, veracity and the underlying beauty. In this sense, abstract mathematics is much more of an art than a science. No-one measures the quality of a painting or sculpture by how useful it is, instead it is the structure, the artist’s technique and the quality of execution that are praised. Research mathematicians, both pure and applied, view mathematics the same way. In areas of mathematics other than Calculus, the link to applications is often more tenuous. The structure and distribution of prime numbers were studied for over 2000 years before, arguably, any serious applications were discovered. Sometimes a real-world problem motivates generalizations that have no obvious application, and may never do so. For example, the geometry of projecting 3D objects onto a 2D screen has obvious applications (TV, computer graphics/design). Why would anyone want to consider projections from 4D? Or from 17 dimensions? Sometimes an application will appear later, sometimes not.1 The reason the mathematician studies such things is because the structure appears beautiful to them and they want to appreciate it more deeply. Just like a painting. 1 There are very useful applications of high-dimensional projections, not least to economics and the understanding of sound and light waves. 3 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 The mathematics you have learned so far has consisted almost entirely of computations, with the theoretical aspects swept under the rug. At upper-division level, the majority of mathematics is presented in an abstract way. This course will train you in understanding and creating abstract mathematics, and it is our hope that you will develop an appreciation for it. Proof The essential concept in higher-level mathematics is that of proof. A basic dictionary entry for the word would cover two meanings: 1. An argument that establishes the truth of a fact. 2. A test or trial of an assertion.2 In mathematics we always mean the former, while in much of science and wider culture the second meaning predominates. Indeed mathematics is one of the very few disciplines in which one can categorically say that something is true or false. In reality we can rarely be so certain. A greasy salesman in a TV advert may claim that to have proved that a certain cream makes you look younger; a defendant may be proved guilty in court; the gravitational constant is 9.81ms−2 . Ask yourself what these statements mean. The advert is just trying to sell you something, but push harder and they might provide some justification: e.g. 100 people used the product for a month and 75 of them claim to look younger. This is a test, a proof in the second sense of the definition. Is a defendant really guilty of a crime just because a court has found them so; have there never been any miscarriages of justice? Is the gravitational constant precisely 9.81ms−2 , or is this merely a good approximation? This kind of pedantry may seem over the top in everyday life: indeed most of us would agree that if 75% of people think a cream helps, then it probably is doing something beneficial. In mathematics and philosophy, we think very differently: the concepts of true and false and of proof are very precise. So how do mathematicians reach this blissful state where everything is either right or wrong and, once proved, is forever and unalterably certain? The answer, rather disappointingly, is by cheating. Nothing in mathematics is true except with reference to some assumption. For example, consider the following theorem: Theorem 1.1. The sum of any two even integers is even. We all believe that this is true, but can we prove it? In the sense of the second definition of proof, it might seem like all we need to do is to test the assertion: for example 4 + 6 = 10 is even. In the first sense, the mathematical sense, of proof, this is nowhere near enough. What we need is a definition of even.3 Definition 1.2. An integer is even if it may be written in the form 2n where n is an integer. The proof of the theorem now flows straight from the definition. 2 It is this notion that makes sense of the seemingly oxymoronic phrase The exception proves the rule. It is the exception that tests the validity of the rule. 3 And more fundamentally of sum and integer. 4 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 Proof. Let x and y be any two even integers. We want to show that x + y is an even integer. By definition, an integer is even if it can be written in the form 2k for some integer k. Thus there exist integers n, m such that x = 2m and y = 2n. We compute: x + y = 2m + 2n = 2(m + n). (∗) Because m + n is an integer, this shows that x + y is an even integer. There are several important observations: • ‘Any’ in the statement of the theorem means the proof must work regardless of what even integers you choose. It is not good enough to simply select, for example, 4 and 16, then write 4 + 16 = 20. This is an example, or test, of the theorem, not a mathematical proof. • According to the definition, 2m and 2n together represent all possible pairs of even numbers. • The proof makes direct reference to the definition. The vast majority of the proofs in this course are of this type. If you know the definition of every word in the statement of a theorem, you will often discover a proof simply by writing down the definitions. • The theorem itself did not mention any variables. The proof required a calculation for which these were essential. In this case the variables m and n come for free once you write the definition of evenness! A great mistake is to think that the proof is nothing more than the calculation (∗). This is the easy bit, and it means nothing without the surrounding sentences. The important link between theorems and definitions is much of what learning higher-level mathematics is about. We prove theorems (and solve homework problems) because they make us use and understand the subtleties of definitions. One does not know mathematics, one does it. Mathematics is a practice; an art as much as it is a science. Conjectures In this course, you will discover that one of the most creative and fun aspects of mathematics is the art of formulating, proving and disproving conjectures. To get a taste, consider the following: Conjecture 1.3. If n is any odd integer, then n2 − 1 is a multiple of 8. Conjecture 1.4. For every positive integer n, the integer n2 + n + 41 is prime. A conjecture is the mathematician’s equivalent of the experimental scientist’s hypothesis: a statement that one would like to be true. The difference lies in what comes next. The mathematician will try to prove that a conjecture is undeniably true by relying on logic, while the scientist will apply the scientific method, conducting experiments attempting, and hopefully failing, to show that a hypothesis is incorrect. 5 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 Once a mathematician proves the validity of a conjecture it becomes a theorem. The job of a mathematics researcher is thus to formulate conjectures, prove them, and publish the resulting theorems. The creativity lies as much in the formulation as in the proof. As you go through the class, try to formulate conjectures. Like as not, many of your conjectures will be false, but you’ll gain a lot from trying to form them. Let us return to our conjectures: are they true or false? How can we decide? As a first attempt, we may try to test the conjectures by computing with some small integers n. In practice this would be done before stating the conjectures. n 1 3 n2 − 1 0 8 24 48 80 120 168 5 7 9 11 13 n 1 n2 + n + 41 43 47 53 61 71 83 97 2 3 4 5 6 7 Because 0, 8, 24, 48, 80, 120 and 168 are all multiples of 8, and 43, 47, 53, 61, 71, 83 and 97 are all prime, both conjectures appear to be true. Would you bet $100 that this is indeed the case? Is n2 − 1 a multiple of 8 for every odd integer n? Is n2 + n + 41 prime for every positive integer n? The only way to establish whether a conjecture is true or false is by doing one of the following: Prove it by showing it must be true in all cases, or, Disprove it by finding at least one instance in which the conjecture is false. Let us work with Conjecture 1.3. If n is an odd integer, then, by definition, we can write it as n = 2k + 1 for some integer k. Then n2 − 1 = (2k + 1)2 − 1 = (4k2 + 1 + 4k) − 1 = 4k2 + 4k. We need to investigate whether this is always a multiple of 8. Since 4k2 + 4k = 4(k2 + k ) is already a multiple of 4, it all comes down to deciding whether or not k2 + k contains a factor 2 for all possible choices of k; i.e. is k2 + k even? Do we believe this? We can return to trying out some small values of k: k k2 + k −2 −1 0 1 2 2 0 3 4 0 2 6 12 20 Once again, the claim seems to be true for small values of k, but how do we know it is true for all k? Again, the only way is to prove it or disprove it. How to proceed? The question here is whether or not k2 + k is always even. Factoring out k, we get: k 2 + k = k ( k + 1). We have therefore expressed k2 + k as a product of two consecutive integers. This is great, because for any two consecutive integers, one is even and the other is odd, and so their product must be even. We have now proved that the conjecture is true. Conjecture 1.3 is indeed a theorem! Everything we’ve done so far has been investigative, and is laid out in an untidy way. We don’t want the reader to have to wade through all of our scratch work, so we formalize the above argument. This is the final result of our deliberations; investigate, spot a pattern, conjecture, prove, and finally present your work in as clean and convincing a manner as you can. 6 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 Theorem 1.5. If n is any odd integer, then n2 − 1 is a multiple of 8. Proof. Let n be any odd integer; we want to show that n2 − 1 is a multiple of 8. By the definition of odd integer, we may write n = 2k + 1 for some integer k. Then n2 − 1 = (2k + 1)2 − 1 = (4k2 + 1 + 4k ) − 1 = 4k2 + 4k = 4k (k + 1). We distinguish two cases. If k is even, then k (k + 1) is even and so 4k (k + 1) is divisible by 8. If k is odd, then k + 1 is even. Therefore k (k + 1) is again even and 4k (k + 1) divisible by 8. In both cases n2 − 1 = 4k (k + 1) is divisible by 8. This concludes the proof. It is now time to explore Conjecture 1.4. The question here is whether or not n2 + n + 41 is a prime integer for every positive integer n. We know that when n = 1, 2, 3, 4, 5, 6 or 7 the answer is yes, but examples do not make a proof. At this point, we do not know whether the conjecture is true or false. Let us investigate the question further. Suppose that n is any positive integer; we must ask whether it is possible to factor n2 + n + 41 as a product of two positive integers, neither of which is one.4 When n = 41 such a factorization certainly exists, since we can write 412 + 41 + 41 = 41(41 + 1 + 1) = 41 · 43. Our counterexample shows that there exists at least one value of n for which n2 + n + 41 is not prime. We have therefore disproved the conjecture that ‘for all positive integers n, n2 + n + 41 is prime,’ and so Conjecture 1.4 is false! The moral of the story is this: to show that a conjecture is true you must prove that it holds for all the cases in consideration, but to show that it is false a single counterexample suffices. Conjectures: True or False? Do your best to prove or disprove the following conjectures. Then revisit these problems at the end of the course to realize how much your proof skills have improved. 1. The sum of any three consecutive integers is even. 2. There exist integers m and n such that 7m + 5n = 4. 3. Every common multiple of 6 and 10 is divisible by 60. 4. There exist integers x and y such that 6x + 9y = 10. 5. For every positive real number x, x + 1 x is greater than or equal to 2. 6. If x is any real number, then x2 ≥ x. 4 Once again we rely on a definition: a positive integer is prime if it cannot be written as a product of two integers, both greater than one. 7 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 7. If n is any integer, n2 + 5n must be even. 8. If x is any real number, then | x | ≥ − x. 9. Consider the set R of all real numbers. For all x in R, there exists y in R such that x < y. 10. Consider the set R of all real numbers. There exists x in R such that, for all y in R, x < y. 11. The sets A = {n ∈ N : n2 < 25} and B = {n2 : n ∈ N and n < 5} are equal. Here N denotes the set of natural numbers. Now we know a little of what mathematics is about, it is time to practice some of it! 8 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 2 Logic and the Language of Proofs In order to read and construct proofs, we need to start with the language in which they are written: logic. Logic is to mathematics what grammar is to English. Section 2.1 will not look particularly mathematical, but we’ll quickly get to work in Section 2.2 using logic in a mathematical context. 2.1 Propositions Definition 2.1. A proposition or statement is a sentence that is either true or false. Examples. 2. 392 1. 17 − 24 = 7. is an odd integer. 3. The moon is made of cheese. 4. Every cloud has a silver lining. 5. God exists. In order to make sense, these propositions require a clear definition of every concept they contain. There are many concepts of God in many cultures, but once it is decided which we are talking about, it is clear that They either exist or do not. This example illustrates that a statement need not be indisputably true or false, or even determinable, in order to qualify as a proposition. Mostly when people argue over propositions and statements, what they are really disagreeing about are definitions! Note that any expression that is neither true nor false is not a proposition. January 1st is not a proposition, neither is Green. Truth Tables One often has to deal with abstract propositions; those where you do not know the truth or falsity, or indeed when you don’t explicitly know the proposition! In such cases it can be convenient to represent the combinations of propositions in a tabular format. For instance, if we have two propositions (P and Q), or even three (P, Q and R) then all possible combinations of truth T and falsehood F are represented in the following tables: P Q T T T F F T F F P Q R T T T T T F T F T T F F F T T F T F F F T F F F The mathematician in you should be looking for patterns and asking: how many rows would a truth table corresponding to n propositions have, and can I prove my assertion? Right now it is hard to prove that the answer is 2n : induction (Chapter 5) makes this very easy. 9 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 Connecting Propositions: Conjunction, Disjunction and Negation We now define how to combine propositions in natural ways, modeled on the words and, or and not. Definition 2.2. Let P and Q be propositions. The conjunction (AND, ∧) of P and Q, the disjunction (OR, ∨) of P and Q, and the negation or denial (NOT, ¬, ∼, ) of P are defined by the truth tables, P Q P∧Q T T T F T F F T F F F F P ¬P T F F T P Q P∨Q T T T T T F F T T F F F It is usually better to use and, or and not rather than conjunction, disjunction and negation: the latter may make you sound educated, but at the risk of being misunderstood! Example. Let P, Q and R be the following propositions: P. Irvine is a city in California. Q. Irvine is a town in Ayrshire, Scotland. R. Irvine has seven letters. Clearly P is true while R is false. If you happen to know someone from Scotland, you might know that Q is true.a We can now compute the following (increasingly grotesque) combinations. . . P ∧ Q P ∨ Q P ∧ R ¬ R (¬ R) ∧ P ¬( R ∨ P) (¬ P) ∨ [((¬ R) ∨ P) ∧ Q] T T F T T F T a The second syllable is pronounced like the i in bin or win. Indeed the first Californian antecedent of the Irvine family which gave its name to UCI was an Ulster-Scotsman named James Irvine (1827–1886). Probably the family name was originaly pronounced in the Scottish manner. How did we establish these facts? Some are quick, and can be done in your head. Consider, for instance, the statement (¬ R) ∧ P. Because R is false, ¬ R is true. Thus (¬ R) ∧ P is the conjunction of two true statements, hence it is true. Similarly, we can argue that R ∨ P is true (because R is false and P is true), so the negation ¬( R ∨ P) is false. Establishing the truth value of the final proposition (¬ P) ∨ [((¬ R) ∨ P) ∧ Q] requires more work. You may want to set up a truth table with several auxiliary columns to help you compute: P Q R ¬ P ¬ R (¬ R) ∨ P ((¬ R) ∨ P) ∧ Q (¬ P) ∨ [((¬ R) ∨ P) ∧ Q] T T F F T T T T The importance of parentheses in a logical expressions cannot be stressed enough. For example, try building the truth table for the propositions P ∨ ( Q ∧ R) and ( P ∨ Q) ∧ R. Are they the same? 10 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 Conditional and Biconditional Connectives In order to logically set up proofs, we need to see how propositions can lead one to another. Definition 2.3. The conditional ( =⇒ ) and biconditional ( ⇐⇒ ) connectives have the truth tables P Q P =⇒ Q T T T F T F F T T T F F P Q P ⇐⇒ Q T T T F T F F T F T F F For the proposition P =⇒ Q, we call P the hypothesis and Q the conclusion. Observe that the expressions P =⇒ Q and P ⇐⇒ Q are themselves propositions: they are sentences which are either true or false! Synonyms =⇒ and ⇐⇒ can be read in many different ways: P =⇒ Q P implies Q Q if P P only if Q P is sufficient for Q Q is necessary for P P ⇐⇒ Q P if and only if Q P iff Q P and Q are (logically) equivalent P is necessary and sufficient for Q Example. The following propositions all mean exactly the same thing: • If you are born in Rome, then you are Italian. • You are Italian if you are born in Rome. • You are born in Rome only if you are Italian. • Being born in Rome is sufficient to be Italian. • Being Italian is necessary for being born in Rome. Are you comfortable with what P and Q are here? The biconditional connective should be easy to remember: P ⇐⇒ Q is true precisely when P and Q have identical truth states. It is harder to make sense of the conditional connective. One way of thinking about it is to consider what it means for an implication to be false. If P =⇒ Q is false, it is impossible to create a logical argument which assumes P and concludes Q. The second row of P =⇒ Q encapsulates the fact that it should be impossible for truth ever to logically imply falsehood. 11 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 Aside. Why is F =⇒ T considered true? This is the most immediately confusing part of the truth table for the conditional connective. Here is a mathematical example, written with an English translation at the side. 7 = 3 =⇒ 0 · 7 = 0 · 3 (If 7 = 3, then 0 times 7 equals 0 times 3) =⇒ 0 = 0 (then 0 equals 0) Thus 7 = 3 =⇒ 0 = 0. Logically speaking this is a perfectly correct argument, thus the implication is true. The argument makes us uncomfortable because 7 = 3 is clearly false. If you want to understand connectives more deeply than this, then take a logic or philosophy course! For example, although neither statement makes the least bit of sense in English; “17 is odd =⇒ Mexico is in China” is false, whilst “17 is even =⇒ Mexico is in China” is true. Such bizarre constructions are happily beyond the consideration of this course! Theorems and Direct Proofs Truth tables and connectives are very abstract. To apply them to mathematics we need the following basic notions of theorem and proof. Definition 2.4. A theorem is a justified assertion that some statement of the form P =⇒ Q is true. A proof is an argument that justifies the truth of a theorem. Think back to the truth table for P =⇒ Q in Definition 2.3. Suppose that the hypothesis P is true and that P =⇒ Q is true: that is, P =⇒ Q is a theorem. We must be in the first row of the truth table, and so the conclusion Q is also true. This is how we think about proving basic theorems. In a direct proof we start by assuming the hypothesis (P) is true and make a logical argument (P =⇒ Q) which asserts that the conclusion (Q) is true. As such, it often convenient to rewrite the statement of a theorem as an implication of the form P =⇒ Q. Here is a very simple theorem which we prove directly. Theorem 2.5. The product of two odd integers is odd. The first thing to do is to write the theorem in terms of propositions and connectives: that is, in the form P =⇒ Q. • P is ‘x and y are odd integers.’ This is our assumption, the hypothesis. • Q is ‘The product of x and y is odd.’ This is what we want to show, the conclusion. • Showing that P =⇒ Q is true, that (the truth of) P implies (the truth of) Q requires an argument. This is the proof. 12 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 Proof. Let x and y be any two odd integers. We want to show that product x · y is an odd integer. By definition, an integer is odd if it can be written in the form 2k + 1 for some integer k. Thus there must be integers n, m such that x = 2n + 1 and y = 2m + 1. We compute: x · y = (2n + 1)(2m + 1) = 4mn + 2n + 2m + 1 = 2(2mn + n + m) + 1. Because 2mn + n + m is an integer, this shows that x · y is an odd integer. It is common to place a symbol (in this case ) at the end of a proof to tell the reader that your argument is complete. Traditionally the letters Q.E.D. (from the Latin quod erat demonstrandum, literally ‘which is what had to be demonstrated’) were used, but this has gone out of style.You may also feel that you want to write more, or less than the above. This is a difficult thing to judge. What do you feel is a convincing argument? Test your argument on your classmates. The appropriate level of detail will depend on your readership: a middle school student will need more detail than a graduate student! At the moment, the best guide is to write for someone with the same mathematical sophistication as yourself. If, in three weeks’ time, you can return to what you’ve written and understand it, then it’s probably good! The Converse and Contrapositive The following constructions are used continually in mathematics: it is vitally important to know the difference between them. Definition 2.6. The converse of an implication P =⇒ Q is the reversed implication Q =⇒ P. The contrapositive of P =⇒ Q is ¬ Q =⇒ ¬ P. In general, we cannot say anything about the truth value of the converse of a true statement. The contrapositive of a true statement is, however, always true. Theorem 2.7. The contrapositive of an implication is logically equivalent the original implication. Proof. Simply use our definitions of negation and implication to compute the truth table: P Q P =⇒ Q T T T T F F T F T F F T ¬Q ¬P ¬Q F F T F F T T T =⇒ ¬ P T F T T Since the truth states in the third and sixth columns are identical, we see that P =⇒ Q and its contrapositive ¬ Q =⇒ ¬ P are logically equivalent. 13 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 Example. Let P and Q be the following statements: P. Claudia is holding a peach. Q. Claudia is holding a piece of fruit. The implication P =⇒ Q is true, since all peaches are fruit. As a sentence, we have: If Claudia is holding a peach, then Claudia is holding a piece of fruit. The converse of P =⇒ Q is the sentence: If Claudia is holding a piece of fruit, then Claudia is holding a peach. This is palpably false: Claudia could be holding an apple! The contrapositive of P =⇒ Q is the following sentence: If Claudia is not holding any fruit, then she is not holding a peach. This is clearly true. Proof by Contrapositive The fact that P =⇒ Q and ¬ Q =⇒ ¬ P are logically equivalent allows us, when convenient, to prove P =⇒ Q by instead proving its contrapositive. As an example, consider another basic theorem. Theorem 2.8. Let x and y be integers. If x + y is odd, then exactly one of x or y is odd. The theorem is an implication of the form P =⇒ Q where P. The sum x + y of integers x and y is odd. Q. Exactly one of x or y is odd. A direct proof would require that we assume P to be true and logically deduce the truth of Q. For instance we might start our argument with: Suppose that x + y = 2n + 1 for some integer n The problem is that this doesn’t really tell us anything about x and y, which we need to think about in order to demonstrate the truth of Q. Instead we consider the negations of our propositions: ¬ Q. ¬ P. x and y are both even or both odd (they have the same parity). The sum x + y of integers x and y is even. Since P =⇒ Q is logically equivalent to the seemingly simpler contrapositive (¬ Q) =⇒ (¬ P), we choose to prove the latter. This is, by Theorem 2.7, equivalent to proving the original implication. 14 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 Proof. Assume that x and y have the same parity. There are two cases: x and y are both even, or both odd. Case 1: Let x = 2m and y = 2n be even. Then x + y = 2(m + n) is even. Case 2: Let x = 2m + 1 and y = 2n + 1 be odd. Then x + y = 2(m + n + 1) is even. In both cases x + y is even, and the result is proved. De Morgan’s Laws In order to perform proofs by contrapositive (and later by contradiction) it is necessary to compute the negations of propositions. The most helpful results in this regard are attributable to Augustus de Morgan, a very famous 19th century logician. Theorem 2.9 (de Morgan’s laws). Let P and Q be any propositions. Then: 1. ¬( P ∧ Q) ⇐⇒ ¬ P ∨ ¬ Q. 2. ¬( P ∨ Q) ⇐⇒ ¬ P ∧ ¬ Q. The first law says that the negation of P ∧ Q is logically equivalent to ¬ P ∨ ¬ Q: that is, the two expressions have the same truth table. Here is a proof of the first law. Try the second on your own. Proof. P Q P ∧ Q ¬( P ∧ Q) ¬ P ¬ Q ¬ P ∨ ¬ Q T T T F F F F T F F T F T T F T F T T F T F T T T T F F Simply observe that the fourth and seventh columns are identical. It is worth pausing to observe how similar the two laws are, and how concise. There is some beauty here. With a written example the laws are much easier to comprehend. Example. (Of the first law) Suppose that of a morning you can choose (or not) to ride the subway to work, and you can choose (or not) to have a cup of coffee. Consider the following sentence: I rode the subway and I had coffee. What would it mean for this sentence to be false? Any sentence which asserts the falsehood of the above is a suitable negation. For example: I didn’t ride the subway or I didn’t have coffee. Note that the mathematical use of or includes the possibility that you neither rode the subway nor had coffee. You will see de Morgan’s laws again when we encounter sets. 15 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 Aside. Think about the meaning! In the previous example we saw how negation switches and to or. This is true only when and denotes a conjunction between two propositions. Before applying De Morgan’s laws, think about the meaning of the sentence. For example, the negation of Mark and Mary have the same height. is the proposition: Mark and Mary do not have the same height. If you blindly appeal to De Morgan’s laws you might end up with the following piece of nonsense: Mark or Mary do not have the same height. Logical rules are wonderfully concise, but very easy to misuse. Always think about the meaning of a sentence and you shouldn’t go wrong. Negating Conditionals You will often want to understand the negation of a statement. In particular, it is important to understand the negation of a conditional P =⇒ Q. Is it enough to say ‘P doesn’t imply Q’? And what could this mean? To answer the question you can use truth tables, or just think. Here is the truth table for P =⇒ Q and its negation: recall that negation simply swaps T and F. P Q P =⇒ Q ¬( P T T T F T F F T T F F T =⇒ Q) F T F F The only time there is a T in the final column is when both P is true and Q is false. We have therefore proved the following: Theorem 2.10. ¬( P =⇒ Q) is logically equivalent to P ∧ ¬ Q (read ‘P and not Q’). Now think in words rather than calculate. What is the negation of the following implication? It’s the morning therefore I’ll have coffee. Hopefully it is clear that the negation is: It’s the morning and I won’t have coffee. The implication ‘therefore’ has disappeared and the expression ‘and won’t’ is in its place. Warning! The negation of P =⇒ Q is not a conditional. In particular it is neither of the following: The converse, Q =⇒ P. The contrapositive of the converse, ¬ P =⇒ ¬ Q. If you are unsure about this, write down the truth tables and compare. 16 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 Example. Let x be an integer. What is the negation of the following sentence? If x is even, then x2 is even. Written in terms of propositions, we wish to negate P =⇒ Q , where P and Q are: P. x is even. Q. x2 is even. The negation of P =⇒ Q is P ∧ ¬ Q, namely: x is even and x2 is odd. This is very different to ¬ P =⇒ ¬ Q (if x is odd then x2 is odd). Keep yourself straight by thinking about the meaning of these sentences. It should be obvious that ‘x even =⇒ x2 even’ is true. It negation should therefore be false. The fact that it is false should make reading the negation feel a little uncomfortable. Tautologies and Contradictions We finish this section with two related concepts that are helpful for understanding proofs. Definition 2.11. A tautology is a logical expression that is always true, regardless of what the component statements might be. A contradiction is a logical expression that is always false. The easiest way to detect these is simply to construct a truth table. Examples. 1. P ∧ (¬ P) is a very simple contradiction: P ¬ P P ∧ (¬ P) T F F F F T Whatever the proposition P is, it cannot be true at the same time as its negation. 2. ( P ∧ ( P =⇒ Q)) =⇒ Q is a tautology. This is essentially how we understand a direct proof: if P is true and we have a correct argument P =⇒ Q, then Q must also be true. P Q P =⇒ Q P ∧ ( P T T T F T F F T T T F F =⇒ Q) ( P ∧ ( P =⇒ Q)) =⇒ Q T T F T F T F T 17 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 Aside. Algebraic Logic One can study logic in a more algebraic manner. De Morgan’s Laws are algebraic. Here are a few of the other basic laws of logic: P ∧ Q ⇐⇒ Q ∧ P P ∨ Q ⇐⇒ Q ∨ P ( P ∧ Q) ∧ R ⇐⇒ P ∧ ( Q ∧ R) ( P ∧ Q) ∨ R ⇐⇒ ( P ∨ R) ∧ ( Q ∨ R) ( P ∨ Q) ∨ R ⇐⇒ P ∨ ( Q ∨ R) ( P ∨ Q) ∧ R ⇐⇒ ( P ∧ R) ∨ ( Q ∧ R) The three pairs are, respectively, the commutative, associative, and distributive laws of logic, and you can check them all with truth tables. Using these rules, one can answer questions, such as deciding when an expression is a tautology, without laboriously creating truth tables. It is even fun! Such an approach is appropriate when you are considering abstract propositions, say in a formal logic course. In this text our primary interest with logic lies in using it to prove theorems. When one has an explicit theorem it is important to keep the meanings of all propositions clear. By relying too much on abstract laws like the above, it is easy to lose the meaning and write nonsense! Self-test Questions (fill in the blanks or select the correct word) • A tautology is a proposition which • A contradiction is a proposition which • The contrapositive of the conditional P =⇒ Q is the conditional • The converse/contrapositive of P =⇒ Q is logically equivalent to P =⇒ Q. • The converse of P =⇒ Q is always logically equivalent to P =⇒ Q. • The negation of the conditional P =⇒ Q is the proposition • State de Morgan’s laws for propositions P and Q: ¬( P ∨ Q) ⇐⇒ ¬( P ∧ Q) ⇐⇒ Exercises 2.1.1 Express each of the following statements in the “If . . . , then . . . ” form. There are many possible correct answers. (a) You must eat your dinner if you want to grow. (b) Being a multiple of 12 is a sufficient condition for a number to be even. (c) It is necessary for you to pass your exams in order for you to obtain a degree. (d) A triangle is equilateral only if all its sides have the same length. 18 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 2.1.2 Suppose that “Girls smell of roses” and “Boys have dirty hands” are true statements and that “The Teacher is always right” is a false statment. Which of the following are true? Hint: Label each of the given statements, and think about each of the following using connectives. (a) If girls smell of roses, then the Teacher is always right. (b) If the Teacher is always right, then boys have dirty hands. (c) If the Teacher is always right or girls smell of roses, then boys have dirty hands. (d) If boys have dirty hands and girls smell of roses, then the Teacher is always right. 2.1.3 Write the negation (in words) of the following claim: If Jack and Jill climb up the hill, then they fall down and like pails of water. 2.1.4 Orange County has two competing transport plans under consideration: widening the 405 freeway and constructing light rail down its median. A local politician is asked, “Would you like to see the 405 widened or would you like to see light rail constructed?” The politician wants to sound positive, but to avoid being tied to one project. What is their response? (Hint: Think about how the word ‘OR’ is used in logic. . . ) 2.1.5 (a) Rewrite the following sentence using the word ‘necessary.’ If I am to get a new bicycle, I must do my homework. (b) Rewrite the following sentence using the word ‘sufficient.’ The United States must play more soccer if it is to win the World Cup. 2.1.6 (a) What are the converse and the contrapositive of the statements in the previous question? Write your answers in sentences, like the originals. (b) What are the negations of the statements in the previous question? 2.1.7 Construct the truth tables for the propositions P ∨ ( Q ∧ R) and ( P ∨ Q) ∧ R. Are they the same? 2.1.8 Apply de Morgan’s laws to the result of Theorem 2.10 to prove that P =⇒ Q is logically equivalent to ¬ P ∨ Q. 2.1.9 Prove that the expressions ( P =⇒ Q) ∧ ( Q =⇒ P) and P ⇐⇒ Q are logically equivalent (have the same truth table). Why does this make sense? 2.1.10 (a) Prove that (( P ∨ Q) ∧ ¬ P) ∧ ¬ Q is a contradiction. (b) Prove that (¬ P ∧ Q) ∨ ( P ∧ ¬ Q) ⇐⇒ ¬( P ⇐⇒ Q) is a tautology. 2.1.11 Prove or disprove: ( P ∧ ¬ Q =⇒ F ) ⇐⇒ ( P =⇒ Q) is a tautology. Here F represents a contradiction: some proposition which is always false. 2.1.12 Suppose that “If Colin was early, then no-one was playing pool” is a true statement. (a) What is its contrapositive of this statement? Is it true? (b) What is the converse? Is it true? (c) What can we conclude (if anything?) if we discover each of the following? Treat the two scenarios separately. (i) Someone was playing pool. (ii) Colin was late. 19 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 2.1.13 Suppose that “Ford is tired and Zaphod has two heads” is a false statement. What can we conclude if we discover each of the following? Treat the two scenarios separately. (a) Ford is tired. (b) Ford is tired if and only if Zaphod has two heads. 2.1.14 Suppose that the following statements are true: • Every Pig likes mud. • If a creature cannot fly then it is not an astronaut. • A creature is an astronaut if it likes mud. Is it true that ‘Pigs can fly’? Explain your answer. (Hint: try rewriting each of the statements in the form ‘x is/likes 2.1.15 =⇒ x is/likes .’) (a) Use a truth table to prove the distributive law ( P ∧ Q) ∨ R ⇐⇒ ( P ∨ R) ∧ ( Q ∨ R) (b) Use logical algebra (see the aside on page 18) to prove that (( P =⇒ R) ∧ ( Q =⇒ R)) ⇐⇒ (( P ∨ Q) =⇒ R) (Hint: start by using the result of question 8) 2.1.16 (a) Do there exists propositions P, Q such that both P =⇒ Q and its converse are true? (b) Do there exist propositions P, Q such that both P =⇒ Q and its converse are false? Justify your answers by giving an example or a proof that no such examples exist. 2.1.17 Let R be the proposition “The summit of Mount Everest is underwater”. Suppose that S is a proposition such that ( R ∨ S) ⇐⇒ ( R ∧ S) is false. (a) What can you say about S? (b) What if, instead, ( R ∨ S) ⇐⇒ ( R ∧ S) is true? Hopefully it is obvious to you that R is false. . . 2.1.18 (Hard) Suppose that P, Q are propositions. Argue that any of the 16 possible truth tables P Q ? T T T/F T F T/F F T T/F F F T/F represents an expression ? created using only P and Q and the operations ∧, ∨, ¬. Can you extend your argument to show that any truth table with any number of inputs represents some logical expression? 20 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 2.2 Methods of Proof There are four standard methods for proving a theorem P =⇒ Q. In practice, long proofs will use several such arguments joined together. We have already discussed the first two types of proof in Section 2.1. Direct Assume P is true and deduce that Q is true. Contrapositive Assume ¬ Q and deduce ¬ P. This is enough since the contrapositive ¬ Q =⇒ ¬ P is logically equavalent to P =⇒ Q. Contradiction Assume that P and ¬ Q are true and deduce a contradiction. Since P ∧ ¬ Q implies a contradiction, it follows that P ∧ ¬ Q must be false. By Theorem 2.10, we see that P =⇒ Q is true. Induction This has a completely different flavor: we will consider it in Chapter 5. Each of the methods has advantages and disadvantages. For instance, the direct method has the advantage of a straightforward logical flow. The contrapositive method is useful when the negations ¬ P, ¬ Q are simpler than P, Q themselves. This is often the case when one or both statements involve the non-existence of something. Working with their negations might give you the existence of ingredients with which you can calculate. Proof by contradiction has a similar advantage: assuming both P and ¬ Q gives you two pieces of information with which you can calculate. Logically speaking there is no difference between the three methods, beyond how you visualize your argument. To illustrate the difference between direct proof, proof by contrapositive, and proof by contradiction, we prove the same simple theorem in three different ways. Theorem 2.12. Suppose that x is an integer. If 3x + 5 is even, then 3x is odd. Direct Proof. We show that if 3x + 5 is even then 3x is odd. Assume that 3x + 5 is even, then 3x + 5 = 2n for some integer n. Hence 3x = 2n − 5 = 2(n − 3) + 1. This is clearly odd, because it is of the form ‘an even integer plus one.’ Contrapositive Proof. We show that if 3x is even then 3x + 5 is odd. Assume that 3x is even, and write 3x = 2n for some integer n. Then 3x + 5 = 2n + 5 = 2(n + 2) + 1. This is odd, because n + 2 is an integer. 21 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 Contradiction Proof. We assume that 3x + 5 and 3x are both even, and we deduce a falsehood. Write 3x + 5 = 2m and 3x = 2n for some integers m and n. Then 5 = (3x + 5) − 3x = 2m − 2n = 2(m − n). Since m − n is an integer, this says that 5 is even: a contradiction. Some simple proofs We now give several examples of simple proofs. The only notation needed to speed things along is that of some basic sets of numbers: N for the positive integers, Z for the integers, R for the real numbers, and ∈ for ‘is a member of the set’. Thus 2 ∈ Z is read as ‘2 is a member of the set of integers’, or more concisely, ‘2 is an integer’. We will properly cover this notation in Chapter 4. Theorem 2.13. Let m, n ∈ Z. Both m and n are odd if and only if the product mn is odd. There are really two theorems here: (⇒) If m and n are both odd integers, then the product mn is odd. (⇐) If the product mn of two integers is odd, then both m and n are odd. Often when there are two directions you’ll have to prove them separately. Here we give a direct proof for (⇒) and a contapositive proof for (⇐). Proof. (⇒) Let m and n be odd. Then m = 2k + 1 and n = 2l + 1 for some k, l ∈ Z. Then mn = (2k + 1)(2l + 1) = 4kl + 2k + 2l + 1 = 2(2kl + k + l ) + 1. This is odd, because 2kl + k + l ∈ Z. (⇐) Suppose that the integers m and n are not both odd. That is, assume that at least one of m and n is even. We show that the product mn is even. Without loss of generality,a we may assume that n is even, from which n = 2k for some integer k. Then, mn = m(2k ) = 2(mk) a See is even. ‘Potential Mistakes’ below for what this means. In the second part of the proof, we did not need to consider whether m was even or odd: if n is even, the product mn is even regardless. The second part would have been very difficult to prove directly. For instance, you might have tried to start a direct proof with: Assume that mn is odd, then mn = 2k + 1 for some integer k. Then. . . We are stuck! 22 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 Theorem 2.14. If 3x + 5 is even, then x is odd. We can prove this directly, by the contrapositive method, or by contradiction. We’ll do all of them, so you can appreciate the difference. Direct Proof. Simply quote the two previous theorems. Because 3x + 5 is even, 3x must be odd by Theorem 2.12. Now, since 3x is odd, both 3 and x are odd by Theorem 2.13. Contrapositive Proof. Suppose that x is even. Then x = 2m for some integer m and we get 3x + 5 = 6m + 5 = 2(3m + 2) + 1. Because 3m + 2 ∈ Z, we have 3x + 5 odd. Contradiction Proof. Suppose that both 3x + 5 and x are even. We can write 3x + 5 = 2m and x = 2k for some integers m and k. Then 5 = (3x + 5) − 3x = 2m − 6k = 2(m − 3k ) is even. Contradiction. Selecting a method of proof is often a matter of taste. You should be able to see the advantages and disadvantages of the various approaches. The direct proof is more logically straightforward, but it depends on two previous results. The contrapositive and the contradiction arguments are quicker and more self-contained, but they require a greater level of comfort with logic. Consider who you are writing for before you decide to present a slick difficult proof over a slow simple one.5 For even more variety, here is a direct proof of Theorem 2.14 that does not use any previous result. Alternative Direct Proof. Suppose 3x + 5 is even, so 3x + 5 = 2n for some integer n. Then x = (3x + 5) − 2x − 5 = 2n − 2x − 5 = 2( x − n − 3) + 1 is odd. The fact that such variety is possible just makes proving theorems even more fun! 5 The Hungarian mathematician Paul Erdős used to refer to simple, elegant proofs as being ‘from the Book,’ as if the Almighty had a book of perfect proofs of which mere mortals might occasionally be permitted a glimpse. Of course, as with all matters spiritual, one person’s Book may be very different to another’s. . . 23 Downloaded by lex lexus (localfocalpoint@gmail.com) lOMoARcPSD|5093418 Common Mistake 1. Generality and ‘Without Loss of Generality’ There are many common mistakes in the writing of proofs that you should be careful to avoid. Here are two incorrect ‘proofs’ of the =⇒ direction of Theorem 2.13. Fake Proof 1. m = 3 and n = 5 are both odd, and so mn = 15 is odd. This is an example of the theorem, not a proof. Examples are critical to helping you understand and believe what a theorem says, but they are no substitute for a proof! Recall the discussion in the Introduction on the usage of the word proof in English. Fake Proof 2. Let m = 2k + 1 and n = 2k + 1 be odd. Then, mn = (2k + 1)(2k + 1) = 2(2k2 + 2k) + 1 is odd. The problem with this second ‘proof’ is that it is insufficiently general. m and n are supposed to be any odd integers, but by setting both of them equal to 2k + 1, we’ve chosen m and n to be the same! Notice how the correct proof uses m = 2k + 1 and n = 2l + 1, where we place no restriction on the integers k and l. By generality we mean that we must make sure to consider all possibilities encompassed by the hypothesis. The phrase Without Loss of Generality, often shorted to WLOG, is used when a choice is made which might at first appear to restrict things but, in fact, does not. Think back to how this was used in the the proof of Theorem 2.13. Since the integers m and n appear symmetrically in the Theorem, if at least one of them is even, then we lose nothing by assuming that the second integer n is even. The phrase WLOG is used to pre-empt a challenge to a proof in the sense of Fake Proof 2, as if to say to the reader: ‘You might be tempted to object that my argument is not general enough. However, I’ve thought about it, and there is no problem.’ Common Mistake 2. Incorrect use of equals Remember that propositions should be joined by connectives: i.e., by =⇒ or ⇐⇒ . It is very common to see students write something like m is odd = m = 2k + 1 for some integer k This is extremely confusing! If this is part of a longer argument, things will become very difficult to follow. Since ‘m is odd’ and ‘m = 2k + 1 for some integer k’ are both propositions, they should be linked by a connective. We should instead write m is odd ⇐⇒ m = 2k + 1 for some integer k 24 Downloaded by lex lexus (localfoca... Purchase answer to see full attachment Tags: greatest common divisor and modular arithmetic infimum and supremum sequences limits of sequences functions and limits of functions User generated content is uploaded by users for the purposes of learning and should be used following Studypool's honor code & terms of service.