Solutions to Principles of Mathematical Analysis (Walter Rudin)
Jason Rosendale
jason.rosendale@gmail.com
December 19, 2011
This work was done as an undergraduate student: if you really don’t understand something in one of these
proofs, it is very possible that it doesn’t make sense because it’s wrong. Any questions or corrections can be
directed to jason.rosendale@gmail.com.
Exercise 1.1a
Let r be a nonzero rational number. We’re asked to show that x ∈ Q implies that (r + x) ∈ Q. Proof of the
contrapositive:
→ r + x is rational
→ (∃p ∈ Q)(r + x = p)
→ (∃p, q ∈ Q)(q + x = p)
→ (∃p, q ∈ Q)(x = −q + p)
assumed
definition of rational
we’re told that r is rational
existence of additive inverses in Q
Because p and q are members of the closed additive group of Q, we know that their sum is a
member of Q.
→ (∃u ∈ Q)(x = u)
→ x is rational
definition of rational
By assuming that r +x is rational, we prove that x must be rational. By contrapositive, then, if x is irrational
then r + x is irrational, which is what we were asked to prove.
Exercise 1.1b
Let r be a nonzero rational number. We’re asked to show that x ∈ Q implies that rx ∈ Q. Proof of the
contrapositive:
→ rx is rational
→ (∃p ∈ Q)(rx = p)
→ (∃p ∈ Q)(x = r−1p)
assumed
definition of rational
existence of multiplicative inverses in Q
(Note that we can assume that r−1 exists only because we are told that r is nonzero.) Because r−1
and p are members of the closed multiplicative group of Q, we know that their product is also a
member of Q.
→ (∃u ∈ Q)(x = u)
→ x is rational
definition of rational
By assuming that rx is rational, we prove that x must be rational. By contrapositive, then, if x is irrational
then rx is irrational, which is what we were asked to prove.
1
Exercise 1.2
√
Proof by contradiction. If
p/q where p and q are nonzero integers with no common divisors.
12 were rational, then we could write it as a reduced-form fraction in the form of
√
12
→ p
q =
→ ( p2
q2 = 12)
→ (p2 = 12q2)
assumed
It’s clear that 3|12q2, which means that 3|p2. By some theorem I can’t remember (possibly the
definition of ‘prime’ itself), if a is a prime number and a|mn, then a|m ∨ a|n. Therefore, since 3|pp
and 3 is prime,
→ 3|p
→ 9|p2
→ (∃m ∈ N)(p2 = 9m)
→ (∃m ∈ N)(12q2 = 9m)
→ (∃m ∈ N)(4q2 = 3m)
→ (3|4q2)
definition of divisibility
substitution from p2 = 12q2
divide both sides by 3
definition of divisibility
From the same property of prime divisors that we used previously, we know that 3|4 ∨ 3|q2:
clearly doesn’t divide 4, so it must be the case that 3|q2. But if 3|qq, then 3|q ∨ 3|q. Therefore:
it
→ (3|q)
And this establishes a contradiction. We began by assuming that p and q had no common divisors, but we
have shown that 3|p and 3|q. So our assumption must be wrong: there is no reduced-form rational number such
that p
√
12.
q =
Exercise 1.3 a
If x = 0 and xy = xz, then
y = 1y = (x−1x)y = x−1(xy) = x−1(xz) = (x−1x)z = 1z = z
Exercise 1.3 b
If x = 0 and xy = x, then
Exercise 1.3 c
If x = 0 and xy = 1, then
y = 1y = (x−1x)y = x−1(xy) = x−1x = 1
y = 1y = (x−1x)y = x−1(xy) = x−11 = x−1 = 1/x
Exercise 1.3 d
If x = 0, then the fact that x−1x =1 means that x is the inverse of x−1: that is, x = (x−1)−1 = 1/(1/x).
Exercise 1.4
We are told that E is nonempty, so there exists some e ∈ E. By the definition of lower bound, (∀x ∈ E)(α ≤ x):
so α ≤ e. By the definition of upper bound, (∀x ∈ E)(x ≤ β): so e ≤ β. Together, these two inequalities tell us
that α ≤ e ≤ β. We’re told that S is ordered, so by the transitivity of order relations this implies α ≤ β.
2
Exercise 1.5
We’re told that A is bounded below. The field of real numbers has the greatest lower bound property, so we’re
guaranteed to have a greatest lower bound for A. Let β be this greatest lower bound. To prove that −β is
the least upper bound of −A, we must first show that it’s an upper bound. Let −x be an arbitrary element in −A:
definition of membership in −A
β = inf(A)
→ −x ∈ −A assumed
→ x ∈ A
→ β ≤ x
→ −β ≥ −x
We began with an arbitrary choice of −x, so this proves that (∀ − x ∈ −A)(−β ≥ −x), which by definition
tells us that −β is an upper bound for −A. To show that −β is the least such upper bound for −A, we choose
some arbitrary element less than −β:
consequence of 1.18(a)
→ α < −β
→ −α > β
assumed
consequence of 1.18(a)
Remember that β is the greatest lower bound of A. If −α is larger than inf(A), there must be some
element of A that is smaller than −α.
(see above)
→ (∃x ∈ A)(x < −α)
→ (∃ − x ∈ −A)(−x > α)
→ !(∀ − x ∈ −A)(−x ≤ α)
→ α is not an upper bound of −A definition of upper bound
This proves that any element less than −β is not an upper bound of −A. Together with the earlier proof
consequence of 1.18(a)
that −β is an upper bound of −A, this proves that −β is the least upper bound of −A.
Exercise 1.6a
The difficult part of this proof is deciding which, if any, of the familiar properties of exponents are considered
axioms and which properties we need to prove. It seems impossible to make any progress on this proof unless we
can assume that (bm)n = bmn. On the other hand, it seems clear that we can’t simply assume that (bm) 1
n = bm/n:
this would make the proof trivial (and is essentially assuming what we’re trying to prove).
As I understand this problem, we have defined xn in such a way that it is trivial to prove that (xa)b = xab
when a and b are integers. And we’ve declared in theorem 1.21 that, by definition, the symbol x 1
n is the element
such that (xn) 1
n = x. But we haven’t defined exactly what it might mean to combine an integer power like n
and some arbitrary inverse like 1/r. We are asked to prove that these two elements do, in fact, combine in the
way we would expect them to: (xn)1/r = xn/r.
Unless otherwise noted, every step of the following proof is justified by theorem 1.21.
3
→ bm = bm
→ ((bm) 1
→ ((bm) 1
n )n = bm
n )nq = bmq
assumed
definition of x 1
n
We were told that m
mq = np. Therefore:
n = p
q which, by the definition of the equality of rational numbers, means that
→ ((bm) 1
→ ((bm) 1
n )nq = bnp
n )qn = bpn
commutativity of multiplication
From theorem 12.1, we can take the n root of each side to get:
→ ((bm) 1
n )q = bp
From theorem 12.1, we can take the q root of each side to get:
→ (bm) 1
n = (bp)
1
q
Exercise 1.6b
As in the last proof, we assume that br+s = brbs when r and s are integers and try to prove that the operation
q where m, n, p, q ∈ Z and
works in a similar way when r and s are rational numbers. Let r = m
n, q = 0.
n and let s = p
m
q
1
nq
1
nq
nq
mq+pn
n + p
→ br+s = b
→ br+s = b
→ br+s = (bmq+pn)
→ br+s = (bmqbpn)
→ br+s = (bmq)
→ br+s = (b
pn
mq
nq )
nq )(b
→ br+s = (b m
p
n )(b
q )
→ br+s = (br)(bs)
definition of addition for rationals
from part a
legal because mq and pn are integers
1
nq
corollary of 1.21
from part a
1
nq (bpn)
Exercise 1.6c
We’re given that b > 1. Let r be a rational number. Proof by contradiction that br is an upper bound of B(r):
→ br is not an upper bound of B(r)
→ (∃x ∈ B(r))(x > br)
hypothesis of contradiction
formalization of the hypothesis
By the definition of membership in B(r), x = bt where t is rational and t ≤ r.
→ (∃t ∈ Q)(bt > br ∧ t ≤ r)
It can be shown that b−t > 0 (see theorem S1, below) so we can multiply this term against both
sides of the inequality.
→ (∃t ∈ Q)(btb−t > brb−t ∧ t ≤ r)
→ (∃t ∈ Q)(bt−t > br−t ∧ t ≤ r)
→ (∃t ∈ Q)(1 > br−t ∧ r − t ≥ 0)
→ (∃t ∈ Q)(1−(r−t) > b ∧ r − t ≥ 0)
→ 1 > b
theorem S2
from part b
And this establishes our contradiction, since we were given that b > 1. Our initial assumption must have
been incorrect: br is, in fact, an upper bound of B(r). We must still prove that it is the least upper bound of
B(r), though. To do so, let α represent an arbitrary rational number such that bα < br. From this, we need to
4
prove that α < r.
→ bα < br
→ bαb−r < brb−r
→ bα−r < br−r
→ bα−r < 1
hypothesis of contradiction
theorem S2
from part b
from part b
Exercise 1.7 a
Proof by induction. Let S = {n : bn − 1 ≥ n(b − 1)}. We can easily verify that 1 ∈ S. Now, assume that k ∈ S:
hypothesis of induction
definition of membership in S
we’re told that b > 1.
→ k ∈ S
→ bk − 1 ≥ k(b − 1)
→ bbk − 1 ≥ k(b − 1)
→ bk+1 − b ≥ k(b − 1)
→ bk+1 ≥ k(b − 1) + b
→ bk+1 − 1 ≥ k(b − 1) + b − 1
→ bk+1 − 1 ≥ (k + 1)(b − 1)
→ k + 1 ∈ S
By induction, this proves that (∀n ∈ N)(bn − 1 ≥ n(b − 1)).
definition of membership in S
Alternatively, we could prove this using the same identity that Rudin used in the proof of 1.21. From the
distributive property we can verify that bn − an = (b − a)(bn−1a0 + bn−2a1 + . . . + b0an−1). So when a = 1, this
becomes bn − 1 = (b − 1)(bn−1 + bn−2 + . . . + b0). And since b > 1, each term in the bn−k series is greater than
1, so bn − 1 ≥ (b − 1)(1n−1 + 1n−2 + . . . + 10) = (b − 1)n.
Exercise 1.7 b
→ n(b 1
→ n(b 1
n − 1) = n(b 1
n − 1) = (1 + 1 + . . . + 1)
n − 1)
n times
n − 1)
(b 1
→ n(b 1
n − 1) = (1n−1 + 1n−2 + . . . + 10)(b 1
n − 1)
It can be shown that bk > 1 when b > 1, k > 0 (see theorem S4). Replacing 1 with b 1
inequality:
n gives us the
→ n(b 1
n − 1) ≤ ((b 1
n )n−1 + (b 1
n )n−2 + . . . + (b 1
n )0)(b 1
n − 1)
Now we can use the algebraic identity bn − an = (bn−1a0 + bn−2a1 + . . . + b0an−1)(b − a):
→ n(b 1
→ n(b 1
n − 1) ≤ ((b 1
n − 1) ≤ (b − 1)
n )n − 1)
Exercise 1.7 c
→ n > (b − 1)/(t − 1)
→ n(t − 1) > (b − 1)
→ n(t − 1) > (b − 1) ≥ n(b 1
→ n(t − 1) > n(b 1
→ (t − 1) > (b 1
→ t > b 1
n − 1)
n − 1)
n
n − 1)
assumed
this holds because n, t, and b are greater than 1
from part b
transitivity of order relations
n > 0 → n−1 > 0 would be a trivial proof
5
Exercise 1.7 d
We’re told that bw < y, which means that 1 < yb−w. Using the substitution yb−w = t with part (c), we’re lead
directly to the conclusion that we can select n such that yb−w > b 1
n , which is what
we were asked to prove. As a corollary, the fact that b 1
n . From this we get y > bw+ 1
n > 1 means that bw+ 1
n > bw.
Exercise 1.7 e
We’re told that bw > y, which means that bwy−1 > 1. Using the substitution bwy−1 = t with part (c), we’re
lead directly to the conclusion that we can select n such that bwy−1 > b 1
n . Multiplying both sides by y gives us
bw > b 1
n > y, which is what we were asked to prove. As a corollary,
the fact that b 1
n > 1 > 0 means that, upon taking the reciprocals, we have b
−1
n < 1 and therefore bw− 1
−1
n gives us bw− 1
n y. Multiplying this by b
n < bw.
Exercise 1.7 f
We’ll prove that bx = y by showing that the assumptions bx > y and bx < y lead to contradictions.
If bx > y, then from part (e) we can choose n such that bx > bx− 1
n > y. From this we see that x − 1
upper bound of A that is smaller than x. This is a contradiction, since we’ve assumed that x =sup(A).
n is an
If bx < y, then from part (d) we can choose n such that y > bx+ 1
n > bx. From this we see that x is not an
upper bound of A. This is a contradiction, since we’ve assumed that x is the least upper bound of A.
Having ruled out these two possibilities, the trichotomy property of ordered fields forces us to conclude that
bx = y.
Exercise 1.7 g
Assume that there are two elements such that bw = y and bx = y. Then by the transitivity of equality relations,
bw = by, although this seems suspiciously simple.
Exercise 1.8
In any ordered set, all elements of the set must be comparable (the trichotomy rule, definition 1.5). We will
show by contradiction that (0, 1) is not comparable to (0, 0) in any potential ordered field containing C. First,
we assume that (0, 1) > (0, 0) :
→ (0, 1) > (0, 0)
→ (0, 1)(0, 1) > (0, 0)
hypothesis of contradiction
definition 1.17(ii) of ordered fields
We assumed here that (0, 0) can take the role of 0 in definition 1.17 of an ordered field. This is
a safe assumption because the uniqueness property of the additive identity shows us immediately
that (0, 0) + (a, b) = (a, b) → (0, 0) = 0.
→ (−1, 0) > (0, 0)
→ (−1, 0)(0, 1) > (0, 0)
→ (0,−1) > (0, 0)
definition of complex multiplication
definition 1.17(ii) of ordered fields, since we initially assumed (0, 1) > 0
definition of complex multiplication
It might seem that we have established our contradiction as soon as we concluded that (−1, 0) > 0
or (0,−1) > 0. However, we’re trying to show that the complex field cannot be an ordered field
under any ordered relation, even a bizarre one in which −1 > −i > 0. However, we’ve shown that
(0, 1) and (0,−1) are both greater than zero. Therefore:
→ (0,−1) + (0, 1) > (0, 0) + (0, 1)
→ (0, 0) > (0, 1)
definition 1.17(i) of ordered fields
definition of complex multiplication
This conclusion is in contradiction of trichotomy, since we initially assumed that (0, 0) < (0, 1). Next, we
assume that (0, 1) < (0, 0):
6
→ (0, 0) > (0, 1)
→ (0, 0) + (0,−1) > (0, 1) + (0,−1)
→ (0,−1) > (0, 0)
→ (0,−1)(0,−1) > (0, 0)
→ (−1, 0) > (0, 0)
→ (−1, 0)(0,−1) > (0, 0)
→ (0, 1) > (0, 0)
hypothesis of contradiction
definition 1.17(i) of ordered fields
definition of complex addition
definition 1.17(ii) of ordered fields
definition of complex multiplication
definitino 1.17(ii) of ordered fields, since we’ve established (0,−1) >
(0, 0)
definition of complex multiplication
Once again trichotomy has been violated.
Proof by contradiction that (0, 1) = (0, 0): if we assume that (0, 1) = (0, 0) we’re led to the conclusion that
(a, b) = (0, 0) for every complex number, since (a, b) = a(0, 1)4 + b(0, 1) = a(0, 0) + b(0, 0) = (0, 0). By the
transitivity of equivalence relations, this would mean that every element is equal to every other. And this is
in contradiction of definition 1.12 of a field, where we’re told that there are at least two distinct elements: the
additive identity (’0’) and the multiplicative identity (’1’).
Exercise 1.9a
To prove that this relation turns C into an ordered set, we need to show that it satisfies the two requirements
in definition 1.5. Proof of transitivity:
→ (a, b) < (c, d) ∧ (c, d) < (e, f )
→ [a < c ∨ (a = c ∧ b < d)] ∧ [c < e ∨ (c = e ∧ d < f )]
→ (a < c ∧ c < e) ∨ (a < c ∧ c = e ∧ d < f )
definition of this order relation
assumption
∨(a = c ∧ b < d ∧ c < e) ∨ (a = c ∧ b < d ∧ c = e ∧ d < f )
→ (a < e) ∨ (a < e ∧ d < f ) ∨ (a < e ∧ b < d) ∨ (a = e ∧ b < f )
distributivity of logical operators
transitivity of order relation on R
Although we’re falling back on the the transitivity of an order relation, we are not assuming what
we’re trying to prove. We’re trying to prove the transitivity of the dictionary order relation on C,
and this relation is defined in terms of the standard order relation on R. This last step is using the
transitivity of this standard order relation on R and is not assuming that transitivity holds for the
dictionary order relation.
→ (a < e) ∨ (a < e) ∨ (a < e) ∨ (a = e ∧ b < f )
→ a < e ∨ (a = e ∧ b < f )
→ (a, b) < (e, f )
To prove that the trichotomy property holds for the dictionary relation on Q, we rely on the trichotomy
property of the underlying standard order relation on R. Let (a, b) and (c, d) be two elements in C. From the
standard order relation, we know that
p ∧ q → p
p ∨ p → p
definition of this order relation
→ (a, b) ∈ C ∧ (c, d) ∈ C
→ a, b, c, d ∈ R
→ (a < c) ∨ (a > c) ∨ (a = c)
→ (a < c) ∨ (a > c) ∨ (a = c ∧ (b < d ∨ b > d ∨ b = d))
→ (a < c) ∨ (a > c) ∨ (a = c ∧ b < d) ∨ (a = c ∧ b > d)
∨(a = c ∧ b = d)
∨(a, b) = (c, d)
→ (a, b) < (c, d) ∨ (a, b) > (c, d) ∨ (a, b) < (c, d) ∨ (a, b) > (c, d)
→ (a, b) < (c, d) ∨ (a, b) > (c, d) ∨ (a, b) = (c, d)
assumed
definition of a complex number
trichotomy of the order relation on R
trichotomy of the order relation on R
distributivity of the logical operators
definition of the dictionary order relation
And this is the definition of the trichotomy law, so we have proven that the dictionary order turns the
7
complex numbers into an ordered set.
Exercise 1.9b
C does not have the least upper bound property under the dictionary order. Let E = {(0, a) : a ∈ R}. This subset
is just the imaginary axis in the complex plane. This subset clearly has an upper bound, since (x, 0) > (0, a) for
any x > 0. But it does not have a least upper bound: for any proposed upper bound (x, y) with x > 0, we see
that
(x, y) < (
, y) < (0, a)
x
2
So that ( x
2 , y) is an upper bound less than our proposed least upper bound, which is a contradiction.
Exercise 1.10
This is just straightforward algebra, and is too tedious to write out.
Exercise 1.11
If we choose w = z|z| and choose r = |z|, then we can easily verify that |w| = 1 and that rw = |z| z|z| = z.
Exercise 1.12
√
√
Set ai
zi and bi =
¯zi and use the Cauchy-Schwarz inequality (theorem 1.35). This gives us
n
j=1
¯zj
√
zj
≤ n
n
| ¯zj|2
|√
zj|2
j=1
j=1
2
which is equivalent to
|z1 + z2 + . . . + zn|2 ≤ (|z1| + |z2| + . . . + |zn|)2
Taking the square root of each side shows that
|z1 + z2 + . . . + zn| ≤ |z1| + |z2| + . . . + |zn|
which is what we were asked to prove.
Exercise 1.13
|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
= |x|2 − 2Re(x¯y) + |y|2
≥ |x|2 − 2|Re(x¯y)| + |y|2
≥ |x|2 − 2|x¯y| + |y|2
= |x|2 − 2|x||¯y| + |y|2
= |x|2 − 2|x||y| + |y|2
= (|x| − |y|)(|x| − |y|)
= (|x| − |y|)(|¯x| − |¯y|)
= (|x| − |y|)(|x| − |y|)
= ||x| − |y||2
Theorem 1.31(a)
Theorem 1.31(c), definition 1.32
x ≤ |x|, so −|x| ≥ |x|.
Theorem 1.33(d)
Theorem 1.33(c)
Theorem 1.33(b)
Theorem 1.33(b)
Theorem 1.31(a)
This chain of inequalities shows us that ||x| − |y||2 ≤ |x − y|2. Taking the square root of both sides results
in the claim we wanted to prove.
8