# Terence Tao least upper bound proposition 5.5.9 [closed]

I am trying to understand the idea of the proof. The idea is based on creating this decreasing sequence of upper bounds. In the sense that the limit must be the least upper bound ? The material is from page 135-136 of Terence Tao's book. My question is what is the idea of the proof.

• What is your question, exactly?
– AJY
Commented Jun 20, 2019 at 4:33
• My question is what is the idea of the proof.
– user682677
Commented Jun 20, 2019 at 4:55

(I'm not very good at pictures, so you'll have to use your imagination here.)

Imagine you have a non-empty set that's bounded above. Picture it plotted on a number line.

Now, imagine adding in marks along the number line, representing the integers. The Archimedean property shows that eventually the integer marks will leave the set behind (it is bounded above by $$M$$, and there is an integer larger than $$M$$).

Find the first integer mark so that the whole set lies to the left of this integer mark. This is the least integer upper bound on the set! In terms of Tao's proof, this is $$m_1$$.

Now, try the exercise again, but instead of marking integer points, mark the half-integer points. That is, included twice as many marks, including at all the integer points, as well as points like $$0.5, 1.5, 2.5, \ldots$$ In particular, you have now marked every number of the form $$\frac{m}{2}$$, where $$m \in \Bbb{Z}$$.

We can still do the same procedure: find the first mark so that the entire set lies to the left of this mark. That is, we find the least half-integer $$\frac{m}{2}$$ so that $$\frac{m}{2}$$ is an upper bound. So, we should find that $$\frac{m - 1}{2}$$ is not an upper bound. This $$m$$ is $$m_2$$ in the proof.

On the same token, we can subdivide as much as we like. If we divide the space between each consecutive integer into $$n$$ equal spaces, then we are putting marks at every number of the form $$\frac{m}{n}$$, where $$m \in \Bbb{Z}$$. We can then find a number $$m$$ such that $$\frac{m}{n}$$ is an upper bound, but $$\frac{m - 1}{n}$$ is not. This value of $$m$$ is called $$m_n$$.

So, we've now constructed a sequence of rational upper bounds $$\frac{m_n}{n}$$. The rest of the proof is devoted to showing that they are Cauchy, and their constructed limit is indeed the least upper bound.

It's not necessarily true that this sequence will be monotone decreasing. I have specific example for this: consider the set $$[0, 0.5]$$. Then (and you should verify this!), $$\frac{m_1}{1} = 1$$, the least integer upper bound. Further, $$\frac{m_2}{2} = \frac{1}{2}$$, the least half-integer upper bound (and the least upper bound, as it turns out). But next, $$\frac{m_3}{3} = \frac{2}{3}$$, the least third-integer upper bound, which is greater than $$\frac{m_2}{2}$$. So, the sequence need not be monotone decreasing, but it will still be Cauchy.

If you like, you can restrict your attention to $$n = 10^k$$. For $$k = 1$$, you're finding the least tenth-of-an-integer upper bound, for $$k = 2$$, you're finding the least hundredth-of-an-integer upper bound, etc. Essentially what you're doing is making your least upper bound more precise by orders of magnitude, and building the supremum's decimal expansion! In this case, because the number line is constantly being subdivided increasingly finely, you will indeed see $$m_{10^k} / 10^k$$ monotone-decreasing to the supremum.

• As an exercise, you may find it helpful to compute (with the help of a calculator) $m_1, m_2, m_3, m_4$ when $E = \{x \in \Bbb{Q} : x^2 < 2\}$. Verify, for $n = 1, 2, 3, 4$, that $\frac{m_n}{n}$ is an upper bound, but $\frac{m_n - 1}{n}$ is not, by finding an element of $E$ between $\frac{m_n - 1}{n}$ and $\frac{m_n}{n}$. Commented Jun 20, 2019 at 5:09
• That is perfect. Thank you so much. Your explanation is very good.
– user682677
Commented Jun 20, 2019 at 17:06
• Can you explain how we can construct such L ? I don't see it from the Archimedean property. The Archimedean property is that given $\epsilon > 0$ and $x > 0$ there exists integer M such that $\epsilon * M > x$.
– user682677
Commented Jun 20, 2019 at 18:18
• @Learner Consider $K$, the integer upper bound on $E$, and the fixed point $x_0 \in E$. Apply the Archimedean property to $x = \frac{K+1}{n} - x_0 \ge \frac{1}{n} > 0$. We also take $\varepsilon = \frac{1}{n}$. This yields an integer $M$ such that $\frac{M}{n} > \frac{K + 1}{n} - x_0$. Rearranging, $\frac{K+1-M}{n} > x_0$, and we let $L = K+1-M$. Commented Jun 21, 2019 at 0:41

The “idea” is that for every $$n$$, he selects $$m_n \in \mathbb{Z}$$ as the least integer such that $$m_n / n$$ is an upper bound for $$E$$. This means that $$(m_n - 1)/n$$ is not an upper bound. This effectively means that $$m_n / n$$ is the least upper bound among the rational numbers with denominator $$n$$. He then argues that the sequence $$(m_n/n)_{n \in \mathbb{N}}$$ converges to the least upper bound.