My Proof is Correct?Verifying Bolzano-Weirstrass Property of R

[quasar987]

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.

 

[matt grime]

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?

 

[MathematicalPhysicist]

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. (-:

 

[MathematicalPhysicist]

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 I am 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, don't you?

 

[matt grime]

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.

 

[MathematicalPhysicist]

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.

 

[quasar987]

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?)

 

[Office_Shredder]

quasar, if you have a bijection that preserves order, it means f(1) is the smallest rational number.

 

[quasar987]

Whaaat?

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?

 

[matt grime]

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.

 

[quasar987]

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.

 

[NateTG]

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].

 

[quasar987]

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!

 

[HallsofIvy]

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 a_j> a_i".

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

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

If {a_n} 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.