Is my proof correct?

  • Thread starter quasar987
  • Start date
  • #1
quasar987
Science Advisor
Homework Helper
Gold Member
4,780
12

Homework Statement


I tried finding a proof for the "Bolzano-Weirstrass property" of R before looking at the actual proof and I came up with something different.

The actual thing to prove is: "Every bounded sequence in R has a subsequence that converges to some points in R."


The Attempt at a Solution



Consider a sequence [itex]f:\mathbb{N}\rightarrow \mathbb{R}[/itex] bounded by M. Let's peek at [itex]f(\mathbb{N})[/itex]. Is it finite?

If yes, then look at the preimage of every element of [itex]f(\mathbb{N})[/itex]. There will be one that is infinite and by the well-ordering property of N, we can thus extract a constant subsequence from f.


If no, then it is denumerable and thus can be put in bijection with the set of rational numbers in (0,1) (or [0,1) or (0,1] or [0,1] depending on whether the sup and inf of [itex]f(\mathbb{N})[/itex] actually are in [itex]f(\mathbb{N})[/itex]). Also, let the bijection respect order. We can now talk of the elements of [itex]f(\mathbb{N})[/itex] as rationals in (0,1).

I will now refer to the set of rationals in (0,1) as Q'. So chose some [itex]x_1[/itex] in Q' and look at its preimage [itex]f^{-1}(x_1)[/itex]. By the well-ordering of N, we can choose the smallest integer of that set, call it [itex]n_1[/itex], and let [itex]a_1=f(n_1)[/itex] be the first element of our subsequence.

Because Q' is dense in itself, we can also select an [itex]x_2[/itex] in Q' with [itex]x_1<x_2<1[/itex]. Look at the preimage of [itex]x_2[/itex]. If all the elements of [itex]f^{-1}(x_2)[/itex] are lesser than [itex]n_1[/itex], then dump [itex]x_2[/itex] and choose some [itex]x_2'[/itex] in Q' with [itex]x_2<x_2'<1[/itex] and look at its preimage, etc. This "rechoosing" of [itex]x_2[/itex] cannot last forever. Actually, it can last at most [itex]n_1[/itex] times! So when we get an [itex]x_2[/itex] whose preimage contains an integer larger than [itex]n_1[/itex], call that smallest such integer [itex]n_2[/itex] and let [itex]a_2=f(n_2)[/itex] be the second element of our subsequence.

Generate all elements in this way. The result is a monotone increasing subsequence of f that is bounded by M and thus, by the completeness of R, converges to some point in R.
 
Last edited:

Answers and Replies

  • #2
matt grime
Science Advisor
Homework Helper
9,395
3
Consider a sequence [itex]f:\mathbb{N}\rightarrow \mathbb{R}[/itex] bounded by M. Let's peek at [itex]f(\mathbb{N})[/itex]. Is it finite?

If yes, then look at the preimage of every element of [itex]f(\mathbb{N})[/itex]. There will be one that is infinite and by the well-ordering property of N, we can thus extract a constant subsequence from f.
The well-ordering of N has nothing to do with anything here. If the sequnce x_n is equal to x for inifnitely many different n then obviously that subsequence is convergent



If no, then it is denumerable and thus can be put in bijection with the set of rational numbers in (0,1) (or [0,1) or (0,1] or [0,1] depending on whether the sup and inf of [itex]f(\mathbb{N})[/itex] actually are in [itex]f(\mathbb{N})[/itex]). Also, let the bijection respect order.
You have not proved that this can be done.

We can now talk of the elements of [itex]f(\mathbb{N})[/itex] as rationals in (0,1).
Why would this help?

I will now refer to the set of rationals in (0,1) as Q'. So chose some [itex]x_1[/itex] in Q' and look at its preimage [itex]f^{-1}(x_1)[/itex]. By the well-ordering of N, we can choose the smallest integer of that set, call it [itex]n_1[/itex], and let [itex]a_1=f(n_1)[/itex] be the first element of our subsequence.

Because Q' is dense in itself, we can also select an [itex]x_2[/itex] in Q' with [itex]x_1<x_2<1[/itex]. Look at the preimage of [itex]x_2[/itex]. If all the elements of [itex]f^{-1}(x_2)[/itex] are lesser than [itex]n_1[/itex], then dump [itex]x_2[/itex] and choose some [itex]x_2'[/itex] in Q' with [itex]x_2<x_2'<1[/itex] and look at its preimage, etc. This "rechoosing" of [itex]x_2[/itex] cannot last forever. Actually, it can last at most [itex]n_1[/itex] times! So when we get an [itex]x_2[/itex] whose preimage contains an integer larger than [itex]n_1[/itex], call that smallest such integer [itex]n_2[/itex] and let [itex]a_2=f(n_2)[/itex] be the second element of our subsequence.

Generate all elements in this way. The result is a monotone increasing subsequence of f that is bounded by M and thus, by the completeness of R, converges to some point in R.
Actually you're not far off getting a proof, though what you've done isn't correct, or apparently useful, nor even necessarily possible. In fact it certainly isn't possible in general, to map an arbitrary sequence bijectively to Qn[0,1] and preserve order. Note that you've also shown that every sequence contains a monotone increasing subsequence. Doesn't that worry you?
 
  • #3
MathematicalPhysicist
Gold Member
4,309
217
matt grime said:
Actually you're not far off getting a proof, though what you've done isn't correct, or apparently useful, nor even necessarily possible.
if that's not hilarious than i really don't know what is. (-:
 
  • #4
MathematicalPhysicist
Gold Member
4,309
217
and quasar, one way to prove this is by using the fact that any sequence has a subsequence which is monotone.
you only need to prove this, i leave it to you to prove, btw, this theorem at least where im learning is covered in the first weeks of calculus 1, which is in the first year of studying, i thought you are in your advanced years, you learn maths as undergrad, dont you?
 
  • #5
matt grime
Science Advisor
Homework Helper
9,395
3
if we take the method above and remove the extraneous appeal to reordering etc, what is the OP doing? He's attempting to find a monotone increasing sequence. Now, this is the start of the proof I believe LQG alludes to: you try to find a clever way to show there is an increasing sequence, and that if this method fails, then it must do so because there is a decreasing sequence. Actually, the method I have in mind makes you attempt to find a decreasing sequence, and if you can't do that it's because there is an increasing subsequence.

Note that all these references to monotone are unnecessary and wrong: the constant sequence does not have a monoton increasing subsequence; it does not have any monotone subsequences.
 
  • #6
MathematicalPhysicist
Gold Member
4,309
217
well it depends on your definitions.
what you refer to in your last statement is of strictly monotone as it's defined in the literature.
 
  • #7
quasar987
Science Advisor
Homework Helper
Gold Member
4,780
12
Did you say matt that we can always put a sequence in bijection with Qn[0,1] but not always make that bijection to preserve order?

Why is that? (when can we, when can't we?)
 
  • #8
Office_Shredder
Staff Emeritus
Science Advisor
Gold Member
3,907
181
quasar, if you have a bijection that preserves order, it means f(1) is the smallest rational number.
 
  • #9
quasar987
Science Advisor
Homework Helper
Gold Member
4,780
12
Whaaat? :smile:

Say f(n)=a_n is a sequence. Also suppose that the inf of f(N) is in f(N) but not the sup. Now let's try to put f in bijection with Qn[0,1) and preserve order.

I will map the inf to 0. Then mmh. Yes I see... it kindda has to do with the fact that Qn[0,1) is dense in itself doesn't it?
 
  • #10
matt grime
Science Advisor
Homework Helper
9,395
3
Did you say matt that we can always put a sequence in bijection with Qn[0,1] but not always make that bijection to preserve order?
yes

Why is that? (when can we, when can't we?)
who knows and who cares, quite frankly.
 
  • #11
quasar987
Science Advisor
Homework Helper
Gold Member
4,780
12
What was your idea of a proof matt?

I my book, they let M be a bound for the sequence. Then look at [-M,M] and split it in half. At least one half contains infinitely many elements of the sequence. Call that half I_0. Choose an n0 such that x_n0 is in I_0. Cut I_0 in half, keep one half that contains infinitely many elements and call it I_1. Choose n1>n0 such that x_n1 is in I_1, etc.

I_k is of the form [a_k, b_k] with b_k - a_k = M/2^k. The sequence {a_k} is bounded by M and increasing so it converges to say, x. From there, showing that {x_n_k} converges to x too is only a triangle inequality away.
 
  • #12
NateTG
Science Advisor
Homework Helper
2,450
6
I_k is of the form [a_k, b_k] with b_k - a_k = M/2^k. The sequence {a_k} is bounded by M and increasing so it converges to say, x. From there, showing that {x_n_k} converges to x too is only a triangle inequality away.
Actually, it's very easy to show that [itex]I_k[/itex] is Cauchy since, for [itex]j>k[/itex], [itex]I_j[/itex] is within [itex]\frac{M}{2^k}[/itex], or to squeeze [itex]I_k[/itex] between [itex]a_k[/itex] and [itex]b_k[/itex] (which both converge - one is increasing bounded above, the other decreasing bounded below, and we know that they meet).

P.S. [itex]I[/itex] is probably a poor letter choice.

I think this is roughly the argument that Matt Grime had in mind:
Case I: Some point in the image of the sequence has an inifinite preimage. In this case, there is a constant subsequence.

Case II: There is no point in the image of the sequence that has an inifinite preimage.
Let [itex]f_0(\mathbb{N})[/itex] be the image of initial sequence.
Let [itex]a_0=\inf(f_0(\mathbb{N}))[/itex].
Since no point in image has an inifinte preimage, then there is some finite [itex]N_0[/itex] such that [itex]n\geq N_0 \rightarrow f_0(n) \neq a_0[/itex].
Then, for [itex]i>0[/itex], [itex]f_i(n)=f_{i-1}(n+N_{i-1})[/itex], [itex]a_i=\inf(f_i(\mathbb{N}))[/itex] and [itex]N_i[/itex] so that [tex]n \geq N_i \rightarrow f_i(n) \neq a_i[/tex].

Now, the [itex]a_i[/itex] are increasing and bounded above, so they must converge.
If [itex]a_i[/itex] is a subsequence of [itex]f_0[/itex] then we're done.
Otherwise, there is some [itex]f_i[/itex] so that [itex]\inf(f_i(\mathbb{N})) \notin f_i(\mathbb{N})[/itex] which (and there are a couple of steps here) means that there is a decreasing subsequence of [itex]f_0[/itex] that converges to the limit of the [itex]a_i[/itex].
 
Last edited:
  • #13
quasar987
Science Advisor
Homework Helper
Gold Member
4,780
12
This theorem comes in my book before the proof that Cauchy==>converges. And in fact it is the main ingredient in the proof that Cauchy==>converges!

I will read case II tomorrow, thanks!
 
  • #14
HallsofIvy
Science Advisor
Homework Helper
41,833
956
Here's a simple proof that every sequence contains a monotone sequence (not necessarily "strictly" monotone):

Let S be the set of all indices i such that "if j> i, then aj> ai".

Case 1: S is infinite.
In this case, we're done! {ai} for i contained in S is a (strictly) increasing sequence.

Case 2: S is either empty of finite.
Then there exist i1 larger than any member of S. Since i1 is larger than any member of S, it is not in S itself: there exist i2 in S, i2> i1 with [itex]a_{i_2}\le a_{i_1}[/itex]. Since i1> i2 it also is not in S and so there exist i3> i2 such that [itex]a_{i_3}\le a_{i_2}[/itex]. Continuing in that way we get a monontone (non-increasing) sequence.

If {an} is a bounded sequence, it has both upper and lower bounds so whether that mononotone sequence is increasing or decreasing, by "monotone convergence" (which is itself equivalent to "least upper bound property") that subsequence converges.
 

Related Threads on Is my proof correct?

  • Last Post
Replies
1
Views
921
  • Last Post
Replies
1
Views
961
  • Last Post
Replies
5
Views
2K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
1
Views
848
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
3
Views
585
  • Last Post
Replies
0
Views
1K
Replies
3
Views
744
Replies
6
Views
610
Top