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

Question

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?

Thanks in advance.

Answer 1

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.

Answer 2

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.