Notes Baby Rudin

Baby Rudin
nathanl3
August 17, 2019

Contents
1 The Real and Complex Number Systems 4

1.1 Ordered Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 The Real Field . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 The Extended Real Number System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5 The Complex Field . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.6 Euclidean Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.7 Appendix: Dedekind’s construction of R . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2 Basic Topology 21
2.1 Finite, Countable and Uncountable Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2 Metric Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3 Compact Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4 Perfect Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.5 Connected Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3 Numerical Sequences and Series 38

3.1 Convergent Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.2 Cauchy Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3 Upper and Lower Limits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.4 Some Special Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.5 Series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.6 Series of Non-negative Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.7 The Number e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.8 The Root and Ratio Tests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.9 Power Series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.10 Summation by Parts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.11 Absolute Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.12 Rearrangements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.13 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4 Continuity 63
4.1 Limits of Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.2 Continuous Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.3 Continuity and Compactness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.4 Continuity and Connectedness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.5 Discontinuities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.6 Monotonic functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
4.7 Infinite Limits and Limits at Infinity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
2
Contents
5 Differentiation 74
5.1 The Derivative of a Real Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.2 Mean Value Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
5.3 The Continuity of Derivatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.4 L’Hopital’s Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.5 Derivatives of Higher Order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.6 Taylor’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.7 Differentiation of Vector-Valued Functions . . . . . . . . . . . . . . . . . . . . . . . . . 77
5.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
6 TODOs 88
3
1 The Real and Complex Number Systems
1.1 Ordered Sets

We realize, considering the solutions to x 2 = 2, that the set of rational numbers Q is incomplete. We
start by defining some terms:
Definition 1. An order < on S is a relation such that
1. If x, y ∈ S, then exactly one of x < y, x = y, or x > y is true.
2. If x, y, z ∈ S with x < y and y < z, then x < z.
A set S is ordered if it admits an order. For example, Q is an order if we take x < y ⇐⇒ y − x is positive.
If S is an ordered set and E ⊆ S, we call β ∈ S an upper bound for E if β ≥ x for all x ∈ S. If such a β
exists, we say E is bounded above (by β). We define lower bounds similarly.
If S is an ordered set and E ⊆ S is bounded above, and there exists α ∈ S such that α is an upper bound for
E and if γ < α then γ is not an upper bound for E, then we call α a least upper bound for E. We write
α = sup E.
Similarly, we can define a greatest lower bound for E, which we write α = inf E.
An ordered set S is said to have the least upper bound property if every non-empty subset E ⊆ S which
is bounded above admits a least upper bound. We define the greatest lower bound property similarly.
The following theorem demonstrates that these properties are in fact equivalent for all ordered sets.
Theorem 1. If S is an ordered set with the least upper bound property, and ∅ , B ⊆ S is bounded below,
then inf B ∈ S.
Proof. Let L be the set of lower bounds for B in S. Since B is bounded below, L is non-empty; and a
subset of S by definition. Since S has the least upper bound property, there exists some α = sup L ∈ S.
We claim that α = inf B and in particular, inf B ∈ S.
To show this, it suffices to show that α is a lower bound for B, and that if β > α in S, then β is not a
lower bound for B. If α were not a lower bound for B, there must be some x ∈ B with x < α. However
this would imply that x is an upper bound for L and thus α ≥ β, a contradiction.
If β > α and β were a lower bound for B (so β ∈ L), then since α = sup L, we would have β ≤ α, a
contradiction.
Thus, α = inf B ∈ S. In particular, since this holds for all non-empty B ⊆ S bounded below, S has the
greatest lower bound property.
1.2 Fields
On to defining the notion of fields!
Definition 2. A field F is a set equipped with two operations, + and × with the following properties:
4
• F is a commutative group under addition, with additive identity 0. We denote the additive inverse of
x to be −x.
• F \ {0} is a commutative group under multiplication, with additive identity 1. We denote the
multiplicative inverse of x to be 1/x.
• x × (y + z) = x × z + y × z for all x, y, z ∈ F .
Proposition 1. If G is a group with operation ·, then for x, y, z ∈ G,
(a) x · y = x · z → y = z
(b) x · y = x → y = 1
(c) x · y = 1 → y = x −1
(d) (x −1 )−1 = x
Proof. Statement (a) follows from multiplying x −1 to both sides. (b) follows by letting z = 1 in (a); (c) by
taking z = x −1 ; and (d) follows since x −1 · x = 1 and by replacing x with x −1 in (c).
Notice that these properties can be applied both to the additive and multiplicative groups in a field F .
In addition to the above group properties, the distributive law leads to the following properties of fields:
Proposition 2. In a field F , for any x, y ∈ F , we have
(a) 0 × x = 0.
(b) If x , 0 and y , 0, then x × y , 0.
(c) (−x) × y = −(x × y) = x × (−y).
(d) (−x) × (−y) = xy.
Proof. For (a), notice that since 0 + 0 = 0, we have 0 × x = (0 + 0) × x = 0 × x + 0 × x, and the result
follows from Proposition 1(b) on the additive group.
For (b), notice that if x × y = 0 in this case, multiplying both sides of the equality by y −1x −1 would
produce 1 = 0, a contradiction.
For (c), notice that 0 = (x + (−x)) × y = x × y + (−x) × y, and the rest follows from Proposition 1(c).
The other side follows similarly.
Statement (d) follows from (c) with −y in place of y and using Proposition 1(d).
Now that we’ve sufficiently introduced ordered sets and fields, we wonder what would happen if we
combined them...
Definition 3. An ordered field F is a field which is also an ordered set, with the following properties for
all x, y, z ∈ F :
1. x + y < x + z if y < z.
2. x × y > 0 if x > 0 and y > 0
If x > 0, we say x is positive, and we say x is negative if x < 0. For example, Q is an ordered field with
the regular notions of +, × and <.
The following properties hold for ordered fields:
Proposition 3. For x, y, z ∈ F for some ordered field F , we have
5
1. If x > 0, then −x < 0.

2. If x > 0 and y < z then xy < xz.
3. If x < 0 and y < z then xy > xz.
4. If x , 0 then x 2 > 0. In particular, 1 > 0.
5. If 0 < x < y then 0 < y −1 < x −1 .
Proof. For (a), if x > 0, then 0 = x + (−x) > 0 + (−x) = −x. The other direction follows similarly.
For (b), notice that since y < z, we have z − y > 0 and thus x(z − y) > 0. Then, notice that xz =
x(z − y) + xy > xy.
For (c), notice that −x > 0 by (a) so −(xy) = (−x)y < (−x)z = −(xz). The result follows by adding
xy + xz to both sides.
For (d), if x > 0, then x 2 = xx > x × 0 > 0, otherwise −x > 0 and the argument is analogous since
(−x)2 = −(−x 2 ) = x 2 . In particular, 1 = 1 × 1 = 12 > 0.
For (e), notice that since x > 0, we must have x −1 > 0 otherwise 1 = x × x −1 < 0, contradicting (d). A
similar argument holds for y −1 , and thus x −1y −1 > 0. The result follows by multiplying the inequality
by the positive value x −1y −1 .
1.3 The Real Field

It is tempting to combine the definitions we have introduced so far: we can imagine some ordered
field which has the least upper bound property, containing the rational numbers Q. In fact, this is the
familiar set of real numbers, R, as shown in the following theorem:
Theorem 2 (Existence (and construction) of R). There exists an ordered field R with the least upper
bound property, and in fact, it contains Q as a subfield. Specifically, this means that Q ⊆ R, and that the
field operations in R coincide with the field operations in Q.
Proof. This proof is presented in the Appendix.
Theorem 3. From here, we can derive the following properties in R:

(a) If x, y ∈ R and x > 0, then there is a positive integer n such that nx > y.
(b) If x < y in R, there exists q ∈ Q with x < q < y.
(c) For every x > 0 in R, there exists one and only one positive y ∈ R such that y n = x, for every positive
integer n.
(d) If a, b > 0 and n > 0, then (ab)1/n = a 1/n b 1/n .
Proof. For (a), let A = {nx : n ∈ N}. If (a) were true, A would be bounded above, and clearly non-empty,
and thus admits a least upper bound α = sup A in R. However, α − x < α is not an upper bound for A,
so there exists some α − x < mx ≤ α in A. But then α < (m + 1)x ∈ A, a contradiction.
For (b), notice that y −x > 0 so from (a), there exists n ∈ N such that n(y −x) > 1. Apply (a) again to find
m 1 > nx and m 2 > −nx so that −m 2 < nx < m 1 . Thus, there exists m ∈ N such that m − 1 ≤ nx < m.
Adding n(y −x) > 1 to both sides of nx ≥ m − 1 yields ny > m and so dividing both sides of nx < m < ny
by n > 0 yields the result.
6
For (c), notice first of all that the function f (x) = x n is monotonically increasing on the positive real
numbers. To see this, factor
b n − an = (b − a)(b n−1 + b n−2a + · · · + b 2an−3 + ban−2 + an−1 ) > n(b − a)an−1 > 0
and similarly we can show b n − an < n(b − a)b n−1 . These inequalities will also be helpful later. The fact
that n-th positive real roots are unique follows immediately from the fact that x n is strictly increasing.
x
Let A = {y > 0 : y n < x }. Then, A is bounded above by max(1, x) and contains 1+x . Since R satisfies
the least upper bound property, α = sup A exists. We claim that α n = x.
Suppose otherwise. If α n < x, then for
x − αn

0 < t < min 1, , we have (α + t)n − α n < nt(α + t)n < nt(α + 1)n < x − α n
n(α + 1)n−1
so (α + t)n < x, contradicting the fact that α is an upper bound for A.

If α n > x, then for
αn − x

0 < t = min 1, , we have α n − (α − t)n < ntα n−1 = α n − x
nα n−1
so (α − t)n > x > z n for each z ∈ A, so in particular α − t is a smaller upper bound than α for A,
contradicting the fact that α is the least upper bound for A.
For (d), notice that a 1/n b 1/n > 0 since both terms are positive from (c), and that (a 1/n b 1/n )n = ab since
multiplication is commutative, so from (c), the n-th positive root is unique, (ab)1/n = a 1/n b 1/n .
Definition 4. Let x ∈ R >0 . Let n 0 be the largest integer such that n 0 ≤ x. Then, given n 0, n 1, . . . , nk −1 ,
let nk be the largest integer such that
n1 nk
n0 + + · · · + k ≤ x.
10 10
Then, letting E be the set of the numbers
n1 nk
n0 + + · · · + k , k ∈ N,
10 10
we have x = sup E. We define n 0 .n 1n 2n 3 . . . to be the decimal expansion of x.
1.4 The Extended Real Number System

Definition 5. The extended real number system consists of R and two symbols +∞ and −∞, with the
normal order and −∞ < x < ∞ for all x ∈ R.
It is customary to define the following results of operations:
x x
• x + ∞ = +∞, x − ∞ = −∞, +∞ = −∞ = 0.
• If x > 0, then x · (+∞) = +∞.
• If x < 0, then x · (+∞) = −∞.
7
1.5 The Complex Field

Definition 6. A complex number is an ordered pair (a, b) of real numbers. We denote C the set of all
complex numbers. Two ordered pairs are equal iff their components are equal. Also, we define
(a, b) + (c, d) = (a + c, b + d), (a, b) × (c, d) = (ac − bd, ad + bc).
and note that the set of complex numbers forms a field, with (0, 0) and (1, 0) playing the roles of 0 and 1
respectively.
We define i = (0, 1) and notice i 2 = −1. This notation is convenient as we can do away with the ordered
pair notation and write (a, b) = a + bi instead.
If z = a + bi for a, b ∈ R, then we define <(z) = a and =(z) = b to be the real part and imaginary part
of z respectively. z = a − bi is called the conjugate of z.
The following properties of complex numbers will be helpful:
Theorem 4. If z, w ∈ C, then
(a) z + w = z + w.
(b) zw = z · w.
(c) z + z = <(z), z − z = 2i=(z).
(d) zz ∈ R >0 when z , 0.
Proof. For all of these, we will suppose z = a + bi and w = c + di.

For (a), notice that z + w = (a + c) + (b + d)i so
z + w = (a + c) − (b + d)i = (a − bi) + (c − di) = z + w.
For (b), notice that zw = (ac − bd) + (ad + bc)i and that
z · w = (a − bi) · (c − di) = (ac − bd) − (ad + bc)i = zw.
For (c), notice that z + z = 2a = 2<(z) and z − z = 2bi = 2i=(z).

For (d), notice that zz = a 2 + b 2 , which is real and positive unless a = b = 0 (that is, z = 0).
Since the value zz is a non-negative real number, we can think of it as some measure of how ‘large’ z is:
the following definition formalizes this:
√
Definition 7. We define |z| = zz, called the magnitude or absolute value of z, which exists and is
unique from Theorem 3c. When x ∈ R, |x | = x when x > 0 and −x otherwise. In particular, the fact that
x ≤ |x | when x ∈ R is sometimes useful.
The following are helpful properties of the absolute value:
Theorem 5. If z = a + bi, w = c + di ∈ C, then the following are true:
(a) |z| ≥ 0, with equality iff z = 0.
(b) |z| = |z|.
(c) |zw | = |z| · |w |.
(d) |<(z)| ≤ |z|.
8
(e) |z + w | ≤ |z| + |w |.
Proof. For (a), clearly |0| = 0. Otherwise, zz is a positive real number, and thus has a positive square
root, which is precisely |z| by definition.
√
For (b), notice that both sides evaluate to a 2 + b 2 .
For (c), if either z or w is 0, the result follows immediately. Otherwise, we can see
√ √ √ √
|zw | = zwzw = zzww = zz ww = |z||w |
where the third equality uses Theorem 3(d) since zz and ww are both positive from Theorem 4(d).
For (d), notice that √ √
|<(z)| = |a| = a 2 ≤ a 2 + b 2 = |z|
where the third inequality follows since f (x) = x 2 is monotonically increasing as shown in Theorem
3(c). Notice that equality holds iff b = 0, that is, z ∈ R.
For (e), notice that
|z + w | 2 = (z + w)(z + w) = zz + ww + zw + wz = |z| 2 + |w | 2 + (zw) + (zw).
From Theorems 4(c) and 5(d), we have
(zw) + (zw) = 2<(zw) ≤ |2<(zw)| ≤ 2|z||w |.
Combining these yields
|z + w | 2 = |z| 2 + |w | 2 + (zw) + (zw) ≤ |z| 2 + |w | 2 + 2|z||w | = (|z| + |w |)2 .
The result follows by taking square roots, since both sides are non-negative real numbers.
Finally, we present a classic inequality, the Cauchy-Schwartz inequality:

Ín 2 Ín Ín
Theorem 6. If a 1, . . . , an , b1, . . . , bn ∈ C, then j=1 a j b j ≤ j=1 |a j | 2 j=1 |b j | 2 .
Proof. Let A = |a j | 2, B = |b j | 2 ∈ R and C = a j b j , so we claim |C | 2 ≤ AB. If B = 0, then we must

Í Í Í
have b1 = b2 = · · · = bn = 0 and the result follows immediately. Otherwise, if B > 0, then
|Ba j − Cb j | 2 =
Õ Õ
0≤ (Ba j − Cb j )(Ba j − Cb j )
= B2
Õ Õ Õ Õ
a j a j − BC a j b j − BC a j b j + CC bjbj
= B2 |a j | 2 − BCC − BCC + CC |b j | 2
Õ Õ
= B 2A − B|C | 2 − B|C | 2 + |C | 2 B
= B(AB − |C | 2 )
and since B > 0, we must have AB − |C | 2 ≥ 0, as required.
1.6 Euclidean Spaces

Motivated by spaces like R2 and R3 , we generalize this notion.
9
Definition 8. For k ∈ N, let Rk be the set of all ordered k-tuples x = (x 1, x 2, . . . , x k ), where x i ∈ R are
called the coordinates of x. We call these tuples vectors.
We define addition as component-wise addition, and scalar multiplication by a real number as component-
wise multiplication, so that Rk is closed under these two operations. The fact that Rk satisfies these
properties, as well as the operations satisfying the associative, commutative, and distributive laws make Rk
into a vector space over R.
We define the inner product of x and y by
k
Õ
x·y= x i yi
j=1
and the norm of x by

k
! 1/2
|x| = (x · x)1/2 = x j2
Õ
j=1
Now, Rk along with its associated inner product and norm is called Euclidean k-space.
We can now use this definition to prove some important properties of Rk :
Theorem 7. Suppose x, y, z ∈ Rk and α ∈ R. Then, the following are true:
(a) |x| ≥ 0.
(b) |x| = 0 iff x = 0.
(c) |αx| = |α ||x|.
(d) |x · y| ≤ |x||y|.
(e) |x + y| ≤ |x| + |y|.
(f) |x − z| ≤ |x − y| + |y − z|.
Proof. The facts (a), (b), and (c) follow directly from the definitions.
For (d), this is precisely the Cauchy-Schwartz inequality restricted to R, applied to the components.
For (e), we write
|x + y| 2 = (x + y)(x + y)
=x·x+x·y+y·x+y·y
= |x| 2 + 2x · y + |y| 2
≤ |x| 2 + 2 |x · y| + |y| 2
≤ |x| 2 + 2|x||y| + |y| 2
= (|x| + |y|)2
and the result follows by taking the square root.

For (f), this is shown by replacing x with x - y and y with y - z in (e).
The fact that x ≥ 0 with equality iff x = 0, and fact (f), called the Triangle Inequality, let us regard Rk
as a metric space.
R1 = R is called the (real) line, R2 is the plane. It is noteworthy that the norms in R2 and C are consistent.
10
1.7 Appendix: Dedekind’s construction of R

Here we construct R from Q in 9 steps.
Step 1. Making R a set.
The elements of R will be certain subsets of Q, called cuts. A cut is a set α with the following
three properties:
(I) ∅ ⊂ α ⊂ Q.
(II) If p ∈ α and q ∈ Q, with q < p, then q ∈ α.
(III) If p ∈ α, then p < r for some r ∈ α.
We will use p, q, r, . . . for rational numbers, and α, β, γ , . . . for cuts.
Note that condition (II) implies the following useful statements:
• If p ∈ α and q < α, then p < q.
• If r < α and r < s, then s < α.
Step 2. Making R an ordered set.
Define an order < on the set of cuts such that α < β iff α ⊂ β. This is clearly transitive, so it
suffices to show that exactly one of α < β, α = β, or α > β can be true at once. Notice that by
the properties of sets, at most one of these can be true at once, so it suffices to show that at
least one is.
To do this, suppose that the first two are false. Then, there exists some q ∈ α which is not in β.
Then, if p ∈ β, then we must have p < q from condition (II). However, since q ∈ α and p < q,
this also means p ∈ α, so we conclude β ⊂ α so α > β as required. Thus, R is now an ordered
set.
Step 3. Showing R has the least-upper-bound property.
Let A be a non-empty subset of R which is bounded above. Let γ = A. We claim that γ ∈ R
Ð
and γ = sup A.
To show γ ∈ R, we prove each condition individually. The first part of condition (I) follows
directly from the fact that A is the non-empty union of non-empty subsets of Q. The second
follows from the fact that A is bounded above by some β , Q. For condition (II), pick p ∈ γ and
q ∈ Q. Since p ∈ γ = A, there exists some α ∈ A for which p ∈ α. Then, from condition (II)
Ð
on α, we must have q ∈ α ⊆ γ , as required. For condition (III), pick the same p, q, α. Then, from
condition (III) on α, there must exist r ∈ α ⊆ γ with p < r , as required. Thus, γ ∈ R.
To show that γ = sup A, notice that by definition, γ is the superset of any α ∈ γ , so γ is an
upper bound for A. Let β < γ . Then, there must be some p in γ but not in β. In particular, there
must be some α ∈ A for which p ∈ α but not in β. However, this means α ≮ β so β is not an
upper bound for A, as required.
Thus, R satisfies the least-upper-bound property.
Step 4. Defining addition on R.
For α, β ∈ R, we define α + β = {r + s : r ∈ α, s ∈ β }. For this, we let 0∗ denote the set of all
negative rational numbers. It’s easily checked that 0∗ ∈ R. We verify the 5 axioms which define
R as a commutative additive group with +.
Let α, β, γ ∈ R.
11
(A1) α + β ∈ R.
Notice that α + β is non-empty since α and β are non-empty. To show that α + β , Q,
take elements r 0 < α, s 0 < β. Then, r 0 + s 0 > r + s for all r ∈ α, s ∈ β, so in particular,
r 0 + s 0 < α + β so α + β , Q, showing condition (I).
For condition (II) let p = r +s ∈ α +β for some r ∈ α, s ∈ β, and q < p. Then, q−s < p−s = r
so q − s ∈ α. Thus, q = (q − s) + s ∈ α + β.
For condition (III), let t > r in α, so that t + s > r + s in α + β.
(A2) α + β = β + α.
This follows from the definition and the commutativity of Q:
α + β = {r + s : r ∈ α, s ∈ β } = {s + r : s ∈ β, r ∈ α } = β + α
(A3) (α + β) + γ = α + (β + γ ).
This follows as above from the definition and the associativity of Q.
(A4) α + 0∗ = α.
If r ∈ α, and s ∈ 0∗ , then r + s < r ∈ α, so α + 0∗ ⊆ α. For the other side, take r ∈ α
and t > r in α. Then, r − t < 0 so r − t ∈ 0∗ and thus r = t + (r − t) ∈ α + 0∗ and thus
α ⊆ α + 0∗ , as required.
(A5) −α exists.
Let β be the set of p such that there exists r > 0 such that −p − r < α. We claim that β ∈ R
and α + β = 0∗ .
Let s < α. Then, s + 1 ∈ β since (s + 1) − 1 < α, so β is non-empty. Also, if r ∈ α, then
r < β, so β , Q, satisfying condition (I) for being a cut. For condition (II) let p ∈ β and
q 0. Then, −q − (−q + p + r ) = −p − r < α, and
−q + p + r > r > 0, so q ∈ β, proving condition (II). For condition (III), let p ∈ β. Then,
there exists r > 0 so that −p − r < α. Then, p + r /2 > p is in β since −(p + r /2) − (r /2) < α
and r /2 > 0, proving condition (III). So β ∈ R.
Let p ∈ α and q ∈ β. Since q ∈ β, there exists r > 0 such that −q − r < α. Thus, from
condition (II) on α, p < −q − r and thus p + q < −r < 0 so p + q ∈ 0∗ . Since our choice of
p and q was arbitrary, α + β ⊆ 0∗ .
Let t < 0. We want to find p ∈ α and q ∈ β such that p + q = t. Let s = −t/2 so that
s > 0. Then, by the Archimedean property, there exists an integer n such that ns ∈ α but
(n + 1)s < α. Take p = ns and q = −(n + 2)s = t − p. Since −(−(n + 2)s) − s < α and s > 0,
q ∈ β, so we are done!
Step 5. Towards an ordered field
Notice that α + β ⊂ α + γ if β ⊂ γ , so the first condition for ordered fields is satisfied. It also
follows that α > 0∗ iff −α < 0∗ .
Step 6. Multiplication, but only somewhat
Let R+ = {α ∈ R : α > 0∗ } be the positive real numbers. If α, β ∈ R+ , define α β to be the set
of p ≤ rs in R+ , for some positive r ∈ α, s ∈ β with r, s > 0. We define 1∗ to be the set of all
rational numbers less than 1.
It can be shown, similarly to the proofs of (A1) to (A5), that the axioms of multiplication and
distributivity hold for multiplication on R+ :
12
Let α, β > 0∗ be arbitrary.

(M1) α β ∈ R.
We prove the three conditions separately. For condition (I): choose r ∈ α and s ∈ β such
that r, s > 0, which exist since α, β > 0∗ . Then, rs ≤ rs so rs ∈ α β, so α β is non-empty.
Now, let p < α and q < β. Then, for any r ∈ α and s ∈ β with r, s > 0, then r 0.
Then, similarly p < q ≤ rs so p ∈ α β. For condition (III), let q ∈ α β where q ≤ rs as above.
Then, choose t > r > 0 and u > s > 0 in α and β respectively. Then, tu ≤ tu so tu ∈ α β
with tu > rs. Thus, α β ∈ R.
(M2) α β = βα.
This follows directly from the definition, since
{rs : r ∈ α, s ∈ β, r, s > 0} = {sr : s ∈ β, r ∈ α, s, r > 0}.
(M3) (α β)γ = α(βγ ).

We prove that both sets are the set A of all p ≤ rst for r ∈ α, s ∈ β, t ∈ γ , where r, s, t > 0.
Since the right side can be written as (βγ )α and is thus symmetric, it suffices to prove
one side.
Let p ∈ A so that p ≤ rst, for some r ∈ α, s ∈ β, t ∈ γ all positive. Then, rs ∈ α β, and
p ≤ (rs)t, so p ∈ (α β)γ . So A ⊆ (α β)γ . The proof of the other side is very similar, so we
omit it.
(M4) α1∗ = α.
Let p ∈ α1∗ , so that p ≤ rs for r ∈ α with r > 0 and 0 < s < 1. Then, p ≤ rs < r so
p ∈ α, showing α1∗ ⊆ α. Now, let t ∈ α. If t < 0, then 2t < t < 0 so 2t ∈ α. Then,
t ≤ (2t) · (1/2) ∈ α1∗ . If t > 0, then let r > t in α, from condition (III) of a cut. Then,
t/r < 1, so t ≤ r · (t/r ) ∈ α1∗ , completing this proof.
(M5) α −1 exists.
For α > 0∗ , denote β to be the set of all p > 0 such that there exists r > 0 with p −1 − r < α,
along with all the non-positive rational numbers. We claim that β ∈ R and α β = 1∗ .
1
For condition (I), clearly 0 ∈ β, so β is non-empty. Also, for any positive q ∈ α, p = q+1 >0
and p −1 − 1 = q ∈ α so p < β, and thus β , Q, proving condition (I) for cuts.
For condition (II), let p ∈ β and q < p. If q ≤ 0, then q ∈ 0∗ ∪ {0} ⊂ β follows by definition.
Otherwise, p > 0 so there exists some r > 0 such that p −1 − r < α. Since q < p, we have
q −1 − r > p −1 − r < α so q −1 − r < α and thus q ∈ β, as required.
Finally for condition (III), let p ∈ β. We want to find q > p in β. If p < 0, this is easy
since 0 ∈ β. Otherwise, p > 0, so there exists r > 0 such that p −1 − r < α. Then, let
q = (p −1 − r /2)−1 > p (if p −1 = r /2, choose r /3 instead). Then, q −1 − r /2 = p −1 − r < α, so
q ∈ β.
Now let t ∈ α β, so that t ≤ rs for some positive r ∈ α, s ∈ β. Then, s −1 − u < α for some
u > 0. Also, r − u ∈ α, so r − u < s −1 − u, implying rs < 1, so t ≤ rs < 1 and thus t ∈ 1∗ .
This proves α β ⊆ 1∗ .
TODO Figure out how to get 1∗ ⊆ α β, then show distributivity.
13
Step 7. Multiplication, for real

Now, define multiplication on all of R by


 0∗ if α = 0∗ or β = 0∗

αβ if α > 0∗ , β > 0∗




α β = −(α(−β))


if α > 0∗ , β < 0∗

−((−α)β) if α < 0∗ , β > 0∗




if α < 0∗ , β < 0∗

 (−α)(−β)


The proofs for the multiplication axioms and distributivity follow from Step 6, with repeated
use of γ = −(−γ ). The proofs are omitted.
This proves that R is an ordered field with the least-upper-bound property!
Step 8. Relation to Q
Associate with each q ∈ Q, a set q ∗ = {r ∈ Q : r < q}. Notice that this definition is consistent
with our definitions of 0∗ and 1∗ above (the asterisk was not a coincidence). These cuts satisfy
the following relations:
a) r ∗ + s ∗ = (r + s)∗ .
b) r ∗s ∗ = (rs)∗ .
c) r ∗ < s ∗ iff r < s.
This shows that Q is isomorphic to Q∗ whose elements are the rational cuts. This relationship
is the reason we can regard Q as a subfield of R.
1.8 Exercises
1. If r is rational and non-zero, and x is irrational, prove that r + x and rx are irrational.
Proof. Suppose otherwise: then (r + x) − r and (rx)/r would be operations on rational numbers,
and thus evaluate to rational numbers. However, these both evaluate to x, which is irrational, a
contradiction.
2. Prove that there is no rational number whose square is 12.
Proof. We first prove that there is no rational number whose square is 3. Suppose that there
existed p/q ∈ Q whose square is 3, and such that p and q share no factors, cancelling factors
when appropriate. Then, multiplying this equality by q 2 , we have p 2 = 3q 2 , showing that p is
divisible by 3. But, this means 3p 02 = 3q 2 , which in turn implies q is divisible by 3, contradicting
the fact that p and q share no factors.
Now, if some rational number r had r 2 = 12, then r /2 would be a rational number such that
(r /2)2 = 3, contradicting our previous statement.
3. Prove that in a field F , the following statements follow from the axioms of multiplication:
(a) If x , 0 and xy = xz then y = z.
(b) If x , 0 and xy = x then y = 1.
(c) If x , 0 and xy = 1, then y = 1/x.
14
(d) If x , 0 then 1/(1/x) = x.
Proof. For (a), if x , 0, then 1/x ∈ F , so we can multiply this to both sides, yielding the result. (b)
follows by letting z = 1 in (a). (c) follows by letting z = 1/x in (a). (d) follows by letting x = 1/x
and y = 1/(1/x) in (c), noticing that 1 = 1/x · x = 1/x · 1/(1/x).
4. Let E be a non-empty subset of an ordered set; suppose α is a lower bound of E and β is an upper
bound of E. Prove that α ≤ β.
Proof. Since E is non-empty, let x ∈ E. Then, since α is a lower bound for E, in particular, α ≤ x.
Similarly, x ≤ β, so α ≤ x ≤ β, as required.
5. Let A be a non-empty set of real numbers which is bounded below, and −A be the set of all
numbers −x for x ∈ A. Prove that inf A = − sup(−A).
Proof. Since A is non-empty and bounded below, and R satisfies the least upper bound property,
α = inf A exists. We claim that −α is the least upper bound to −A.
First, notice that −α ≥ −x for all −x ∈ −A, since α ≤ x for all x ∈ A. Also, if −β < −α were a
smaller upper bound for −A, then β would be a larger lower bound for A, contradicting the fact
that α is the greatest lower bound for A.
6. Fix b > 1.
(a) If m, n, p, q ∈ Z with n, q > 0 and r = m/n = p/q, prove that (b m )1/n = (b p )1/q so it makes
sense to define b r = (b m )1/n .
Proof. Let x = (b m )1/n and y = (b p )1/q . Now, notice that x nq = (x n )q = (b m )q = b mq and

similarly y nq = b np . Since m/n = p/q, we have qm = np, so in fact x nq = y nq , so the result
follows by the uniqueness of positive real nq-th roots.
(b) Prove b r +s = b r b s if r, s ∈ Q.
Proof. Write r = m/n and s = p/q for m, n, p, q ∈ Z with n, q > 0. Then, r + s = (mq + np)/nq.
Now, notice that from properties of integer powers, b mq+np = b mq b np . So,
(b r +s )nq = (b (mq+np)/nq )nq = b mq+np = b mq b np = b r nq b snq = (b r b s )nq
and the result follows from the uniqueness of nq-th positive real roots.
(c) If x is real, define B(x) to be the set of all numbers b t , where t is rational and t ≤ x. Prove
that
b r = sup B(r )
when r is rational. Hence, we can define b x = sup B(x) for every real x.
Proof. We first prove a helpful lemma: if q > 0 in Q, then b q > 1. Let q = m/n for m, n ∈ N
and n , 0. Since x m and x n are monotonically increasing, then if b > 0,
1 1 as required. It follows that if r ≤ t, then b r ≤ b t : simply consider b t − b r =

b r (b t −r − 1) ≥ 0, since both terms are non-negative.
15
In fact, the previous statement shows that b r is indeed an upper bound for B(r ): if t ≤ r and
thus b t ∈ B(r ), then b t ≤ b r . Since r ≤ r , b r ∈ B(r ), so any upper bound for B(r ) must be at
least b r . Thus b r must be the least upper bound for B(r ), as required.
(d) Prove b x +y = b x b y for all x, y ∈ R.
Proof. First, we want to show that b x b y is an upper bound for B(x +y). Suppose that q ≤ x +y
in Q. Then, we can write q = u + v for u ≤ x, v ≤ y in Q (from the Archimedean property,
we can choose choose u ∈ Q in the non-empty interval [q − y, x]), so that b q = b u+v = b u b v .
However, since u ≤ x and v ≤ y, b u ≤ b x and b v ≤ b y , so b q = b u b v ≤ b x b y as required.
Now, suppose r r , to show that
r is not an upper bound for B(x + y).
Dividing both sides by b x yields r /b x r /b x so r r /b v . Thus, r 1, y > 0, and prove that there is a unique real x such that b x = y, by completing the
following outline. (This x is called the logarithm of y to the base b.)
(a) For any positive integer n, we have b n − 1 ≥ n(b − 1).
Proof. Factor b n − 1 = (b − 1)(b n−1 +b n−2 + · · · +b + 1). Since b k > 1 for every positive integer
k (inductively), the above expression is greater than or equal to (b −1)(1+1+· · ·+1) = n(b −1),
where there are n 1’s, as required.
(b) Hence b − 1 ≥ n(b 1/n − 1).
Proof. Since f (x) = x n is monotonically increasing, b 1/n > 1 since b > 1, so substituting b 1/n
for b in (a) yields the result.
(c) If t > 1 and n > (b − 1)/(t − 1), then b 1/n < t.
Proof. We have
b − 1 n(b 1/n − 1)
n> ≥
t −1 t −1
so cancelling the positive n from the outermost expressions, multiplying by the positive value
t − 1, and adding 1 to both sides yields the result.
(d) If w is such that b w < y, then b w +1/n < y for sufficiently large n; to see this, apply part (c)
with t = y · b −w .
Proof. Following the prompt, we notice that letting t = y · b −w > 1 in (c), if n > (b − 1)/(y ·
b −w − 1) ∈ R, then b 1/n < y · b −w , which after multiplying both sides by the positive value
b w , gives the result.
(e) If b w > y, then b w −1/n > y for sufficiently large n.
Proof. Similarly, letting t = b w /y in (c) yields b 1/n (b − 1)/(b w /y − 1) ∈ R,
after which rearranging for y yields the result.
16
(f) Let A be the set of all w such that b w < y, and show that x = sup A satisfies b x = y.
Proof. Suppose otherwise. If b x < y, then from (d), there exists some n ∈ N such that
b x +1/n < y, so x + 1/n ∈ A, contradicting the fact that x is an upper bound for A.
Similarly, if b x > y, then from (e), there exists some n ∈ N such that b x −1/n > y, and so for
any w ∈ A, we have b w < y < b x −1/n and thus w < x − 1/n from the lemma in Exercise 6(c),
making x − 1/n a smaller upper bound for A, a contradiction.
(g) Prove that this x is unique.
Proof. Suppose that x , y in R and b x = b y . Without loss of generality, suppose x < y. But
then b x < b y from the statement proved in Exercise 6(c), contradicting our assumption, so
we are done.
8. Prove that no order can be defined in the complex field that turns it into an ordered field. Hint:
−1 is a square.
Proof. Suppose otherwise. Then, notice that since 1 = 12 and −1 = i 2 are both non-zero squares,
they are both positive. Thus, their sum, 0, would have to be positive, a contradiction.
9. Suppose z = a + bi and w = c + di. Define z < w if a < c, and also if a = c but b < d. Prove that
this turns the set of all complex numbers into an ordered set. (This type of order relation is called
a dictionary order or lexicographic order, for obvious reasons.) Does this ordered set have
the least-upper-bound property?
Proof. First, we show that exactly one of z < w, z = w, or z > w is true. Suppose that z , w, so
that a , c or b , d. If a , c, then either a < c, in which case z < w, or a > c, in which case z > w.
Otherwise, either b < d, in which case z < w, or b > d, in which case z > w.
Next, we show that this order is transitive. Suppose a + bi < c + di and c + di < e + f i. If a < c,
then since c ≤ e, a < e and thus a + bi < e + f i. If a = c, then b < d. If further c = e, then
b < d < f and thus a + bi < e + f i. If further c < e, then a = c < e so a + bi < e + f i. In all cases,
a + bi < e + f i.
This ordered set does not have the least-upper-bound property: consider the set A = iR = {ir :
r ∈ R}, which is bounded above by 1. We claim that though A is non-empty and bounded above,
there does not exist a least upper bound. Let α be an upper bound for A. Notice that α must have
a non-negative real component. If α has a strictly positive real component, say r , then r /2 will be
smaller than r but still larger than all of A. Thus, a least upper bound will never have positive real
component. If α had real component 0, then α + 1 ∈ A would be larger than it, a contradiction.
Thus, no least upper bound for A exists.
10. Suppose z = a + bi, w = u + vi, and

1/2 1/2
|w | + u |w | − u

a= ,b= .
2 2
Prove that z 2 = w if v ≥ 0 and that (z)2 = w if v ≤ 0. Conclude that every complex number (with
one exception!) has two complex square roots.
17
Proof. Notice that (a + bi)2 = (a 2 − b 2 ) + i(2ab), so

r r !
+ u u + u u

|w | |w | − |w | |w | −
z2 =
p
− + 2i · = u + i |w | 2 − u 2 = u + i |v |
2 2 2 2
so z 2 = u + iv when v ≥ 0. Similarly,
z 2 = (a 2 − b 2 ) − 2iab = u − i |v | = u + iv
if v < 0. Thus, if v ≥ 0, then z and −z are two complex square roots of w, and similarly ±z are
square roots of w if v < 0. The exception here is of course when z = −z, namely when z = 0 and
thus w = z 2 = 0.
11. If z is a complex number, prove that there exists an r ≥ 0 and a complex number w with |w | = 1
such that z = rw. Are w and r always uniquely determined by z?
Proof. Let r = |z| ≥ 0 and w = z/|z|. Notice that |w | = |z|/||z|| = 1, and z = rw by definition. w
and r are uniquely defined for all z ∈ C except 0, in which case r = 0 and w can be any complex
number with unit absolute value.
Suppose z , 0 and z = r 1w 1 = r 2w 2 with the required conditions. Take absolute values to get
|z| = |r 1 ||w 1 | = |r 2 ||w 2 |, which implies |r 1 | = |r 2 |. Since r 1, r 2 ≥ 0, we must have r 1 = r 2 , uniquely
determining w 1 and w 2 , as required.
12. If z 1, . . . , zn are complex, prove that
|z 1 + z 2 + · · · + zn | ≤ |z 1 | + |z 2 | + · · · + |zn |.
Proof. We proceed by induction on n. The base case is given by Theorem 7(e), as applied to
complex numbers taken as ordered pairs of real numbers. Then, for n > 2, assuming the statement
is true for n − 1 inductively, we have
|z 1 + z 2 + · · · + zn−1 + zn | ≤ |z 1 + z 2 + · · · + zn−1 | + |zn |

≤ |z 1 | + |z 2 | + · · · + |zn−1 | + |zn |,
completing the induction.
13. If x, y ∈ C, prove that

||x | − |y|| ≤ |x − y|.
Proof. Notice |x | = |(y − x) − y| ≤ |y − x | + |y| so |x − y| = |y − x | ≥ |x | − |y|.

Similarly, |y| = |(y − x) + x | ≤ |y − x | + |x | so |x −y| ≥ |y| − |x |. Combining these two inequalities
yields
−|x − y| ≤ |x | − |y| ≤ |x − y|
and so
||x | − |y|| ≤ |x − y|,
as required.
14. If z ∈ C such that |z| = 1, compute
|1 + z| 2 + |1 − z| 2
18
Proof. Simply write
|1 + z| 2 + |1 − z| 2 = (1 + z)(1 + z) + (1 − z)(1 − z) = 1 + z + z + zz + 1 − z − z + zz = 4.
15. Under what conditions does equality hold in the Schwartz inequality?
Proof. Notice that in the proof, equality holds iff |Ba j − Cb j | 2 = 0, and equivalently a j = Cb j /B
Í
for each j. In particular, if the a j are each the same multiple of b j , then equality will hold.
16. Suppose k ≥ 3, x, y ∈ Rk , |x − y| = d > 0, and r > 0. Prove:

(a) If 2r > d, there are infinitely many z ∈ Rk such that
|z − x| = |z − y| = r .
Proof. Let m = 12 (x + y). Without loss of generality, suppose y = −x, translating when
necessary. Also, let t = r 2 − d 2 /4, which is well defined since 2r > d. Then, the set of
p
vectors on the hyperplane orthogonal to the line crossing x and y with distance t to m satisfy
the required equation, and there are infinitely many.
(b) If 2r = d, there is exactly one such z.
Proof. If such a z existed, then d = |x − y| ≤ |x − z| + |z − y| = 2r = d, so equality must hold

in the triangle inequality. This happens when the three points are co-linear, and there is a
unique point which satisfies this, namely z = m as defined above.
(c) If 2r < d, there are no such z.
Proof. If such a z existed, then d = |x − y| ≤ |x − z| + |z − y| = 2r < d, a contradiction.
How must these statements be modified if k < 3?
Proof. If k = 2, then (a) will have 2 solutions instead, and everything else remains the same. If
k = 1, (a) will have no solutions.
17. Prove that

|x + y| 2 + |x − y| 2 = 2|x| 2 + 2|y| 2
if x, y ∈ Rk . Interpret this geometrically, as a statement about parallelograms.
Proof. We expand:
|x + y| 2 + |x − y| 2 = (x + y) · (x + y) + (x − y) · (x − y)
=x·x+x·y+y·x+y·y+x·x−x·y−y·x+y·y
= 2|x| 2 + 2|y| 2
The interpretation of this is that in a parallelogram, the sums of the squares of the lengths of the
diagonals is equal to the sum of the squares of the lengths of the four sides.
18. If k ≥ 2 and x ∈ Rk , prove that there exists y ∈ Rk such that y , 0 but x · y = 0. Is this also true
if k = 1?
19
Proof. If x = 0, then any non-zero vector will do. If x has only one non-zero component, then
choose i such that x i = 0 and let y be the vector with yi = 1 and y j = 0 if j , i. Otherwise, if
x 12 +x 22 +...+x k2 −x i2
x = (x 1, . . . , x k ), there exists x i , 0. Then, let y j = x j if j , i, and yi = xi . Then,
k k
!
x j x j − x i2 − x i yi = 0
Õ Õ
x·y= x jyj =
j=1 j=1
as required. Notice that y is non-zero since there exists yk = x k , 0 for k , i by presumption.

This statement is not true for k = 1: consider x = (1).
19. Suppose a, b ∈ Rk . Find c ∈ Rk and r > 0 such that
|x − a| = 2|x − b|
iff |x − c| = r .
1
Proof. This is an example of Circles of Apollonius. c = 3 (4b − a), r = 23 |b − a|.
20. With reference to the Appendix, suppose that property (III) were omitted from the definition of a
cut. Keep the same definitions of order and addition. Show that the resulting ordered set has the
least-upper-bound property, that addition satisfies axioms (A1) to (A4) (with a slightly different
zero-element!) but that (A5) fails.
Proof. TODO
20
2 Basic Topology
2.1 Finite, Countable and Uncountable Sets

Definition 9. Let A, B be two sets such that every element x of A is associated an element of B, denoted by
f (x). Then, f is a function from A to B or a mapping from A into B. The set A is called the domain
of A, and the elements f (x) are called the values of f . The set of all values of f is called the range of f .
Let A, B be two sets and f be a mapping of A into B. If E ⊆ A, then f (E) is defined to be the set of all
elements f (x) for x ∈ E. We call f (E) the image if E under f . In this notation, f (A) is the range of f . It is
clear that f (A) ⊆ B. If f (A) = B, we say that f maps A onto B, or that f is surjective.
It is important to note the difference between into and onto.
If E ⊆ B, then f −1 (E) denotes the set of all x ∈ A such that f (x) ∈ E. f −1 (E) is the inverse image of E
under f . If y ∈ B, f −1 (y) is the set of all x ∈ A such that f (x) = y.
If f −1 (y) consists of at most one element of A for each y ∈ B, then f is a one-to-one, or injective mapping
of A into B. A mapping f which is both injective and surjective is called bijective, or a 1-1 correspondence.
If there exists a bijection between A and B, we say that A and B have the same cardinal number, or
briefly that A and B are equivalent, and we write A ∼ B. This relation has the reflexive, symmetric, and
transitive properties, and is thus called an equivalence relation.
For any positive integer n, let Jn be the set {1, 2, 3, . . . , n}, and J be the set consisting of all positive integers.
For any set A, we say
(a) A is finite if A ∼ Jn for some n.
(b) A is infinite if A is not finite.
(c) A is countable if A ∼ J .
(d) A is uncountable if A is neither finite nor countable.
(e) A is at most countable if A is finite or countable.
Countable sets are sometimes called enumerable or denumerable. Notice that if A, B are both finite, then
A ∼ B iff they contain the same number of elements. The notion of bijection extends this idea to infinite sets.
For example, the set of all integers Z is countable: consider the ordering
0, 1, −1, 2, −2, 3, −3, . . .
given by the bijection

n
(
2 if n even
f (n) =
− n−1
2 if n odd
An interesting property of Z is thus that it is equivalent to one of its proper subsets. This is never true
of finite sets, so in fact a set is infinite if it is equivalent to one of its proper subsets.
21
2 Basic Topology
Definition 10. A sequence is a function f defined on the set J of positive integers. If f (n) = x n for n ∈ J ,
then we denote f by the symbol {x n } or sometimes x 1, x 2, . . . . The values x n of f are called the terms
of the sequence. If A is a set and x n ∈ A for each n ∈ J , then {x n } is a sequence in A, or a sequence of
elements in A.
Theorem 8. Every infinite subset of a countable set A is countable.
Proof. Let {x n } be a sequence of distinct elements in A. Then, for any infinite subset E of A, we can
take the subsequence {x nk } of {x n } corresponding to E, so E is countable.
The above theorem shows that countable sets are the ‘smallest infinity’ in some sense.
Definition 11. Let A and Ω be sets, and suppose that for each element α ∈ A, there is associated a subset
of Ω which we denote by E α . We call the set whose elements are the sets E α a collection or family of sets,
denoted {E α }.
The union of the sets E α is the set S such that x ∈ S iff x ∈ E α for at least one α ∈ A, denoted
Ø
S= Eα .
α ∈A
The intersection of the sts E α is the set P such that x ∈ P iff x ∈ E α for every α ∈ A, denoted
Ù
P= Eα .
α ∈A
If A ∩ B is not empty, we say that A and B intersect, otherwise they are disjoint.
The operations ∪ and ∩ are commutative and associative, but they also distribute:
Theorem 9. For sets A, B, C, we have
E = A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) = F .
Suppose that x ∈ E. Then, x ∈ A and at least one of x ∈ B or x ∈ C. Thus at least one of x ∈ (A ∩ B) or

x ∈ (A ∩ C), so x ∈ F .
Similarly, if x ∈ F , then at least x is in at least one of A ∩ B or A ∩ C, so x ∈ A, and at least one of B or C,
so x ∈ E, completing the proof.
Theorem 10. Let {En } where n ∈ J be a sequence of countable sets, and let S be their countable union.
Then S is countable.
Proof. Let every En be arranged in a sequence {x nk }k ∈J . Then, consider the sequence
x 11 , x 21, x 12, x 31, x 22, x 13, x 41, x 32, x 23, x 14, . . .

|{z} | {z } | {z } | {z }
which enumerates S. If any two of the sets En have elements in common, these will appear more
than once in S. So the sequence is at most countable, but since E 1 ⊆ S, it is at least countable, so it is
countable.
Corollary 1. Suppose A is at most countable, and for every α ∈ A, B α is at most countable. Then,
T = α ∈A B α is at most countable.
Ð
This follows since T is equivalent to a subset of S in the above theorem.
22
2 Basic Topology
Theorem 11. Let A be a countable set, and Bn be the set of all n-tuples (a 1, . . . , an ) in A, where the ak
need not be distinct. Then Bn is countable.
Proof. B 1 = A is countable. Suppose that Bn−1 is countable for n > 1. Then, the elements of Bn are of
the form (b, a) for b ∈ Bn−1 and a ∈ A, so the set of all pairs (b, a) ∼ A and is thus countable. Then, Bn is
the countable union of countable sets, and is thus countable. The result follows by induction on n.
Corollary 2. The set of all rational numbers is countable.
Proof. Associate with each r = m/n ∈ Q the pair (m, n) of integers. The set of pairs (m, n) is countable,
and thus Q is countable.
But not all infinite sets are countable:

Theorem 12. The set A of all sequences in {0, 1} is uncountable.
Proof. Suppose otherwise, so that A is countable, and thus admits a sequence {sn }. Then, construct a
sequence t ∈ A such that t j = 1 − s j j so t j , s j j for all j ∈ J . Then, t < {sn } since it differs from each
sequence at at least one point. Thus, t < A, a contradiction.
Notice the above theorem can be combined with the binary representation of real numbers to show
that the real numbers are uncountable.
2.2 Metric Spaces

Definition 12. A set X , whose elements are points, is a metric space if for any two points p, q ∈ X there
is a real number d(p, q) called the distance from p to q, such that
(a) d(p, q) ≥ 0, with equality iff p = q.
(b) d(p, q) = d(q, p).
(c) d(p, q) ≤ d(p, r ) + d(r, q) for any r ∈ X .
Any function with these three properties is called a distance function, or a metric.
We can define metrics in the Euclidean spaces Rk , with the distance d(x, y) = |x − y|. It is important to
note that every subset of a metric space is still a metric space under the same distance function.
Definition 13. We denote the segment (a, b) to be the set of real numbers x such that a < x < b. Similarly,
the interval [a, b] is the set of all real numbers x such that a ≤ x ≤ b.
If ai < bi for all i ∈ Jk , then the set of all points x = (x 1, . . . , x k ) ∈ Rk such that ai ≤ x i ≤ bi is called a
k-cell.
If x ∈ Rk and r > 0, the open (or closed respectively) ball B is the set of all y ∈ Rk such that |y − x| < r
(or ≤ r respectively).
A set E ⊆ Rk is convex iff λx + (1 − λ)y ∈ E whenever x, y ∈ E and λ ∈ (0, 1).
Balls and k-cells are convex.
Definition 14. Let X be a metric space. Then,
(a) A neighbourhood of p is a set Nr (p) consisting of all q such that d(p, q) < r for some r > 0, where r
is the radius of Nr (p).
23
2 Basic Topology
(b) A point p is a limit point of the set E if every neighbourhood of p contains a point q , p such that
q ∈ E. (That is, points in E get arbitrarily close to p.)
(c) If p ∈ E is not a limit point, it is called an isolated point.
(d) A set E is closed iff every limit point of E is in E.
(e) A point p is an interior point of E if there is a neighbourhood N of p such that N ⊆ E.
(f) E is open if every point in E is an interior point of E.
(g) The complement of E, denoted E c , is the set of all points in X but not in E.
(h) E is perfect if E is closed and every point of E is a limit point of E.
(i) E is bounded if there exists a real number M and a point q ∈ X such that d(p, q) < M for all p ∈ E.
(j) E is dense in X if every point in X is a limit point of E, or a point of E (or both). (So points in E get
arbitrarily close to any point in X ).
Theorem 13. Every neighbourhood is an open set.
Proof. Let E = Nr (p) be a neighbourhood, and q be any point in E. Then, d(p, q) < r so d(p, q) = r − h
for some positive h. Then for any s ∈ Nh (q), we have
d(s, r ) ≤ d(s, q) + d(q, p) < h + (r − h) = r
so s ∈ E and thus Nh (q) ⊆ E. Thus E is open.
Theorem 14. If p is a limit point of E, then every neighbourhood of p contains infinitely many points of E.
Proof. Suppose not, so that some neighbourhood Nr (p) contains finitely many points in E. Then, there
exists some closest point q , p in that neighbourhood with d(q, p) = h > 0. Then, the neighbourhood
Nh/2 (p) contains no points in E which are not p, contradicting the definition of a limit point.
Corollary 3. A finite point set has no limit points.
Proof. If p were a limit point in a finite point set E, then some neighbourhood must have infinitely
many points in E, a contradiction.
Theorem 15. Let {E α } be a possibly infinite collection of sets. Then

!c
E αc = B.
Ø Ù
A= Eα =
α α
Proof. Let x ∈ A. Since it is not in E α , x is not in any of the E α . Thus, it is in each of the E αc , so
Ð
α
x ∈ B.
Let y ∈ B. By definition, y is in E αc , so it is not in any of the E α . Thus, y < E α so y ∈ A, completing
Ð
α
the proof.
Theorem 16. A set E is open iff its complement is closed.
24
2 Basic Topology
Proof. Suppose E c is not closed. Then, there exists a limit point of E c , say x which is not in E c (and
thus in E). However this means that there are points in E c in neighbourhoods arbitrarily close to x: so
no neighbourhood around x will be a subset of E, so E is not open, proving the contrapositive of the
forward statement.
Now suppose E is not open, so there exists some x ∈ E for which no neighbourhood is entirely contained
within E. Thus, every neighbourhood of x contains some point in E c , so x is a limit point of E c not in E c ,
so E c is not closed, proving the contrapositive of the backwards statement, completing the proof.
Corollary 4. A set F is closed iff its complement is open.

Theorem 17. With the previous theorems, we can prove the following:
(a) For any possibly infinite collection {G α } of open sets, A = α G α is open.
Ð
(b) For any possibly infinite collection {F α } of closed sets, B = α F α is closed.

Ñ
(c) For any finite collection G 1, . . . , G n of open sets, C = ni=1 G i is open.

Ñ
(d) For any finite collection F 1, . . . , Fn of closed sets, D = ni=1 Fi is closed.

Ð
Proof. For (a), let x ∈ A be arbitrary. Then, x ∈ G α for some open set G α , so Nr (x) ⊆ G α ⊆ A.
Thus, x is interior in A and A is open. For (b), notice that {F αc } is a collection of open sets, so by (a),
Ð c c
α F α = ( α F α ) is open, so B = α F α is closed.
Ñ Ñ
For (c), let x ∈ C. Then, there are neighbourhoods Nr i (x) ⊆ G i for some positive r i . Then, taking
r = minni=1 r i , we have Nr (x) ⊆ Nr i (x) ⊆ G i for each i ∈ Jn , so Nr (x) ⊆ C so x is interior to C, and thus
C is open. Statement (d) reduces to (c) with reasoning similar to (b).
Notice that in parts (c) and (d) in the previous theorem, finiteness of the collections is essential. Otherwise,
the minimum of the radii of your neighbourhoods could be 0, and no neighbourhood would exist. For
instance, take G n = (−1/n, 1/n).
Definition 15. If X is a metric space, and E ⊆ X and E 0 is the set of all limit points of E in X , then the
closure of E is the set E = E ∪ E 0.
Theorem 18. If X is a metric space with E ⊆ X , then
(a) E is closed.
(b) E = E iff E is closed.
(c) E ⊆ F for every closed set F ⊆ X with E ⊆ F .
Notice that (a) and (c) imply E is the smallest closed subset of X containing E, so the name ‘closure’ is
appropriate.
Proof. For (a), if p ∈ X and p < E, then p is neither a point of E nor a limit point of E. Hence, p has a
c
neighbourhood which does not intersect E, so E is open and E is closed.
For (b), if E is closed, then E 0 ⊆ E so E = E. If E = E, then (a) implies E is closed.
For (c), let F ⊆ X be a closed set such that E ⊆ F . Let x ∈ E. If x ∈ E, then clearly x ∈ F . If x ∈ E 0 but
not in F , then x would be a limit point of F ⊃ E not in F , contradicting the fact that F is closed.
Theorem 19. Let E be a non-empty set of real numbers which is bounded above. Let y = sup E, then
y ∈ E, hence y ∈ E if E is closed.
25
2 Basic Topology
Proof. Suppose that y were not in E, so it is neither a point in E nor a limit point of E, so there exists a
neighbourhood (y − ϵ, y + ϵ) which does not contain any elements in E. But then y − ϵ/2 would be a
smaller upper bound for E than y, contradicting the minimality of y, proving the first statement.
Then, if E is closed, y = sup E ∈ E = E.
Remark. Suppose E ⊆ Y ⊆ X where X is a metric space. We say E is an open subset of X when every
point p ∈ E has associated to it a positive real number r such that d(p, q) < r implies q ∈ E. But we know
Y is also a metric space under the same distance function, so we can extend our definitions to Y .
We say E is open relative to Y when to each p ∈ E, there exists a positive r such that q ∈ E whenever
d(p, q) < r and q ∈ Y .
Theorem 20. Suppose Y ⊆ X . Then a subset E ⊆ Y is open relative to Y iff E = Y ∩ G for some open
subset G of X .
Proof. Suppose E ⊆ Y is open relative to Y . Then, for every p ∈ E, we associate some positive rp such
that Nrp (p) ∩ Y ⊆ E. Let G = p ∈E Nrp (p) ⊆ X . Since each Nrp (p) is open, the infinite union G is open.
Ð
Then, clearly E ⊆ Y ∩ G. By our choice of Nrp (p), Nrp (p) ∩ Y ⊆ E for each p ∈ E, so G ∩ Y ⊆ E. Thus,
E = G ∩ Y.
Conversely, if G is open in X and E = G ∩ Y , then every p ∈ E has a neighbourhood Nrp (p) ⊆ G, so
Nrp (p) ∩ Y ⊆ E and thus E is open relative to Y .
2.3 Compact Sets

Definition 16. Let X be a metric space and E ⊆ X . Then, an open cover of E is a collection {G α } of open
subsets of X such that E ⊆ α G α .
Ð
Definition 17. A subset K of a metric space X is said to be compact if every open cover of K contains a
finite subcover.
Formally, if {G α } is an open cover of K, then there exist indices α 1, . . . , α n such that K ⊆ G α 1 ∪ · · · ∪ G α n .
Clearly every finite set is compact.
Theorem 21. Suppose K ⊆ Y ⊆ X . Then K is compact relative to X iff K is compact relative to Y .
Proof. Suppose K is compact relative to Y , and we have some open cover {G α } in X . Then, letting
H α = Y ∩ G α , {H α } is still an open cover of K since K ⊆ Y . In fact, each H α is open relative to Y from
Theorem 20, and a subset of Y , so {H α } is an open cover of K in Y . Since K is compact in Y , there exists
some finite subcover {H α k }kn=1 of K. Then, G ⊆ nk =1 H α i ⊆ nk=1 G α i so {G α k }kn=1 is a finite subcover
Ð Ð
of K.
Now, suppose K is compact relative to X , and we have some open cover {H α } in Y . Since each H α is
open relative to Y , we can write H α = G α ∩ Y for some open subset G α of X . Then, {G α } is an open
cover of K in X and thus a finite subcover {G α k }kn=1 exists. Then {H α k }kn=1 is a finite subcover of K in
Y , so K is compact relative to Y , completing the proof.
Theorem 22. Compact subsets of metric spaces are closed.
Proof. Let K be compact in X . Let x ∈ E c . For each y ∈ E, let Gy be some neighbourhood of y with radius
less than 12 d(x, y). Then, {Gy } forms an open cover of K. Since K is compact, there exist y1, . . . , yn such
that Gy1 , . . . , Gyn forms a finite subcover of K.
26
2 Basic Topology
Then, there exists a closest point y ∗ within y1, . . . , yn to x, with distance r from x. Then, there are no
points in E closer than r /2 to x, so E c contains a neighbourhood of x completely contained in E c so E c
is open and thus E is closed.
Theorem 23. Closed subsets of compact sets are compact.
Proof. Let F ⊆ K ⊆ X be closed relative to X and K compact. Then, let {G α } be an open cover of F ,
and append the open set F c to make it an open cover of G ⊆ X . Then, since K is compact, there exists
n
some finite subcover {G α k }k=1 of K. Then the finite subcover without F c is also a finite subcover of F ,
so F is compact.
Corollary 5. If F is closed and K is compact, then F ∩ K is compact.
Proof. F ∩ K ⊆ K is closed as the finite intersection of closed sets, and thus compact by the previous
theorem.
Theorem 24. If {K α } is a collection of compact subsets of a metric space X such that the intersection of
every finite subcollection of {K α } is non-empty, then K α is non-empty.
Ñ
Proof. Let K be some element of {K α }. Suppose, for the sake of contradiction, that there are no points
in K which are in every K α . That is, for every x ∈ K, there is some K αc such that x ∈ K αc . So K ⊆ α K αc ,
Ð
so {K αc } forms an open cover of K, so since K is compact, there exists a finite subcover {K αc k }k=1
n of K.
But then K ∩ K α 1 ∩ . . . ∩ K α n = ∅, contrary to our assumption.
Corollary 6 (Cantor’s intersection theorem). If {Kn } is a sequence of non-empty compact sets such that
Kn ⊇ Kn+1 , then n=1 Kn is non-empty.
Ñ∞
Proof. Notice that Kk1 ∩ · · · ∩ Kkn = Kk where k = max(k 1, . . . , kn ), so any finite intersection is
non-empty. Thus, the result follows by applying the above theorem.
Theorem 25. If E is an infinite subset of a compact set K, then E has a limit point in K.
Proof. Suppose that E has no limit points in K. Then, every x ∈ K will have some sufficiently small
neighbourhood N x which contains at most one point in E. However, no finite subcollection of {N x }
can cover E and thus K, contradicting the fact that K is compact.
Theorem 26 (Nested intervals). If {In } is a sequence of intervals in R such that In ⊇ In+1 , then n=1 I n
Ñ∞
is not empty.
Proof. Let In = [an , bn ], and A be the set of all an which is non-empty and bounded above, say by b1 .
Then, let α = sup A. For any m, n, we have an ≤ an+m ≤ bn+m ≤ bm , so x ≤ bm for any bm . Thus,
x ∈ Im for all m, and thus n=1 In is non-empty.
Ñ∞

Theorem 27. Let k be a positive integer. If {In } is a sequence of k-cells such that In ⊇ In+1 for all n, then
n=1 I n is non-empty.
Ñ∞
Proof. Taking the intervals corresponding to each dimension, we can invoke the previous theorem to
find values x i in the intersections of each of the intervals, so x = (x 1, . . . , x k ) ∈ n=1 In .
Ñ∞

Theorem 28. Every k-cell is compact.
27
2 Basic Topology
Proof. Suppose I = [a 1, b1 ] × · · · × [ak , bk ]. Then, let δ = |b − a|, where a = (a 1, . . . , ak ) and b =

(b1, . . . , bk ). Then, notice that |x − y| ≤ δ , whenever x, y ∈ I .
Now suppose for the sake of contradiction that some open cover {G α } admits no finite subcover of
I . Subdividing each interval in half determines 2k smaller k-cells whose union is I . At least one of
these cells, I 1 cannot be covered by any finite subcollection of {G α }. Continue this indefinitely to get a
sequence of nested intervals {In }, all of which cannot be covered by a finite subcollection of {G α }.
By the previous theorem, there exists some x in every one of these intervals, so x ∈ G α for some α. Since
G α is open, there must exist some neighbourhood Nr (x) completely contained in G α . However, since the
diameter of the intervals decreases by a factor of 2 each time, for sufficiently large n, In ⊆ Nr (x) ⊆ G α ,
contradicting the fact that In cannot be covered by any finite subcollection of {G α }, completing the
proof.
Theorem 29 (Heine-Borel). The following are equivalent for sets E ⊆ Rk :

(a) E is closed and bounded.
(b) E is compact.
(c) Every infinite subset of E has a limit point in E.
Proof. The fact that (b) implies (c) is precisely Theorem 25.
To show that (c) implies (a), suppose that every infinite subset of E has a limit point in E, but E is not
closed and bounded.
• If E is not closed, there exists a limit point x of E which is not contained in E. We construct an
infinite subset of E which has only x as a limit point. Let x 1 be an arbitrary point in N 1 (x) ∩ E and
r 1 = d(x, x 1 ). Now, let x n be a point in E which is closer than min(1/n, r n−1 /2) to x. This must
exist since x is a limit point. This defines a sequence {x n }. Let X be the infinite set of these points.
Then clearly x is a limit point of X . However, we still have to show that it is the only limit point
of X . Let y , x be another limit point. Since d(x, y) > 0 and the r n are monotonically decreasing,
there exists some n such that r n ≤ d(x, y) ≤ r n+1 . taking r 0 = d(x, y) and r < min(r 0 −r n , r 0 −r n+1 ),
the neighbourhood with radius r around y has no points in X and is thus not a limit point of X .
• Similarly, if E is not bounded, let w ∈ E be arbitrary. Then we can create a sequence {x n } such
that d(w, x n ) > n and x n ∈ E. Then, if y ∈ E, then there are only finitely many x n such that
d(w, x n ) < d(w, y) + 1, so there are not infinitely many x n in N 1 (y) ∩ E, so y is not a limit point.
Thus, X has no limit points in E.
Finally, to show (a) implies (b), suppose E is closed and bounded. Since E is bounded, we can surround
it with a sufficiently large k-cell I . That is, E ∩ I = E is compact, as the intersection of a closed set and a
compact set.
Remark. Notice that the above theorem was specific to Rk . One may ask how much of the theorem extends
to general metric spaces. In general, (b) and (c) are equivalent in any metric space, but (a) does not imply
(b) and (c).
Theorem 30 ((Weierstrass)). Every bounded infinite subset of Rk has a limit point in Rk .
Proof. Let E ⊆ Rk be bounded. Then, E ⊆ I for some k-cell I . Since I is compact, E is an infinite subset
of I and thus has a limit point in I ⊆ Rk from the above theorem.
28
2 Basic Topology
2.4 Perfect Sets

Theorem 31. Let P be a non-empty perfect set in Rk . Then, P is uncountable.
Proof. Suppose P is non-empty but not uncountable. Since P has limit points, it must be infinite, and
thus countable. Enumerate the points of P as x 1, x 2, . . . .
Let V1 be any neighbourhood of x 1 . Suppose we have Vn such that Vn ∩ P is non-empty. Since every
point of P is a limit point of P, there exists some neighbourhood Vn+1 such that Vn+1 ⊆ Vn , x n < Vn+1 ,
and Vn+1 ∩ P is non-empty.
Put Kn = Vn ∩ P. Notice that Vn is closed and bounded and thus compact. The Kn are thus compact
as closed subsets of Vn . Notice Kn form a decreasing sequence of compact sets, each of which are
non-empty by construction, so n=1 must be non-empty. In particular, since K 1 ⊆ P, there must be
Ñ∞
some x k in this intersection. However, the construction forbids this.
Corollary 7. Every interval [a, b] with a < b is uncountable. In particular, the set of all real numbers is
uncountable.
Proof. Every interval is perfect and thus uncountable. The set of real numbers is larger.
Are combinations of intervals the only perfect sets? No: we construct a perfect set in R with no segment,
the Cantor set.
Let E 0 = [0, 1]. Remove the segment (1/3, 2/3) so that E 1 = [0, 1/3] ∪ [2/3, 1]. Removing the middle
thirds indefinitely yields a decreasing sequence of compact sets, whose infinite intersection is non-empty.
Call this set the Cantor set.
The Cantor set contains no segment, since every segment of the form
3k + 1 3k + 2

, m
3m 3
has a point in common with P. It can be shown that every segment (α, β) shares a segment of the above
form, so the Cantor set contains no segment.
To show that P is perfect, let x ∈ P and let S be any segment containing x. Let In be an interval chosen
such that n is so large that In ⊆ S. Then, let either endpoint is in P, so x is a limit point and P is perfect.
2.5 Connected Sets

Definition 18. Two subsets A, B of a metric space X are said to be separated if both A ∩ B and A ∩ B are
empty.
A set E ⊆ X is said to be connected if it is not a union of two non-empty separated sets.
Theorem 32. A subset E of the real line R is connected iff it has the property that if x, y ∈ E and x < z < y,
then z ∈ E.
Proof. Suppose otherwise, so that for some x, y ∈ E, there exists some z ∈ R such that x < z < y but
z < E. Then we claim A = E ∩ (−∞, z) and B = E ∩ (z, ∞) form a separating pair for E.
Clearly A ∪ B = E. Also, clearly A and B are non-empty, since they contain x and y respectively. Now,
notice that everything in A is ≤ z, and everything in B is > z. Thus, they are disjoint. A similar argument
holds for the other pair. Thus, A and B form a separating pair for E, contradicting the fact that E is
connected.
29
2 Basic Topology
Conversely, suppose that E is not connected, and in particular admits the separation (A, B). Then, let
x ∈ A and y ∈ B, and suppose without loss of generality that x < y. Let z = sup(A ∩ [x, y]) ∈ A. Since
A and B are separated, z < B.
If z < A, then x < z < y but z < A ∪ B = E. Otherwise, if z ∈ A, then it mustn’t be in B, so there exists
z 1 ∈ (z, y) such that z 1 < B. Then x < z 1 < y with z 1 < E. In either case, the contrapositive holds,
completing the proof.
2.6 Exercises
1. Prove that the empty set is a subset of every set.
Proof. The definition of set inclusion is vacuously true here.
2. A complex number z is said to be algebraic if there are integers a 0, . . . , an not all zero such that
a 0z n + . . . + an z 0 = 0.
Prove that the set of all algebraic numbers is countable. Hint: For every positive integer N , there
are only finitely many equations with n + |a 0 | + . . . + |an | = N .
Proof. For any n, let Sn be the set of tuples (k, a 0, a 1, . . . , ak ) such that k + |a 0 | + . . . + |ak | = n.
Notice that this set is finite, and that each corresponding equation can only have finitely many
roots. Thus, the set of algebraic numbers An whose polynomials map to a given Sn is finite. Then,
A = i=1 Ai is countable.
Ð∞

3. Prove that there exist real numbers which are not algebraic.
Proof. If every real number were algebraic, there would be countably many of them, contradicting
the uncountability of the reals.
4. Is the set of all irrational real numbers countable?
Proof. If the set of irrational real numbers were countable, then R = Q ∪ (R \ Q) would be
countable, contradicting the uncountability of the reals.
5. Construct a bounded set of real numbers with exactly three limit points.
Proof. Let A = {k + 1/n : n ∈ N, k ∈ {0, 1, 2}}. We claim that the limit points of A are precisely
0, 1, and 2. Clearly, all three are limit points (for any r > 0, take 1/n < r by the Archimedean
property of R; then k + 1/n is within r of k).
Let y < {0, 1, 2}. Consider k ∈ {0, 1, 2}. If y < k or y > k + 1, then taking some radius smaller than
the distance to [k, k +1] fails. Otherwise, we have y −k ∈ [1/(n +1), 1/(n −1)] for some n. Taking a
radius smaller than the distance to the nearest of the three points k +1/(n +1), k +1/n, k +1/(n −1)
fails.
6. Let E 0 be the set of all limit points of a set E. Prove that E 0 is closed. Prove that E and E have the
same limit points. (Recall that E = E ∪ E 0.) Do E and E 0 always have the same limit points?
7. Let A1, A2, . . . be subsets of a metric space.
(a) If Bn = ni=1 Ai , prove that Bn = ni=1 Ai .
Ð Ð
30
2 Basic Topology
Proof. Let C = ni=1 Ai . Let x ∈ Bn = Bn ∪ Bn0 . If x ∈ Bn , then x ∈ Ak ⊆ Ak ⊆ C. If

Ð
x ∈ Bn0 , then construct a sequence {x k } such that d(x k , x) < 1/k and x k ∈ Bn . Since {x n }
is countable, there exists at least one set A j for which x k ∈ A j infinitely many times. Thus,
x ∈ A0j ⊆ A j ⊆ C. Putting this together, Bn ⊆ C.
Now, let y ∈ C. If y ∈ A j for some j, then y ∈ A j ⊆ Bn ⊆ Bn . If y ∈ A0j for some j, then

every neighbourhood of y contains an element yk ∈ A j ⊆ Bn , so y ∈ Bn0 ⊆ Bn . The result
follows.
(b) If B = i=1 Ai , prove that B ⊇ i=1 Ai . Show, by an example, that this inclusion can be
Ð∞ Ð∞
proper.
Proof. Let x ∈ i=1 Ai , then x ∈ A j for some j. Either x ∈ A j ⊆ B ⊆ B, or x ∈ A0j , so there

Ð∞
are elements x k ∈ A j ⊆ B in every neighbourhood of x, ie. x ∈ B.

The inclusion can be proper: let An be the set of rationals such that q = m/n in lowest form.
Then, B = Q, whose closure is R, whereas the right side is still Q, as Ai = Ai for all i.
8. Is every point of every open set E ⊆ R2 a limit point of E? Answer the same question for closed
sets in R2 .
Proof. For open sets, yes. Every interior point has a neighbourhood completely contained within
E, so every smaller neighbourhood will contain (infinitely many) points in E. The same is not
true in general for closed sets. For example, consider {(0, 1/n) : n ∈ N} ∪ {(0, 0)}, in which 1 is
not a limit point.
9. Let E ◦ denote the set of all interior points of a set E, called the interior of E.
(a) Prove that E ◦ is always open.
Proof. This is immediate.
(b) Prove that E is open iff E ◦ = E.
Proof. If E is open, then every point in E is interior, so E ◦ = E. Similarly, if E = E ◦ , then E is

open from (a).
(c) If G ⊆ E and G is open, prove that G ⊆ E ◦ .
Proof. Let x ∈ G. Then x is an interior point of G ⊆ E, and thus an interior point of E.
(d) Prove that the complement of E ◦ is the closure of the complement of E.
Proof. Let x < E ◦ , so x is not an interior point of E. So every neighbourhood of x is not

completely contained in E, so there exists a point in E c in every neighbourhood of x. In other
words, x ∈ E c 0 ⊆ E c .
Now let y ∈ E c . If y ∈ E c , then y < E ◦ ⊆ E. If y ∈ E c 0, then every neighbourhood of y contains
an element of E c , and thus no neighbourhood of y is completely contained in E, so y < E ◦ .
(e) Do E and E always have the same interiors?
31
2 Basic Topology
Proof. No: let A = {1/n : n ∈ N} ∪ {0} be a subset of R and let E = Ac . Then, E = R so its
interior is R. However, 0 is not an interior point of E: every neighbourhood contains at least
one point 1/n not in E.
(f) Do E and E ◦ always have the same closures?
Proof. No: consider E = Q. Then E = R and E ◦ = ∅, whose closure is also empty.
10. Let X be an infinite set. For p, q ∈ X , define d(p, q) = 1 − δp,q . Prove that this is a metric. Which
subsets of the resulting metric space are open? Which are closed? Which are compact?
Proof. By definition, d(p, q) ≥ 0, with equality iff p = q. Now let p, q, r ∈ X . Then if p , r , then
d(p, r ) = 1, while d(p, q) + d(q, r ) is at least 1, since at least one of the terms must be non-zero. If
p = r , then either q = r = p in which case equality holds, or q , r , in which case 0 ≤ 2. Thus d is
a metric.
Notice that for any E ⊆ X , a neighbourhood of size 1/2 around any point x ∈ E consists only of
the point x (any other point has d(x, y) = 1 > 1/2). Thus every point in any set E is an interior
point, so every set is open. Similarly, considering any set F ⊆ X , F c is open, so F is closed.
Now, notice that finite sets are always compact. Infinite sets can be covered by singletons, but
thus admit no finite subcover. Thus, a set in X is compact iff it is finite.
11. For x, y ∈ R, define
d 1 (x, y) = (x − y)2
d 2 (x, y) = |x − y|
p
d 3 (x, y) = |x 2 − y 2 |
d 4 (x, y) = |x − 2y|
|x − y|
d 5 (x, y) = .
1 + |x − y|
Determine, for each of these, whether it is a metric or not.
Proof. We prove them individually:

d 1 (x, y): This is not a metric: it violates the Triangle inequality with (x, y, z) = (0, 1, 2).
d 2 (x, y): This is a metric: this is clearly non-negative, and zero iff |x − y| = 0 and thus x = y.
Also, the Triangle inequality holds.
d 3 (x, y): This is not a metric since d(−1, 1) = 0 while 1 , −1.
d 4 (x, y): This is not a metric since d(2, 1) = 0 while 2 , 1.
d 5 (x, y): Maybe.

12. Let K = {1/n : n ∈ N} ∪ {0} ⊆ R. Prove that K is compact without invoking Heine-Borel.
Proof. Let {G α } be any open cover of K. Then, 0 ∈ K is in some G α , and since G α is open, there
must exist some neighbourhood Nr (0) ⊆ G α . Thus, if n > 1/r , 1/n ∈ G α . Taking this, and one
open set for each of the remaining 1/n yields a finite cover for K.
32
2 Basic Topology
13. Construct a compact set of real numbers whose limits form a countable set.
Proof. Let A = {(1 + 2−m )/n : m, n ∈ N}. Notice that {1/n : n ∈ N} ∪ {0} ⊆ A0. We claim these
1
are the only limit points. Let y ∈ [0, 2] not in the above set of limit points. Then, n+1 < y < n1
for some n. Now for every k > n in N, mk1+1 < y − k1 ≤ m1k for some mk ∈ N. Notice that as k
h i
increases, mk decreases, so the interval mk1+1 , m1k only gets larger. Thus, there are no elements
in
1 1 1 1

A∩ + , + ,
n + 1 mn+1 + 1 n + 1 mn+1
a neighbourhood of y by construction. Thus y is not a limit point, and thus A has countably many
limit points.
14. Give an example of an open cover of the segment (0, 1) which has no finite subcover.
Proof. Let G n = (1/(n + 2), 1/n) for n ∈ N. This is a cover since for any r ∈ (0, 1), there exists
n such that 1/(n + 2) < r < 1/n so r ∈ G n . However, notice that 1/(n + 1) is only in G n , so
every subcover of (0, 1) would have to contain G n for every n ∈ N, forcing it to be countable, as
required.
15. Show that Cantor’s intersection theorem becomes false if the condition of compactness is weak-
ened to either solely closed or bounded.
Proof. Suppose the restriction is weakened to closed sets. Then let Kr = {x ∈ R : x ≤ r }, each of
which is closed. Also,
Ka1 ∩ . . . ∩ Kan = K min(a1 ,...,an ) , ∅
but r ∈R Kr = ∅.
Ñ
Now let Fk = (0, 1/k) be bounded sets. Then
Fk1 ∩ . . . ∩ Fkn = F max(k1 ,...,kn ) , ∅
but k ∈N F k = ∅.
Ñ

16. Regard Q as a metric space with d(p, q) = |p − q|. Let E be the set of all p ∈ Q with 2 < p 2 < 3.
Show that E is closed and bounded in Q but not compact. Is E open in Q?
Proof. E is bounded below and above by 1 and 2 respectively. Also, E is closed since Q is dense in
R. To show E is not compact, we employ a similar construction as in Exercise 14. E is open in Q,
since a neighbourhood sufficiently small can be chosen around every point, completely contained
in E.
17. Let E be the set of all x ∈ [0, 1] whose decimal expansion contains only the digits 4 and 7. Is E
countable? Is E dense in [0, 1]? Is E compact? Perfect?
Proof. E is uncountable: there is a bijection between E and the real numbers between 0 and 1,
simply by replacing 4’s with 0’s and 7’s with 1’s and interpreting the resulting string as a binary
expansion. E is not dense in [0, 1] since there are no elements of E in (0.5, 0.6), as the first digit
will always be 5. E is clearly bounded.
Suppose that x contained a digit other than 4 or 7. That is, suppose x = 0.x 1x 2x 3 . . . x k . . . with
x k < {4, 7}. Then, choosing a neighbourhood of size 2 · 10−(k+1) assures that either x k or x k +1
33
2 Basic Topology
will not be either a 4 or a 7. Thus, the neighbourhood will contain no elements in E. Thus, the
contrapositive states that every limit point of E must be in E, so E is closed and thus compact.
Let x ∈ E 0. We can find elements x n in E arbitrarily close to x by switching the n-th digit between
a 4 and a 7, acquiring elements in E which are a distance 3·10−n from x. Thus, E is also perfect.
18. Is there a non-empty perfect set in R which contains no rational number?
Proof. Yes: enumerate the rational numbers between 0 and 1 as qn . Then, let A be the set of real
numbers between 0 and 1 such that the n-th ternary digit of any x ∈ A is chosen to be different
from the n-th ternary digit of qn . In this way, A contains no rational numbers.
A is non-empty: this must be the case if [0, 1] is to be uncountable. A is closed: suppose x is a
limit point of A so that we can find elements of A arbitrarily close to x. In particular, we can find
elements of A whose fist n ternary digits match. If x were not in P, then there would be some n
for which x n = (qn )n , but we can find some element of P which matches x to more than n digits,
a contradiction. Finally, A is perfect since we can always generate close elements in P to any x by
choosing the other possibility for any one of the digits.
19. Prove the following:

a) If A, B are closed and disjoint in some metric space X , they are separate.
Proof. Since A and B are closed, A = A and B = B, so (A, B) and (A, B) are both disjoint sets
(they are both (A, B)).
b) Prove the same for disjoint open sets.
Proof. Suppose otherwise, and without loss of generality, suppose x ∈ A ∩ B. Then, some
neighbourhood of x is completely contained in B. Also, there exists some element of A in
this neighbourhood, so there exists y ∈ A ∩ B, contradicting the disjointness of A and B.
c) Fix p ∈ X , δ > 0, and define A = {q ∈ X : d(p, q) < δ }. Define B similarly, with > instead of
<. Show A and B are separated.
Proof. If B is empty, we are done. (Notice A is never empty: p ∈ A).

Let α = supq ∈A d(p, q), which exists since the set is bounded above by δ . Similarly, let
β = inf q ∈B d(p, q), since the set is bounded below by δ and non-empty by assumption. We
have α ≤ δ ≤ β. Now A = {q ∈ X : d(p, q) ≤ α } and B = {q ∈ X : d(p, q) ≥ β }, so the result
follows since α ≤ β so the required sets are disjoint.
d) Prove that every connected metric space with at least two points is uncountable. Hint: Use
(c).
Proof. Suppose a, b are distinct elements of a connected metric space X . Let δ = d(α, β) > 0.
Then, for every r ∈ (0, δ ), let Ar and Br be the sets of elements of X with distance less than,
or greater than respectively, r . Then, there must be an element zr in X with d(zr , a) = r ,
otherwise Ar and Br form a separation of X , as in (c). Thus, there exists an injection from
the uncountable set (0, δ ) to X so X is uncountable.
20. Are closures and interiors of connected sets always connected? (Look at subsets of R2 .)
34
2 Basic Topology
Proof. Closures of connected sets are connected. Suppose E is connected but E is not. Then, E
admits a separation (A, B). Then, (A ∩ E, B ∩ E) forms a separation of E, a contradiction. However,
this is not the same for interiors: take A = N 1 (−2) ∪ N 1 (2) ∪ L(−2, 2) ⊆ C where L(a, b) is the line
segment between a and b. Then A◦ = N 1 (−2) ∪ N 1 (2) which is disconnected.
21. Let A, B be separated subsets of Rk . Suppose a ∈ A, b ∈ B, and define p(t) = (1 − t)a + tb for
t ∈ R. Put A0 = p −1 (A) and B 0 = p −1 (B).
a) Prove that A0 and B 0 are separated subsets of R1 .
Proof. Notice firstly that both sets are non-empty as they contain 0 and 1 respectively. Now
suppose, for the sake of contradiction that t ∈ A0 ∩ B 0 , so that there are t 0 arbitrarily close
to t in A0 , and also t ∈ B 0 . This implies there are p(t 0 ) arbitrarily close to p(t) in A and also
p(t) ∈ B, so p(t) ∈ A ∩ B, contradicting the fact that A, B are separated.
b) Prove that there exists t 0 ∈ (0, 1) such that p(t 0 ) < A ∪ B.
Proof. Suppose otherwise, so that A0 ∪ B 0 = [0, 1]. Let β = inf B 0 ∈ B 0 . We know β < A0
since A0 ∩ B 0 = ∅. However, since A0 ∪ B 0 = [0, 1], there are points in A0 arbitrarily close
to β. This implies β ∈ A0 so β < B 0 . This implies β < A0 ∪ B 0 = [0, 1] which is impossible,
forming our desired contradiction.
c) Prove that every convex subset of Rk is connected.
Proof. If a subset E were not connected, then the above construction shows that there exists
an incomplete line in E, so it fails to be convex.
22. A metric space is called separable if it contains a countable dense subset. Show that Rk is
separable. Hint: Consider the set of points which have only rational coordinates.
Proof. Let Qk be the set of k-tuples of rational numbers. Notice that in every open ball, we can
completely enclose a k-cell. This k-cell is determined by k intervals in R, each of which contain
a rational number since Q is dense. Taking these as coordinates yields an element of Qk in the
original neighbourhood. Now Qk is countable by an earlier theorem, so Rk is separable.
23. A collection {Vα } of open subsets of X is said to be a base for X if the following is true: For every
x ∈ X and every open set G ⊆ X containing x, we have x ∈ Vα ⊆ G for some α. In other words,
every open set in X is the union of a subcollection of {Vα }.
Prove that every separable metric space has a countable base. Hint: take all neighbourhoods with
rational radius and center in some countable dense subset of X .
Proof. As the hint suggests, take {Vα } = {Nr (x) : x ∈ D, r ∈ Q}, for some countable dense subset
D of X . Then, let G be an open set. Then, G is the union of all the elements of {Vα } which
are subsets of G. This works since R satisfies the least-upper-bound property, so a sequence of
rationals can approximate any radius arbitrarily closely). Also, {Vα } is countable since there
exists a surjection from it to D × Q which is countable.
24. Let X be a metric space in which every infinite subset has a limit point. Prove that X is separable.
35
2 Basic Topology
Proof. Fix δ > 0 and pick x 1 ∈ X . Then, choose x j+1 ∈ X inductively such that d(x i , x j+1 ) ≥ δ for
i = 1, . . . , j, if possible. This process must terminate after a finite number of steps, otherwise the
set A = {x n : n ∈ N} is an infinite set without a limit point. Then, X can be covered by finitely
many neighbourhoods of size δ .
Take δ = 1/n, n ∈ N. Then, let K be the union of all the sets of centers (x i ) in the above
construction, for each δ = 1/n. We claim K is dense. Let x ∈ X and r > 0. We aim to find some
y ∈ Nr (x) ∩ Y . Let n ∈ N such that 1/n < r . If no elements of K are in N 1/n (x) ⊆ Nr (x), then the
above construction for x i could have proceeded one more step, contradicting our construction.
Thus K is a countable dense set in X , so X is separable.
25. Prove that every compact metric space K has a countable base, and that K is therefore separable.
Hint: For every positive integer n, there are finitely many neighbourhoods of radius 1/n whose
union covers K.
Proof. For n ∈ N, consider the cover {N 1/n (x) : x ∈ K }. Since K is compact, some finite subset
of these neighbourhoods must cover K. From the same conclusion as in Exercise 24, the set G
of all the centres of the neighbourhoods for n ∈ N forms a countable dense set in K, so K is
separable.
26. Let X be a metric space in which every infinite subset has a limit point. Prove that X is compact.
Proof. By Exercise 24, X is separable. By Exercise 23, X has a countable base, say {Vn }. Then
every open cover of X has a countable subcover {G n } ⊆ {Vn }. Suppose that there exists no finite
subcover of {G n } which covers X . Then, the complement Fn = (G 1 ∪ . . . ∪ G n )c is non-empty for
each n but Fn is empty. Let E be a set which contains a point from each Fn , and let x ∈ X be a
Ñ
limit point of E, which exists by presumption. But then x < G n for any G n , a contradiction.
27. Define a point p in a metric space X to be a condensation point of a set E ⊆ X if every

neighbourhood of p contains uncountably many points of E.
Suppose E ⊆ Rk is uncountable, and let P be the set of all condensation points of E. Prove that P
is perfect and that at most countably many points of E are not in P. In other words, show that
P c ∩ E is at most countable. Hint: Let {Vn } be a countable base of Rk , let W be the union of those
Vn for which E ∩ Vn is at most countable, and show that P = W c .
Proof. We follow the construction of W outlined in the hint. Let x ∈ W c . Then x is not in any
Vn for which E ∩ Vn is at most countable. In fact, this means that if x ∈ Vn , then E ∩ Vn must be
uncountable. Now consider Nr (x). It is an open set, so it can be written as the union of some
subcollection Vn1 ∪ . . . ∪Vnk of {Vn }, of which each Vni ∩ E is uncountable. So Nr (x) ∩ E ⊇ Vn1 ∩ E
is an uncountable set, so x ∈ P.
Now, let y ∈ W , so y ∈ Vn for some n such that E ∩ Vn is at most countable. Then, Vn contains
some neighbourhood of y which contains at most countably many points in E, so y < P. Thus
W ⊆ P c and so P ⊆ W c , so we conclude P = W c .
The fact that P c ∩ E = W ∩ E is at most countable follows by construction. Now we claim W c
is perfect. The fact that W c is closed follows directly from the fact that it is the complement
of a countable union of open sets. It suffices to show that each point of W c is a limit point of
W c . Let x ∈ W c . If some neighbourhood of x did not contain any points in W c , then there must
be only points in W ∩ E. However, there are at most countably many of these points, and any
neighbourhood of x is uncountable. Thus the result follows.
36
2 Basic Topology
28. Prove that every closed set in a separable metric space is the union of a (possibly empty) perfect
set and a set which is most countable. (Corollary: Every countable closed set in Rk has isolated
points.) Hint: Exercise 27.
Proof. If F is at most countable, we are done. Otherwise, if F is uncountable, the proof from
Exercise 27 extends to F ⊆ X , so if P is the set of condensation points of F , then F = P ∪ (F \ P)
with F \ P at most countable, as required.
For the corollary, let E be a countable closed set in the separable metric space Rk . If it had no
isolated points, it would be perfect and thus uncountable, a contradiction.
29. Prove that every open set in R is the union of an at most countable collection of disjoint segments.
Hint: Exercise 22.
Proof. Let A be open. For every x, let I x = (a, b) be the largest segment in A containing x. That
is, let a = inf {z : (z, x) ∈ A}, b = sup{y : (x, y) ⊆ A} in the extended reals R. Then, a, b < A
otherwise a larger interval exists (since A is open). Also, every c ∈ (a, b) must be in A as otherwise
if x ≤ c, there would exist some x ≤ c < y a. Since a, c < A, we must
have a ≥ c and c ≥ a, so a = c. Similarly b = d so the intervals are the same. That is, if two
intervals share any point, they must be the same interval. Now, every interval I x contains at
least one rational since Q is dense, so there exists an injection from our set of open sets to the
countable set of rational numbers. Thus, our set is countable, as required.
30. Imitate the proof of Theorem 31 to obtain the following result:

If Rk = n=1 Fn where Fn is a closed subset of Rk , then at least one Fn has a non-empty interior.
Ð∞
Equivalently: If G n are dense open subsets of Rk , then n=1 G n is not empty (in fact, it is dense
Ñ∞
k
in R ).
(This is a special case of Baire’s theorem; see Exercise 3.22 for the general case).
Proof. Let x 1 ∈ G 1 , so it has a neighbourhood V1 whose closure is in G 1 . Since G 2 is dense, V1

contains a point x 2 in G 2 for which there exists a neighbourhood whose closure is completely in
V1 ∩ G 2 . Repeat this process indefinitely, choosing x n in Vn−1 ∩ G n and some neighbourhood Vn
around it whose closure is completely contained in Vn−1 ∩ G n . This yields a nested sequence of
non-empty closed and bounded sets {Vn }, so n=1 Vn is non-empty. But inductively
Ñ∞
"n−1 # n
Ù Ù
Vn ⊆ Vn−1 ∩ G n ⊆ Vn−1 ∩ G n ⊆ Gk ∩ Gn = Gk
k =1 k=1
so any element in n=1 Vn is also in k∞=1 G k , so the latter is non-empty, proving the given
Ñ∞ Ñ
equivalent statement.
37
3 Numerical Sequences and Series
3.1 Convergent Sequences

Definition 19. A sequence {pn } in a metric space X converges if there exists p ∈ X such that for every
ϵ > 0, there exists an integer N such that n ≥ N implies d(pn , p) < ϵ. In this case, we say p is the limit
of {pn }, or pn → p, or limn→∞ pn = p. A sequence which does not converge diverges. A sequence is
bounded if its range is bounded.
We prove some important properties of convergent sequences in metric spaces.
Theorem 33. Let {pn } be a sequence in a metric space X .
(a) {pn } converges to p ∈ X iff every neighbourhood of p contains all but finitely many n.
(b) If p, p 0 ∈ X and {pn } converges to both p and p 0, then p = p 0.
(c) If {pn } converges, then it is bounded.
(d) If E ⊆ X and p is a limit point of E, then there is a sequence {pn } in E such that pn → p.
Proof. For (a), suppose that pn → p. Then every neighbourhood of size ϵ > 0 must contain all pn for
some n ≥ N by definition. Now suppose every neighbourhood of p contains all but finitely many pn .
Then for any ϵ > 0, the neighbourhood of size ϵ contains all but finitely many pn , so there exists N
such that n ≥ N implies pn ∈ Nϵ (x).
For (b), if p , p 0, then d(p, p 0) = r > 0. Selecting ϵ < r /2 will force all but finitely many pn lie in
Nr /2 (p) ∩ Nr /2 (p 0) = ∅, a contradiction.
For (c), let N such that n ≥ N implies d(p, pn ) < 1. Then, d(p, pn ) ≤ max{d(p, p1 ), . . . , d(p, p N −1 ), 1}.
For (d), take pn to be some element of E in N 1/n (p), which exists since p is a limit point of E. This
converges to p, given N > 1/ϵ.
The following theorem states we can combine convergent sequences the way we expect.
Theorem 34. Suppose {sn }, {tn } are complex sequences and sn → s, tn → t.
(a) (sn + tn ) → s + t.
(b) csn → cs, c + sn → c + s.
(c) sn tn → st.
(d) 1/sn → 1/s given sn , s , 0.
Proof. For (a), let ϵ > 0 be arbitrary and choose Ns , Nt such that n ≥ Ns (n ≥ Nt ) implies |sn − s | < ϵ/2
(|tn − t | < ϵ/2). Then, if n ≥ max(Ns , Nt ),
∆
|sn + tn − (s + t)| ≤ |sn − s | + |tn − t | < ϵ
and the result follows.
38
For the first part of (b), if c = 0, the result is immediate. Otherwise, let ϵ > 0 and N ∈ N such that
n ≥ N implies |s − sn | < ϵ/|c |. Then n ≥ N implies |cs − csn | < |c|c|ϵ| = ϵ, completing the proof. The
second part is similarly easy.
For (c), we use the following manipulation:
sn tn − st = sn tn − sn t + sn t − st = sn (tn − t) + (sn − s)t
Choose Ns such that n ≥ Ns implies |sn − s | < ϵ/2|t | and Nt such that n ≥ Nt implies |tn − t | < ϵ/2S,
where S = maxn ∈N |sn |. Then, if n ≥ max(Ns , Nt ),
ϵ ϵ
|sn tn −st | = |sn (tn −t) + (sn −s)t | ≤ |sn (tn −t)| + |(sn −s)t | = |sn ||tn −t | + |sn −s ||t | ≤ S · + · |t | = ϵ
2S 2|t |
as required. If |t | = 0, then choose Ns such that n ≥ Ns implies |tn | < ϵ/S, and the result follows.
For (d), we can use (c) to conclude (1/sn )sn → 1, and since sn → s, we must have 1/sn → 1/s.
Theorem 35. The following statements are true:

1. Suppose xn ∈ Rk and xn = (α 1,n , . . . , α k ,n ). Then {xn } converges to x = (α 1, . . . , α k ) iff each {α i,n }
converges to α i .
2. Suppose {xn }, {yn } are sequences in Rk , and {c n } is a sequence of real numbers, and xn → x,
yn → y, and c n → c. Suppose further that xn = (α 1,n , . . . , α k ,n ) and yn = (β 1,n , . . . , βk ,n ).
Then,
xn + yn → x + y, xn · yn → x · y, c n xn → cx
Proof. For (a), suppose {xn } converges to x. So for ϵ > 0, we can choose N ∈ N such that n ≥ N implies
|xn − x| < ϵ. Then for any i, |α i,n − α i | < ϵ and the result follows.
Suppose
√ each {α i,n } converges to α i . Let ϵ > 0. For each i, we can choose Ni ∈ N such that |α i,n − α i | <
ϵ/ k so that if n ≥ max(N 1, . . . , Nk ), then
v
u
t k r
Õ ϵ2
|xn − x| = |α i,n − α i | 2 ≤ k · = ϵ,
i=1
k

For the first part of (b),
(xn + yn )i = α i,n + βi,n → α i + βi = (x + y)i
so the result follows from part (a).
For the second part,
k
Õ k
Õ
xn · yn = α i,n βi,n → α i βi = x · y.
i=1 i=1
For the final part,

(βn xn )i = βn α i,n → βα i = (βx)i
so the result follows from part (a).
Definition 20. Given a sequence {pn }, consider an increasing sequence of positive integers {nk }. Then the
sequence {pnk } is a subsequence of {pn }. If {pnk } converges, its limit is called a subsequential limit of
{pn }.
39
Theorem 36. {pn } converges to p iff every subsequence of {pn } converges to p.
Proof. Suppose pn → p. Then for any ϵ > 0, there exists N ∈ N such that n ≥ N implies |pn − p| < ϵ.
Then if {pnk } is a subsequence of pn , then there exists some K ∈ N such that k ≥ K implies nk ≥ N . So
for k ≥ K, we have |pnk − p| < ϵ.
If every subsequence of pn converges to p, then in particular, the subsequence with nk = k (the entire
sequence) converges, so we are done!
Theorem 37. The following are true:

1. If {pn } is a sequence in a compact metric space X , then some subsequence of {pn } converges to a
point of X .
2. Every bounded sequence in Rk contains a convergent subsequence.
Proof. For (a), let K be the image of {pn }. Then if K is finite, there exists some p ∈ K which is
attained infinitely often. The subsequence of these points converges to p. Otherwise, K is an
infinite subset of a compact metric space, and thus admits a limit point in X . The result follows
from Theorem 3.2(d).
The result in (b) follows from (a) since bounded subsets of Rk lie inside a compact subset of Rk
(namely the closure of the image of the sequence).
Theorem 38. The subsequential limits of a sequence {pn } in a metric space X form a closed subset of X .
Proof. Let E ∗ be the set of all subsequential limits of {pn } and let q be a limit point of E ∗ . Choose n 1
such that pn1 , q. If this doesn’t exist, E ∗ has one point and we are done. Put δ = d(q, pn ). Then build
nk inductively, so that given n 1, . . . , ni−1 , we choose x ∈ E ∗ such that d(x, q) < 2−i δ . Since x ∈ E ∗ , we
can choose ni > ni−1 such that d(x, pni ) < 2−i δ . Then d(q, pni ) < 21−i δ so pni → q so q ∈ E ∗ .
3.2 Cauchy Sequences

Definition 21. A sequence {pn } in a metric space X is said to be a Cauchy sequence if for every ϵ > 0,
there exists an integer N such that d(pn , pm ) < ϵ if n, m ≥ N .
Let E be a non-empty subset of a metric space X and let S be the set of all real numbers of the form d(p, q)
with p, q ∈ E. Then diam E = sup S is the diameter of E.
Clearly a sequence {pn } is Cauchy iff diam E N → 0, where En = {pn , pn+1, . . . }.
1. If E is a subset of a metric space X , then diam E = diam E.
2. If Kn is a sequence of compact sets in X such that Kn ⊇ Kn+1 and diam Kn → 0, then n=1 K n
Ñ∞
consists of exactly one point.
Proof. For (a), notice that E ⊆ E so diam E ≤ diam E. If diam E > diam E, there exists a pair of elements
x, y ∈ E with |x − y| > diam E. If one of x, y is not in E, then a neighbourhood of size less than
(|x − y| − diam E)/2 around the element in E has no elements in E, a contradiction. A similar argument
can be made if both are not in E.
For (b), we know from Nested interval theorem that S = n=1 Kn is non-empty. If S had more than one
Ñ∞
point, say a and b, then diam Sn ≥ d(a, b) > 0 all n and thus diam Sn 9 0, a contradiction.
40

1. In any metric space X , every convergent sequence is a Cauchy sequence.
2. If X is a compact metric space and if {pn } is a Cauchy sequence in X , then {pn } converges to some
point of X .
3. In Rk , every Cauchy sequence converges.
Proof. For (a), let ϵ > 0. Then there exists N such that n ≥ N implies d(pn , p) ≤ ϵ/2. Then for any
m, n ≥ N , we have d(pn , pm ) ≤ d(pn , p) + d(pm , p) < ϵ.
For (b), let En = {pn , pn+1, . . . }. Then since {pn } is Cauchy, diam En → 0. Also, En are subsets of X and
thus compact. Finally, En ⊇ En+1 by definition. By Theorem 3.10, n=1 En consists of one point. Let
Ñ∞
this point be p. Since diam En → 0, points in {pn } get arbitrarily close to p so {pn } converges to p ∈ X .
For (c), Cauchy sequences are bounded, and thus their image is contained in a compact subset of Rk .
The result follows from (b).
Definition 22. A metric space in which every Cauchy sequence converges is complete.
Theorem 3.11 says that all compact metric spaces and all Euclidean spaces are complete.
Also, every closed subset of a complete metric space is complete.
Definition 23. A sequence {sn } of real numbers is said to be
• monotonically increasing if sn ≤ sn+1 for all n,
• monotonically decreasing if sn ≥ sn+1 for all n
The class of monotonic sequences consists of the increasing and decreasing sequences.
Theorem 41. Suppose {sn } is monotonic. Then {sn } converges iff it is bounded.
Proof. Suppose {sn } is increasing and bounded. Then its image admits a least upper bound α. For every
ϵ > 0, there exists N such that s − ϵ < s N ≤ s, otherwise s − ϵ would be a smaller upper bound. For
n ≥ N , s − ϵ < s N ≤ sn ≤ s, as required.
The converge follows from Theorem 3.2(c).
3.3 Upper and Lower Limits

Definition 24. If {sn } is a sequence of real numbers such that for any M ∈ R there exists N ∈ N such
that n ≥ N implies sn ≥ M, then we say sn → +∞.
Similarly, if for any M ∈ R, there exists N ∈ N such that n ≥ N implies sn ≤ M, then we say sn → −∞.
Let {sn } be a sequence of real numbers. Let E be the set of possibly infinite subsequential limits. Then, let
s ∗ = sup E and s ∗ = inf E, called the upper and lower limits of {sn } respectively.
We say
lim sup sn = s ∗ and lim inf sn = s ∗ .
n→∞ n→∞
Theorem 42. Let {sn } be a sequence of real numbers. Let E be the set of possibly infinite subsequential
limits of {sn }, and s ∗ = lim sup sn . Then the following are true:
1. s ∗ ∈ E.
41
2. If x > s ∗ , there is an integer N such that n ≥ N implies sn < x.

Moreover, s ∗ is the only number with these properties.
Proof. For (a), if sn → ±∞, then every subsequence goes to ±∞ so s ∗ ∈ E. Otherwise, it is bounded and
thus E is closed by Theorem 3.7, so s ∗ = sup E ∈ E = E.
For (b), notice that is this weren’t the case, then there are sn ≥ x for n arbitrarily large. Taking these sn
as a subsequence yields a subsequence with limit ≥ x > sn , contradicting the maximality of s ∗ in E.
Finally, let a, b ∈ E ⊆ R both satisfy these above properties. Without loss of generality, a > b. Let x ∈ R
such that b < x < a. Then statement (b) holds for b so sn < x < a for n ≥ N . Then a cannot satisfy
(a).
For example, the sequence containing all rational numbers {sn } has every real number as a subsequential
limit. Also, its lim sup is +∞ and lim inf is −∞.
Also, it is noteworthy that a sequence converges iff its lim sup is equal to its lim inf.
Theorem 43. If sn ≤ tn for n ≥ N , where N is fixed, then
lim inf sn ≤ lim inf tn and lim sup sn ≤ lim sup tn

n→∞ n→∞ n→∞ n→∞
Proof. The cases with infinities are simple casework. Thus, suppose all values involved are finite real
numbers. Suppose, for the sake of contradiction that lim inf n→∞ sn > lim inf n→∞ tn . Then, there exists
some y ∈ Et strictly less than all the x ∈ Es , where Es and Et are the sets of subsequential limits of {sn }
and {tn } respectively.
Consider the subsequence {tnk } which converges to this y. Suppose without loss of generality that
each nk ≥ N . Then each term in {snk } is at most the corresponding term in {tnk }. In particular, some
subsequence {snki } converges to a value at most y, a contradiction, since some x ∈ Es is at most y.
The corresponding proof for lim sup follows similarly.
3.4 Some Special Sequences

Theorem 44. We compute the limits of some helpful sequences, using the helpful fact that if 0 ≤ x n ≤ sn
for n ≥ N , then sn → 0 implies x n → 0.
1. If p > 0, then n−p → 0.
2. If p > 0, then p 1/n → 1.
3. n −n → 1.
nα
4. If p > 0 and α ∈ R, then (1+p)n → 0.
5. If |x | < 1, then x n → 0.
Proof. For (a), take n > (1/ϵ)1/p .

For (b), p = 1 is obvious. If p > 1, let x n = p 1/n − 1 > 0. Then, by the binomial theorem, 1 + nx n ≤
p−1
(1 + x n )n = p so 0 < x n ≤ n and the rightmost terms go to 0. p < 1 follows by taking reciprocals.
q
For (c), let x n = n1/n − 1 > 0. Then n = (1 + x n )n ≥ n(n−1)
2 x 2 . Then 0 ≤ x ≤
n n
2
n−1 . and the result
follows.
42
For (d), let k > max(0, α) be an integer. For n > 2k,
n k n(n − 1) · · · (n − k + 1) k nk p k

n
(1 + p) > p = p > k .
k k! 2 k!
Hence
nα 2k k! α −k
0< < n
(1 + p)n pk
which approaches zero since α − k < 0 and by (a).
Statement (e) follows by taking α = 0 in (d).
3.5 Series
Definition 25. Given {an } we associate a sequence {sn } where
n
Õ
sn = ak = a 1 + a 2 + · · · + ak ,
k =1
where sn are called the partial sums of {an }.

We also write
∞
Õ
{sn } = a 1 + a 2 + a 3 + · · · = an .
n=1
If sn → s, we say the series converges, and that

∞
Õ
an = s.
n=1
The notion of Cauchy sequences on the partial sums can be extended to series:
Theorem 45. an converges iff for every ϵ > 0, there exists an integer N such that
Í
n
Õ
ak < ϵ
k =m
for all n ≥ m ≥ N .
Proof. Notice that nk=m ak = sn − sm , so the condition is equivalent to the sequence {sn } being Cauchy.
Í
The result follows from the fact that Cauchy sequences and convergent sequences are equivalent in
Rk .
In particular, taking m = n we have |an | < ϵ for n ≥ N . More formally,

Theorem 46. If an converges, then an → 0.
Í
Theorem 47. A series of non-negative terms converges if and only if its partial sums form a bounded
sequence.
Proof. The partial sums form a monotonically increasing sequence, so the result follows as in Theorem
3.14.
43
We now prove a helpful theorem called the ‘Comparison test’.

(a) If |an | ≤ c n for n ≥ N 0 , where N 0 is some fixed integer, and if c n converges, then an converges.
Í Í
(b) If an ≥ dn ≥ 0 for n ≥ N 0 , and if dn diverges, then an diverges.

Í Í
Proof. For (a), let {sn } be the sequence of partial sums of an and C = c n . Also, notice that c n ≥ 0. Let
Í
ϵ > 0. Then since c n converges, there exists an integer N such that for n ≥ m ≥ N ,
Í
n
Õ
c k < ϵ.
k=m
Then, for any n ≥ m ≥ N ,

n n n n
Õ ∆ Õ Õ Õ
ak ≤ |ak | ≤ ck ≤ ck < ϵ
k =m k =m k=m k =m
so an converges.
Í
For (b), suppose without loss of generality that dn diverges to +∞. Then let M be a real number. Then
Í
for n ≥ N ,
Õn n
Õ
ak ≥ dk > M
k =1 k=1
so an diverges too.
Í

3.6 Series of Non-negative Terms

Theorem 49. If 0 ≤ x < 1, then
∞
1
xn =
Õ
.
n=0
1−x
If x ≥ 1, the series diverges.
Ín k. 1−x n+1
Proof. If 0 ≤ x < 1, let sn = k=0 x It can be shown by induction that sn = 1−x . Then,
1 1 x n+1 1 1
sn − = − − = x n+1 · →0
1−x 1−x 1−x 1−x 1−x
so the result follows.

If x ≥ 1, then sn ≥ n. The result follows immediately.
The following theorem states that a rather ‘thin’ subsequence of decreasing sequences determines the
convergence of an .
Í
Theorem 50 (Cauchy). Suppose a 1 ≥ a 2 ≥ · · · ≥ 0. Then the series an converges if and only if the
Í
series
∞
2k a 2k = a 1 + 2a 2 + 4a 4 + · · ·
Õ
S :=
k =0
converges.
44
Proof. Let {bn } be a sequence related to an such that bn = a f (n) where f (n) is the largest power of two
at most n. That is, the sequence {bn } starts (a 1, a 2, a 2, a 4, a 4, a 4, a 4, · · · ). Since an is decreasing, {bn } is a
strictly decreasing sequence where each term is at least the corresponding an . Also, notice S is bn , so
Í
the fact that an converges if S converges follows by the comparison test.
Í
Now suppose an converges. Then,

Í
2k 2k
1 1Õ
= a 1 + a 2 + (a 3 + a 4 ) + . . . + (a 2k −1 +1 + · · · + a 2k ) ≥ a 1 + a 2 + 2a 4 + . . . + 2k−1a 2k =
Õ
bi
i=1
2 2 i=1
so the result follows again by the comparison test.
Theorem 51. The series n−p converges if p > 1 and diverges if p ≤ 1.

Í
k
Proof. We can write 2k a 2k = 22kp = 2(1−p)k so k∞=0 (2(1−p) )k converges iff 0 ≤ 21−p < 1 from Theorem
Í
3.26, which occurs when p > 1. The result follows by the previous theorem, since the original sequence
was decreasing.
Theorem 52. If p > 1, then

∞
Õ 1
n=2
n(log n)p
converges. Otherwise, the series diverges.
Proof. Write
2k 1 c
2k a 2k = = p
= p
k k
2 (log 2 )p (k log 2) k
1
with c = so by Theorem 3.27, an converges iff
Í
(log 2)p
∞
Õ 1
c
kp
k =1
converges, but that happens iff p > 1 by the previous theorem.
3.7 The Number e

Definition 26. We define
∞
Õ 1
e= .
n=0
n!
This is well-defined since
1 1 1 1 1 1
sn = 1 + 1 + + +···+ < 1 + 1 + + 2 + · · · + n−1 < 3
1·2 1·2·3 1·2·····n 2 2 2
There is an equivalent definition:

Theorem 53. We have n
1

lim 1 + = e.
n→∞ n
45
Ín 1 1 n
Proof. Let sn = and tn = 1 + n . By the binomial theorem,

k=0 k !
n n n k −1
n 1 1 n! 1 Ö i
Õ Õ Õ
tn = = · = 1− .
k nk k! (n − k)!nk k! i=1 n
k=0 k =0 k =0
Clearly tn ≤ sn termwise, so lim supn→∞ tn ≤ e.

Also, if m ≤ n, then
m k −1
1 Ö i
Õ
tn ≥ 1−
k! i=1 n
k=0
which, as n increases, becomes

m
Õ 1
lim inf tn ≥ .
n→∞ m!
k =0
Letting m go to infinity yields e ≤ lim inf n→∞ tn so the result follows.
As a sidenote, the following bound on the error of the partial sums proves helpful:
Remark. Notice that
∞ ∞
Õ 1 1 Õ 1 1
0 < e − sn = < =
k! (n + 1)! (n + 1)k n!n
k=n+1 k =0
which shows that this infinite sum representation converges extremely quickly.
Theorem 54. e is irrational.
Proof. Suppose otherwise, so that e = p/q for positive integers p, q. By the above remark, 0 < q!(e −sq ) <
1
q . Then both q!sq and q!e are integers, so the above inequality implies the existence of an integer
between 0 and 1/q, a contradiction.
3.8 The Root and Ratio Tests

Theorem 55 (Root Test). Given an , put α = lim supn→∞ n |an |. Then,
Í p
(a) If α < 1, then an converges.

Í
(b) If α > 1, then an diverges.

Í
(c) If α = 1, the test gives no information.
Proof. For (a), we know then that for large enough n, n |an | ≤ α so |an | ≤ α n . The result follows from
p
the comparison test. For (b), notice that for large enough n, |an | ≥ 1, so the series diverges by the
contrapositive of Theorem 3.23.
For (c), the series 1/n and 1/n2 work.
Í Í

a n+1 a n+1
Theorem 56 (Ratio Test). The series an converges if lim supn→∞ < 1 and diverges if ≥1
Í
an an
for all n ≥ n 0 where n 0 is some fixed integer.
Proof. For the first part, for n ≥ N , we will have aan+1

n
= β < 1. Then |an | ≤ |a N |β n−N so the result
follows by comparing with a geometric series. For the second part, the fact that |an+1 | ≥ |an | eventually,
means that an 9 0, so the series cannot converge.
46
The previous two tests are very useful for determining convergence. In most cases, the ratio test is
easier to use, but we show in the following theorem than the root test is stronger.
Theorem 57. For any sequence {c n } of positive numbers,
c n+1 √ √ c n+1
lim inf ≤ lim inf n c n ≤ lim sup n c n ≤ lim sup
n→∞ cn n→∞ n→∞ n→∞ cn
Proof. Let α = lim supn→∞ ccn+1 . If α = +∞, we are done. Otherwise, suppose some subsequence {c nk }
n √
had the property that limk→∞ nk c nk = β > α. Then, there must exist infinitely many terms {c n } with
c nn > α n . But this cannot occur if the ratios of consecutive terms does not exceed α infinitely often, a
contradiction. The left inequality is similar.
3.9 Power Series

Definition 27. Given a sequence {c n } of complex numbers, the series
∞
cn zn
Õ
n=0
is called a power series. The numbers c n are called the coefficients of the series, and z is a complex
number.
Theorem 58. Given a power series as above, let
n
p 1
α = lim sup |c n |, R = .
n→∞ α
Then c n z n converges if |z| < R and diverges when |z| > R.

Í
Proof. The value for α is derived from the result of the root test, so this proof is just like unwrapping a
present you wrapped for yourself.
3.10 Summation by Parts

Theorem 59. Given two sequences {an }, {bn }, put An = nk =0 ak if n ≥ 0 and A−1 = 0. Then, if 0 ≤ p ≤ q,
Í
we have
Õq q−1
Õ
a n bn = An (bn − bn+1 ) + Aq bq − Ap−1bp .
n=p n=p
Proof. Expand the sum and telescope differently:

q
Õ q
Õ
a n bn = (An − An−1 )bn
n=p n=p
= Aq bq − Aq−1bq + Aq−1bq−1 − Aq−2bq−1 + · · · + Ap+1bp+1 − Ap bp+1 + Ap bp − Ap−1bp

= Aq bq + (Aq−1 (bq−1 − Aq−1bq ) + · · · + Ap (bp − Ap bp+1 ) − Ap−1bp
q−1
Õ
= An (bn − bn+1 ) + Aq bq − Ap−1bp
n=p
as required.
47
Theorem 60. Let {an } be a sequence such that

(a) The partial sums An of an form a bounded sequence.
Í
(b) b0 ≥ b1 ≥ · · · .
(c) bn → 0.
Then an bn converges.
Í
Proof. The above theorem suggests using the Cauchy criterion. Let ϵ > 0 and suppose the An are
bounded by M. We first manipulate:
q
Õ q−1
Õ
a n bn = An (bn − bn+1 ) + Aq bq − Ap−1bp
n=p n=p
" q−1 #
Õ
≤M (bn − bn+1 ) + |bq | + |bp |
n=p
= 2Mbq
so choosing N such that q ≥ p ≥ N implies bq < ϵ/(2M), completing the proof.
Theorem 61. Suppose {c n } is a sequence such that

(a) |c 1 | ≥ |c 2 | ≥ · · · .
(b) c 2m−1 ≥ 0, c 2m ≤ 0.
(c) c n → 0.
Then c n converges.
Í
Proof. This follows from the previous theorem, letting an = (−1)n+1 and bn = |c n |.
Theorem 62. Suppose the radius of convergence of c n z n is 1, and that |c 0 | ≥ |c 1 | ≥ · · · and c n → 0.

Í
Then c n z n converges at every point on the circle |z| = 1 except possibly at z = 1.
Í
2
Proof. Let an = z n and bn = |c n |. Then the An are bounded by |1−z | , so Theorem 3.42 applies.
3.11 Absolute Convergence

A seriesan is said to converge absolutely if |an | converges.
Í Í
Theorem 63. If an converges absolutely, then an converges.

Í Í
Proof. Let ϵ > 0 be arbitrary and N such that the Cauchy criterion holds for n ≥ m ≥ N . Then, for
these same n, m, we have
Õn Õn
ak ≤ |ak | < ϵ
k =m k=m
so an converges by the Cauchy criterion.

Í

48
Notice that absolute convergence is convergence if your terms are positive. Series which converge but
not absolutely converge non-absolutely.
We see that we can manipulate absolutely convergent sums much like finite sums. Let’s explore the
types of operations we can perform on general series.
Theorem 64. If an = A and bn = B, then (an + bn ) = A + B and can = cA for any c.
Í Í Í Í
Proof. The first statement follows after noticing that the partial sums of (an + bn ) are simply the sums
Í
of the partial sums of an and bn . The second statement follows similarly.
Í Í

Can we multiply infinite series? The answer is slightly more complicated.

Definition 28. Given an and bn , we put
Í Í
n
Õ
cn = ak bn−k
k=0
and call c n the product of the two series. This is motivated by considering the coefficients of the related
Í
generating series an z n and bn z n .
Í Í
The following theorem, due to Mertens, characterizes a large set of situations where this notion of
product is consistent.
Theorem 65 (Mertens). Suppose that
(a) an converges absolutely.
Í
(b) an = A.
Í
(c) bn = B.
Í
(d) c n = nk=0 ak bn−k as above.

Í
Then c n = AB.
Í
Proof. Let An , Bn and Cn be the n-th partial sums of an , bn , c n respectively. Also, let β = Bn − B. We
manipulate Cn , essentially switching the order of summations:
Cn = a 0b0 + (a 0b1 + a 1b0 ) + (a 0b2 + a 1b1 + a 2b0 ) + · · · + (a 0bn + a 1bn−1 + · · · + an b0 )
= a 0 Bn + a 1 Bn−1 + · · · + an B 0
= a 0 (B + βn ) + a 1 (B + βn−1 ) + · · · + an (B + β 0 )
= An B + a 0 βn + a 1 βn−1 + · · · + an β 0 .
Thus if we let
γn = a 0 βn + a 1 βn−1 + · · · + an β 0,
it suffices to prove that γn → 0. Let ϵ > 0 be arbitrary and choose N such that |βn | < ϵ for n ≥ N . Also,
let α = |an |. Then
Í
|γn | = |a 0 βn + a 1 βn−1 + · · · + an β 0 |
≤ |a 0 βn + a 1 βn−1 + · · · + a N βn−N | + |a N +1 βn−N −1 + · · · + an β 0 |
≤ |a 0 βn + a 1 βn−1 + · · · + a N βn−N | + ϵα
so if we fix N and let n → ∞, then we have
lim sup |γn | ≤ ϵα
n→∞
so the result follows since ϵ was arbitrary.
49
We now wonder whether this definition of product makes sense in the sense that if c n converges,
Í
whether it will have the sum AB. Abel proved that this is true.
Theorem 66. If an , bn , c n converge to A, B, C and c n = a 0bn + · · · + an b0 , then C = AB.
Í Í Í
Proof. Note: This is an incomplete proof, as it assumes that power series are continuous without
justification. We will fill in this gap in Theorem 8.2. This proof will be replaced later, since it is most
likely circular or wrong.
Let a(z) = an z n , b(z) = bn z n , and c(z) = c n z n . Then we (will) have seen that c(z) = a(z)b(z)
Í Í Í
if c n = a 0bn + · · · + an b0 , if we consider partial sums of c(z). Then the result follows by substituting
z = 1.
3.12 Rearrangements
Definition 29. Let {kn } be a bijection from N to itself. Then letting an0 = akn , we say that an0 is a
Í
rearrangement of an .
Í
Notice that the partial sums of these have no reason to be the same, so the question arises: should they
converge? Will their sums be the same if so?
We prove Riemann’s rearrangement theorem, which says that all hell breaks loose if our sequence
doesn’t converge absolutely:
Theorem 67 (Riemann Rearrangement). Let an which converges non-absolutely, and −∞ ≤ α ≤ β ≤
Í
+∞. Then, there exists a rearrangement an with partial sums sn0 such that
Í 0
lim inf sn0 = α and lim sup sn0 = β .

n→∞ n→∞
Proof. This proof is well-studied. We present an informal proof hopefully sufficient to provide intuition.
The actual proof is long-winded.
Let an+ and an− denote the subsequences of positive and negative terms of an . If either subsequence were
finite, then the other would overpower it and eventually either diverge or converge (after which an
would converge absolutely since the subsequence has all the same sign). Thus both must be infinite.
If α ≥ 0, take positive terms until our partial sums go above α. We must be able to do this, since
both subseries diverge. Similarly, if α < 0, take negative terms. Then, repeat the following process
indefinitely. Take positive terms until our partial sums go above β, then negative terms until our partial
sums return below α. This is again made possible since both subsequences diverge.
Taking the terms which are ‘turning points’ on both sides, we have sequences which converge to α and
β, so the result follows.
Now, the following theorem states that absolutely convergent series do indeed behave nicely:
Theorem 68. If an converges absolutely, then every rearrangement of an converges, and further they
Í Í
converge to the same sum.
Proof. Let an0 = akn be a rearrangement of an . Let ϵ > 0. Take N ∈ N such that if n ≥ m ≥ N ,
Í Í Í
then
n
Õ
|ak | < ϵ.
k =m
50
Then, take N 0 = max(k 1, . . . , k N ) + 1, so that no n 0 ≥ m 0 ≥ N 0 will be in {1, 2, . . . , N }. Then

n0
Õ n
Õ
|ak0 | ≤ lim sup |ak0 | ≤ ϵ
k =m 0 n→∞ k=N +1
so the result follows by the Cauchy criterion.
3.13 Exercises
1. Prove that convergence of {sn } implies convergence of |sn |. Is the converse true?
Proof. If sn → 0, then the result follows by definition. Otherwise, suppose sn → s and s > 0. We
can find N such that n ≥ N implies s/2 < sn < 3s/2, so that ||sn | − |s || = |sn − s | < ϵ. The proof
when s < 0 is similar, except we take ϵ = −s/2.
The converse is not true: consider the sequence sn = (−1)n for which |sn | = 1 converges trivially,
but for which no N exists for ϵ < 2.
√
2. Calculate limn→∞ ( n2 + n − n).
Proof. We manipulate:
√ n2 + n − n2 n 1
n2 + n − n = √ =√ =p .
n2 + n + n n2 + n + n 1 + 1/n + 1
We prove that 1 + 1/n → 1: notice that

p
p 1 + 1/n − 1 1
| 1 + 1/n − 1| = p ≤ →0
1 + 1/n + 1 2n
so √ 1 1 1
n2 + n − n = p → = .
1 + 1/n + 1 1+1 2

√ √
3. If s 1 = 2 and sn+1 = 2 + sn , prove that {sn } converges and that sn < 2.
p
p √
Proof. Notice that the function f (x) = 2 + x is monotonic in the sense that if a < b, then
p √ √
f (a) < f (b). Also, s 2 = 2 + 4 2 ≥ 2 = s 1 . Also, if sn−1 ≤ sn , then
√ √
q q
sn = 2 + sn−1 ≤ 2 + sn = sn+1 .
so it follows by induction that sn is an monotonically increasing sequence.

We claim sn < 2 inductively. The base case is true, and if n ≥ 1,
√
q
√
q
sn+1 = 2 + sn < 2 + 2 < 2.
Thus {sn } converges by Theorem 3.14.
4. Find the upper and lower limits of the sequence {sn } defined by
s 2m−1 1
s 1 = 0; s 2m = ; s 2m+1 = + s 2m .
2 2
51
Proof. We claim that s ∗ = 0 and s ∗ = 1. First, the fact that 0 ≤ sn ≤ 1 with s 2m ≤ 1/2 can be
shown inductively. The base case follows immediately. Otherwise, dividing by 2 preserves the
conditions, and adding 1/2 to s 2m gives a number at most 1. It suffices now to find two sequences
converging to 0 and 1.
k

the sequence {s 2k } is identically 0. The sequence s 2k +1 −1 = 0, 12 , 34 , . . . , 2 2k−1 , . . . converges to

1.
5. For any two real sequences {an }, {bn }, prove that
lim sup(an + bn ) ≤ lim sup an + lim sup bn ,

n→∞ n→∞ n→∞
provided the sum on the right is not of the form +∞ − ∞.
Proof. If both α and β are +∞, the result proves itself. Likewise if α and β are both −∞, so it
suffices to consider the finite cases.
Let α = lim supn→∞ an and β = lim supn→∞ bn . Suppose that lim supn→∞ (an + bn ) = γ > α + β.
Then, some sequence {sn } with sn = an + bn converges to γ . For each sn , either an > α or bn > β.
Thus, either an > α infinitely often, or bn > β infinitely often. In either of these cases, either
lim supn→∞ an > α, or lim supn→∞ bn > β, a contradiction.
6. Investigate the behaviour of an if

Í
√ √
(a) an = n + 1 − n.
√
Proof. The partial sums sn = n + 1 − 1 diverge to +∞, so the sum diverges.
√ √
n+1− n
(b) an = n .
Proof. Manipulate:
√ √
n+1− n (n + 1) − n 1
0 ≤ an = = √ √ ≤ 3/2
n n( n + 1 + n) n
so since n−3/2 converges, an converges by the comparison test.

Í Í

√ n
(c) an = n
n−1 .
Proof. Since we have

√ √
lim sup n an = lim sup n n − 1 = 0 < 1,

n→∞ n→∞
the series an converges by the root test.

Í

1
(d) an = 1+z n for complex z.
Proof. Notice that if |z| < 1, then an → 1 , 0, so the sum does not converge. If |z| > 1, notice
that the ratios
an 1 + z n−1 1
= n
→ <1
an−1 1+z z
so an converges by the ratio test. If |z| = 1, the sum diverges.
Í

52
Í √an
7. Prove that the convergence of an implies the convergence of , if an ≥ 0.
Í
n
Proof. We consider the ratio:

√ √
bn n−1 an an
= ·√ < √
bn−1 n an−1 an−1
so
bn an
r
lim sup ≤ lim sup <1
n→∞ bn−1 n→∞ an−1
since an converges by the ratio test.
Í

8. If an converges and {bn } is monotonic and bounded, prove that an bn converges.

Í Í
Proof. Let B = bn . We can write

Í
Õ Õ Õ
a n bn = an (bn − B) + B an
for which the first sum converges by Theorem 3.42, and the second sum converges as a scalar
multiple of a convergent series.
9. Find the radius of convergence of the following power series:

(a) n3z n .
Í
Proof. In order for n3z n to converge, we must have

Í
n 3z n
lim sup = |z| < 1
n→∞ (n − 1)3z n−1
so the radius of convergence is 1.
Í 2n n.
(b) n! z
Proof. Using the ratio test, we must have

2n (n − 1)!z n 2
lim sup n−1 n−1
= lim sup |z| = 0 < 1
n→∞ 2 n!z n→∞ n
which holds regardless of z, so the radius of convergence is +∞.

Í 2n
(c) n2
zn .
Proof. Using the ratio test, we must have

2n (n − 1)2z n (n − 1)2
lim sup = lim sup 2 |z| = 2|z| < 1
n→∞ 2n−1n2z n−1 n→∞ n2
so the radius of convergence is 1/2.
Í n3 n.
(d) 3n z
Proof. By the ratio test, we must have

n3 3n−1z n 1 n3 1
lim sup 3 n n−1
= lim sup 3
|z| = |z| < 1
n→∞ (n − 1) 3 z n→∞ 3 (n − 1) 3
so the radius of convergence is 3.
53
10. Suppose that the coefficients of the power series an z n are integers, infinitely many of which
Í
are non-zero. Prove that the radius of convergence is at most 1.
Proof. Let {bn } be the sequence of non-zero coefficients. Then |bn | ≥ 1 so n

|bn | ≥ 1. Thus any
p
subsequential limit of the |bn | will converge to a value at least 1, so

n
p
lim sup n |bn | ≥ 1

p
n→∞
and thus the radius of convergence is at most 1.
11. Suppose an > 0 and sn = a 1 + · · · + an and an diverges.

Í
Í an
(a) Prove that 1+a n
diverges.
an
Proof. We prove the contrapositive. Let bn = 1+a and suppose bn converges. Then we
Í
n
1
know bn → 0 so 1 − bn = 1+a n
→ 1. Thus for 0 < ϵ < 21 , there exists N ∈ N such that if
n ≥ N,
1 bn 1
−1 = −1 <
1 + an an 2
so an < 2bn if n ≥ N . This implies that
m
Õ m
Õ
an < 2 bn < M
n=N n=N
where m ≥ N and M is a bound on the partial sums of bn which exists since bn converges.
Í Í
So the partial sums of an monotonically increasing and bounded above, so an converges.
Í Í

(b) Prove that

a N +1 a N +k sN
+···+ ≥ 1−
s N +1 s N +k s N +k
Í an
and deduce that sn diverges.
Proof. Notice that sn is a monotonically increasing sequence since an > 0, so

a N +1 a N +2 a N +k a N +1 a N +2 a N +k
+ +···+ ≥ + +···+
s N +1 s N +2 s N +k s N +k s N +k s N +k
a N +1 + a N +2 + · · · + a N +k
=
s N +k
sN
=1−
s N +k
Then, letting ϵ = 1/2 > 0, we can fix N and choose k ≥ N such that s N +k > 2s N since the sn
are unbounded, so that
a N +1 a N +2 a N +k sN 1
+ +···+ ≥ 1− >
s N +1 s N +2 s N +k s N +k 2
Í an
so sn is not Cauchy and thus diverges.
(c) Prove that

an 1 1
2
≤ −
sn sn−1 sn
Í an
and deduce that s n2
converges.
54
Proof. We have sn > sn−1 so

an an sn − sn−1 1 1
≤ = = −
sn2 sn sn−1 sn sn−1 sn−1 sn
so
m m
Õ an Õ 1 1 1 1 1
≤ − = − →
s2
n=2 n
s
n=2 n−1
s n s 1 sm a1
Í an
and thus s n2
converges by the comparison test.
(d) What can be said about Õ an Õ an

and ?
1 + nan 1 + n 2a n
an
Proof. The first series converges for some an and diverges for some other an . But 1+n 2 a n
<
an
n 2 an
= n12 so the second series converges by the comparison test and the p-test.
12. Suppose an > 0 and an converges. Put

Í
∞
Õ
rn = am .
m=n
(a) Prove that

am an rn
+···+ > 1−
rm rn rm
Í an
if m < n, and deduce that rn diverges.
Proof. Since an > 0, the sequence r n is decreasing, so

am an am an am + · · · + an−1 rm − r n rn
+···+ > +···+ > = =1− .
rm rn rm rm rm rm rm
Now for any ϵ > 0, suppose ϵ < 1/2 without loss of generality. Then, for any n ∈ N, we can
find m ≥ n such that rrmn < 1 − ϵ since r n → 0, so nk =m ar kk = 1 − rrmn > ϵ. Then ar kk is not
Í Í
Cauchy and thus diverges.
(b) Prove that

an √ √
√ < 2( r n − r n+1 )
rn
a
and deduce that √n converges.
Í
rn
√ √
r n + r n+1
Proof. Since r n+1 < r n , we have √
rn
< 2. Reorganizing yields
an √ √
√ < 2( r n − r n+1 )
rn
since an = r n − r n+1 . Now,

n n
Õ ak Õ √ √ √ √
√ < 2 ( r k − r k+1 ) = 2 rm − 2 r n
rk
k =m k=m
√
which can be made arbitrarily small since r n → 0 so r n → 0. Thus √arnn converges.
Í

55
13. Let an and bn converge absolutely. Then, letting c n = nk =1 ak bn−k , prove that c n converges
Í Í Í Í
absolutely.
Proof. Notice that

n n
Õ ∆ Õ
|c n | = ak bn−k ≤ |ak ||bn−k |.
k=1 k=1
and that letting dn be the positive terms on the right side, dn converges by Merten’s theorem.
Í
Thus, c n converges absolutely by the comparison test.
Í

1
14. If {sn } is a complex sequence, define its arithmetic means σn = n+1 (s 0 + . . . + sn ).
(a) If sn → s, prove that σn → s.
Proof. Let ϵ > 0 be arbitrary and N 0 ∈ N such that |sn − s | < ϵ/2 for n ≥ N 0 . Notice then that
N0 n
∆ Õ |sk − s | Õ |sk − s | S ϵ
|σn − s | ≤ + < +
n+1 n+1 n+1 2
k =0 k=N 0
ÍN0
where S = k=0
|sk − s | is finite. Then, letting N = max(N 0, 2S/ϵ), we notice that
S ϵ
|σn − s | ≤ + ≤ϵ
n+1 2
if n ≥ N , so σn → s.
(b) Construct a sequence {sn } which does not converge, but σn does.
Proof. Consider sn = (−1)n . Then clearly sn does not converge as the partial sums alternate
between 0 and 1, but (
0 if n even
σn = 1
n+1 if n odd
does.
(c) Can it happen that sn > 0 for all n and that lim supn→∞ sn = +∞, but σn → 0?
√ √
Proof. Yes, let s 0 = 1, then sn = 3 n > 0 if 3 n is an integer, otherwise let sn = 1/n2 > 0. Then,
n n
!
1 Õ 1 π2
1 + 2n2/3 + 1/i 2 < 2n−1/3 + n−1 → 0
Õ
σn = sn <
n+1 n+1 i=0
6
k=0
but for any M ∈ R, there exists some integer k > M, and thus s (k−1)2 > M, so lim supn→∞ sn =
+∞, as required.
(d) Put an = sn − sn−1 . Show that

n
1 Õ
s n − σn = kak .
n+1
k =1
Assume that nan → 0 and {σn } converges. Prove that {sn } converges. (Notice this provides a
converse of (a) given nan → 0.
56
Proof. We begin manipulating:

n
1 Õ
s n − σn = s n − sk
n+1
k=0
n−1
n 1 Õ
= sn − sk
n+1 n+1
k=0
" n−1 #
1 Õ
= − sk + nsn − s 0
n+1
k =1
" n n
#
1 Õ Õ
= ksk − ksk −1
n+1
k =1 k =1
n
1 Õ
= kak .
n+1
k =1
Ín
so clearly if nan → 0 and σn → σ , then eventually |σn −σ | < ϵ/2 and k=1 ka k < (n +1)/2·; ϵ,
so |sn − s | < ϵ for any ϵ > 0, and thus {sn } converges.
(e) Prove (d) with the weaker hypothesis that nan is bounded by M < ∞ and σn → σ . Show that
sn → σ , by completing the following outline:
(i) If m < n, then
n
m+1 1 Õ
s n − σn = (σn − σm ) + (sn − si ).
n −m n − m i=m+1
Proof. We manipulate:
n m n m
1 Õ 1 Õ n −m 1 Õ 1 Õ
sn = sk − sk + · sn − sk + sk
n −m n −m n −m n −m n −m
k =0 k =0 k =0 k =0
" n m
# " n m
#
1 Õ Õ 1 Õ Õ
= sk − sk + (sn − sk ) − (sn − sk )
n −m n −m
k =0 k=0 k=0 k=0
n
1 1 Õ
= [(n + 1)σn − (m + 1)σm ] + (sn − sk )
n −m n −m
k=m+1
n
n+1 m+1 1 Õ
= σn − σm + (sn − sk )
n −m n −m n −m
k =m+1
so
n
n+1 m+1 1
Õ
s n − σn = − 1 σn − σn + (sn − sk )
n −m n −m n −m
k=m+1
n
m+1 1 Õ
= (σn − σm ) + (sn − si ),
n −m n − m i=m+1
as required.
(ii) For these i,

(n − i)M (n − m − 1)M
|sn − si | ≤ ≤ .
i +1 m+2
57
Proof. We can write sn − si as a telescoping sum of an :

n n n
Õ ∆ Õ Õ M (n − i)M
|sn − si | = (sk − sk −1 ) ≤ |ak | ≤ = ,
i +1 i +1
k =i+1 k =i+1 k=i+1
since we have k ≥ i + 1 and thus

M M
|ak | ≤ ≤ .
k i +1
and the latter inequality follows immediately from the fact that i ≥ m + 1 in the previous
part of the proof.
(iii) Fix ϵ > 0 and associate to every n the integer m such that
n −ϵ
m≤ < m + 1.
1+ϵ
Then (m + 1)/(n − m) ≤ 1/ϵ and |sn − si | < Mϵ so lim supn→∞ |sn − σ | ≤ Mϵ so the
result follows.
Proof. We have m ≤ n−ϵ

1+ϵ , so (m + 1)/(n −m) ≤ 1/ϵ follows from manipulation. Similarly,
n−m−1
we have m+2 < ϵ. Thus,
(n − m − 1)M
|sn − si | ≤ < Mϵ
m+2
and thus
m+1∆ 1
|sn − σn | ≤ |σn − σm | + |sn − si | < Mϵ
n −m n −m
for sufficiently large m, n such that the first term vanishes (since σn → σ ). Thus
lim sup |sn − σn | ≤ Mϵ,

n→∞
so sn converges to σ since ϵ was arbitrary.
15. Extend Definition 3.21 to points in Rk . Show that Theorems 3.22, 3.23, 3.25(a), 3.33, 3.34, 3.42,
3.45, 3.47, 3.55 are true in this more general setting.
Proof. Each proof is presented in a sufficiently general fashion such that replacing |x − y| with
the respective metric in Rk suffices to prove each theorem for infinite sums in Rk .
√
16. Fix α > 0. Choose x 1 > α and let
1 α

x n+1 = xn + .
2 xn
√
(a) Prove that {x n } decreases monotonically and that x n → α.
√ √
Proof. Notice that x n > α for each n from the AM-GM inequality, and thus α/x n < α.
Thus, x n+1 < x n and the sequence is monotonically decreasing and bounded below. Thus, it
√
converges to some L ≥ α. Then, notice that
1 α 1

L = lim x n+1 = lim xn + = (L + α/L)
n→∞ n→∞ 2 xn 2
√ √
which has solutions ± α, so limn→∞ x n = α, as required.
58
√
(b) Put ϵ = x n − α and show that
ϵn2 ϵ2
ϵn+1 = < √n
2x n 2 α
√
so that if β = 2 α,
2n
ϵ1

ϵn+1 <β .
β
Proof. We have
√
ϵn2 (x n − α)2 1 √ α 1 α √

= = xn − 2 α + = xn + − α = ϵn+1 .
2x n 2x n 2 xn 2 xn
√
and the second part of the inequality follows from the fact proven in part (a) that x n > α
for all n. The second fact follows inductively by the above statement.
(c) This presents a great algorithm for computing square roots. Show that if α = 3 and x 1 = 2,
that ϵ1 /β < 0.1 so ϵ5 < 4 · 10−16 and ϵ6 < 4 · 10−32 .
√ √
Proof. We have β = 2 3 and ϵ1 = 2 − 3 so
√
ϵ1 2 − 3 4−3 1
= √ = √ √ < < 0.1
β 2 3 2 3(2 + 3) 10.5
√ 4 5
since 3 < 1.5. Then ϵ5 < β · 10−2 < 4 · 10−16 and similarly ϵ6 < β · 10−2 < 4 · 10−32 as
required.
√
17. Fix α > 1 and take x 1 > α and
α + xn α − x n2
x n+1 = = xn + .
1 + xn 1 + xn
(a) Prove that x 1 > x 3 > x 5 > · · · .
(b) Prove that x 2 < x 4 < x 6 < · · · .
Proof. Manipulating, we have
α + x n+1 (1 + x n )(α + x n+1 ) α + αx n + α + x n

x n+2 = = = < xn
1 + x n+1 (1 + x n )(1 + x n+1 ) 1 + xn + α + xn
if and only if
α + αx n + α + x n < x n + x n2 + αx n + x n2 ⇐⇒ 0 < α < x n2

√ √
so it suffices to show that x 2k +1 > α and x 2k < α inductively to conclude both results.
√
Now, if x n > α, then
√
α − x n2 √ α + xn √
x n+1 − x n = = (x n − α) > xn − α
1 + xn 1 + xn
√ √
since α > 1. Then x n+1 < α. The argument is symmetric for the other condition,
√
(c) Prove that x n → α.
59
√
Proof. The subsequence {x 2k+1 } is decreasing and bounded below by α, and is thus conver-
√
gent. It must converge to a value L ≥ α such that
α + xn α + L
L = lim x n+2 = lim = ,
n→∞ n→∞ 1 + xn 1+L
√ √
whose solutions are ± α. Thus, L = α.
(d) Compare the rapidity of convergence of this process with the previous one.
Proof. TODO: It converges slower, but I’m not able to show this...
18. Replace the recursive definition in Exercise 16 by

p−1 1 α
x n+1 = x n + · p−1
p p xn
where p is a fixed positive integer. Describe the behaviour of the resulting sequences {x n }.
√
Proof. Notice that according to the definition, we must have x n+1 ≥ p α by the AM-GM inequality.
√
Then let x 1 > p α without loss of generality, then by a similar argument as above, x n+1 < x n so
the sequence converges since it is monotonically decreasing and bounded below. It must converge
√ √
to its unique fixed point at least p α, namely x n → p α.
19. Associate to each sequence a = {α n } ∈ {0, 2}N the real number

∞
Õ αn
x(a) = .
n=1
3n
Prove that the set of all x(a) is the Cantor set.
Proof. First, notice that for any real number r ∈ [0, 1], we can associate a ternary representation
{an } ∈ {0, 1, 2}N such that r = n=0 an 3−n , so this question reduces to showing that r is in the
Í∞
Cantor set iff it contains no 1s in its ternary representation.
Notice that by construction, the middle thirds of each segment that we remove in the i-th iteration
have a 1 as the i-th trit. So {0, 2}N ⊇ C. The converse follows again by noticing that any
r ∈ {0, 2}N is in each closed partial Cn , and thus in its infinite intersection C.
20. Suppose {pn } is a Cauchy sequence in a metric space X and some subsequence {pni } converges
to a point p ∈ X . Prove that the full sequence {pn } converges to p.
Proof. Let ϵ > 0 be arbitrary and let I ∈ N such that d(pni , p) < ϵ/2 for all i ≥ I . Also, let
N ∈ N such that for all n ≥ m ≥ N , we have d(pn , pm ) < ϵ/2. Let N 1 be some ni for i ≥ I such
that ni ≥ N . Then for all n ≥ N 1 , we have d(pn , p) ≤ d(pn , p N1 ) + d(pn I , p) ≤ ϵ so pn → p as
required.
21. Prove the following analogue of Theorem 3.10(b): If {En } is a sequence of closed non-empty
and bounded sets in a complete metric space X , if En ⊇ En+1 , and if diam En → 0, then n=1 En
Ñ∞
contains a single point.
Proof. Let pn ∈ En . Then {pn , pn+1, . . . } ⊆ En so diam{pn , pn+1, . . . } → 0, ie. {pn } is Cauchy.
Since X is complete, pn → p for some p ∈ X . But now for any n, the sequence {pn , pn+1, . . . }
converges to p ∈ En since En is closed. Thus, p ∈ n=1 En . Now p must be the unique point in
Ñ∞
E otherwise the diameters of E would not fall below some positive real value.
Ñ∞
n=1 n n
60
22. Suppose X is a non-empty complete metric space, and {G n } is a sequence of dense open subsets
of X . Prove Baire’s theorem, namely that n=1 G n is non-empty, and in fact dense in X .
Ñ∞
Proof. Let S be a neighbourhood in X . We show that S ∩ n=1 G n is non-empty. We define a

Ñ∞
sequence {Fn } of closed and bounded subsets of X : let E 0 = S, and construct En inductively as
follows: take x n from the dense open set En−1 ∩ G n , and En some neighbourhood of x n with
En ⊆ G n ∩ En−1 . This defines a sequence {En } such that En ⊆ S ∩ ni=1 G i inductively. Then,
Ñ
{Fn = En } forms a sequence of closed and bounded sets in the complete metric space X , so by
the previous theorem, n=1 Fn ⊆ S ∩ n=1 G n is non-empty, as required.
Ñ∞ Ñ∞

23. Suppose {pn }, {qn } are Cauchy sequences in a metric space X . Show that the sequence {d(pn , qn )}
converges.
Proof. Let ϵ > 0 be arbitrary. Let Np ∈ N such that if n ≥ m ≥ Np , then d(pn , pm ) < ϵ/2. Define
Nq similarly. Then, for any n ≥ m ≥ max(Np , Nq ), we have
d(pn , qn ) ≤ d(pm , qm ) + d(pn , pm ) + d(qn , qm ) < d(pm , qm ) + ϵ,
and similarly d(pm , qm ) ≤ d(pn , qn ) +ϵ, so |d(pn , qn ) −d(pm , qm )| < ϵ, so the sequence {d(pn , qn )}
is Cauchy in R and thus convergent since R is complete.
24. Let X be a metric space.

(a) Call two Cauchy sequences {pn }, {qn } equivalent if d(pn , qn ) → 0. Show that this is an
equivalence relation.
Proof. Clearly d(pn , pn ) → 0 so {pn } ∼ {pn }. Also, since d(pn , qn ) = d(qn , pn ), the relation
is symmetric. Finally, if {pn } ∼ {qn } and {qn } ∼ {r n }, then 0 ≤ d(pn , r n ) ≤ d(pn , qn ) +
d(qn , r n ) → 0 converges to 0 by the comparison test. Thus the relation is transitive. These
properties together make ∼ an equivalence relation on the Cauchy sequences in X .
(b) Let X ∗ be the set of equivalence classes under the above relation. If P, Q ∈ X ∗ and {pn } ∈ P,
{qn } ∈ Q, define
∆(P, Q) = lim d(pn , qn ),
n→∞
which exists from Exercise 23. Show that the number ∆(P, Q) is unchanged if we replace {pn }
or {qn } by equivalent sequences, so that ∆ is a distance function in X ∗ .
Proof. Suppose D = ∆(P, Q) = limn→∞ d(pn , qn ) for Cauchy sequences {pn } ∈ P, {qn } ∈ Q.
Suppose that {r n } ∈ P. Then, notice that
∆ ∆
d(pn , qn ) − d(pn , r n ) ≤ d(r n , qn ) ≤ d(pn , r n ) + d(pn , qn )
so limn→∞ d(r n , qn ) = D by the Squeeze theorem so we are done.
(c) Prove that the resulting metric space X ∗ is complete.
Proof. It is always true that convergent sequences are Cauchy. It suffices to show that
Cauchy sequences in X ∗ converge in X ∗ . Suppose that {Pn } is Cauchy with respect to
the distance metric ∆. Then, for each n, there exists a Cauchy sequence in Q kn such that
limk→∞ ∆(Pn , Q kn ) = 0. Then, for each n, we extract a subsequence Q n0 of Q kn such that
∆(Pn , Q n0 ) < 1/n for all n. Then,
∆
∆(Q n0 , Qm
0
) ≤ ∆(Pn , Q n0 ) + ∆(Pn , Pm ) + ∆(Pm , Qm
0
) < 1/n + 1/m + ϵ < 3ϵ
61
for sufficiently large m, n, where ϵ > 0 can be made arbitrarily small. Thus {Q n0 } is Cauchy.
Also, if {Q n0 } ∈ P, then
∆(P, Pn ) ≤ ∆(P, Q n0 ) + ∆(Q n0 , Pn ) < 2ϵ
so Pn → P is convergent, as required.
(d) For each p ∈ X , there is a Cauchy sequence all of whose terms are p. Let Pp be the element of
X ∗ which contains this sequence. Prove that
∆(Pp , Pq ) = d(p, q)
for all p, q ∈ X , so that ϕ : p 7→ Pp is an isometry (a distance-preserving mapping) of X onto

X ∗.
Proof. This is trivial if we take the representative sequence to be the constant sequence of p
and q: the limit is that of a constant sequence.
(e) Prove that ϕ(X ) is dense in X ∗ , and that ϕ(X ) = X ∗ if X is complete. By (d), we may identify
X and ϕ(X ) and thus regard X as embedded in the complete metric space X ∗ . We call X ∗ the
completion of X .
Proof. Take P ∈ X ∗ and {pn } ∈ P with pn ∈ X . Then Ppn → P since {pn } is Cauchy, so ϕ(X )
is dense in X ∗ . Similarly, if X were complete, then every element P ∈ X ∗ admits a constant
sequence, so X ∗ ⊆ ϕ(X ) completing the proof.
25. Let X be a metric space whose points are the rational numbers, with the metric d(x, y) = |x − y|.
What is the completion of this space? (Compare Exercise 24).
Proof. The completion is R! Clearly Q∗ ⊆ R by definition, and every element r ∈ R has some
Cauchy sequence in Q which converges to it, namely the one generated by its decimal expansion.

62
4 Continuity
4.1 Limits of Functions

Definition 30. Let X, Y be metric spaces and E ⊆ X . Let f map E into Y , and p be a limit point of E. We
write f (x) → q as x → p, or equivalently
lim f (x) = q
x →p
iff there is a point q ∈ Y such that for every ϵ > 0, there exists δ > 0 such that dY (f (x), q) < ϵ for all
points x ∈ E such that 0 < d X (x, p) < δ .
Note that p ∈ X , but that p need not be in E. Also, even if p ∈ E, we do not necessarily have f (p) =
limx →p f (x). This property is interesting and we will formalize it later.
Theorem 69. Let X, Y , E, f , p as in Definition 4.1. Then, f (x) → q when x → p iff f (pn ) → q for every
sequence {pn } in E \ {p} which converges to p.
Proof. Suppose that f (x) → q as in Definition 4.1. Then, let ϵ > 0 be arbitrary, and let δ such that
Definition 4.1 holds. Then, if {pn } is some sequence converging to p, then eventually d X (pn , p) < δ , so
dY (f (pn ), q) < ϵ eventually. Thus f (pn ) → q.
Now suppose that f (x) 9 q as in Definition 4.1. Then, there exists some ϵ > 0 such that for every δ > 0,
we can find some x ∈ E such that 0 < d X (x, p) < δ but dY (f (x), q) ≥ ϵ. Let δ = 1/n for every n, giving
us some sequence x n such that dY (f (x n ), q) ≥ ϵ. Thus f (x n ) 9 q, proving the contrapositive.
Corollary 8. If f has a limit at p, then this limit is unique.

Definition 31. If f , д are complex functions, then we denote f +д to be the function such that (f +д)(x) =
f (x) + д(x). We define f − д, f д and f /д similarly. If f (x) = c for all x, then we say f is constant, and
write f = c. If f (x) ≥ д(x) for all x, we sometimes write f ≥ д.
Theorem 70. Let E ⊆ X a metric space, p a limit point of E, and f and д complex functions on E.
Furthermore, let A = limx →p f (x) and B = limx →p д(x). Then,
1. limx →p (f + д)(x) = A + B.
2. limx →p (f д)(x) = AB.
3. limx →p (f /д)(x) = A/B if B , 0.
4. If f and д map into Rk , then additionally limx →p (f · д)(x) = A · B.
Proof. This follows immediately from the analogous properties of sequences.
4.2 Continuous Functions

Definition 32. Suppose X, Y are metric spaces, E ⊆ X , p ∈ E, and f : E → Y . Then, f is continuous at
p if for every ϵ > 0, there exists δ > 0 such that
dY (f (x), f (p)) < ϵ
63
4 Continuity
for all points x ∈ E for which d X (x, p) < δ . If f is continuous at every point in E, then f is continuous
on E.
Notice that every function f is continuous at isolated points of p, since we can always choose δ > 0
sufficiently small such that E ∩ Nδ (x) = {p} so dY (f (x), f (p)) = 0 < ϵ.
Theorem 71. Let everything as Definition 4.5. If p is a limit point of E, then f is continuous at p iff
f (x) → f (p) as x → p.
Theorem 72. Suppose X, Y , Z are metric spaces, f : (E ⊆ X ) → Y and д : f (E) → Z , and h = д ◦ f .
Then, if f is continuous at p ∈ E and д is continuous at f (p), then h is continuous at p.
Proof. Let ϵ > 0. Since д is continuous at f (p), there exists some δ > 0 such that d Z (д(f (x)), д(f (p))) < ϵ
for all f (x) ∈ f (E) such that 0 < dY (f (x), f (p)) < δ . However, since f is continuous, we can find δ 0 > 0
such that dY (f (x), f (p)) < δ whenever 0 < d X (x, p) < δ 0. In other words, we’ve found δ 0 > 0 such that
d Z (h(x), h(p)) < ϵ whenever 0 < d X (x, p) < δ 0, so h is continuous at p as required.
Theorem 73. A mapping f of a metric space X into a metric space Y is continuous on X iff f −1 (V ) is
open in X for every open set V in Y .
Proof. Suppose f is continuous on X . Then, if y ∈ V for some open V , then there exists some neigh-
bourhood Nϵ (y) around y. By the definition of continuity, this admits Nδ (f −1 (y)) in f −1 (V ) for positive
δ , so f −1 (V ) is open in X , so the forward direction is done since V was chosen arbitrarily.
Now for the contrapositive, suppose f −1 (V ) is open for every open subset V of Y . Then, for any x ∈ X ,
for any ϵ > 0, the set V = Nϵ (f (x)) is an open set in Y , so f −1 (V ) is open by assumption. Therefore,
f −1 (f (x)) = x is an interior point of f −1 (V ), so in particular, this gives us the δ > 0 we need for
continuity.
Corollary 9. A mapping f of a metric space X into a metric space Y is continuous iff f −1 (C) is closed in
X for every closed set C in Y .
Theorem 74. If f , д are continuous complex functions on X , then f + д, f д and f /д are continuous on X .
Proof. These follow directly from the corresponding theorems on sequences, and the equivalence of
the sequential definition of continuity.
Theorem 75. Let f 1, f 2, . . . , fk be real functions on X and f be the mapping of X into Rk defined by
f(x) = (f 1 (x), f 2 (x), . . . , fk (x)).
then f is continuous iff each of the functions f 1, . . . , fk is continuous.
Furthermore, if f, g : X → Rk are continuous, then f + g and f · g are continuous.
Proof. Part (a) follows from the fact that

v
k
u
t
Õ
| fi (x) − fi (y)| ≤ |x − y| = | f j (x) − f j (y)| 2, ∀i ∈ {1, 2, . . . , k},
j=1
and part (b) follows from (a) and Theorem 4.9.
Now, we show that a very large class of functions is continuous. Firstly, the component function
f ((x 1, . . . , x k )) = x i is continuous for any i ∈ {1, 2, . . . , k }. This shows that polynomials in the
components are continuous, and thus rational functions on (x i ) are continuous. Finally, it can be seen
that f (x) = |x| is continuous.
64
4 Continuity
4.3 Continuity and Compactness

Definition 33. A mapping f : E → Rk is bounded if there is a real number M such that |f(x)| ≤ M for
all x ∈ E.
Theorem 76. Suppose f is a continuous mapping of a compact metric space X into a metric space Y .
Then f (X ) is compact.
Proof. Let {G α } be an open cover of f (X ). Then, since f is continuous, each f −1 (G α ) is open, forming
an open cover for X . Since X is compact,
n
Ø
X ⊆ f −1 (G i )
i=1
Ðn
for some finite subset {G i } of {G α }. Then, since f (f −1 (E)) ⊆ E for all E ⊆ X , we have f (X ) = i=1 G i ,
so f (X ) is compact.
Theorem 77. If f : X → Rk , then f(X ) is closed and bounded. Thus, f is bounded.
Proof. By Theorem 4.14, f(X ) is compact. Thus it is closed and bounded. In particular it is bounded.
Theorem 78 (Extreme Value Theorem). Suppose f is a continuous real function on a compact metric
space X , and
M = sup f (p), m = inf f (p),
p ∈X p ∈X
then f attains M and m.
Proof. From Theorem 4.14, f (X ) is compact and thus closed and bounded. Hence f (X ) contains M and
m, proving the result.
Theorem 79. Suppose f is a continuous bijection from a compact metric space X onto a metric space Y .
Then, f −1 is a continuous mapping of Y onto X .
Proof. To use Theorem 4.8, it suffices to show that f (V ) is open for every open set V in X . But V c is
closed and thus compact in X , and thus f (V c ) is compact and thus closed in Y . Since f is bijective,
f (V ) is the complement is f (V c ), thus f (V ) is open.
Definition 34. A mapping f : X → Y is uniformly continuous on X if for every ϵ > 0, there exists
δ > 0 such that
dY (f (p), f (q)) < ϵ, ∀p, q ∈ X : d X (p, q) < δ .
Theorem 80. If f is a continuous mapping from a compact metric space X into a metric space Y , then f
is uniformly continuous on X .
Proof. We prove the contrapositive: suppose f is not uniformly continuous on X . Then, for some
ϵ > 0, we can find pn , qn ∈ X such that d X (pn , qn ) < 1/n but dY (f (pn ), f (qn )) > ϵ. Then, since X is
compact, we can find a subsequence (pnk ) which converges, then take a subsequence (qnkm ) of (qnk )
which converges, again since X is compact. We relabel these subsequences (r n ) and (sn ). By the Squeeze
Theorem, r n , sn → x 0 for some x 0 ∈ X . However, dY (f (r n ), f (sn )) > ϵ, so f cannot be continuous at x 0
by the sequential definition of continuity, completing the proof.
Theorem 81. Let E be a non-compact set in R. Then:
65
4 Continuity
1. There exists a continuous unbounded function on E.

2. There exists a continuous and bounded function on E which does not attain its maximum.
3. If E is bounded, there exists a continuous function on E which is not uniformly continuous.
Proof. For (a), if E is unbounded, then f (x) = x is continuous but unbounded. Otherwise, E is not
closed, so there exists a limit point x 0 of E which is not in E. Then f (x) = 1/(x − x 0 ) is continuous but
unbounded (consider the sequence converging to x 0 ).
For (b), if f (x) is the function constructed in part (a), then д(x) = −1/| f (x)| is bounded above by 0 and
continuous, but never attains its maximum of 0.
For (c), notice E is thus not closed. Then f (x) from part (a) is not uniformly continuous.
4.4 Continuity and Connectedness

Theorem 82. If f : X → Y and E is a connected subset of X , then f (E) is connected.
Proof. We prove the contrapositive: suppose f (E) = A ∪ B and A, B are non-empty separated sets. Then,
letting A0 = E ∩ f −1 (A) and B 0 = E ∩ f −1 (B), we see that E = A0 ∪ B 0.
Now
A0 ∩ B 0 ⊆ E ∩ f −1 (A) ∩ f −1 (B) = ∅
since A ∩ B = ∅, and repeating the argument for A0 and B 0 shows that (A0, B 0) is a separation of E,
proving the contrapositive.
Theorem 83 (Intermediate Value Theorem). Let f be a continuous real function on the interval [a, b]. If
f (a) < c < f (b), then f (x) = c for some x ∈ (a, b).
Proof. If not, then f ([a, b]) ∩ (f (a), c) and f ([a, b]) ∩ (c, f (b)) form a disconnection of f ([a, b]), contra-
dicting Theorem 4.22.
4.5 Discontinuities
Definition 35. If f : X → Y and x ∈ X is such that f is not continuous at x, we say f is discontinuous
at x, or that f has a discontinuity at x.
Let f : (a, b) → Y . Let x ∈ [a, b). We define f (x+) = q if f (tn ) → q for any sequence {tn } in (x, b) with
tn → x. We define f (x−) symmetrically. Clearly limt →x f (t) exists iff f (x−) = f (x+) = limt →x f (t).
Definition 36. Let f : (a, b) → Y . If f is discontinuous at x, but f (x−) and f (x+) both exist, f is said to
have a discontinuity of the first kind, or a simple discontinuity at x. Otherwise, the discontinuity
is said to be of the second kind.
If f has a simple disconinuity at x, either f (x+) , f (x−), or f (x+) = f (x−) , f (x).
4.6 Monotonic functions

Definition 37. Let f : (a, b) → R. Then f is monotonically increasing on (a, b) if a < x < y <
b implies f (x) ≤ f (y). If instead f (x) ≥ f (y) with the same conditions, then f is monotonically
decreasing.
66
4 Continuity
Theorem 84. Let f be monotonically increasing on (a, b). Then f (x+) and f (x−) exist at every point
x ∈ (a, b).
Proof. Every sequence converging to x from the left has a monotonically increasing subsequence. Then
f (x n ) is monotonically increasing and bounded above, say by f (x + δ ). Thus f (x n ) converges by the
Monotone Convergence Theorem. The argument for f (x+) is analogous.
Corollary 10. Monotonic functions have no discontinuities of the second kind.

Theorem 85. Let f be monotonic on (a, b). Then the set of discontinuities of f in (a, b) is at most countable.
Proof. We associate each discontinuity x in (a, b) with a rational number r such that f (x−) < r < f (x+),
forming an injection from the set of discontinuities to Q, proving the result.
4.7 Infinite Limits and Limits at Infinity

Definition 38. The set (c, +∞) is considered a neighbourhood of +∞. Similarly for (−∞, c) being neigh-
bourhoods of −∞.
Definition 39. Let f : (E ⊆ R) → Y . We say f (t) → y as t → x, where A, x ∈ R, if for every
neighbourhood U of y, there is a neighbourhood V of x such that V ∩ E is non-empty, and f (t) ∈ U for all
t ∈ V ∩ E \ {x }. Limits of functions still combine in the same ways.
4.8 Exercises
1. Suppose f : R → R with limh→0 [f (x + h) − f (x − h)] = 0 for all x ∈ R. Is f continuous?
Proof. No, consider the function f which is 1 at 0 and 0 everywhere else. Then f satisfies the
condition everywhere but is discontinuous at x = 0.
2. Let f : X → Y be continuous. Prove that
f (E) ⊆ f (E)
for every E ⊆ X . Show that this inequality can be proper.
Proof. Let E be arbitrary and x ∈ E. If x ∈ E, then clearly f (x) ∈ f (E) ⊆ f (E). Otherwise, x is a
limit point of E, so some sequence (x n ) in E converges to x, so since f is continuous, the sequence
f (x n ) → f (x), and thus f (x) ∈ f (E), as required.
Let f (x) = 1 for all x < 1 and f (x) = 1/x if x > 1. Then f is continuous on R, but 0 ∈ f (R) but
is not in f (R), so the inclusion can be proper.
3. Let f : X → R be continuous. Let Z (f ) be the kernel of f . Prove that Z (f ) is closed.
Proof. Let x n → x be a convergent sequence in Z (f ). Then f (x n ) = 0 for all n, and thus

f (x n ) → 0. Since f is continuous, this implies that f (x) = 0, and thus that x ∈ Z (f ), completing
the proof.
4. Let f , д : X → Y be continuous, and E be dense in X . Prove that f (E) is dense in f (X ). If

д(p) = f (p) for p ∈ E, prove that д(p) = f (p) for all p ∈ X .
67
4 Continuity
Proof. Let V ⊆ f (X ) be open. Since f is continuous, f −1 (V ) is open, and since E is dense, we can
find p ∈ E ∩ f −1 (V ), which corresponds to p ∈ E such that f (p) ∈ V , so in particular, f (p) is an
element of f (E) in V . Since V was arbitrary, f (E) is dense in f (X ).
Notice that E is a dense subset of Z = Z (д − f ). Thus, E = X ⊆ Z ⊆ X , so in particular, X = Z
since Z is closed from the previous Exercise, completing the proof.
5. Let f : (E ⊆ R) → R be continuous, and E be closed. Prove that there exist continuous functions
д : R → R such that д = f on E. These are called continuous extensions of f from E to R.
Show that the result becomes false if E is not closed, and extend the result to vector-valued
functions.
Proof. We know that E c is open and thus a countable union of disjoint open segments of R. For
each of these segments (a, b), assign д(at + b(1 − t)) = t f (a) + (1 − t)f (b), and д(x) = f (x) on E.
Then д = f on E, and д is continuous at the endpoints a and b, as required.
Now, if E = {±1/n : n ∈ N+ }. Then let f (1/n) = 1 + 1/n and f (−1/n) = −1 + 1/n. Then the
sequences f (1/n) → 1 and f (−1/n) → −1 while both ±1/n → 0. Thus any д which agrees with
f on E must be discontinuous at 0, and thus no such continuous extension of f exists.
6. If f is defined on E, the graph of f is the set of points (x, f (x)) for x ∈ E. Suppose E is compact.
Prove that f is continuous on E iff its graph is compact.
Proof. First, suppose f is continuous. Let {G α } be an open cover of (E, f (E)). Then since f
is continuous, E and f (E) are both compact, so we can choose elements {G n } such that the
restrictions of the G n to X cover E, and similarly Gm to cover f (E). These two sets combined give
a finite cover for the graph of f .
Now suppose the graph of f is compact. Then [ TODO ]
7. If E ⊆ X and f is defined on X , the restriction of f to E is the function whose domain is

E, such that д(p) = f (p) for p ∈ E. Define f , д : R2 → R such that f (0, 0) = д(0, 0) = 0,
f (x, y) = xy 2 /(x 2 + y 4 ), д(x, y) = xy 2 /(x 2 + y 6 ) otherwise. Prove that f is bounded on R2 , and
that д is unbounded in every neighbourhood of (0, 0), and that f is not continuous at (0); but
nevertheless that the restrictions of both f and д to every straight line in R2 are continuous!
Proof. Notice that a 2ab

+b 2
≤ 21 since (a − b)2 = a 2 − 2ab + b 2 ≥ 0 for any a, b. Thus f is bounded.
3
Now, we have д(1/n , 1/n) = n/2 so д is unbounded in any neighbourhood of (0, 0). Finally,
f (1/n2, 1/n) = 1/2 for any n, so f is discontinuous at (0, 0).
cy 3 cy
However, if x = cy, f (cy, y) = c 2y 2 +y 4 = c 2 +y 2 → 0 as y → 0, so f is continuous on the line
x = cy. On any other line not passing through (0, 0), the restriction is purely within the domain
cy
of the continuous definition. Similarly, д(cy, y) = c 2 +y 4 → 0 as y → 0, so д is continuous on any
straight line.
8. Let f : E → R be uniformly continuous on a bounded set E ⊆ R. Prove that f is bounded on R.
Proof. Suppose not, and let x n be a sequence in E such that f (x n ) ≥ n for all n ∈ N. Then, (x n )
admits a convergent subsequence (x nk ), which converges to x 0 , which is not necessarily in E.
Then any sufficiently small neighbourhood of x 0 contains elements f (x nk ) which are arbitrarily
far apart, contradicting the fact that f is uniformly continuous, proving the result.
68
4 Continuity
9. Show that the requirement in the definition of uniform continuity can be rephrased as follows,
in terms of diameters of sets: To every ϵ > 0, there exists δ > 0 such that diam f (E) < ϵ for all
E ⊆ X with diam E < δ .
Proof. Suppose the new definition holds. Then, let ϵ > 0 be arbitrary and δ as in the definition.
Then, for any two x, y ∈ E such that d X (x, y) < δ , the set E = {x, y} has diameter strictly less
than δ , and thus diam f ({x, y}) < ϵ, corresponding to the fact that dY (f (x), f (y)) < ϵ.
Now, suppose the old definition holds, and ϵ > 0 be arbitrary. Let δ > 0 as in the old definition
with ϵ/2 > 0. Furthermore, let E be a set such that diam E < δ . Now, for any pair x, y ∈ E,
we have d X (x, y) ≤ diam E < δ , so dY (f (x), f (y)) < ϵ. Thus, diam f (E) = sup{dY (f (x), f (y)) :
x, y ∈ E} ≤ ϵ/2 < ϵ, as required.
10. Complete the details of the following alternative proof of Theorem 4.19.
Proof. Plot twist: I accidentally wrote this proof as I went along proving while copying over the
notes.
11. Suppose f : X → Y is uniformly continuous, and let {x n } be Cauchy in X . Prove that { f (x n )} is

Cauchy in Y . Use this result to give an alternative proof of the theorem stated in Exercise 13.
Proof. Let En = {x n , x n+1, . . . }. Let ϵ > 0. We want to show that diam f (En ) < ϵ for sufficiently
large N . Choose δ > 0 such that the definition from Exercise 4.9 holds. Then choose N ∈ N such
that diam En < δ for all n ≥ N , which exists some {x n } is Cauchy. Then, for any n ≥ N , we have
diam En < δ and thus diam f (En ) < ϵ as required.
12. A uniformly continuous function of a uniformly continuous function is uniformly continuous.

State this more precisely and prove it.
Proof. Let X, Y , Z be metric spaces and f : (E ⊆ X ) → Y and д : Y → Z be uniformly continuous.

Let h = д ◦ f . Then h is uniformly continuous on E.
Let ϵ > 0 be arbitrary. Then there exists δ > 0 such that diam E < δ implies diam д(E) < ϵ.
Furthermore, there exists ν > 0 such that diam F < ν implies diam f (F ) < δ . Then if diam F < ν ,
then diam f (F ) < δ and thus diam h(F ) = diam(д ◦ f )(F ) < ϵ, as required.
13. Let E be a dense subset of a metric space X , and let f : E → R be uniformly continuous. Prove
that f has a continuous extension from E to X . Could the range space R be replaced by Rk ? By
any compact metric space? By any complete metric space? By any metric space?
Proof. We define д : X → Y such that д = f on E, and д(x) = limn→∞ f (x n ) for any sequence
x n → x. We must show that this definition is well defined: specifically that the right hand side
does not depend on our choice of x n .
Let {x n } and {yn } be two sequences which converge to x ∈ X , and let ϵ > 0 be arbitrary. We
wish to show that limn→∞ dY (f (x n ), f (yn )) < ϵ. Now since f is uniformly continuous, there
exists some δ > 0 such that if d X (x n , yn ) < δ , then dY (f (x n ), f (yn )) < ϵ. Since x n , yn → x, we
∆
can choose N ∈ N sufficiently large so that d X (x n , x), d X (yn , x) < δ /2, such that d X (x n , yn ) < δ ,
and thus dY (f (x n ), f (yn )) < ϵ. The result follows.
14. Let I be the closed unit interval, and f : I → I be continuous. Prove that f (x) = x for at least one
x ∈ I.
69
4 Continuity
Proof. If f (0) = 0 or f (1) = 1, we are done. Otherwise, f (0) > 0 and f (1) < 1, so the function
д(x) = f (x) − x is positive at 0 and negative at 1. By the Intermediate Value Theorem, д(x) =
f (x) − x = 0 so f (x) = x for some x ∈ (0, 1) ⊆ I , as required.
15. A mapping f : X → Y is open if f (V ) is open in Y whenever V is open in X . Prove that every

continuous open mapping f : R → R is monotonic.
Proof. Suppose the contrary, specifically that f : R → R is a non-monotonic continuous open

mapping . Then there exists a segment (a, b) such that either the supremum or the infimum of
f on (a, b) is not achieved at either endpoint. Then, by the Extreme Value Theorem, f attains
this extremum within the segment, say at c ∈ (a, b). Then, f ((a, b)) is not open, as it contains no
neighbourhoods of f (c), contradicting the fact that f is open.
16. Let [x] denote the floor of x, and (x) = x − [x]. What discontinuities do [x] and (x) have?
Proof. They are both discontinuous at the integers.
17. Let f : (a, b) → R. Prove that the set of points at which f has a simple discontinuity is at most
countable.
Proof. Following the hint, let E < be the set of all simple discontinuities x of f such that f (x−) <
f (x+). Then, associate to each x ∈ E < a triple of rational numbers (p, q, r ) such that f (x−) p. We claim that every
triple represents a unique simple discontinuity of f :
Suppose that x and x 0 are simple discontinuities and x < x 0 WLOG, both represented by the
triples (p, q, r ). Then in the interval (x, x 0) lie in both the intervals (x, r ) and (q, x 0), and thus f (t)
must be both less than, and greater than, p at the same time, a contradiction. Thus, we must have
x = x 0, as required.
We can define E > and associate triples a similar way. For E = , we associate to each discontinuity
(p, q, r ) where p is between f (x) and f (x−) = f (x+), q such that f (t) < p in (q, x) and (x, r ).
Again, these triples map uniquely from the discontinuities in E = . Since each of these sets must be
at most countable, their union is also at most countable.
18. Every rational x can be written as x = m/n with n > 0 and (m, n) = 1. When x = 0, take n = 1.
Then, consider f (x) = 1/n if x is rational, and 0 otherwise. Prove that f is continuous at every
irrational point, and that f has a simple discontinuity at every rational point.
Proof. Let x ∈ R. For sufficiently small neighbourhoods of x, Nδ (x) contains no fractions of

the form m/n for some n < N . Thus, f (x k ) = 1/n < 1/N for x k sufficiently close to x. Thus,
every sequence converging to x has f (x) → 0. Thus, f is continuous at x iff f (x) = 0, iff x is
irrational. Otherwise, sequences from both sides converge to 0, so f has simple discontinuities at
the rationals.
19. Suppose f : R → R has the intermediate value property, and that f −1 ({r }) is closed for all r ∈ Q.
Prove that f is continuous.
Proof. First, we show that there cannot be any sequence {x n } converging to any x such that
f (x n ) > r > f (x) for some r ∈ Q and all n ∈ N, otherwise there exist tn between x n and x for
each n such that f (tn ) = r , and thus r > f (x) = r since f −1 ({r }) is closed, a contradiction. Thus,
if r < f (x) < s for r, s ∈ Q and {x n } is a sequence converging to x, there must only be finitely
many terms x nk not in (r, s), and thus f (x n ) → f (x), so f is continuous.
70
4 Continuity
20. If E is a non-empty subset of a metric space X , define the distance from x ∈ X to E by ρ E (x) =
inf z ∈E d(x, z).
a) Prove that ρ E (x) = 0 iff x ∈ E.
Proof. If x ∈ E, then either x ∈ E and the result is trivial, or x is a limit point of E and thus
there is a sequence {x n } which gets arbitrarily close to x. Conversely, if ρ E (x) = 0, then
there exists some sequence {x n } in E such that d(x, x n ) < 1/n for every n, so x n → x and
thus x ∈ E.
b) Prove that ρ E is a uniformly continuous function on X by showing that
|ρ E (x) − ρ E (y)| ≤ d(x, y), ∀x, y ∈ X
Proof. Suppose without loss of generality that ρ E (x) ≥ ρ E (y). Then, let {zn } ∈ E N such that
d(y, zn ) − ρ E (y) < 1/n for all n. Then,
∆
ρ E (x) ≤ d(x, zn ) ≤ d(x, y) + d(y, zn ) < d(x, y) + ρ E (y) + 1/n
for all n. Then, taking the limit as n → ∞, we have |ρ E (x) − ρ E (y)| = ρ E (x) − ρ E (y) ≤ d(x, y)
as required. Then ρ E is 1-Lipschitz and thus uniformly continuous.
21. Suppose K, F are disjoint sets in X , where K is compact and F is closed. Prove that there exists
δ > 0 such that d(p, q) > δ if p ∈ K and q ∈ F . Show that the conclusion may fail for two disjoint
closed sets if neither is compact.
Proof. For every x ∈ K, let G x be the open ball around x with radius ρ F (x)/2, so that each G x is
disjoint from F . Then {G x : x ∈ K } forms an open cover of K, so since K is compact, there exists a
finite set x 1, . . . , x n such that G x 1 ∪· · ·∪G x n ⊇ K. Then taking δ = min(ρ F (x 1 ), . . . , ρ F (x n ))/2 > 0,
the result follows.
To show that compactness is required for at least one of the sets, let X = {(x, y) : y ≤ −1/x, x ≥ 1}
and Y = {(x, y) : y ≥ 1/x, x ≥ 1} in R2 . Clearly both sets are closed and disjoint, but the points
(n, −1/n) ∈ X and (n, 1/n) ∈ Y get arbitrarily close as n → ∞.
22. Let A, B be disjoint non-empty closed sets in a metric space X , and define
ρ A (p)
f (p) = .
ρ A (p) + ρ B (p)
Show that f is a continuous function on X whose range lies in [0, 1], and that f (p) = 0 precisely
on A and f (p) = 1 precisely on B. This establishes a converse of Exercise 3: Every closed set
A ⊆ X is Z (f ) for some continuous real f on X . Setting
V = f −1 ([0, 1/2)) and W = f −1 ((1/2, 1]),
show that V ,W are open and disjoint, and that A ⊆ V , B ⊆ W , and thus that pairs of disjoint
closed sets in a metric space can be covered by pairs of disjoint open sets. This property of metric
spaces is called normality.
Proof. The fact that f is continuous stems from the fact that ρ E is uniformly continuous and thus
continuous, for any E, and the rules about combining continuous functions. It is also clear that
the range of f lies in [0, 1], and that f (p) = 0 precisely on A and f (p) = 1 precisely on B.
71
4 Continuity
Now define V and W as in the statement. Clearly V and W are disjoint, A ⊆ V and B ⊆ W . The
fact that V and W are open comes from the fact that f is continuous, and that the definitions can
be rewritten V = f −1 ((−1/2, 1/2)) and W = f −1 ((1/2, 3/2)) respectively as the inverse image of
an open set. Thus, metric spaces are normal.
23. A function f : (a, b) → R is convex iff
f (λx + (1 − λ)y) ≤ λ f (x) + (1 − λ)f (y)
for x, y ∈ (a, b) and λ ∈ (0, 1). Prove that every convex function is continuous. Prove that every
increasing convex function of a convex function is convex.
If f is convex in (a, b) and a < s < t < u < b, show that
f (t) − f (s) f (u) − f (s) f (u) − f (t)
≤ ≤ .
t −s u −s u −t
Proof. We begin by proving the inequality. Notice that we can write t = λs + (1 − λ)u for some
λ ∈ (0, 1). Then,
f (t) − f (s) f (λs + (1 − λ)s) − f (s) conv. λ f (s) + (1 − λ)f (u) − f (s) f (u) − f (s)
= ≤ = .
t −s λs + (1 − λ)u − s (1 − λ)(u − s) u −s
A similar argument can be used to show the second inequality. [ TODO ]
24. Let f : (a, b) → R be continuous such that

x + y f (x) + f (y)
f ≤ , ∀x, y ∈ (a, b).
2 2
Show that f is convex.
Proof. Let x, y ∈ (a, b) and λ ∈ (0, 1). Let

x +y
(a 0, z 0, b0 ) = (x, , y).
2
Then, define (an , zn , bn ) recursively: if λ ≥ zn−1 , take
zn−1 + bn−1

(an , zn , bn ) = zn−1, , bn−1 ,
2
otherwise, take an−1 + zn−1
(an , zn , bn ) = an−1, , zn−1 .
2
Then, zn → λx + (1 − λ)y. Also, it can be shown inductively that if zn = λn x + (1 − λn )y, then
f (zn ) ≤ λn f (x) + (1 − λn )f (y), so the result follows since f is continuous.
25. If A, B ⊆ Rk , define A + B = {x + y : x ∈ A, y ∈ B}.

a) If K is compact and C is closed in Rk , prove that K + C is closed.
Proof. Let zn = x n + yn → z in K + C, with x n ∈ K and yn ∈ C. By the Bolzano-Weierstrass

Theorem, (x n ) admits a convergent subsequence (x nk ) → x ∈ K, so ynk = znk − x nk is a
convergent sequence in C. Say ynk → y ∈ C. Then z = x + y ∈ K + C so K + C is closed.
b) Let α be irrational. Let C 1 = Z and C 2 = αZ. Show that C 1, C 2 are closed subsets of R whose
sum C 1 + C 2 is not closed, by showing that C 1 + C 2 is a countable dense subset of R.
72
4 Continuity
Proof. C 1 and C 2 are countable sets of isolated points and are thus closed sets in R. Also,
C 1 +C 2 is countable, as every element can be associated to a pair of integers (x, y) 7→ x + αy.
Notice that S = {x n := nα − bnαc : n ∈ Z} is an infinite subset of the compact set [0, 1].
Thus, Bolzano-Weierstrass shows the existence of a convergent sequence in S, and thus we
can find pairs (x i , x j ) arbitrarily close together, and thus |x i − x j | = |x i−j | < 1/n for any n.
Then, given any segment (a, b) with length at least 1/n, at least one multiple of x i−j must
exist inside the segment, so S = (C 1 + C 2 )/Z is dense in (0, 1) and thus the result.
26. Suppose X, Y , Z are metric spaces such that Y is compact. Let f : X → Y , and д : Y → Z be a
continuous bijection, and let h = д ◦ f .
Prove that f is uniformly continuous if h is uniformly continuous. Prove also that f is continuous
if h is continuous. Show, that the compactness of Y cannot be omitted from the hypotheses, even
when both X and Z are compact.
Proof. From Theorem 4.17, д−1 is a continuous function, and thus д(Y ) is compact. Then, д−1 is
continuous on a compact domain, and thus uniformly continuous. Then, f = д−1 ◦ h is uniformly
continuous by Exercise 4.12. Similarly, д−1 is continuous so f = д−1 ◦ h is continuous by Theorem
4.7.
Let X = [0, 2π ], Y = [0, 2π ), and Z = {x ∈ R2 : |x | = 1}, and notice that X and Z are compact.
Also, let f : X → Y with f (x) = π − x for x ∈ [0, π ] and f (x) = 3π − x on (π, 2π ). Clearly f is
discontinuous at π . Also, let д(t) = {cos t, sin t } be a continuous bijection from Y to Z . Then,
h = д ◦ f is a clockwise path from (0, 1) to (0, −1) along the unit circle, which is uniformly
continuous. However, f is discontinuous, as required.
73
5 Differentiation
5.1 The Derivative of a Real Function

Definition 40. Let f : [a, b] → R. Then for any x ∈ [a, b], define
f (t) − f (x)
ϕ(t) =
t −x
and
f (t) − f (x)
f 0(x) = lim ϕ(t) = lim.
t →x t →x t −x
given the limit exists. This f 0, whose domain is exactly the set of points x where the above limit exists, is
called the derivative of f .
If f 0 is defined at x, we say f is differentiable at x. If f is differentiable at every point of a set E ⊆ [a, b],
we say f is differentiable on E. Extending the above limit definition with left-hand and right-hand limits,
we get the left-hand and right-hand derivatives, respectively. Notice thus that f 0 is not defined on the
endpoints a nor b.
Theorem 86. Let f : [a, b] → R be differentiable at x ∈ (a, b). Then f is continuous at x.
Proof. As t → x, we have
f (t) − f (x)
f (t) − f (x) = · (t − x) → f 0(x) · 0 = 0.
t −x

Notice that the converse is not true: consider f (x) = |x | on [−1, 1].
Theorem 87. Suppose f , д are defined on [a, b] and differentiable at x ∈ [a, b]. Then f + д, f д, f /д are
differentiable at x, and
(a) (f + д)0(x) = f 0(x) + д 0(x);
(b) (f д)0(x) = f 0(x)д(x) + f (x)д 0(x);
f 0 (x )д(x )−f (x )д 0 (x )
(c) (f /д)0(x) = д 2 (x )
.
Proof. (a) follows from properties of limits. (b) follows from writing
(f д)(t) − (f д)(x) f (t)[д(t) − д(x)] + [f (t) − f (x)]д(x)

= → f (x)д 0(x) + f 0(x)д(x).
t −x t −x
Similarly, (c) follows from writing
1 f (t) − f (x) д(t) − д(x) f 0(x)д(x) − f (x)д 0(x)

(f /д)(t) − (f /д)(x)
д(x) − f (x) → .
= д(t)д(x) t −x t −x д2 (x)

74
5 Differentiation
It can be shown inductively that polynomials are differentiable, and that (x n )0 = nx n−1 . Also, 5.3(c)
shows that rational functions are differentiable, except at points where the denominator is zero.
Theorem 88. Suppose f : [a, b] → R is continuous on [a, b] and differentiable at x ∈ [a, b]. Also, suppose
д is defined on an interval I containing the range of f and differentiable at f (x). Then, (д ◦ f )0(x) =
д 0(f (x))f 0(x).
Proof. We have
h(t) − h(x) д(f (t)) − д(f (x)) д(f (t)) − д(f (x)) f (t) − f (x)
= = · → д 0(f (x))f 0(x)
t −x t −x f (t) − f (x) t −x
where the first term converges since f (t) → f (x) as f is continuous.
5.2 Mean Value Theorems

Definition 41. Let f be a real-valued function on a metric space X . We say f has a local maximum
at a point p ∈ X when there exists δ > 0 such that f (q) ≤ f (p) for all q ∈ Nδ (p). A local minimum is
defined similarly.
Theorem 89. Let f : [a, b] → R with a local maximum at x ∈ (a, b). If f 0(x) exists, then f 0(x) = 0.
Proof. Define f and x as above, and suppose f 0(x) exists. If f 0(x) = c > 0, then there must exist some
y > x sufficiently close (say, at most δ away) from x such that ϕ(y) > 0 but this implies f (y) > f (x), a
contradiction. The argument against f 0(x) < 0 is symmetric.
Theorem 90 (Cauchy’s MVT). If f , д are continuous real functions on [a, b] which are differentiable on
(a, b), then there is a point x ∈ (a, b) at which
[f (b) − f (a)]д 0(x) = [д(b) − д(a)]f 0(x).
Notice that differentiability is not required at the endpoints.
Proof. Let h(x) = [f (b) − f (a)]д(x) − [д(b) − д(a)]f (x). It suffices to show that h 0(x) = 0 for some
x ∈ (a, b). Notice that h(a) = h(b). If h is constant on [a, b], then h 0(x) = 0 everywhere. Otherwise, h
admits a local extremum, and thus has derivative 0 at that extremum, completing the proof.
Corollary 11 (Mean Value Theorem). If f : [a, b] → R is differentiable on (a, b), then
f (b) − f (a) = (b − a)f 0(x)
for some x ∈ (a, b).
Proof. Take д(x) = x.
Theorem 91. Suppose f is differentiable in (a, b).

(a) If f 0 ≥ 0 on (a, b), then f is monotonically non-decreasing.
(b) If f 0 = 0 on (a, b), then f is constant.
(c) If f 0 ≤ 0 on (a, b), then f is monotonically non-increasing.
Proof. For any pair a ≤ x < y ≤ b, there exists some z ∈ (x, y) such that f 0(z)(y − x) = f (y) − f (x), so
each result follows trivially.
75
5 Differentiation
5.3 The Continuity of Derivatives

We have seen that derivatives need not be continuous, but the following theorem states they still have
the intermediate value property:
Theorem 92 (Darboux property of derivatives). Suppose f : [a, b] → R is differentiable and f 0(a) <
λ < f 0(b). Then, there exists a point x ∈ (a, b) such that f 0(x) = λ.
Proof. Let h(t) = f (t) − λt, and notice that h 0(a) = f 0(a) − λ < 0 and similarly h 0(b) > 0. Then there
exist a < s < t < b such that h(s) < h(a) and h(t) < h(b). Then h is continuous on the compact interval
[s, t] and thus attains a minimum at u ∈ (s, t). Then h 0(u) = 0 so f 0(u) = λ as required.
Corollary 12. If f is differentiable on [a, b], then f 0 has no simple discontinuities on [a, b]. (Discontinuities
of the second kind as still possible)
5.4 L’Hopital’s Rule

Theorem 93 (L’Hopital’s Rule). Suppose f , д are real and differentiable in (a, b) and д 0(x) , 0 for all
x ∈ (a, b) with −∞ ≤ a < b ≤ +∞. Suppose f 0(x)/д 0(x) → A as x → a.
If f (x) → 0 and д(x) → 0 as x → a, OR д(x) → +∞ as x → a, then f (x)/д(x) → A as x → a.
Proof. If A < r < q < +∞, then we find c 2 such that f (x)/д(x) < q for all x ∈ (a, c 2 ). Repeating the
argument to find c 3 such that p < f (x)/д(x) for x ∈ (a, c 3 ) completes the argument.
Notice that since f 0(x)/д 0(x) → A, we can find c sufficiently close to a such that f 0(x)/д 0(x) < r for
x ∈ (a, c). Furthermore,
f (x) − f (y) f 0(t)
= 0 <r
д(x) − д(y) д (t)
for some t ∈ (x, y) ⊆ (a, c) if a < x < y < c. If f (x), д(x) → 0, then the previous expression becomes
f 0(t)/д 0(t) < r for all t ∈ (a, c). Otherwise, if д(x) → +∞, then we can find a < c 1 < y such that
д(x) > д(y) and д(x) > 0 whenever x ∈ (a, c 1 ). Multiplying the previous expression by [д(x)−д(y)]/д(x),
we obtain
f (x) д(y) f (y)
< r −r + , x ∈ (a, c 1 ).
д(x) д(x) д(x)
If we let x → a, then we can find c 2 such that f (x)/д(x) ≤ r < q whenever x ∈ (a, c 2 ), as required. This
completes the proof.
5.5 Derivatives of Higher Order

Definition 42. If f has a derivative f 0 on aninterval, and f 0 is itself differentiable, then we denote the
derivative of f 0 as f 00 and call f 00 the second derivative of f . Proceeding this way, we can define
f , f 0, f 00, f (3), . . . , f (n),
each of which is the derivative of the preceding one. f (n) is called the n-th derivative, or the derivative
of order n, of f .
76
5 Differentiation
5.6 Taylor’s Theorem

Theorem 94 (Taylor’s Theorem). Suppose f : [a, b] → R, n ∈ N, f n−1 is continuous on [a, b], f (n) exists
for every t ∈ (a, b). Let α, β be distinct points of [a, b] and define
n−1 (k )
f (α)
(t − α)k .
Õ
P(t) =
k!
k=0
Then there exists a point x between α and β such that
f (n) (x)
f (β) = P(β) + (β − α)n .
n!
Notice that n = 1 is the Mean Value Theorem, and in general that f can be approximated by a polynomial
of degree n − 1, and that we can estimate the error given we can bound | f (n) (x)|.
Proof. Let M ∈ R such that f (β) = P(β) + M(β − α)n , and take д(t) = f (t) − P(t) − M(t − α)n . Then,
since P(t) is a polynomial of degree n − 1 < n,
д(n) (t) = f (n) (t) − n!M.
But now д(α) = д 0(α) = · · · = д(n−1) (α) from the definition of д and P, and also д(β) = 0 by our definition
of M. Thus, by the Mean Value Theorem, д 0(x 1 ) = 0 for some x 1 ∈ (α, β). Similarly, д(i) (x i ) = 0 for some
x i ∈ (α, x i−1 ). Thus, д(n) (x n ) = 0 for some x n ∈ (α, x n−1 ) ⊆ (α, β), so in particular,
f (n) (x n )
M= ,
n!
as required.
5.7 Differentiation of Vector-Valued Functions

To extend our definition of differentiation to vector-valued functions, we write
f(t) − f(x)
f0(x) = lim ∈ Rk ,
t →x t −x
where the limit is taken with the norm in Rk .
If f 1, . . . , fk are the components of f, then f0 = (f 10, f 20, . . . , fk0), and f is differentiable at a point x iff
each component is differentiable at x.
Also,
(f · g)0(x) = f0(x) · g(x) + f(x) · g0(x).
ie. the product rule works with the multiplies replaced with dot products.
Notice that the mean value theorem no longer holds in general: consider f (x) = e ix , where f (0) = f (2π ),
but f 0(x) = ie ix , 0 for x ∈ R.
2
Also, L’Hopital’s rule fails: define f (x) = x and д(x) = x + x 2e i/x . Then limx →0 f (x)/д(x) = 1 but
limx →0 f 0(x)/д 0(x) = 0 , 1.
However, there is a consequence of the mean value theorem which is almost as useful as Theorem 5.10:
Theorem 95. Suppose f : [a, b] → Rk is continuous on [a, b] and differentiable in (a, b). Then, there
exists x ∈ (a, b) such that
|f(b) − f(a)| ≤ (b − a)|f0(x)|.
77
5 Differentiation
Proof. Let z = f(b) − f(a) and ϕ(t) = z · f(t). Then ϕ is continuous on [a, b] and differentiable on (a, b).
Then, the Mean Value Theorem tells us that
|z| 2 = ϕ(b) − ϕ(a) = (b − a)ϕ 0(x) = (b − a)z · f0(x),
for some x ∈ (a, b). Then Cauchy-Schwartz yields
|z| 2 = (b − a)|z · f’(x)| ≤ (b − a)|z||f0(x)|
and the result follows.
5.8 Exercises
1. Let f : R → R and | f (x) − f (y)| ≤ (x − y)2 for all x, y ∈ R. Prove that f is constant.
Proof. Let x ∈ R be arbitrary. Then, we can find a sequence of rational numbers pn /qn converging
to x such that (pn − 1)/qn ≤ x < pn /qn for each n. Without loss of generality (multiplying pn and qn
by some positive integer otherwise), suppose that qn is a strictly increasing sequence. However,
pn pn pn − 1 1

∆
| f (x) − f (0)| ≤ f (x) − f + f −f +···+ f − f (0)
qn qn qn qn
≤ 1/qn2 + 1/qn2 + . . . + 1/qn2
| {z }
pn times
1 pn 1 1 2 1 2

= + ≤ x+ ≤ x+ → 0.
qn qn qn qn qn n n
so taking the limit yields | f (x) − f (0)| = 0 so f is constant, as required.
2. Suppose f 0(x) > 0 in (a, b). Prove that f is strictly increasing in (a, b), and let д be its inverse
function. Prove that д is differentiable, and that
1
д 0(f (x)) = , x ∈ (a, b).
f 0 (x)
Proof. Take x < y in (a, b). Then, by the mean value theorem, there exists some z ∈ (x, y) such that
f (y) − f (x)
= f 0(z) > 0,
y −x
so f (y) > f (x), so f is strictly increasing. Thus, f is continuous and strictly increasing, so it has an
inverse д. Then д(f (x)) = x so applying the chain rule yields
1 = (д ◦ f )0(x) = д 0(f (x)) · f 0(x)
and thus the result.
3. Suppose д : R → R has bounded derivative, say |д 0 | ≤ M. Fix ϵ > 0 and define f (x) = x + ϵд(x).
Prove that f is one-to-one for sufficiently small ϵ.
Proof. If M = 0, this is trivial. Otherwise, choose ϵ < 1/M so that f 0(x) = 1 +ϵд 0(x) ≥ 1 +ϵ(−M) > 0,
and thus f is strictly increasing and thus one-to-one.
78
5 Differentiation
4. If
C1 Cn−1 Cn
C0 + +...+ + = 0,
2 n n+1
prove that the polynomial f (x) = ni=0 Ci x i has at least one real root between 0 and 1.
Í
Proof. Let
n
Õ Ci i+1
д(x) = x
i=0
i +1
and notice that д 0(x) = f (x). Then, the identity gives д(0) = д(1) = 0, so the result follows by the
mean value theorem.
5. Suppose f is defined and differentiable for every x > 0, and f 0(x) → 0 as x → +∞. Define
д(x) = f (x + 1) − f (x). Prove that д(x) → 0 as x → +∞.
Proof. Let x n such that | f 0(x)| ≤ 1/n for all x ≥ x n , since f 0(x) → 0. Then, by the mean value
theorem, we can find z ∈ (y, y + 1) ⊆ (x n , +∞) such that
f (y + 1) − f (y)
1/n ≥ | f 0(z)| = = |д(y)|
y + 1 −y
so |д(y)| ≤ 1/n for all y > x n , proving the result.
6. Suppose f is continuous for x ≥ 0 and differentiable for x > 0, f (0) = 0 and f 0 is monotonically
increasing. Put д(x) = f (x)/x for x > 0 and prove that д is monotonically increasing.
[ TODO ]
7. Suppose f 0(x), д 0(x) exist, д 0(x) , 0, and f (x) = д(x) = 0. Prove that
f (t) f 0(x)
lim = 0 .
t →x д(t) д (x)
[ TODO ]
8. Suppose f 0 is continuous on [a, b] and ϵ > 0. Prove that there exists δ > 0 such that
f (t) − f (x)
− f 0(x) < ϵ
t −x
whenever 0 < |t − x | < ϵ and x, t ∈ [a, b]. Does this hold for vector-valued functions too?
Proof. Notice that f 0 is continuous on a compact domain and thus uniformly continous. Then, we
can select δ > 0 such that | f 0(y) − f 0(x)| < ϵ whenever |x − y| < δ . Let x, t ∈ [a, b] such that
|t − x | < δ . Then, for some z between x and t, we have
f (t) − f (x)
− f 0(x) = | f 0(z) − f 0(z)| < ϵ
t −x
since z is between t and x and thus at most as close to x as t is, ie. δ away. This proves the result. If
f is vector-valued, applying the above result to each component and recombining iyields the result
for vector-valued functions.
9. Let f : R → R be continuous everywhere and differentiable for x , 0, and that f 0(x) → 3 as x → 0.

Does it follow that f 0(0) exists?
79
5 Differentiation
Proof. Yes, by L’Hopital’s, we have

f (x) − f (0)
f 0(0) = lim = lim f 0(x) = 3.
x →0 x −0 x →0
10. Suppose f , д are complex differentiable functions on (0, 1), and that f (x) → 0, д(x) → 0 f 0(x) → A
and д 0(x) → B as x → 0, where A, B ∈ C, and B , 0. Prove that
f (x) A
lim = .
x →0 д(x) B
Proof. From L’Hopital’s rule, we have

f (x)
lim = lim f 0(x) = A,
x →0 x x →0
and the similar statement with x/д(x) → 1/B, so
f (x) f (x) x x 1 1

= −A · +A· → 0· +A·
д(x) x д(x) д(x) B B
and thus we are done.
11. Suppose f is defined in a neighbourhood of x and f 00(x) exists. Show that

f (x + h) + f (x − h) − 2f (x)
lim = f 00(x).
h→0 h2
Proof. f is (twice) differentiable at x and thus continuous. Thus the numerator tends to 0 as h → 0.
Applying L’Hopital’s yields
f (x + h) + f (x − h) − 2f (x) f 0(x + h) + f 0(x − h) − 2f 0(x)
lim = lim
h→0 h2 h→0 2h
f 0(x + h) − f 0(x) f 0(x) − f 0(x − h)
= lim −
h→0 2h 2h
= f (x)
00
so we are done.
12. If f (x) = |x | 3 , compute f 0(x), f 00(x) for all real x and show that f (3) (0) does not exist.
Proof. If x > 0, then f (x) = x 3 in any sufficiently small neighbourhood of x, so f 0(x) = 3x 2, f 00(x) =
6x. If x < 0, then f (x) = −x 3 in any sufficiently small neighbourhood of x, so f 0(x) = −3x 2, f 00(x) =
−6x. At x = 0, we have
|h| 3 − 0
f 0(0) = lim = 0,
h→0 h
and
f 0(h) − f 0(0) ±3h 2
f 00(0) = lim ∼ lim = 0.
h→0 h h→0 h
Now, f (3) (0) does not exist, since the left-hand derivative of f 00 at 0 is −6 while the right-hand
derivative is 6.
13. Suppose a, c ∈ R c > 0 and f is defined on [−1, 1] such that f (x) = x a sin(|x | −c ) whenever x , 0 and
0 otherwise. Prove that:
80
5 Differentiation
(a) f is continuous iff a > 0.
Proof. This follows immediately from the fact that x a is continuous (specifically at x = 0) iff
a > 0.
(b) f 0(0) exists iff a > 1.
Proof. We have
ha sin(|h| −c )
f 0(0) = lim
h→0 h
which is 0 by the Squeeze theorem if a > 1. Otherwise, the limit does not exist.
(c) f 0 is bounded iff a ≥ 1 + c.
Proof. If x > 0, then
| f 0(x)| = |ax a−1 sin(x −c ) + x a cos(x −c ) · −cx −c−1 | ≤ a|x | a−1 + c |x | a−c−1
which is bounded iff a ≥ 1 + c.
(d) f 0 is continuous iff a > 1 + c.
Proof. From the above formulation of f 0, the derivative is continuous at 0 iff a − c − 1 > 0, so
a > 1 + c as required.
(e) f 00(0) exists iff a > 2 + c.
Proof. We have
f 00(0) = lim [aha−2 sin(h −c ) − cha−c−2 cos(h −c )]
h→0
which exists iff a − c − 2 > 0, so a > 2 + c.
(f) f 00 is bounded iff a ≥ 2 + 2c.
Proof. Bash the product rule and find the largest term.
(g) f 00 is continuous iff a > 2 + 2c.
Proof. See above.
14. Let f be differentiable on (a, b). Prove that f is convex iff f 0 is monotonically increasing. Assume
next that f 00(x) exists for every x ∈ (a, b), and prove that f is convex iff f 00(x) ≥ 0 for all x ∈ (a, b).
Proof. If f 0 is not monotonically increasing, there exist points x, y ∈ (a, b) such that x < y and
f 0(x) > f 0(y). Then, for some δ > 0 sufficiently small, f (x + δ ) is above the secant formed between
(x, f (x)) and (y, f (y)). Conversely, if f 0 is monotonically increasing, but not convex, then for some
x, y ∈ (a, b), there exists z = λx + (1 − λ)y such that f (z) > λ f (x) + (1 − λ)f (y). Then applying the
mean value theorem to the intervals (x, z) and (z, y) yields w 1 < w 2 such that f 0(w 1 ) > f 0(w 2 ), a
contradiction, proving the first result.
We know that if f 00(x) ≥ 0, then f 0 is strictly increasing and thus f is convex. Conversely, if
f 00(x) < 0, then for δ > 0 sufficiently small, we have
1
f (x) ≥ (f (x − δ ) + f (x + δ ))
2
81
5 Differentiation
so f is not convex, as required.
15. Suppose a ∈ R and f : (a, +∞) is twice-differentiable, and M 0, M 1, M 2 are the least upper bounds of
| f (x)|, | f 0(x)|, | f 00(x)| respectively on (a, +∞). Prove that M 12 ≤ 4M 0 M 2 .
Proof. If h > 0, setting (α, β, n) = (x, x +2h, 2) in Taylor’s theorem shows that for some ξ ∈ (x, x +2h),
(2h)2 00
f (x + 2h) = f (x) + 2h f 0(x) + f (ξ )
2!
and thus
1
f 0(x) = [f (x + 2h) − f (x)] − h f 00(ξ )
2h
so
1
| f 0(x)| ≤ M 1 ≤M 0 + hM 2 .
h
Now the right side attains its minimum by AM-GM at
1 1
r
p
M 0 + hM 2 ≥ 2 M 0 · hM 2 = 2 M 0 M 2,
h h
√
so M 1 ≤ 2 M 0 M 2 and the result follows.
16. Suppose f is twice-differentiable on (0, ∞), f 00 is bounded on (0, ∞) and f (x) → 0 as x → ∞. Prove
that f 0(x) → 0 as x → ∞.
Proof. Let M 2 be the least upper bound of f 00 and ϵ > 0 be arbitrary. Then, since f (x) → 0 as x → ∞,
we can choose x 0 such that | f (x)| ≤ ϵ 2 /(4M 2 ) for all x ≥ x 0 . Then taking a = x 0 in Exercise 15, we
have p
f 0(x) ≤ sup | f 0(x)| ≤ 2 M 0 M 2 < 2 ϵ 2 /4 = ϵ,
p
x ≥x 0
for all x ≥ x 0 as required.
17. Suppose f is real and thrice-differentiable on [−1, 1], such that f (−1) = 0, f (0) = 0, f (1) = 1 and
f 0(0) = 0. Prove that f (3) (x) ≥ 3 for some x ∈ (−1, 1).
Proof. Applying Taylor’s theorem, we have

1 1
f (1) = f (0) + f 0(0) · 1 + f 00(0) · 12 + f (3) (t) · 13
2 6
for some t ∈ (0, 1) and
1 1
f (−1) = f (0) + f 0(0) · (−1) + f 00(0) · (−1)2 + f (3) (s) · (−1)3
2 6
for some s ∈ (−1, 0) so adding these, substituting known values, and rearranging yields f (3) (s) +
f (3) (t) = 6 for some s, t, yielding the result.
18. Suppose f is a real function on [a, b], n is a positive integer, and f (n−1) exists for every t ∈ [a, b]. Let
α, β, P be as in Taylor’s theorem. Define
f (t) − f (β)
Q(t) =
t −β
for t ∈ [a, b] and t , β, differentiate n − 1 times at t = α and derive the following version of Taylor’s
theorem:
Q (n−1) (α)
f (β) = P(β) + (β − α)n .
(n − 1)!
82
5 Differentiation
Proof. Take f (t) − f (β) = (t − β)Q(t) and differentiate at α to get
f (k) (α) = kQ (k −1) (α) − (β − α)Q (k ) (α),
so
f (k) (α) Q (k−1) (α) Q (k) (α)
(β − α)k = (β − α)k − (β − α)k+1 .
k! (k − 1)! k!
Then,
n−1 (k)
f (α)
(β − α)k
Õ
P(α) = f (α) +
k!
k=1
n−1 (k −1)
Q Q (k ) (α)

Õ (α) k k+1
= f (α) + (β − α) − (β − α)
(k − 1)! k!
k=1
Q (n−1) (α)
= f (α) + Q(α)(β − α) − (β − α)n
(n − 1)!
Q (n−1) (α)
= f (β) − (β − α)n ,
(n − 1)!
and thus the result.
19. Suppose f is defined in (−1, 1) and f 0(0) exists. Suppose −1 < α n < βn < 1, with α n → 0, βn → 0 as
n → ∞. Define the difference quotients
f (βn ) − f (α n )
Dn = .
βn − α n
Prove the following statements:

a) If α n < 0 < βn , then D n → f 0(0).
Proof. Suppose without loss of generality that f (0) = 0, by subtracting any necessary constants.
f (β )−f (α )
Then, let γn ∈ (α n , βn ) by the mean value theorem such that f 0(γn ) = βnn −α n n . Then, γn → 0,
so applying L’Hopital’s rule,
f (γn ) − f (0)
lim D n = lim f 0(γn ) = lim = f 0(0),
n→∞ n→∞ n→∞ γn − 0
as required.
b) If 0 < α n < βn and {βn /(βn − α n )} is bounded, then D n → f 0(0).
Proof. Let ϵ > 0 be arbitrary and λn = βn /(βn − α n ). Also, let M such that |λn | ≤ M for all n,
so that
f (βn ) − f (α n )
Dn =
βn − α n
f (βn ) − f (0) + f (0) − f (α n )
=
βn − α n
βn f (βn ) − f (0) αn f (α n ) − f (0)
= · − ·
βn − α n βn − 0 βn − α n αn − 0
f (βn ) − f (0) f (α n ) − f (0)
= λn + (1 − λn )
βn − 0 αn − 0
83
5 Differentiation
so choosing N sufficiently large and letting n ≥ N , we have
f (βn ) − f (0) f (α n ) − f (0)

|D n − f 0(0)| ≤ λn + (1 − λn ) − f 0(0)
βn − 0 αn − 0
∆ f (βn ) − f (0) f (α n ) − f (0)
≤ λn − f 0(0) + |1 + λn | · − f 0(0)
βn αn
≤ (1 + 2M)ϵ
c) If f 0 is continuous in (−1, 1), then D n → f 0(0).
Proof. Constructing γn as in part (a), we have
lim D n = lim f 0(γn ) = f 0(0),

n→∞ n→∞
since f 0 is continuous, as required.
Give an example in which f is differentiable in (−1, 1) (but f 0 is not continous at 0), and in which
α n , βn tend to 0 in a way that lim D n exists but is different from f 0(0).
[ TODO ]
20. Formulate and prove an inequality which follows from Taylor’s theorem and which remains valid
for vector-valued functions.
Proof. If f : [a, b] → Rm is n-times differentiable and f(n−1) is continuous on [a, b], and α < a < b < β
and
n−1 (k)
f (α)
(t − α)k ,
Õ
P(t) =
k!
k=0
then there exists x ∈ (α, β) such that
(β − α)n (n)
|f(β) − P(β)| ≤ |f (x)|
n!
and notice that if n = 1, this is the vector-valued version of Theorem 5.19.
[ TODO ]
21. Let E be a closed subset of R. We saw in Exercise 4.22 that there is a real continuous function f on R
whose zero set is E. Is it possible, for each closed set E to find such an f which is differentiable on R,
or one which is n times differentiable, or even one which has derivatives of all orders on R?
Proof. Take n ∈ N. Then, define
tn
fn (t) = , д(x) = f (ρ E (x)),
t n + (1 − t)n
for x ∈ R. Then, д(x) = 0 iff x ∈ E, and since fn has the property that its first n − 1 derivatives are 0
at t = 0 and 1, д is n-times differentiable on E and thus on R.
For the infiitely differentiable case, it is possible to define a similar function. This depends largely on
the fact that R is separable.
22. Suppose f is a real function on R. Call x a fixed point of f is f (x) = x.
84
5 Differentiation
(a) If f is differentiable and f 0(t) , 1 for every real t, prove that f has at most one fixed point.
Proof. If there were more than one, then applying mean value theorem with the fixed points
as endpoints would give you some point between them with derivative 1, contrary to the
assumption.
(b) Show that the function f defined by
f (t) = t + (1 + e t )−1
has no fixed point, although 0 < f 0(t) < 1 for all t ∈ R.
Proof. Clearly f has no fixed points. However,
f 0(t) = 1 − (1 + e t )−2 · e t ∈ (0, 1)
since x/(1 + x 2 ) ∈ (0, 1) for all x > 0.
(c) However, if there is a constant A < 1 such that | f 0(t)| ≤ A for all t ∈ R, then prove that a fixed
point x of f exists, and that x = lim x n where x 1 is an arbitrary real number, and x n+1 = f (x n ).
Proof. Yes, let C = | f (x 1 ) − x 1 |, so that for arbitrary n, we have some tn between x n and x n+1 by
the mean value theorem such that
| f (x n+1 − f (x n )|
= f 0(tn ) ≤ A,
|x n+1 − x n |
so inductively,
|x n+1 − x n | ≤ An−1C,
so for m and n sufficiently large
m−1 ∞
∆
Ak−1 = CAk−1 /(1 − A),
Õ Õ
|xm − x n | ≤ |x k +1 − x k | ≤ C
k=n k =n
which can be made arbitrarily small. Thus, {x n } is Cauchy in R and thus convergent since R is
complete.
Then, we have
x := lim x n = lim f (x n−1 ) = f (x)
n→∞ n→∞
since f is differentiable and thus continuous, so x = lim x n is a fixed point of f .
(d) Show that the process described in (c) can be visualized by the zig-zag path
(x 1, x 2 ) → (x 2, x 2 ) → (x 2, x 3 ) → (x 3, x 3 ) → · · · .
Proof. It just can, draw it!
23. The function f (x) = (x 3 + 1)/3 has three fixed points
−2 < α < −1, 0 < β < 1 < γ < 2.
For arbitrary chosen x 1 , define {x n } by setting x n+1 = f (x n ).

(a) If x 1 < α, prove that x n → −∞ as n → ∞.
85
5 Differentiation
Proof. We can find inductively that x n < x n−1 < . . . < x 1 < α. It cannot converge, as then the
limit would tend to a fixed point of f , but it is strictly smaller than any of the three. Thus it must
diverge to −∞.
(b) If α < x 1 < γ , prove that x n → β as n → ∞.
Proof. We can find that x n approaches β monotonically, but is bounded by β, and thus converges.
The limit point must be a fixed point of f , and only β fits, completing the proof.
(c) If γ < x 1 , prove that x n → +∞ as n → ∞.
Proof. The proof is similar to part (a).
Thus only β can be located using this method.

24. The process described in part (c) of Exercise 22 can of course also be applied to functions that map
(0, ∞) to (0, ∞). Fix some α > 1 and put
1 α +x
f (x) = (x + α/x) , д(x) = .
2 1+x
√
Both f and д have α as their only fixed point in (0, ∞). Try to explain, on the basis of properties of
f and д why the convergence in Exercise 3.16 is so much more rapid than it is in Exercise 17. Do the
same when 0 < α < 1.
Proof. Consider the derivatives of f and д at their fixed point. We have

1 √
f 0(x) = (1 − α/x 2 ), f 0( α) = 0
2
and √
1−α 0 √ 1+ α
д (x) =
0
, д ( α) = √ <0
(1 + x)2 1− α
√
so intuitively, for x n sufficiently close to α, the horizontal lines for f in the zigzag path take the x n
√
much closer to y = α than the corresponding paths in д.
25. Suppose f is twice-differentiable on [a, b], f (a) < 0, f (b) > 0, f 0(x) ≥ δ > 0, and 0 ≤ f 00(x) ≤ M
for all x ∈ [a, b]. Let ξ be the unique point in (a, b) at which f (ξ ) = 0.
Complete the details in the following outline of Newton’s method for computing ξ .
(a) Choose x 1 ∈ (ξ , b) and define {x n } by x n+1 = x n − f (x n )/f 0(x n ). Interpret this geometrically, in
terms of a tangent to the graph of f .
Proof. x n+1 is the x-coordinate of the point at which the tangent of f at (x n , f (x n )) intersects
the x-axis.
(b) Prove that x n+1 < x n and that x n → ξ .
Proof. We claim inductively that ξ ≤ x n+1 < x n . If x n+1 < ξ , then choosing the point t ∈ (ξ , x n )
such that
f (x n ) − f (ξ )
f 0(t) = > f 0(x n ),
xn − ξ
contradicting the fact that f 0 is increasing. Also, since ξ ≤ x n inductively, f (x n ) > 0 so
f (x n )/f 0(x n ) > 0, proving the first result.
86
5 Differentiation
Then, the sequence converges by the monotone convergence theorem. If the sequence converged
to y > ξ , then f 0(y) > 0 would imply a contradiction. Thus, we must have x n → ξ .
(c) Use Taylor’s theorem to show that
f 00(tn )
x n+1 − ξ = (x n − ξ )2,
2f 0(x n )
for some t ∈ (ξ , x n ).
(d) If A = M/2δ , deduce that
n
0 ≤ x n+1 − ξ ≤ 1/A[A(x 1 − ξ )]2 .
(e) Show that Newton’s method amounts to finding a fixed point of the function д(x) = x −f (x)/f 0(x).
How does д 0(x) behave for x near ξ ?
(f) Put f (x) = x 1/3 on R and try Newton’s method. What happens?
26. Suppose f is differentiable on [a, b], f (a) = 0, and there is a real number A such that | f 0(x)| ≤ A| f (x)|
on [a, b]. Prove that f (x) = 0 for all x ∈ [a, b].
27. Let ϕ be a real function defined on a rectangle R on the plane, given by a ≤ x ≤ b, α ≤ y ≤ β. A
solution of the initial-value problem
f 0 = ϕ(x, y), y(a) = c, (α ≤ c ≤ β)
is, by definition, a differentiable function f on [a, b] such that f (a) = c, for c ∈ [α, β], and f 0(x) =
ϕ(x, f (x)) for x ∈ [a, b].
Prove that such a problem has at most one solution if there is a constant A such that
|ϕ(x, y2 ) − ϕ(x, y1 )| ≤ A|y2 − y1 |
whenever (x, y1 ) and (x, y2 ) are both in R.

28. Formulate and prove an analogous uniqueness theorem for systems of differential equations of the
form
y j0 = ϕ j (x, y!, y2, . . . , yk ), y j (a) = c j , j ∈ [k].
Note that this can be rewritten y0 = Φ(x, y), y(a) = c, where y ranges over a k-cell, and Φ is a
mapping of a (k + 1)-cell into Rk whose components are the functions ϕ i and c = (c 1, . . . , c k ).
29. Specialize Exercise 28 by considering the system
k
Õ
y j0 = y j+1, j ∈ [k − 1], yk0 = f (x) − дj (x)y j ,
j=1
where f , д1, . . . , дk are continuous real functions on [a, b] and derive a uniqueness theorem for
solutions of the equation
y (k) + дk (x)y k −1 + . . . + д2 (x)y 0 + д1 (x)y = f (x),
subject to the initial conditions
y(a) = c 1, y 0(a) = c 2, . . . , y (k−1) (a) = c k .
87
6 TODOs
1. Finish the proof for multiplicative inverses in Appendix 1

2. Exercise 1.20
3. Exercise 2.11
4. Exercise 3.7 has a weird ≤ vs. < problem. See if you can spot it.
5. Exercise 3.17d
6. Fix the theorem/example/etc. numbers so they match with Rudin
7. Exercise 4.6
8. Exercise 4.23
9. Exercise 5.6
88

Notes Baby Rudin

Uploaded by

Copyright:

Available Formats

Notes Baby Rudin

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Notes Baby Rudin

Uploaded by

Copyright:

Available Formats

Baby Rudin

August 17, 2019

1 The Real and Complex Number Systems 4

3 Numerical Sequences and Series 38

1.1 Ordered Sets

1. If x > 0, then −x < 0.

1.3 The Real Field

Proof. This proof is presented in the Appendix.

Theorem 3. From here, we can derive the following properties in R:

so (α + t)n < x, contradicting the fact that α is an upper bound for A.

1.4 The Extended Real Number System

1.5 The Complex Field

(a, b) + (c, d) = (a + c, b + d), (a, b) × (c, d) = (ac − bd, ad + bc).

Proof. For all of these, we will suppose z = a + bi and w = c + di.

z + w = (a + c) − (b + d)i = (a − bi) + (c − di) = z + w.

z · w = (a − bi) · (c − di) = (ac − bd) − (ad + bc)i = zw.

For (c), notice that z + z = 2a = 2<(z) and z − z = 2bi = 2i=(z).

|z + w | 2 = (z + w)(z + w) = zz + ww + zw + wz = |z| 2 + |w | 2 + (zw) + (zw).

From Theorems 4(c) and 5(d), we have

(zw) + (zw) = 2<(zw) ≤ |2<(zw)| ≤ 2|z||w |.

Combining these yields

|z + w | 2 = |z| 2 + |w | 2 + (zw) + (zw) ≤ |z| 2 + |w | 2 + 2|z||w | = (|z| + |w |)2 .

Finally, we present a classic inequality, the Cauchy-Schwartz inequality:

Proof. Let A = |a j | 2, B = |b j | 2 ∈ R and C = a j b j , so we claim |C | 2 ≤ AB. If B = 0, then we must

and since B > 0, we must have AB − |C | 2 ≥ 0, as required.

1.6 Euclidean Spaces

and the norm of x by

and the result follows by taking the square root.

1.7 Appendix: Dedekind’s construction of R

Let α, β > 0∗ be arbitrary.

{rs : r ∈ α, s ∈ β, r, s > 0} = {sr : s ∈ β, r ∈ α, s, r > 0}.

(M3) (α β)γ = α(βγ ).

Step 7. Multiplication, for real

2. Prove that there is no rational number whose square is 12.

(d) If x , 0 then 1/(1/x) = x.

Proof. Let x = (b m )1/n and y = (b p )1/q . Now, notice that x nq = (x n )q = (b m )q = b mq and

(b r +s )nq = (b (mq+np)/nq )nq = b mq+np = b mq b np = b r nq b snq = (b r b s )nq

1 < b m/n ⇐⇒ 1n = 1 < b m ⇐⇒ 1 < b

so b q > 1 as required. It follows that if r ≤ t, then b r ≤ b t : simply consider b t − b r =

(d) Prove b x +y = b x b y for all x, y ∈ R.

(b) Hence b − 1 ≥ n(b 1/n − 1).

(c) If t > 1 and n > (b − 1)/(t − 1), then b 1/n < t.

(e) If b w > y, then b w −1/n > y for sufficiently large n.

(g) Prove that this x is unique.

10. Suppose z = a + bi, w = u + vi, and

Proof. Notice that (a + bi)2 = (a 2 − b 2 ) + i(2ab), so

12. If z 1, . . . , zn are complex, prove that

|z 1 + z 2 + · · · + zn−1 + zn | ≤ |z 1 + z 2 + · · · + zn−1 | + |zn |

completing the induction.

13. If x, y ∈ C, prove that

Proof. Notice |x | = |(y − x) − y| ≤ |y − x | + |y| so |x − y| = |y − x | ≥ |x | − |y|.

14. If z ∈ C such that |z| = 1, compute

Proof. Simply write

16. Suppose k ≥ 3, x, y ∈ Rk , |x − y| = d > 0, and r > 0. Prove:

(b) If 2r = d, there is exactly one such z.

Proof. If such a z existed, then d = |x − y| ≤ |x − z| + |z − y| = 2r = d, so equality must hold

(c) If 2r < d, there are no such z.

Proof. If such a z existed, then d = |x − y| ≤ |x − z| + |z − y| = 2r < d, a contradiction.

How must these statements be modified if k < 3?

17. Prove that