Problem 9 section 3.3 from Bartle

[issacnewton]

Here is the problem

Let A be an infinite subset of \(\mathbb{R} \) that is bounded above and let \( u= \mbox{sup }A \). Show that there exists an increasing sequence \( (x_n) \)with \( x_n\in A\) for all \(n\in\mathbb{N} \) such that \(u=\lim (x_n)\).

My try. Since A is infinite, it means \(A\neq \varnothing\). We can consider two cases here. Case 1 is when \( u\in A\). So we can construct a
constant sequence \( x_n=u \) which converges to u. Case 2 is when \(u \neq A\). Since \( A\neq \varnothing\), let \( x_1 \in A\). So we have
\( x_1 < u \). Since \( u= \mbox{sup }A \), there exists \( x_2\in A\) such that \(x_1 <x_2 \). Again \( x_2 < u \). So we can go on building the sequence. So consider the set \( \{x_n |n\in\mathbb{N} \} \). This is bounded below by \(x_1 \) and bounded above by \(u\) and its increasing, so by monotone convergence theorem, this is convergent and \( \lim(x_n)=\mbox{sup }\{x_n |n\in\mathbb{N} \} \). I think my reasoning is correct till this point. Now I need to prove that \( u=\lim (x_n)\). So I basically need to prove that
\[ \mbox{sup }\{x_n |n\in\mathbb{N} \}=u \]

I could prove that \( \forall n\in \mathbb{N} (x_n \leqslant u) \) using the way the sequence is constructed. But I am having trouble with proving that
if \( k < u \) there should exist some \( n_1 \in\mathbb{N} \) such that \( k< x_{n_1} \).

I have seen some proofs floating on the net. But didn't quite understand it. So wanted to post here.

 

[Plato2]

Here is the problem
Let A be an infinite subset of \(\mathbb{R} \) that is bounded above and let \( u= \mbox{sup }A \). Show that there exists an increasing sequence \( (x_n) \)with \( x_n\in A\) for all \(n\in\mathbb{N} \) such that \(u=\lim (x_n)\).

Does the question really say increasing, for it it does then that statement is false unless $\sup(A)\notin A$.
It should say non-decreasing or say $\sup(A)\notin A$.

 

[alexmahone]

Does the question really say increasing, for it it does then that statement is false unless $\sup(A)\notin A$.
It should say non-decreasing or say $\sup(A)\notin A$.

Some books use:
increasing to mean non-decreasing
strictly increasing to mean increasing

(This has caused considerable confusion between us in http://www.mathhelpboards.com/showthread.php?289-Alternating-series-test&p=1732#post1732. :D)

 

[issacnewton]

Hi Plato

here's the definition of the increasing sequence from Bartle ,3ed. Sequence \( x_n \) is said to be increasing if it satisfies the inequalities

\[ x_1\le x_2\le\cdots\le x_n \le x_{n+1} \le \cdots \]

I was thinking of doing logical manipulation on the problem, using contrapositive and such things. But from logical point of view, the statement is
quite complex. Sequence is a function from \(\mathbb{N} \) to \( A\). Then its increasing. Also there is a mention of limit in the statement. So to convert the statement in full logical language will be tedious if not impossible. So logical manipulations will be difficult. But the straightforward approach of constructing the desired sequence does not seem very difficult. So I need some help

 

[alexmahone]

I had posted the same question (I think) a while ago on MHB.

http://www.mathhelpboards.com/showthread.php?218-Supremum-problem

 

[Plato2]

I had posted the same question (I think) a while ago on MHB.
http://www.mathhelpboards.com/showthread.php?218-Supremum-problem

But my objection has to do with vocabulary.
If $A=[0,1]\cup\{2\}$ then $\sup(A)=2$
Now the only sequence of points of $A$ converging to $2$ looks like $a_n=2,~\forall n>N$
That is hardly increasing .
If anyone says so, that is an abuse of language.
What does increase mean?
If $x=2~\&~y=2$ is $y$ an increase of $x~?$

 

[alexmahone]

But my objection has to do with vocabulary.
If $A=[0,1]\cup\{2\}$ then $\sup(A)=2$
Now the only sequence of points of $A$ converging to $2$ looks like $a_n=2,~\forall n>N$
That is hardly increasing .
If anyone says so, that is an abuse of language.
What does increase mean?
If $x=2~\&~y=2$ is $y$ an increase of $x~?$

I agree that it is abuse of language. However at least 2 books: Bartle and my book Mattuck use it.

 

[issacnewton]

thanks for the input.

I came across the following proof of this in Kenneth Ross's Elementary Analysis.
The author is talking about the case 2, where \( u\notin A\)Let \( u=\mbox{sup }A \). Since \( u-1 \) is not an upper bound for A, there exists
\( x_1\in A\) such that \( u-1 < x_1 \). Since \( u\notin A\) , we have \( u-1 <x_1<u \).
Now \( \mbox{max}\{u-\frac{1}{2},x_1\} \) is not an upper bound for A, so there exists
\( x_2\in A\) such that \( \mbox{max}\{u-\frac{1}{2},x_1\} <x_2 \). Then we have
\( x_1<x_2 \) and \( u-\frac{1}{2} <x_2<u \).Now proceed by induction.( here I have
questions). Assume that \(x_1,x_2,\cdots,x_n \) have been selected in A so that
\( x_1<x_2<\cdots <x_n \) and \( u-\frac{1}{n} <x_n <u \). Then \( \mbox{max}\{u-\frac{1}{n+1},x_n\} \) is not an upper bound for A,so there exists
\( x_{n+1} \in A \) such that \( \mbox{max}\{u-\frac{1}{n+1},x_n\} < x_{n+1} \). Then
\( x_1<x_2<\cdots <x_{n+1} \) and \( u-\frac{1}{n+1} < x_{n+1} < u \). and therefore
the construction continues.So this shows that we can construct an increasing sequence
in A. Now \( \forall n\; (u-\frac{1}{n} < x_n < u) \). So using squeeze theorem or
sandwich theorem, we can see that \( \lim (x_n) = u \).Now I have some question regarding this proof. Ross uses induction. I think he is using
strong induction here. Now in strong induction, to prove the goal of the form
\( \forall n\in\mathbb{N} P(n) \), we decide to prove that
\( \forall n[(\forall k<n\;P(k))\to P(n)] \). So if he is using strong induction, what is
\( P(n) \), he is using ?thanks

 

[issacnewton]

I am just wondering if following \( P(n) \) would work here.
\[ P(n)\;:\; \exists (f(n)\wedge f(n+1)) [f(n)\in A \wedge f(n+1)\in A \wedge f(n)<f(n+1) < u] \]

So base case would be constructing two numbers, f(1) and f(2). And then we can go on using ordinary induction.

 

[issacnewton]

Here is the solution I have prepared. This is an existence proof. I am going to build the
sequence using induction. So let P(n) be the statement

\[ \exists\; f(n), f(n+1)\in A\left[\left\{u-\frac{1}{n}<f(n)<u\right\}\wedge \left\{u-\frac{1}{n+1}<f(n+1)<u\right\} \wedge\left\{f(n)<f(n+1)\right\}\right] \]

I am taking \( \mathbb{N}\) starting with 1. So the goal is to prove
\[ \forall n\in\mathbb{N}\; P(n) \]
Base Case: n=1. Since \( u-1\) is not an upper bound of A, there exists \(a\in A\)
such that \( u-1 <a \). Since \( u\notin A\) we have \( u-1<a<u \)
Let \( f(1)=a \). So
\( f(1)\in A\) and \( u-1<f(1) <u \). Now \(\max\{u-\frac{1}{2},f(1)\}\)
is not an upper bound for A, so there exists \(a_1\in A\) such that
\(\max\{u-\frac{1}{2},f(1)\} < a_1 \). Let \( f(2)=a_1\). So
\( f(2)\in A\) and since \( f(1) < a_1 \), we have \( f(1) < f(2) < u \),
and \( u-\frac{1}{2} < f(2) < u \) , which proves P(1).
Induction Case : Let \(n\geqslant 1\) be arbitrary. Suppose P(n). Which means,
we have \( f(n), f(n+1)\in A\) such that \( u-\frac{1}{n}<f(n)<u \) and
\( u-\frac{1}{n+1}<f(n+1)<u \) and \( f(n) < f(n+1) \). Now
\(\max\{u-\frac{1}{n+2},f(n+1)\}\) is not an upper bound of A, so
there exists \( a_2\in A\) such that \( \max\{u-\frac{1}{n+2},f(n+1)\}<a_2\).
Let \( f(n+2)= a_2\). Then \( f(n+2)\in A\) and \(f(n+1)<f(n+2) \). So
we have \( u-\frac{1}{n+2}< f(n+2)<u \). Which proves P(n+1). Hence by
induction, we construct a sequence \(\{f(1),f(2),\cdots \}\) in A which is strictly
increasing. Above proof also proves that \(\forall n\in\mathbb{N} [u-\frac{1}{n}<f(n)<u] \) ,
which means
\[ \forall n\in\mathbb{N} [u-\frac{1}{n}\leqslant f(n)\leqslant u]\cdots (1) \]
Now since \(\lim (u-\frac{1}{n})=u\) and \(\lim (u)=u\), using
squeeze theorem (or sandwich theorem), it follows that \(\lim\;f(n)=u \).

Well I had written the author (Ken Ross), showing him this proof of mine. I am quoting him.

Your sequence of propositions is inadequate and has been tripped up by the notation f(n). To avoid confusion, in your P(n) the functions should be called f_n. Let's consider S=[0,1] so that u=1.

The choices f_1(1)=0.9 and f_1(2)=0.95 verify P(1).


The choices f_2(2)=0.6 and f_3(2)=0.8 verify P(2).


Etc. For the induction construction, one needs to have the entire nondecreasing sequence up to the point in question. I don't see how to do this just based on the mathematical induction principle described in section 1. This is why the logic books deal with inductive constructions in a different careful way. It's a tricky issue.


Another way to see my problem with your propositions P(n) is this. I should be able to understand each P(n) on its own. If I were to look at only P(1) and P(3), I would get four values of f, and I would not even realize that f(2) and f(3) were related

I didn't understand him completely. Is there something wrong in my proof ?

 

[issacnewton]

I think Ross is using recursion and not induction. Recursion is used to construct or define something. Induction is used to prove the
statements which depend on natural number. And I think that recursive step need not be defined using simple mathematical operation
like addition. Recursive step can involve complicated construction of (n+1) th term assuming that n th term with the specified property
exists. So with this mind, Ross's proof makes sense.