1

This is a problem discussed in Analysis 1 by Terence Tao.

$E$ is a non-empty set of Real numbers. $ n\geq 1$, $L,K$ are two integers such that $L<K$. Let $\frac{L}{n}$ is not an upper bound of $E$ but $\frac{K}{n}$ is an upper bound. It is required to prove that:

There exists an integer $m$ where $L<m \leq K$ such that $\frac{m}{n}$ is an upper bound for $E$ but $\frac{m-1}{n}$ is not.

Suppose $E=(0,1)$ and $n=2$. Let $L=1 ,K=3$ then $L,K$ satisfies the required properties and we can find $m$ as 2. Then we can verify the result. It is given as a hint to prove by contradiction.

So we can assume that There exist integers $ L,M$ satisfying the conditions but for every integer $m$ with $L<m \leq K$, $ \frac{m}{n}$ cannot be an upper bound for $E$ .That means there exists $ x \in E $ such that $x >\frac{m}{n}$ .

I can't proceed from this step. It is also given that we have to use induction.

Community
  • 1
Madhu
  • 1,695
  • Just consider the numbers ${ K \over n}, { K-1 \over n},..., { L+1 \over n}$. Take the smallest one that is an upper bound for $E$. – copper.hat Aug 20 '14 at 02:41
  • Related: https://math.stackexchange.com/questions/399216/constructive-proof-of-a-problem-from-the-book-analysis-by-terence-tao – Henry Aug 07 '19 at 00:14

1 Answers1

0

Define the set $ NE = \{n x \ | \ x \in E\} $. Now clearly $ x \le \frac {K}{n}$ for every $x \in E$ and hence $ nx \le K $ whence it follows that $K$ is an upper bound for $ NE $. Then $l = \sup NE$ exists.

Now consider the set $A = \{ n \in \Bbb N \ | n \ge l \ \} $. This set is non-empty since it contains $K$. By the Well-Ordering principle this set has a least element and call this, $m$.

Firstly,

$$\forall x\in E \;\; m \ge l \ge nx \implies x \le \frac m n \;\; \forall x\in E $$

Secondly, suppose $ \dfrac{m - 1}{n} $ is an upper bound for $E$. Then,

$$ \forall x \in E \;\; x \le \dfrac{m - 1}{n} \implies nx \le m - 1 $$

Then $m - 1$ is an upper bound for $NE$ and hence $l \le m - 1$. But then $m - 1 \in A$ and $m - 1 \lt m$ contradicting the choice of $m$. So there you have it.

I have not used induction but I have used the equivalent condition the Well-Ordering Principle.

Note all we have done here is to divide the real line into segments of size $\frac 1 n$. You can obviously do this. This gives an "index" if you will of the real line. Now the supremum of the set $E$ exists and is on the real line. But this must lie between two indices. That is $ \dfrac{m - 1}{n} \lt l \le \dfrac{m }{n}$.

Ishfaaq
  • 10,034
  • 2
  • 30
  • 57
  • This seems like overkill? – copper.hat Aug 20 '14 at 02:43
  • @copper.hat: Well I think it's exactly what you suggested above. But rigorous. This can be rewritten in about three lines. Just trying to be descriptive. – Ishfaaq Aug 20 '14 at 02:44
  • I understood the proof but in Tao's book Well ordering principle and supremum property is not discussed before this theorem.Actually this problems comes in the way of the proof of the theorem " Existence of Least upper bound" ( page 116 theorem 5.5.9) – Madhu Aug 21 '14 at 01:39
  • The Supremum is the Least Upper Bound. You can replace this phrase wherever I've used the word Supremum in the solution. Haven't read Tao's book. But I can guess the Well-Ordering Principle will not be introduced beyond the 100th page. Its pretty much part of the definition of $\Bbb N$. If you take the set of natural numbers to exist then implicitly you take on the W.O.P. – Ishfaaq Aug 21 '14 at 01:43