Terence Tao, Analysis I, Ex. 5.5.2: Entry point needed

Question

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:

1. $(m-1)/(n+1)$ is not an upper bound and $m/(n+1)$ is not an upper bound.
2. $(m-1)/(n+1)$ is an upper bound and $m/(n+1)$ is not an upper bound.
3. $(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.

Answer 1

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.

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.

Answer 3

Put more formally, prove that, for $L, K, n \in \mathbb{Z}$, $n \ge 1$,

$$ \tag{1}\label{proposition} (L < K) \wedge (L < m \le K) \wedge (K/n \text{ is upper bound}) \wedge (L/n \text{ is no upper bound}) \Rightarrow (\exists m) (m/n \text{ is upper bound} \wedge (m-1)/n \text{ is no upper bound}) $$

Proof is by induction over $K - L$.

Base case ($K-L = 1$):

Choose $m = K$. Then $m/n$ is upper bound, and $(m-1)/n = L/n$ is lower bound, by assumption.

Induction step ($K_k - L_k = k \Rightarrow K_{k+1} - L_{k+1} = k + 1$):

Let $m_k$ be the integer in $(L_k, K_k]$ such that $m_k/n$ is an upper bound and $(m_k-1)/n$ is not. If $m_k$ was not in $(L_{k+1}, K_{k+1}]$, then either $m_k > K_{k+1}$ or $m_k \le L_{k+1}$.

But if $m_k > K_{k+1}$ then $(m_k - 1)/n \ge K_{k+1}/n$, violating the assumption that $K_{k+1}/n$ is an upper bound.

If, in turn, $m_k \le L_{k+1}$ then $m_k/n \le L_{k+1}/n$ which renders $m_k/n$ being no upper bound, violating the induction hypothesis.

Hence, there is an integer $m_k \in (L_{k+1}, K_{k+1}]$ such that $m_k/n$ is upper bound and $(m_k - 1)/n$ is not.

$\square$

In effect, this means that for every subset of the reals $E$ that has an upper bound there are integers $(m, n), n \ge 1$ such that $(\forall x \in E) \; m/n \ge x$ and $(\exists x \in E) \; x \ge (m - 1)/n$.

Answer 4

This answer is similar to that given by @kolewtt123. But emphasise the logic behind this question. One can easily generalise this proof to any other properties, as the logic behind it is loosely coupled to the property of upper bound.

Let $L, K\in \mathbb{Z}$ and $n\in \mathbb{Z}^+$ where $K/n$ is an upper bound of $E$ and $L/n$ is not. Let

$$P(m):\forall x\in E\quad \frac{m}{n}\ge x$$

Then $P(K)\land\lnot P(L)$ must be true.

We want to prove $\exists m\in\mathbb{Z}$ where $L < m\le K$ such that $P(m)\land\lnot P(m-1)$ is true. Suppose for the sake of contradiction, the statement above is false, i.e. $\forall m\in\mathbb{Z}$ where $L<m\le K$, $\lnot P(m)\lor P(m-1)$. Let

$$Q(m):\lnot P(m)\lor P(m-1)\equiv P(m)\implies P(m-1)$$

Notice that $Q(m)$ is false only if $P(m)$ is true and $P(m-1)$ is false, hence an implication. Knowing that $Q(m)$ is an implication should provide one some insight into how to apply induction. We shall prove $P(m)$ is true for all $L\le m\le K$.

For the base case, let $m=K$, $P(m)$ is true by assumption. Now suppose $P(m)$ is true for some $L<m\le K$, since $Q(m)$ is true, $P(m-1)$ is also true. This closes the induction and we get $P(m)$ for all $L\le m\le K$. Immediately, we can see that $P(L)$ is true, which contradicts $P(L)$ is false.

Hence, $\exists m\in\mathbb{Z}$ where $L<m\le K$ such that $\lnot Q(m)\equiv P(m)\land\lnot P(m-1)$.$\quad\square$