3

Let $E$ be a non-empty subset of $R$, let $n \geq 1$ be an integer, and let $L < K$ be integers. Suppose that $\frac{K}{n}$ is an upper bound for $E$, but that $\frac{L}{n}$ is not an upper bound for $E$. Show that there exists an integer $L < m \leq K$ such that $\frac{m}{n}$ is an upper bound for $E$, but that $\frac{m-1}{n}$ is not an upper bound for $E$.

The author has given the hint to use cntradiction and then induction to prove but I am not able to make any progress on this question.

It is a step in the proof of existence of least upper bound.

(Reference: Analysis 1, Terrence Tao, Exercise 5.5.2, page 121)

vivek kumar
  • 583
  • 1
    Just choose the smallest $m$ for which $m/n$ is an upper bound. (then automatically $(m-1)/n$ will not be an upper bound.) – coffeemath Sep 05 '15 at 14:16
  • 1
    @coffeemath I need to establish the existence of $m$ but choosing any $m$ will presuppose that $m$ exists. Moreover, this appears to be a general result and thus author has hinted at induction, but I am not sure on what to induct. Should I induct on $m$ or on $n$? – vivek kumar Sep 05 '15 at 14:21
  • 1
    Given $n$ you have only a finite number of $m$'s to look for the smallest one, no need for induction here. The smallest in a finite set exists always. Further, the smallest $m>L$, otherwise contradiction. – A.Γ. Sep 05 '15 at 14:57
  • 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:15
  • https://math.stackexchange.com/a/3327368/172142 – Max Herrmann Aug 26 '19 at 20:34

1 Answers1

2

If you want an inductive proof, you could set one up by defining $d=K-L$ so $d$ is a positive integer. The base case $d=1$ then lets you take $m=K,$ since then $m-1=L$ and the assumptions are that then $m/n$ is an upper bound but $(m-1)/n$ is not.

Now assume the statement is true for $K-L=d \ge 1$ and since we want to get to the case $d+1$ from this, define say $K'=K+1$ so that $K'-L=d+1.$ We are assuming now that $K'/n$ is an upper bound but $L/n$ is not. Two possibilities: First it may be that $(K'-1)/n=K/n$ is not an upper bound, in which case we finish by taking $m=K'$ in the statement, or else $K/n$ is an upper bound, in which case the inductive hypothesis applies and we get the required integer $m.$

[Note that to me it doesn't seem all that necessary to show this by induction...]

coffeemath
  • 29,884
  • 2
  • 31
  • 52
  • 1
    I found similar questions here http://math.stackexchange.com/questions/909303/a-question-about-a-proof-of-the-least-upper-bound-property-in-the-taos-real-a?rq=1. But this one uses the fact the LUB already exist. There is another similar question here http://math.stackexchange.com/questions/903624/for-every-n-there-exists-m-such-that-m-n-is-an-upper-bound-but-m-1-n-i?rq=1 . – vivek kumar Sep 06 '15 at 03:31
  • And here http://www.math.ucla.edu/~tao/resource/general/131ah.1.03w/week2.pdf (page no. 32) also he explains. What I could understand is that he uses the following strategy - Assume $m$ does not exist in $L \leq m \leq M $ that is m/n is not an upper bound of E. Now use induction to prove that K/n is not an upper bound. But this contradicts that K/n is an upper bound. This mean we need to induct on $m$. But I am not able to induct? – vivek kumar Sep 06 '15 at 03:41
  • @Vivekkumar There is no mention of the LUB in my inductive proof above. The only thing used is that either $j/n$ is an upper bound for $E$ or else it is not. But that is just logic, and it is all that gets used in the induction proof. – coffeemath Sep 06 '15 at 07:54