Terence Tao, Analysis I, Ex. 5.5.2: Entry point needed
Terence Tao, Analysis I, 3e, Exercise 5.5.2:
Let $E$ be a non-empty subset of $\mathbb{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$. Without using Theorem 5.5.9, show that there exists an integer $L < m \le K$ such that $m/n$ is an upper bound for $E$, but that $(m-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.)
This answer does not do the trick for me, since I'm looking for the proof by contradiction, equipped only with the set of propositions and theorems covered so far.
What I'm actually looking for is an entry point to the proof, since I find it quite hard to negate the assumption.
My attempt is to induct over $n$. Assume I have been able to prove the statement for $n = 1$, is the following a valid negation of the assumption?
For all integers in the range $(L, K]$, at least one of the following statements holds:
- $(m-1)/(n+1)$ is not an upper bound and $m/(n+1)$ is not an upper bound.
- $(m-1)/(n+1)$ is an upper bound and $m/(n+1)$ is not an upper bound.
- $(m-1)/(n+1)$ is an upper bound and $m/(n+1)$ is an upper bound.
If I were able to prove that there is an integer in the given range such that none of the above holds, am I done?
Theorem 5.5.9 (Existence of least upper bound). Let $E$ be a non-empty subset of $\mathbb{R}$. If $E$ has an upper bound, (i.e., $E$ has some upper bound $M$), then it must have exactly one least upper bound.
I went through another loop considering this comment of Steve Kass, but I ended up wondering why the proof needs induction at all:
Assume for all integers $m$ where $L < m \le K$ we have that $m/n$ and $(m-1)/n$ are upper bounds of $E$. Then $(m-1)/n = L/n$ is also an upper bound. But $L/n$ is no upper bound, by assumption. Assume $m/n$ and $(m-1)/n$ are no upper bounds. Then $m/n = K/n$ is also no upper bound. But $K/n$ is an upper bound, by assumption.
Hence, there is an integer in the range $(L, K]$ s.t. $m/n$ is an upper bound for $E$, and $(m-1)/n$ is not.
Let $A \subseteq \mathbb Z$ defined by $$ A = \{ m \in \mathbb Z \cap [L, K] \mid m/n \text{ is an upper bound of $E$}\} $$ Then $A$ is a non-empty ($K \in A$ by assumption) bounded below ($L$ is a lower bound) subset of $\mathbb Z$. As such, it has a least element ($A -L\subset \mathbb N$ is non-empty and $\mathbb N$ is well-ordered). Let $m$ be this least element. Then $m/n$ is an upper bound of $E$, but $(m-1)/n$ isn't, as $m$ is the least element of $A$. As $L/n$ is not an upper bound, we have $L < m \le K$ as wished.
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.