# Verification of a proof from the book Analysis (by Terence Tao)

What a day trying to understand the proof of the least upper bound theorem in the Analysis by Terence Tao:

Well one exercise which is necessary to complete the proof says the following:

Let $$E$$ be a non-empty subset of $$R$$, let $$n \ge 1$$ be an integer, and let $$L < K$$ be integers. Suppose that $$K/n$$ is an upper bound for $$E$$, but that $$L/n$$ is not an upper bound for $$E$$. Show that there exists an integer $$L < m_n \leq K$$ such that $$m_n/n$$ is an upper bound for $$E$$, but that $$(m_n-1)/n$$ is not an upper bound for E. (Hint: prove by contradiction, and use induction. It may also help to draw a picture of the situation.)

My silly attempt is as follows:

Suppose for the sake of the contradiction that there is not $$m$$ between the integers $$L$$ and $$K$$ such that $$m/n$$ is an upper bound of $$E$$. This means that whenever $$(L+m-1)/n$$ is not an upper bound we must have that neither $$(L+m)/n$$ is an upper bound. Since $$(L+0)/n$$ is not an upper bound, thus we have that $$(L+1)/n$$ neither is. Then it is easy to use induction to show that $$(L+m)/n$$ is not an upper bound for every natural number $$^{(1)}$$. But $$\,0\le K-L\in \mathbb{N}$$ and then $$(\,L+(K-L)\,)/n = k/n$$ is an upper bound (by hypothesis) contradicting the claim that $$(L+m)/n$$ is not an upper bound for every natural number. This contradiction gives the proof.

$$^{(1)}$$ We may use induction to show $$(L+m)/n$$ is not an upper bound for every natural number. The claim clearly holds for $$m=0$$ as we have shown above. Now we assume that it holds for $$m$$. Thus, $$(L+m)/n$$ is not an upper bound for $$E$$ so $$(L+1+m)/n$$ is not an upper bound, which closes the induction

I'd like to know if my attempt is correct. I don't know is kinda silly. So, do you think the proof is correct?

• Commented Aug 7, 2019 at 0:13

Despite the complicated language, the question is just to prove that if $L<K$ are integers and $P$ is some property such that $P(K)$ holds but $P(L)$ does not hold, there exists an integer $m$ with $L<m\leq K$ such that $P(m)$ holds but not $P(m-1)$. The details of the property $P$ do not matter at all. This should be intuitively obvious: $m=\min\{\, i\in\Bbb Z\cap(L,K] \mid P(i) \,\}$ is well defined (the set contains$~K$ so it is nonempty, and it is finite) and works. If you really find this too informal to be convincing, do a proof by contradiction and induction as the book suggests. You did this, and your proof is correct.

• Thanks for you illustrative answer. Indeed my first thought was that since $M = \{\, i\in\Bbb Z\cap(L,K] \mid P(i) \,\}$ is nonempty an bounded below $M-L$ (I don't know if is correct call it the shifted version)is a subset of the natural numbers and has a minimum by the well ordering principle and it is unique. But I have not prove the WOP yet, so I tried by contradiction... but I think I used a circular argument... Commented Sep 16, 2013 at 7:23
• You proof is OK, it is not circular at all. Commented Sep 16, 2013 at 7:27
• Thanks for you kindness :) Commented Sep 16, 2013 at 7:30
• Mind explaining "This means that whenever $(L+m−1)/n$ is not an upper bound we must have that neither $(L+m)/n$ is an upper bound."? Where does that $(L+m-1)/n$ come from? Commented Aug 3, 2019 at 13:08
• @MaxHerrmann Don't know what you question has to do with my answer, as it applies to the OP. But FWIW, the argument there is by contradiction, and the negation of the condition "there exists .. such that $m_n/n$ is an upper bound.., but $(m_n-1)/n$ is not an upper bound" is (renaming the variable) "for every $k$ such that $k/n$ is an upper bound, $(k-1)/n$ is (also) an upper bound", which is equivalent (by contrapositive inside "for every") to "whenever $(k-1)/n$ is not an upper bound, neither is $k/n$". Apply that with $k=L+m$. Commented Aug 9, 2019 at 7:07

Let $$E$$ be a non-empty subset of real numbers. Let $$n \geq 1$$ be an integer, and let L < K be integers. Suppose that $$\frac{L}{n}$$ is not an upper bound and that $$\frac{K}{n}$$ is an upper bound for $$E$$. We need to show that there exists an integer $$L < m \leq K$$, such that $$\frac{m - 1}{n}$$ is not an upper bound and $$\frac{m}{n}$$ is an upper bound for the set $$E$$.

Suppose for the sake of contradiction, that for all integers $$m$$, $$L < m \leq K$$, the rational number $$\frac{m - 1}{n}$$ is an upper bound or $$\frac{m}{n}$$ is not an upper bound. Let $$m_{k}$$ denote the integer $$L + k$$. Then for the integer $$m_{1} = L + 1$$ we must have $$L < m_{1} \leq K$$, so that $$\frac{m_{1} - 1}{n}$$ is an upper bound or $$\frac{m_{1}}{n}$$ is not an upper bound. If $$\frac{m_{1} - 1}{n}$$ is an upper bound, then $$\frac{L}{n} = \frac{m_{1} - 1}{n}$$ is an upper bound, which contradicts the assumption that $$\frac{L}{n}$$ is not an upper bound. So we must have that $$\frac{m_{1}}{n}$$ is not an upper bound.

Now we show that $$\frac{m_{k}}{n}$$ is not an upper bound for all natural numbers $$k \geq 1$$ for which $$L < m_{k} \leq K$$. The previous argument shows that the base case $$k = 1$$ holds. Now suppose inductively that $$\frac{m_{k}}{n}$$ is not an upper bound for some natural number $$k$$, such that $$L < m_{k} \leq K$$. We need to show that $$\frac{m_{k + 1}}{n}$$ is not an upper bound.

By induction hypothesis $$\frac{m_{k}}{n}$$ is not an upper bound. If $$m_{k + 1} > K$$, then $$\frac{m_{k + 1}}{n}$$ is an upper bound because we would have that $$m_{k} \geq K$$, i.e. $$\frac{m_{k}}{n} \geq \frac{K}{n}$$, which contradicts the assumption that $$\frac{m_{k}}{n}$$ is not an upper bound. So we must have that $$L < m_{k + 1} \leq K$$. Then either $$\frac{m_{k}}{n}$$ is an upper bound or $$\frac{m_{k + 1}}{n}$$ is not an upper bound. The first alternative leads to contradiction with the assumption that $$\frac{m_{k}}{n}$$ is not an upper bound, so we must have that $$\frac{m_{k + 1}}{n}$$ is not an upper bound. This proves the claim for all $$k$$ such that $$L < m_{k} \leq K$$.

In particular, this implies that $$\frac{m_{k}}{n}$$ is not an upper bound for $$k$$ such that $$m_{k} = K$$. But this contradicts the fact that $$\frac{K}{n}$$ is an upper bound and finishes the proof.