Exercise 5.5.2

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$ .

4 thoughts on “Exercise 5.5.2”

Pingback: Exercise 5.5.3 | Tao Analysis Solutions
Karim Taha says:

July 10, 2020 at 3:20 pm

Why can’t we just argue by contradiction.

We suppose for the sake of contradiction that such an $m$ doesn’t exist, then for all $L<m \leq K$ $m/n$ is an upper bound for $E$ , or for all $L\leq m < K$ $m/n$ is not an upper bound for $E$ .
The first case contradicts that $m=L+1$ satisfies the required properties.
The second case contradicts that $m=K$ satisfies the required properties.
What is the need of induction in both Model answer 2 and 3 ?

LikeLike

1. Paul says:
  
  April 3, 2024 at 2:49 am
  
  Your negated statement is incorrect. The correct negation is presented in the first paragraph of Model solution 2.
  
  LikeLike
Karim Taha says:

July 10, 2020 at 3:36 pm

I mean why use induction, if we can use the fact that the logical negation of $\exists$ quantifier with some statement $P(x)$ is the $\forall$ quantifier with not $P(x)$ .

LikeLike