# A question about a proof of the "Least Upper Bound Property" in the Tao's Real Analysis notes

I am using Terence Tao's Real Analysis notes to self-learn Analysis 1. There is one thing in the proof of Theorem 27 (Least Upper Bound Property) in the “week 2” notes that I don’t understand (found here).

On page 32, it says that “there exists some natural number $i$ with $0\leq i \leq k$ such that $x_0+\frac{i}{n}$ is an upper bound for $E$, while $x_0+\frac{i-1}{n}$ is not an upper bound for E ……. then it is easy to use induction to show that $x_0+\frac{i}{n}$ is not an upper bound for E for any $0\leq i \leq k$".

I really don't understand this point. What is the induction hypothesis here? How should we consider $x_0+\frac{i-1}{n}$ is not an upper bound for E? Would anyone please tell me the specific process of this induction proof? Thank you very much.

We already know that $x_0-\dfrac{1}{n}$ is not a upper bound for $E$, while $x_0+\dfrac{K}{n}$ is an upper bound for $E$. Let's then prove that:

There exists a natural number $i$ with $0\leq i\leq K$ such that $x_0+\dfrac{i}{n}$ is an upper bound for $E$, but $x_0+\dfrac{i-1}{n}$ is not an upper bound for $E$.

Let's give two different proofs: One by induction (as in the text) and one using the well-order of natural numbers.

Proof 1 (Induction). Suppose no such $i$ existed, that is, for every natural number $0\leq i\leq K$, either both numbers $x_0+\dfrac{(i-1)}{n}$ and $x_0+\dfrac{i}{n}$ are upper bounds for $E$ or both of them are not upper bounds for $E$ (let's call this property $(*)$).

Let $$B=\left\{i\in\mathbb{N}:i>K\text{ or }x_0+\dfrac{i}{n}\text{ is not an upper bound for }E\right\}.$$ Let's show, by induction, that $B=\mathbb{N}$. First, notice that $0\leq 0\leq K$, but $x_0-\dfrac{0-1}{n}=x_0-\dfrac{1}{n}$ is not an upper bound for $E$, so $x_0+\dfrac{0}{n}$ is also not an upper bound for $E$ (by $(*)$), thus $0\in B$.

Now, suppose that $i\in B$. We have two cases:

1. If $i\geq K$, then $i+1>K$, so $i+1\in B$.

2. The second case is $i<K$. Then $i+1\leq K$, and $x_0+\dfrac{(i+1-1)}{n}=x_0+\dfrac{i}{n}$ is not an upper bound for $E$ (because $i\in B$), so $(*)$ again implies that $x_0+\dfrac{i+1}{n}$ is not an upper bound for $E$, so $i+1\in B$.

By induction, we proved that $B=\mathbb{N}$. In particular, since $K$ is not strictly larger than $K$, we have that $x_0+\dfrac{K}{n}$ is not an upper bound for $E$, a contradiction. Thus, there exists an $i$ with the desired properties.

Proof 2 (Well-ordering). Let $A=\left\{i\in\mathbb{N}:x_0+\dfrac{i}{n}\text{ is an upper bound for }E\right\}$. Notice that $K\in A$, so $A$ is nonempty and hence has a minimum element (by the Well-Ordering Principle). Let $i=\min A$. In particular, $i\leq K$ and $x_0+\dfrac{i}{n}$ is an upper bound for $E$. It remains only to show that $x_0+\dfrac{(i-1)}{n}$ is not an upper bound for $A$. Again we have two cases:

1. If $i=0$, then $x_0+\dfrac{i-1}{n}=x_0-\dfrac{1}{n}$ is not an upper bound for $E$ (as we know)$, as we wanted. 2. If$i\neq 0$, then$i-1$is a natural number which is lesser than the minimum of$A$, so$i-1\not\in A$, that is,$x_0+\dfrac{(i-1)}{n}$is not an upper bound for$E\$, as we wanted.

• Luiz Cordeiro, thank you very much. Both of your two proofs are straightforward and clear. I get whant I want. Commented Aug 26, 2014 at 6:39