Category Archives: Solutions

Exercise 5.5.4

May 16, 2020 Issa Rice 1 Comment

Exercise statement

Let $q_1, q_2, q_3, \ldots$ be a sequence of rational numbers with the property that $|q_n - q_{n'}| \leq \frac1M$ whenever $M \geq 1$ is an integer and $n,n' \geq M$ . Show that $q_1, q_2, q_3, \ldots$ is a Cauchy sequence. Furthermore, if $S := \mathrm{LIM}_{n\to\infty} q_n$ , show that $|q_M - S| \leq \frac1M$ for every $M \geq 1$ .

Hints

Use Exercise 5.4.8.

How to think about the exercise

This is a fairly straightforward exercise.

One thing I will mention is that for the second part, if you find it confusing that $M$ is a variable, you can try to first show that $|q_1 - S| \leq 1$ .

Model solution

We will first show that the sequence is Cauchy. Let $\varepsilon > 0$ be a rational number. We need to find some $M \geq 1$ such that $|q_n - q_{n'}| \leq \varepsilon$ for all $n,n' \geq M$ . By Exercise 5.4.4, we can pick a positive integer $M$ such that $0 < 1/M < \varepsilon$ . Now for all $n, n' \geq M$ we have $|q_n - q_{n'}| \leq \frac1M < \varepsilon$ . This shows that the sequence is Cauchy.

Now let $S := \mathrm{LIM}_{n\to\infty} q_n$ . We want to show that $|q_M - S| \leq \frac1M$ for every $M \geq 1$ . Let $M \geq 1$ . Then if $n \geq M$ we have $|q_n - q_M| \leq \frac1M$ since $M \geq M$ . By Exercise 5.4.6, this is equivalent to $q_M - \frac1M \leq q_n \leq q_M + \frac1M$ . Now we can define an equivalent sequence $a_n := q_n$ if $n \geq M$ and $a_n := q_M$ if $n < M$ . This is a Cauchy sequence equivalent to $(q_n)_{n=1}^\infty$ (because it has the same infinite tail as $(q_n)_{n=1}^\infty$ ) and we also have $q_M - \frac1M \leq a_n \leq q_M + \frac1M$ for all $n \geq 1$ . Thus we can apply Exercise 5.4.8 to conclude that $q_M - \frac1M \leq S \leq q_M + \frac1M$ . Again by Exercise 5.4.6, this is the same thing as $|S - q_M| \leq \frac1M$ . Since $|S - q_M| = |q_M - S|$ , the proof is complete.

Solutions

Exercise 5.5.3

May 15, 2020 Issa Rice 4 Comments

Exercise statement

Let $E$ be a non-empty subset of $\mathbf R$ , let $n \geq 1$ be an integer, and let $m,m'$ be integers with the properties that $m/n$ and $m'/n$ are upper bounds for $E$ , but $(m-1)/n$ and $(m'-1)/n$ are not upper bounds for $E$ . Show that $m=m'$ . This shows that the integer $m$ constructed in Exercise 5.5.2 is unique.

Hints

Drawing a picture will be helpful.

How to think about the exercise

This is a simple exercise, so I don’t have much to say.

I want to comment on one part of the proof below, which is where I go from $m-1 < m'$ to $m \leq m'$ . This is valid when $m,m'$ are both integers—you can think of it as a generalization of Proposition 2.2.12(e). How would we prove this? If $a < b$ are integers, we can add $-a$ to both sides to get $0 < b-a$ . Now both sides are natural numbers, so we can apply Proposition 2.2.12(e) to get $1 \leq b-a$ , and finally we can add $a$ to both sides to get $a+1 \leq b$ as required. The other direction is similar, but we don’t need it for this exercise so I will omit it.

Model solution

Since $(m-1)/n$ is not an upper bound for $E$ , there exists some $x \in E$ such that $(m-1)/n < x$ . Similarly, since $(m'-1)/n$ is not an upper bound for $E$ , there exists some $y \in E$ such that $(m'-1)/n < y$ . Thus we have $(m-1)/n < x \leq m'/n$ and $(m'-1)/n < y \leq m/n$ using the fact that $m/n$ and $m'/n$ are upper bounds for $E$ . This implies $m-1 < m'$ and $m'-1 < m$ (by multiplying through by $n$ , which we can do since $n \geq 1$ is positive). Since $m,m'$ are integers, we have $m \leq m'$ and $m' \leq m$ , which means $m=m'$ as required.

Solutions

Exercise 5.5.2

May 14, 2020 Issa Rice 4 Comments

Exercise statement

Let $E$ be a non-empty subset of $\mathbf R$ , let $n \geq 1$ be an integer, and let $L < K$ be integers. Suppose $K/n$ is an upper bound for $E$ , but that $L/n$ is not an upper bound for $E$ . Without using Theorem 5.5.9, show that there exists an integer $L < m \leq K$ such that $m/n$ is an upper bound for $E$ , but that $(m-1)/n$ is not an upper bound for $E$ .

Hints

Prove by contradiction, and use induction.
It may help to draw a picture of the situation.

How to think about the exercise

I think this is a pretty tricky exercise, if you decide to go the induction route (as suggested in the book, and as in model solution 1 below).

If you go the route of model solution 1, the tricky things are:

When using induction, you have to realize that you shouldn’t induct on $n$ (which is the obvious choice), but instead on the difference $K-L$ .
The inductive statement $P(d)$ must bring in the universal quantifiers over all $K$ and $L$ . If we don’t do this, then during the inductive step, we have both $K-L = d$ and $K-L=d+1$ , which is nonsense. In other words, if we fix $K,L$ outside the inductive statement $P(d)$ , then we can’t pretend that the difference $K-L$ keeps changing.

As can be seen in model solution 1, a direct proof is possible. Model solutions 2 and 3 prove by contradiction, so they are probably the sorts of proof that Tao had in mind.

Model solution 1

Let $P(d)$ be the statement “for all integers $K,L$ , if $K-L = d$ , $K/n$ is an upper bound for $E$ , and $L/n$ is not an upper bound for $E$ , then there exists an integer $L < m \leq K$ such that $m/n$ is an upper bound for $E$ and $(m-1)/n$ is not an upper bound for $E$ ”. We will induct on $d$ to show that $P(d)$ is true for all natural numbers $d \geq 1$ .

For the base case we have $d=1$ . Let $K,L$ be two integers such that $K-L=1$ , and such that $K/n$ is an upper bound for $E$ and $L/n$ is not an upper bound for $E$ . We will show that choosing $m := K$ will work. Indeed, $L < m \leq K$ since $L = K-1 < K = m$ . Also, $m/n = K/n$ is an upper bound for $E$ , while $(m-1)/n = L/n$ is not an upper bound for $E$ . Thus we have found an integer, and we conclude that $P(1)$ is true.

Now suppose inductively that $P(d)$ is true. We want to show that $P(d+1)$ is also true. Let $K,L$ be two integers such that $K-L = d+1$ , and where $K/n$ is an upper bound for $E$ and $L/n$ is not an upper bound for $E$ . We have two cases, depending on whether or not $(L+1)/n$ is an upper bound for $E$ .

Suppose first that $(L+1)/n$ is not an upper bound for $E$ . Then $K - (L+1) = d$ so we may apply the inductive hypothesis to conclude that there exists an integer $L+1 < m \leq K$ such that $m/n$ is an upper bound for $E$ and $(m-1)/n$ is not an upper bound for $E$ . But $L < L+1$ , so we have $L < m \leq K$ , which means this same $m$ will work.
Now suppose that $(L+1)/n$ is an upper bound for $E$ . Then we may take $m := L+1$ . Indeed we have $L < L+1 =m$ and also $K-L = d+1$ so $K = L+1 + d$ , which means $K \geq L+1 = m$ (since $d$ is a natural number). Thus we have $L < m \leq K$ . Also, $m/n = (L+1)/n$ is an upper bound for $E$ while $(m-1)/n = L/n$ is not.

In both cases, we have shown that such an integer $m$ exists, so this closes the induction.

We have shown that $P(d)$ is true for all $d \geq 1$ . Now we need to show that the actual result holds. Let $L < K$ be integers. Then $K-L > 0$ is a positive integer, so $P(K-L)$ is true. Thus we are given an integer $m$ with the properties we want.

Model solution 2

Suppose for sake of contradiction that there is no $m$ such that $L < m \leq K$ and where $m/n$ is an upper bound for $E$ and $(m-1)/n$ is not an upper bound for $E$ . We can rewrite this statement in the following form: for all $m$ such that $L < m \leq K$ , if $m/n$ is an upper bound for $E$ then $(m-1)/n$ is an upper bound for $E$ .

Now the idea is to start at $K$ and go down. Since $L < K \leq K$ and $K/n$ is an upper bound for $E$ , we see that $(K-1)/n$ is an upper bound for $E$ . Continuing, we have $L < K-1 \leq K$ and know that $(K-1)/n$ is an upper bound for $E$ , so $(K-2)/n$ is also an upper bound for $E$ . We keep going until we reach $L$ , and conclude that $L/n$ is an upper bound for $E$ , which is a contradiction.

To do this rigorously, we use induction. Let $P(j)$ be the statement “if $L < K-j \leq K$ , then $(K-j-1)/n$ is an upper bound for $E$ ”. For the base case, we already showed above that $(K-1)/n$ is an upper bound for $E$ .

Now suppose inductively that $P(j)$ is true. We must show that $P(j+1)$ is true. So suppose $L < K-(j+1) \leq K$ . Then $L < K-(j+1) < K-j \leq K$ so the antecedent for $P(j)$ is true. Thus by inductive hypothesis, we see that $(K-j-1)/n$ is an upper bound for $E$ . But now this means that $(K-j-2)/n$ is an upper bound for $E$ (by using the statement in the first paragraph of this proof). This shows that $P(j+1)$ is true, which closes the induction.

So $P(j)$ is true for all natural numbers $j$ . Since we assumed that $K > L$ , we have $K - L > 0$ , so $K-L-1 \geq 0$ is a natural number. Thus $P(K-L-1)$ is true. This says that if $L < K - (K-L-1) \leq K$ , then $(K - (K-L-1) - 1)/n$ is an upper bound for $E$ . We have $K - (K-L-1) = L+1$ , so indeed $L < L+1 \leq K$ . Thus $(K - (K-L-1) - 1)/n = L/n$ is an upper bound for $E$ , a contradiction.

Model solution 3

Suppose for sake of contradiction that there is no $m$ such that $L < m \leq K$ and where $m/n$ is an upper bound for $E$ and $(m-1)/n$ is not an upper bound for $E$ .

We will show by induction on $j$ that $(K-j)/n$ is an upper bound for $E$ for all natural numbers $j$ .

For the base case, we see that $K/n$ is an upper bound for $E$ by assumption.

Now suppose inductively that $(K-j)/n$ is an upper bound for $E$ . We want to show that $(K-(j+1))/n$ is an upper bound for $E$ . By assumption $L/n$ is not an upper bound for $E$ so there exists some $x \in E$ such that $L/n < x$ . Since $(K-j)/n$ is an upper bound for $E$ , we have $x \leq (K-j)/n$ . Thus $L < K-j$ . Since $j$ is a natural number we have $K-j \leq K$ . Thus $L < K-j \leq K$ . If $(K-(j+1))/n$ were not an upper bound for $E$ , then putting $m := K-j$ would give an integer such that $L < m \leq K$ and where $m/n$ is an upper bound while $(m-1)/n$ is not, a contradiction. Thus we see that $(K-(j+1))/n$ is an upper bound for $E$ . This closes the induction.

Since $L < K$ , we have that $K - L > 0$ is a natural number. Thus $(K - (K-L))/n = L/n$ is an upper bound for $E$ by what we said above, a contradiction.

Model solution 4

This is one of those problems where it is much easier to use the well-ordering principle (which is equivalent to induction but doesn’t appear until later in this book). The proof of equivalence between mathematical induction and the well-ordering principle does not require any results from analysis, so there is no circularity if we use the well-ordering principle. I’ll show it here so you get an idea of how clean the solution can be (compared to the above three solutions). I will try to remember to point back to here when I get to the well-ordering principle in the book.

Define the set

$A := \{j \in \mathbf Z : L < j \leq K\text{ and }j/n\text{ is upper bound for }E\}$

This set is non-empty since $K \in A$ . Also, $L$ is a lower bound for $A$ since $L < j$ for all $j \in A$ . Thus by the well-ordering principle there is a minimum element $m := \min(A)$ . By definition of minimum element, $m \in A$ so $m/n$ is an upper bound for $E$ . If $(m-1)/n$ were an upper bound for $E$ then since $L/n$ is not there is some $x \in E$ such that $L/n < x \leq (m-1)/n$ . Thus $L < m-1$ . We also have $m \leq K$ so $m-1 < m \leq K$ . Thus $L < m-1 \leq K$ , which shows that $m-1 \in A$ . But this contradicts the fact that $m$ is the minimum element of $A$ .

Solutions

Exercise 5.5.1

May 13, 2020 Issa Rice Leave a comment

Exercise statement

Let $E$ be a subset of the real numbers $\mathbf R$ , and suppose that $E$ has a least upper bound $M$ which is a real number, i.e., $M = \sup(E)$ . Let $-E$ be the set

$-E := \{-x : x \in E\}$ .

Show that $-M$ is the greatest lower bound of $-E$ , i.e., $-M = \inf(-E)$ .

Hints

Draw a picture.

How to think about the exercise

The standard way to show that something is the greatest lower bound is to show both that it is a lower bound and that among all lower bounds it is the greatest one. That’s the approach I take in the first solution below.

A second, more general, approach to showing that two numbers $A, B$ are equal is to show that both the assumptions $A > B$ and $A < B$ lead to contradictions. Then by trichotomy of order, we must have $A=B$ . I will show this approach in the second solution below; however it requires some tricks that are only officially introduced in the text in Chapter 6.

As Tao hints at in Remark 5.5.15, this exercise justifies us studying only one of supremum or infimum. For example, we can use this exercise to show an analogue for Theorem 5.5.9 that if $E \subseteq \mathbf R$ is a non-empty subset of the real line which has a lower bound, then it has a real greatest lower bound. Here’s how such a proof would go: we consider the set $-E$ . Since $E$ has a lower bound, this mean that $-E$ has an upper bound. So we can apply Theorem 5.5.9 to $-E$ and find $\sup(-E)$ , the unique least upper bound for $-E$ . Using the result in this current exercise, we see that $-\sup(-E) = \inf(-(-E)) = \inf(E)$ . So $-\sup(-E)$ is the greatest lower bound for $E$ . In a similar way, statements about the supremum can be converted into “mirror” statements about the infimum and this exercise allows us to quickly prove the equivalent versions for infimum. We don’t even need to be lazy and say “a similar proof exists for the infimum”; we can be fully rigorous and still economical! (Though we can certainly still be lazy.)

Model solution 1

First we show that $-M$ is a lower bound of $-E$ . Let $y \in -E$ be an element of $-E$ . Thus $y = -x$ for some element $x \in E$ . Since $M$ is an upper bound of $E$ , we have $x \leq M$ . Thus we have $-M \leq -x$ , i.e. $-M \leq y$ . Since $y$ was arbitrary, this shows that $-M$ is a lower bound of $-E$ .

Next we show that $-M$ is the greatest lower bound. Let $L$ be any lower bound of $-E$ , i.e. $L \leq y$ for all $y \in -E$ . We will show that $-L$ is an upper bound of $E$ . Let $x \in E$ . Then $-x \in -E$ so $L \leq -x$ . This means $x \leq -L$ . Since $x \in E$ was arbitrary, this means $-L$ is an upper bound of $E$ . By hypothesis, $M$ is the least upper bound of $E$ , so $M \leq -L$ , which means $L\leq -M$ . This means $-M$ is greater than or equal to any lower bound of $E$ , which is what we wanted to show.

Model solution 2

(Thanks to Kenny for giving me the idea for this proof.)

We will show that both the assumptions $-M > \inf(-E)$ and $-M < \inf(-E)$ lead to contradictions.

Suppose for the sake of contradiction that $-M > \inf(-E)$ . Then $-M$ cannot be a lower bound for $-E$ since $\inf(-E)$ is the greatest lower bound and $-M$ is even greater. So there is some number $y \in -E$ such that $-M > y$ . But by definition of $-E$ there is some $x \in E$ such that $y=-x$ . Rearranging $-M > y$ we have $M < -y = x$ . In other words, we have $\sup(E) = M < x$ , which contradicts the fact that $M$ is an upper bound for $E$ .

Now suppose for the sake of contradiction that $-M < \inf(-E)$ . There are a few different ways to proceed from here:

By Proposition 5.4.14, there is some number $-q$ such that $-M < -q < \inf(-E)$ . This means $M > q$ , so $q$ cannot be an upper bound for $E$ (as $M$ is the least upper bound, any number less than it cannot be an upper bound). Thus there is some $x \in E$ such that $q < x$ . But now we have $-x < -q < \inf(-E)$ so we have $-x < \inf(-E)$ even though $-x \in -E$ , a contradiction.
Alternatively: This means that $M > -\inf(-E)$ . If we can show that $-\inf(-E)$ is an upper bound for $E$ , this will mean we have found an even smaller upper bound for $E$ , contradicting the fact that $M$ is the least upper bound for $E$ . So let $x \in E$ . We want to show $-\inf(-E) \geq x$ . By definition of $-E$ , we have $-x \in -E$ . Since $\inf(-E)$ is a lower bound for $-E$ , we thus have $\inf(-E) \leq -x$ . But this means $-\inf(-E) \geq x$ as required.

Solutions

Exercise 5.4.2

May 12, 2020 Issa Rice 1 Comment

Exercise statement

Prove the remaining claims in Proposition 5.4.7.

Proposition 5.4.7. All the claims in Proposition 4.2.9 which held for rationals, continue to hold for real numbers.

Let $x,y,z$ be real numbers. Then the following properties hold.

(a) (Order trichotomy) Exactly one of the three statements $x=y$ , $x < y$ , or $x > y$ is true.
(b) (Order is anti-symmetric) One has $x < y$ if and only if $y > x$ .
(c) (Order is transitive) If $x < y$ and $y < z$ , then $x < z$ .
(d) (Addition preserves order) If $x < y$ , then $x+z < y+z$ .
(e) (Positive multiplication preserves order) If $x < y$ and $z$ is positive, then $xz < yz$ .

Hints

None.

How to think about the exercise

This is a straightforward exercise, so I don’t have anything to say.

Model solution

(a) First we show that at least one of the possibilities is true. Consider the number $x-y$ . By Proposition 5.4.4, it is zero, positive, or negative. If $x-y$ is zero, then $x=y$ . If $x-y$ is positive, then $x > y$ by definition of order. If $x-y$ is negative, then $x < y$ by definition of order. Thus in each case, at least one of the possibilities is true.

Now we show that at most one of the possibilities is true. If $x=y$ and $x > y$ , then $x-y$ is both zero and positive, which contradicts Proposition 5.4.4. Similarly if $x=y$ and $x < y$ , then $x-y$ is both zero and negative, a contradiction. Also if $x > y$ and $x < y$ , then $x-y$ is both positive and negative, which is again a contradiction.

(b) Suppose $x < y$ . Then $x-y$ is negative. Thus by Proposition 5.4.4, we see that $-(x-y) = y-x$ is positive. This means $y > x$ , which is what we wanted to show. Conversely, suppose $y > x$ . Then $y-x$ is positive, so by Proposition 5.4.4 we see that $-(y-x) = x-y$ is negative, which means $x < y$ as required.

(c) Suppose $x < y$ and $y < z$ . By part (b), this means $y > x$ and $z > y$ , so $y-x$ and $z-y$ are positive. By Proposition 5.4.4, we thus see that $(y-x) + (z-y) = z-x$ is a positive number, so that $z > x$ . By part (b) again, this means $x < z$ as required.

(d) Suppose $x < y$ . By definition of order, $x-y$ is negative. But $x-y = (x+z) - (y+z)$ , so $x+z < y+z$ .

(e) This was already proved in the book.

Solutions

Exercise 5.4.7

May 11, 2020 Issa Rice 1 Comment

Exercise statement

Let $x$ and $y$ be real numbers. Show that $x \leq y + \varepsilon$ for all real numbers $\varepsilon > 0$ if and only if $x \leq y$ . Show that $|x-y| \leq \varepsilon$ for all real numbers $\varepsilon > 0$ if and only if $x=y$ .

Hints

None.

How to think about the exercise

Do we have the strict versions of this exercise? In other words, do we have that $x < y + \varepsilon$ for all real numbers $\varepsilon > 0$ if and only if $x < y$ ? Do we have that $|x-y| < \varepsilon$ for all real numbers $\varepsilon > 0$ if and only if $x=y$ ?

Model solution 1

First we show that $x \leq y + \varepsilon$ for all real numbers $\varepsilon > 0$ if and only if $x \leq y$ .

Suppose $x \leq y + \varepsilon$ for all real numbers $\varepsilon > 0$ . We must show that $x \leq y$ . Suppose for sake of contradiction that $x > y$ . Then we may subtract $y$ from both sides to see that $x-y > 0$ is a positive number, which means that $(x-y)/2$ is also a positive real number. So for $\varepsilon := (x-y)/2$ in particular, we have $x \leq y + (x-y)/2$ . But this means $2x \leq 2y + x - y$ , so $x \leq y$ , a contradiction.

Conversely, suppose that $x \leq y$ . Let $\varepsilon > 0$ be a positive real number. Then we have $y + 0 < y + \varepsilon$ . Thus by transitivity we have $x \leq y < y + \varepsilon$ as required.

Now we show that $|x-y| \leq \varepsilon$ for all real numbers $\varepsilon > 0$ if and only if $x=y$ .

Suppose that $|x-y| \leq \varepsilon$ for all real numbers $\varepsilon > 0$ . We want to show that $x=y$ . Suppose for sake of contradiction that $x\ne y$ . Then $|x-y|/2$ is a positive number, so for $\varepsilon := |x-y|/2$ we see that $|x-y| \leq |x-y|/2$ . This implies that $|x-y| \leq 0$ , a contradiction of the fact that $|x-y|$ is positive. This contradiction shows that $x=y$ .

Now suppose $x=y$ . Then $|x-y|=0 < \varepsilon$ for all $\varepsilon > 0$ .

Model solution 2

This version proves the second part using the first part. It’s slightly longer but some people might prefer this version.

We can show that $x \leq y + \varepsilon$ for all real numbers $\varepsilon > 0$ if and only if $x \leq y$ just like in model solution 1.

Now we show that $|x-y| \leq \varepsilon$ for all real numbers $\varepsilon > 0$ if and only if $x=y$ .

Suppose first that $|x-y| \leq \varepsilon$ for all real numbers $\varepsilon > 0$ . We have two cases. If $x-y$ is positive or zero, then $|x-y| = x-y$ . Thus we have $x-y \leq \varepsilon$ for all real numbers $\varepsilon > 0$ . We can rewrite $x-y \leq \varepsilon$ as $x \leq y + \varepsilon$ . Thus by the first part we have $x\leq y$ . Since $x-y$ is positive or zero, this means $0 \leq x-y$ , i.e. $y \leq x$ . Combining these two inequalities we have $x=y$ as required. Now suppose $x-y$ is negative. Then $|x-y| = y-x$ . Thus $y-x \leq \varepsilon$ for all real numbers $\varepsilon > 0$ . We can rewrite $y-x \leq \varepsilon$ as $y \leq x+\varepsilon$ . By the first part of this exercise, we thus have $y \leq x$ . Since $x-y$ is negative, we have $x-y < 0$ , i.e. $x < y$ , which means $x \leq y$ . Thus we have $x=y$ as required. (Alternatively, we could have seen that $y \leq x$ and $x < y$ lead to a contradiction, so that this case isn’t even possible.)

Conversely suppose that $x=y$ . Then we have both $x\leq y$ and $y \leq x$ . Thus for all $\varepsilon > 0$ we have $x-y \leq \varepsilon$ and $y-x \leq \varepsilon$ . Thus no matter what value $|x-y|$ takes, we have $|x-y| \leq \varepsilon$ for all $\varepsilon > 0$ .

Solutions

Exercise 5.4.6

May 10, 2020 Issa Rice 3 Comments

Exercise statement

Let $x,y$ be real numbers and let $\varepsilon > 0$ be a positive real. Show that $|x-y| < \varepsilon$ if and only if $y-\varepsilon < x < y + \varepsilon$ , and that $|x-y| \leq \varepsilon$ if and only if $y-\varepsilon \leq x \leq y+\varepsilon$ .

Hints

None.

How to think about the exercise

This maneuver, of going between $|x-y| < \varepsilon$ and $y-\varepsilon < x < y + \varepsilon$ , is very common in analysis, so you should get very comfortable with it.

The exercise itself is pretty straightforward, so I don’t have anything to say.

Model solution 1

Suppose first that $|x-y| < \varepsilon$ . If $x-y$ is positive or zero then we have $-\varepsilon < 0 \leq x-y < \varepsilon$ . By Proposition 5.4.7, we can add $y$ to each part to obtain $y-\varepsilon < x < y+\varepsilon$ . If $x-y$ is negative, then we have $-\varepsilon < 0 < y-x < \varepsilon$ . By Proposition 5.4.7 we can add $-y$ to each part to obtain $-y-\varepsilon < -x < -y+\varepsilon$ . Using $-y-\varepsilon < -x$ we can add $x+y+\varepsilon$ to both sides to obtain $x < y+\varepsilon$ . Using $-x < -y+\varepsilon$ we can add $x + (y-\varepsilon)$ to both sides to obtain $y-\varepsilon < x$ . Combining these inequalities we have $y-\varepsilon < x < y+\varepsilon$ as required.

Conversely, suppose that $y-\varepsilon < x < y + \varepsilon$ . Subtracting $y$ from each part we obtain $-\varepsilon < x-y < \varepsilon$ . By trichotomy we have three cases. If $x-y=0$ then $|x-y| = 0 < \varepsilon$ . If $x-y$ is positive then $|x-y| = x-y < \varepsilon$ . If $x-y$ is negative, then $|x-y| = -(x-y)$ . From $-\varepsilon < x-y$ we can add $\varepsilon - (x-y)$ to each side to obtain $-(x-y) < \varepsilon$ . Thus $|x-y| = -(x-y) < \varepsilon$ , which completes the proof.

The proof for non-strict inequality is similar.

Model solution 2

I haven’t checked this too carefully, but I think you can make this work. The proof of Proposition 4.3.3(c) only relies on the basic properties of order that appear in Proposition 5.4.7, so we can carry out the same proof for the reals. Thus $|x-y| \leq \varepsilon$ if and only if $-\varepsilon \leq x-y \leq \varepsilon$ . Now we can add $y$ to each part of $-\varepsilon \leq x-y \leq \varepsilon$ , or subtract $y$ from each part of $y-\varepsilon \leq x \leq y+\varepsilon$ , to complete the proof.

The case for strict inequality is similar, except now we first have to show the analogue of Proposition 4.3.3(c) for strict inequality.

Solutions

Exercise 5.4.5

May 10, 2020 Issa Rice 7 Comments

Exercise statement

Prove Proposition 5.4.14.

Proposition 5.4.14. Given any two real numbers $x < y$ , we can find a rational number $q$ such that $x < q < y$ .

Hints

Use Exercise 5.4.4.
You may need to argue by contradiction.
You might also want to use Exercise 5.4.3.

How to think about the exercise

To use Exercise 5.4.4, we need a positive real number. But the problem only says that $x < y$ , saying nothing about whether $x,y$ are positive. Thankfully, it’s not too hard to make a positive real number: we can just subtract the two, to get $y-x > 0$ . So now we apply Exercise 5.4.4 to get an integer $N$ such that $y-x > 1/N > 0$ . Now what?

We can try adding $x$ to each part, to get $y > x+1/N > x$ . But $x$ is not guaranteed to be a rational number, so $x+1/N$ is not guaranteed to be rational either.

We can play around with $y-x > 1/N$ to get $Ny - Nx > 1$ . And $Ny > Nx + 1 > Nx$ . It’s not clear what to do from here.

Let’s try another thing. What’s another way to get a number between $x$ and $y$ ? We can average the two, to get $\frac{x+y}{2}$ . Does this help? Again, we are not guaranteed to have $\frac{x+y}{2}$ be rational. (Actually, this does seem to be the start of a proof, but it requires going back to the Cauchy sequence definition of the reals, which makes it messy.)

How can we get a rational number between $x$ and $y$ ? Here’s a thought: what would that look like? We must have $x < a/b < y$ for some integers $a,b$ (with $b$ positive). So we can play around with this a bit. We have $bx < a < by$ . It looks like $b$ is playing the role of $N$ from above. We can subtract to get $0 < a-bx < by-bx$ , but this doesn’t seem to help because $a-bx$ is hard to work with. However since we already know how to get $b$ , we just need to find the integer $a$ somehow.

At this point, I like to use actual numbers. If we take $x=1/6$ and $y=1/3$ (using rational numbers will simplify things), we want to scale these numbers to be large enough that an integer can be found between them. If we try $b=6$ , then $bx=1$ and $by=2$ , which is too narrow for an integer to fit (there is no integer $a$ such that $1 < a < 2$ ). On the other hand, if we try $b=12$ , then $bx=2$ and $by=4$ , so we can take $a=3$ .

At this point, we have two questions: (1) Is the number $b$ we get from Exercise 5.4.4 large enough of a scaling factor that an integer fits between $bx$ and $by$ ? (2) How can we show in general that the integer $a$ exists?

To answer question (1), we would have $y-x > 1/b > 0$ , which means $by - bx > 1$ . If two real numbers are more than a distance $1$ apart, then there must be an integer between them (just imagine a number line). So the answer to this question is yes. That leaves question (2), and this is where we must fiddle with inequalities, which we leave to the solutions below.

I want to stress the core insight here. We want a rational number between $x$ and $y$ . But $x$ and $y$ might be super close to each other, and it’s hard to directly find a rational number. What do we do?

We blow up the scale. Even if $x$ and $y$ are close, if we take $N$ large enough, then $Nx$ and $Ny$ will come apart. Eventually, they will come apart to such an extent that an integer can be guaranteed to be found between them.

So we can find some integer $a$ such that $Nx < a < Ny$ . Now dividing through by $N$ completes the proof.

I like this exercise because even after the hint in the book, it’s not obvious what to do, and you naturally get stuck, so you have to backtrack and try a few things before you get it to work.

Model solution 1

Let $x,y$ be real numbers such that $x < y$ . Then $y-x > 0$ so by Exercise 5.4.4 there exists a positive integer $b$ such that $y-x > 1/b > 0$ . Multiplying through by $b$ we have $by - bx > 1$ .

By Exercise 5.4.3, there is some integer $n$ such that $n \leq bx < n+1$ . By $n \leq bx$ we have $n+1 \leq bx+1$ . Also from $by - bx > 1$ we have $bx+1 < by$ . Combining the inequalities, we have $bx < n+1 \leq bx+1 < by$ . Dividing through by $b$ , we have $x < (n+1)/b < y$ , so we may take $q:=(n+1)/b$ as the rational number we seek.

Model solution 2

Let $x,y$ be real numbers such that $x < y$ . Then $y-x > 0$ so by Exercise 5.4.4 there exists a positive integer $b$ such that $y-x > 1/b > 0$ . Multiplying through by $b$ we have $by - bx > 1$ .

Since $x < y$ and $b$ is positive, we have $bx < by$ . We will now show that there exists an integer $a$ such that $bx < a < by$ . Suppose for sake of contradiction that there is no such integer. By Exercise 5.4.3, there is some integer $n$ such that $n \leq bx < n+1$ . By assumption, we cannot have $bx < n+1 < by$ . Thus we must have $n+1 \geq by$ . Putting together the inequalities, we have $n \leq bx < by \leq n+1$ . But this means $by - bx \leq 1$ . (To see this, use $n \leq bx$ to conclude that $-bx \leq -n$ , then add this inequality to $by \leq n+1$ to obtain $by-bx \leq (n+1)-n = 1$ .) This contradicts the fact that $by-bx > 1$ . Thus we must in fact have some integer $a$ such that $bx < a < by$ . Now dividing through by $b$ we have $x < a/b < y$ , so we may take $q := a/b$ as the rational number that we seek.

Model solution 3

This one is pretty messy, but it uses a proof by contradiction and doesn’t use Exercise 5.4.3 so it’s possibly the proof that Tao had in mind.

Let $x,y$ be real numbers such that $x < y$ . Then $y-x > 0$ so by Exercise 5.4.4 there exists a positive integer $b$ such that $y-x > 1/b > 0$ . Multiplying through by $b$ we have $by - bx > 1$ .

Since $x < y$ and $b$ is positive, we have $bx < by$ . We will now show that there exists an integer $a$ such that $bx < a < by$ . Suppose for sake of contradiction that there is no such integer. If $a$ is an integer such that $a \leq bx$ , then $a+1$ cannot be between $bx$ and $by$ so we must have either $a+1 \leq bx$ or $by \leq a+1$ . If $by \leq a+1$ then we have $a \leq bx < by \leq a+1$ , which contradicts the fact that $by-bx > 1$ . Thus we must have $a+1 \leq bx$ . In other words we have shown that for all integers $a$ , if $a \leq bx$ then $a+1 \leq bx$ . By Proposition 5.4.12, there is a positive integer $N$ such that $-bx \leq N$ , so $-N \leq bx$ .

Now let $P(n)$ be the statement $n-N \leq bx$ . We will show by induction that $P(n)$ is true for all natural numbers $n$ . By what we said above, $P(0)$ is true. Now suppose inductively that $n-N \leq bx$ . Then since $n-N$ is an integer, we see that $n-N+1 \leq bx$ , i.e. $(n+1)-N \leq bx$ . So we see that $P(n+1)$ is true. This closes the induction.

By Proposition 5.4.12 again, there is some positive integer $M$ such that $bx \leq M$ , so $bx < M+1$ . But $N+M+1$ is a natural number, so $P(N+M+1)$ is true, i.e. $M+1 \leq bx$ , which is a contradiction. This contradiction shows that our assumption that there is no integer $a$ such that $bx < a < by$ was mistaken.

So there is some integer $a$ such that $bx < a < by$ , and we can divide by $b$ to complete the proof.

Model solution 4

This one is just a sketch, based on this PDF. The idea is that once we find a positive integer $N$ such that $y-x > 1/N$ , we consider rational numbers of the form $k/N$ , where $k$ is an integer. Then we pick the largest number $k/N$ such that $k/N \leq x$ , and show that $q:=(k+1)/N$ works as desired. (See the linked PDF for details.) The only trouble with this approach is to rigorously show that we can uniquely pick such a number $k/N$ .

But first of all, what does it even mean to say that $k/N$ is the largest number in this form such that $k/N \leq x$ ? It means that (1) $k/N \leq x$ and (2) for all integers $k'$ , if $k'/N \leq x$ then $k'/N \leq k/N$ . Uniqueness is easy to see: if $k,k'$ both satisfy this condition, then we must have $k'/N \leq k/N$ and $k/N \leq k'/N$ (why?), so $k=k'$ (why?).

Now to find this $k$ , our strategy is to narrow the selection to some finite set of rationals of the form $k/N$ , then pick the one we want from this set.

We can use the Archimedean property to show that there is some integer $M$ such that $M/N > x$ . Similarly, we can apply the Archimedean property to $-x$ to show that there is some integer $-m$ such that $-m/N > -x$ , i.e. $m/N < x$ . Now we have $m/N < x < M/N$ . Now there is a finite number of rationals $m/N, (m+1)/N, \ldots, (M-1)/N, M/N$ to pick from, which makes it particularly easy to find the $k$ we want. (I can think of other ways to do this, but they require either the the least upper bound property or the well-ordering principle, neither of which have been covered in the book yet. The method I describe below will only need a simple induction proof.) Let’s see how this works more rigorously.

Consider the set $A := \{n \in \mathbf Z : {m \leq n \leq M}\text{ and }{n/N \leq x}\}$ . This set is finite (why? Show that $\{ n \in \mathbf Z : m \leq n \leq M\}$ is finite by using the definition of cardinality, then use Proposition 3.6.14(c)). Every non-empty finite set of numbers has a (unique) maximum element $\max A$ , i.e. an element $a \in A$ such that $a' \leq a$ for all $a' \in A$ (why? Use induction). The set $A$ is non-empty since $m \in A$ . Thus we may define $k := \max A$ .

Now we show that $k$ has the required properties, i.e. that $k/N \leq x$ and that $k'/N \leq x$ implies $k'/N \leq k/N$ for all integers $k'$ . First, $k \in A$ so $k/N \leq x$ as required. Next, let $k'$ be an integer and suppose $k'/N \leq x$ . Suppose for a contradiction that $k'/N > k/N$ . Then $m/N \leq k/N < k'/N \leq x < M/N$ (why?) so $k' \in A$ (why?). But $k$ is the maximum element of $A$ , so we have $k' \leq k$ , which means $k'/N \leq k/N$ , a contradiction.

So we have shown that the integer $k$ exists, and we also know it is unique. Now we can just proceed as in the linked PDF.

Solutions

Exercise 5.4.4

May 7, 2020 Issa Rice 8 Comments

Exercise statement

Show that for any positive real number $x > 0$ there exists a positive integer $N$ such that $x > 1/N > 0$ .

Hints

None.

How to think about the exercise

This is a straightforward exercise, so I don’t have anything to say.

Model solution 1

Let $x > 0$ be a positive real number. Then $1/x$ is also a positive real number (by Proposition 5.4.8) so by Proposition 5.4.12, there exists a positive integer $M$ such that $1/x \leq M$ . Thus $1/x < M+1$ . We can multiply by $x/(M+1)$ on both sides (alternatively, we could have used Proposition 5.4.8 again) to obtain $0 < 1/(M+1) < x$ . So we can take $N:=M+1$ as the integer.

Model solution 2

Let $x > 0$ be a positive real number. By Proposition 5.4.12, there exists a positive rational number $q$ such that $x \geq q$ . Since $q$ is a positive rational, there are positive integers $a,b$ such that $q = a/b$ . Since $a$ is positive, we have $a \geq 1$ . Thus $x \geq a/b \geq 1/b > 1/(b+1)$ , so we may take $N:=b+1$ .

Model solution 3

(Thanks to Diego for the idea of this proof.)

Let $x > 0$ be a positive real number. By the Archimedean property (Corollary 5.4.13), there exists a positive integer $N$ such that $Nx > 1$ (in the statement of the Archimedean property, we are setting “ $x$ ” to be $1$ , setting “ $\varepsilon$ ” to be our given $x$ , and setting “ $M$ ” to be $N$ ). Dividing through by $N$ gives $x > 1/N > 0$ as required.

Solutions

Exercise 5.4.3

May 6, 2020 Issa Rice 22 Comments

Exercise statement

Show that for every real number $x$ there is exactly one integer $N$ such that $N \leq x < N+1$ . (This integer is called the integer part of $x$ , and is sometimes denoted $N = \lfloor x\rfloor$ .)

Hints

Use Proposition 4.4.1.

How to think about the exercise

Here’s one tempting way to think about this exercise. If $x$ is a real number, we can write $x = \mathrm{LIM}_{n\to\infty} a_n$ for some Cauchy sequence $(a_n)_{n=1}^\infty$ of rational numbers. For each rational number $a_n$ , we can use Proposition 4.4.1 to find some unique integer $N_n$ such that $N_n \leq a_n < N_n + 1$ . These inequalities hold for all $n$ , so we can take formal limits by Corollary 5.4.10 to get $\mathrm{LIM}_{n\to\infty} N_n \leq x \leq \mathrm{LIM}_{n\to\infty} (N_n+1)$ . Writing $N := \mathrm{LIM}_{n\to\infty} N_n$ we have $\mathrm{LIM}_{n\to\infty} (N_n+1) = N+1$ by Definition 5.3.4. So we have $N \leq x \leq N+1$ . Now we have two cases. If $x \ne N+1$ then we have $N \leq x < N+1$ . If $x = N+1$ then we have $N+1 \leq x < N+2$ . Does this prove the existence of the integer we seek? The problem is that we did not show that $(N_n)_{n=1}^\infty$ is a Cauchy sequence or that it converges to an integer. And in fact, we cannot in general show this. Consider the sequence $((-1)^n \frac1n)_{n=1}^\infty = (-1, 1/2, -1/3, 1/4, -1/5, \ldots)$ . This is a Cauchy sequence that defines the real number $0$ . What is the corresponding $(N_n)_{n=1}^\infty$ for this sequence? It is $(-1, 0, -1, 0, -1, \ldots)$ which is not Cauchy (it is not $0.5$ -steady). The problem is that $((-1)^n \frac1n)_{n=1}^\infty$ keeps oscillating around zero in smaller and smaller distances, so there is never a single point after which the sequence stays on one side of zero. And since $N_n$ can take on only integer values, its oscillations are integer-valued oscillations, which are far too big to be Cauchy.

Model solution 1

Since $x$ is a real number, we can write $x = \mathrm{LIM}_{n\to\infty} a_n$ for some Cauchy sequence $(a_n)_{n=1}^\infty$ of rational numbers. The sequence $(a_n)_{n=1}^\infty$ is Cauchy, so it is eventually $1/2$ -steady. This means we can find some natural number $N$ such that $|a_j - a_k| \leq 1/2$ for all $j,k\geq N$ . Since $N\geq N$ , we can fix $k$ to be $N$ . Thus we have $|a_j - a_N| \leq 1/2$ for all $j\geq N$ . Expanding this out using Proposition 4.3.3(c) we get $-1/2 \leq a_j - a_N \leq 1/2$ , and adding $a_N$ to each expression we obtain $a_N - 1/2 \leq a_j \leq a_N + 1/2$ , which holds for all $j\geq N$ .

Now we define a new sequence $(b_n)_{n=1}^\infty$ by $b_n := a_N$ if $n < N$ and $b_n := a_n$ if $n \geq N$ . This new sequence is a Cauchy sequence which is equivalent to $(a_n)_{n=1}^\infty$ because the two sequences are eventually the same (see proof of Lemma 5.3.14 in the book for a similar argument). Also by definition of $(b_n)_{n=1}^\infty$ , we have $a_N - 1/2 \leq b_j \leq a_N + 1/2$ for all $j \geq 1$ . Since $a_N - 1/2$ and $a_N + 1/2$ are constant rational numbers, they automatically define Cauchy sequences of rationals, which means we can apply Corollary 5.4.10 to conclude that $a_N - 1/2 \leq x \leq a_N + 1/2$ .

(Here you might wonder why we define a new sequence $(b_n)_{n=1}^\infty$ rather than just using $(a_n)_{n=N}^\infty$ , i.e. the original sequence cut off at $N$ . The theory can be developed in either way, but in the book, while sequences have arbitrary starting index $m$ , if you look at the definition of Cauchy sequences (5.1.8) it has a fixed starting index of $0$ (although Tao is inconsistent and also uses a starting index of $1$ at times). I think he did this because the formal limit notation $\mathrm{LIM}$ has no place to specify a starting index, and it’s simpler to assume all sequences have the exact same indices (which allows you to do things like comparisons, define sequence equivalence straightforwardly, etc.). If some Cauchy sequence starts at $5$ but another one starts at $0$ , then you’d have to change a bunch of the definitions to insert phrases like “for all $n$ greater than the max of the starting indices”. So, if we’re playing by the formal rules and being pedantic, then our sequence has to start at $0$ or $1$ , so that’s why I decided to define a whole new sequence. You might also wonder why we can’t use a shifted sequence $(a_{N+j})_{j=1}^\infty$ . This also works, but it will be a little bit more work to show that it’s equivalent to the original sequence $(a_n)_{n=1}^\infty$ . You basically need to show that $|a_j - a_{N+j}|$ goes to $0$ as $j$ goes to infinity. It shouldn’t be too hard but it’s not trivial, whereas showing $(a_n)_{n=1}^\infty$ and $(b_n)_{n=1}^\infty$ are equivalent is trivial since after $N$ the two sequences are literally the same. Thanks to Stephen for discussions about these subtleties!)

Since $a_N$ is a rational number, we can apply Proposition 4.4.1 to find some integer $M$ such that $M \leq a_N < M+1$ . Combining the inequalities we have so far, we get

$\begin{aligned}M-1 &< M-1/2 \\ &\leq a_N - 1/2 \\ &\leq x \\ &\leq a_N + 1/2 \\ &< (M+1) + 1/2 \\ &< M+2\end{aligned}$

The important point is that we have $M-1 < x < M+2$ . Now we just have to hunt down $x$ by using order trichotomy:

If $x < M$ then $M-1 \leq x < M$ .
If then we have two cases:
- If $x < M+1$ then $M \leq x < M+1$ .
- If $x \geq M+1$ then $M+1 \leq x < M+2$ .

In every case, we have found an integer that works, so this completes the existence part of the proof.

To show uniqueness, we can repeat the same steps as in the proof of Proposition 4.4.1 (search “uniqueness”). The same steps work thanks to Proposition 5.4.7.

Model solution 2

Here’s the sketch of a slightly different proof (just the existence part, since the uniqueness part isn’t much work). This one I think is harder to follow than the previous solution, but you might be interested in it if you happened to come up with a proof that’s more similar to this one than the previous one.

We can write $x = \mathrm{LIM}_{n\to\infty} a_n$ for some Cauchy sequence $(a_n)_{n=1}^\infty$ of rational numbers.

The idea is that because $(a_n)_{n=1}^\infty$ is Cauchy, we can eventually get the values of the sequence in some interval like $[a_N - \varepsilon, a_N + \varepsilon]$ . Now as we make $\varepsilon$ smaller (in particular, make $\varepsilon$ smaller than $1/2$ so that the width of the interval is less than $1$ ), the value of $N$ changes. Now we can ask, for a small $\varepsilon$ , does $[a_N - \varepsilon, a_N + \varepsilon]$ straddle an integer?

If it doesn’t straddle an integer, then we can let $M:=\lfloor a_N -\varepsilon\rfloor$ be the lower bound.

On the other hand, if $[a_N - \varepsilon, a_N + \varepsilon]$ does straddle an integer, things get more complicated.

Now $x$ could land to the left, to the right, or on top of $M$ . If $x=M$ , then we can take $M$ to be the integer. If $x\ne M$ , then the sequences $(a_n)_{n=1}^\infty$ and $(M)_{n=1}^\infty$ are not equivalent, so there exists some $\delta > 0$ such that for all $N\geq 1$ there is some $n \geq N$ such that $|a_n-M| > \delta$ . Since $(a_n)_{n=1}^\infty$ is Cauchy, it is eventually $\delta/2$ -steady. So there is some $N'$ such that $|a_j - a_k| \leq \delta/2$ for all $j,k\geq N'$ . Now for this $N'$ , we can find some $n \geq N'$ such that $|a_n - M| > \delta$ . Since $n \geq N'$ , we have $|a_j - a_n| \leq \delta/2$ for all $j \geq N'$ . This means that if $a_n > M$ then the integer $M$ will work, and if $a_n < M$ then $M-1$ will work.

For instance, if $a_n > M$ then using the inequalities above, we can show that $M < M + \delta/2 < a_n - \delta/2 \leq a_j$ for all $j \geq N'$ . So we can “take limits” using Corollary 5.4.10 to see that $M < M+\delta/2 \leq x$ . We already know that $x < M+1$ , so this case is done.

The important part is that we do not want to have the “tail” $(a_j)_{j=N}^\infty$ of the sequence to keep oscillating about $M$ ; that would mean we can’t make up our minds about whether $M$ or $M-1$ is the lower bound. To get around this problem, we need to stake out some point $a_n$ and say that $a_n$ is far enough away from $M$ and also that all of the elements of the tail are close enough to $a_n$ . So we get a cloud of points on exactly one side of $M$ , which lets us decide between $M$ and $M-1$ .