Proving the Least Upper Bound Axiom

[Surlethe]

A long time ago (last March, actually), Kuroneko and I discussed defining the real numbers in this thread. I've since been working on and off on a document to try to make the discussion accessible to someone who's unfamiliar with symbolic logic.

Unfortunately, it's not done; in the course of writing it, I thought it would be a good exercise to derive the basic axioms of analysis from the definition of the real numbers. Most of them are straightforward; of those that aren't immediately so, trichotomy was handled in the above thread, but I'm having trouble with the Least Upper Bound Axiom (for any non-empty subset E of the reals, if it is bounded above, then its supremum exists).

This is what I've put together so far, and I'm wondering if anyone can help correct me or set me straight; I feel like I'm missing a simple proof.

Let E be a non-empty subset E of R, the real numbers. By assumption, (∃Ω)(∀x∈E)Ω>x. Since Ω = {O_n} is real, it is Cauchy; thus, (∀ε>0)(∃N∈ℕ)(n,m>N→|a_n-a_m|<ε). Choose an ε -- call it ε_1 -- and pick the associated O_k.

Now, choose ω = {o_n} s.t. ω is still a strict upper bound of E, but ω<Ω. Note that this is possible because (∀x∈E)(Ω>x), and the reals are dense. (ω<Ω)→(∃ε>0)(∃N∈ℕ)(n>N→O_n-o_n>ε. The fact the tails do not converge togeter, in turn, indicates that you may choose some o_k<O_k. Do so.

Now, choose another strict upper bound ω' of E such that ω'<ω. Apply the preceding argument to choose an o'_k<o_k. Rinse and repeat ad infinitum.

Now, let us examine the sequence we've constructed. φ = {O_k, o_k, o'_k, o''_k, ... } has the property that it is strictly decreasing. It also has the property that (∀x∈E)(∀α>x)(φ<α) because, by construction, the tail of φ converges beneath that of α. Therefore, φ is less than any upper bound of E; (∀x∈E)(φ≥x), by construction. Since {o_k} is a strictly decreasing sequence of rational numbers, it must converge to φ; we have established the existence of sup(E).

[Wyrm]

A long time ago (last March, actually), Kuroneko and I discussed defining the real numbers in this thread. I've since been working on and off on a document to try to make the discussion accessible to someone who's unfamiliar with symbolic logic.

I remember...

Unfortunately, it's not done; in the course of writing it, I thought it would be a good exercise to derive the basic axioms of analysis from the definition of the real numbers. Most of them are straightforward; of those that aren't immediately so, trichotomy was handled in the above thread, but I'm having trouble with the Least Upper Bound Axiom (for any non-empty subset E of the reals, if it is bounded above, then its supremum exists).

This is what I've put together so far, and I'm wondering if anyone can help correct me or set me straight; I feel like I'm missing a simple proof.

Let E be a non-empty subset E of R, the real numbers. By assumption, (∃Ω)(∀x∈E)Ω>x. Since Ω = {O_n} is real, it is Cauchy; thus, (∀ε>0)(∃N∈ℕ)(n,m>N→|a_n-a_m|<ε). Choose an ε -- call it ε_1 -- and pick the associated O_k.

What conditions does O_k fulfill?

Now, choose ω = {o_n} s.t. ω is still a strict upper bound of E, but ω<Ω.

What if Ω is the least upper bound of E (who says that E contains its supremum)? Then ω cannot fulfill these conditions, so your ω does not exist. Indeed, I think that you have to prove that if Ω is not the LUB of E, then some ω fulfills your conditions.

[Kuroneko]

et E be a non-empty subset E of R, the real numbers. By assumption, (∃Ω)(∀x∈E)Ω>x. Since Ω = {O_n} is real, it is Cauchy; thus, (∀ε>0)(∃N∈ℕ)(n,m>N→|a_n-a_m|<ε). Choose an ε -- call it ε_1 -- and pick the associated O_k. Now, choose ω = {o_n} s.t. ω is still a strict upper bound of E, but ω<Ω. Note that this is possible because (∀x∈E)(Ω>x), and the reals are dense. (ω<Ω)→(∃ε>0)(∃N∈ℕ)(n>N→O_n-o_n>ε. The fact the tails do not converge togeter, in turn, indicates that you may choose some o_k<O_k. Do so. ... Rinse and repeat ad infinitum.

Of course the reals are dense. Every set is dense in itself. This is poorly worded, but there's a deeper problem.

Now, let us examine the sequence we've constructed. φ = {O_k, o_k, o'_k, o''_k, ... } has the property that it is strictly decreasing. It also has the property that (∀x∈E)(∀α>x)(φ<α) because, by construction, the tail of φ converges beneath that of α.

What if E = {x in R: x<0}, Ω = Ω^0 = 1 and Ω^n_k = 1/44+1/n and one just happens to be picking an ω from the set {Ω^n} during the iterations of the above procedure? This satisfies the conditions given for ω, but there resulting sequence is merely a sequence of monotone decreasing upper bounds, never even approaching the least upper bound of zero.

What if Ω is the least upper bound of E (who says that E contains its supremum)? Then ω cannot fulfill these conditions, so your ω does not exist. Indeed, I think that you have to prove that if Ω is not the LUB of E, then some ω fulfills your conditions.

No need--it can be assumed, since if Ω is already the least upper bound, there is nothing to do.

---

We defined defined a real number ζ to be a Cauchy sequence of rationals, ζ:N→Q. There exist sequences of rationals (a_k), (b_k), (c_k) such that (a_k) and (b_k) are respectively monotone increasing and decreasing, and a_k ≤ b_k ≤ c_k and [c_k-a_k]→0 as k→inf, then b_k is Cauchy. Hence, β = (b_k) is a real number. This analogoue of the squeeze theorem is fairly useful for what you want to do.

It is not too difficult to verify that if a set of real numbers E is bounded from above by a real η, then it is bounded by some rational, which can be picked from the range of η. Pick x_0 in E and define ζ(0) = x_0(0) and ξ(0) = r. Now, for each k>0, let y_k = [ζ(k-1)+ξ(k-1)]/2, and define ζ(k) = {y_k, (∃x∈E)(x≥y_k); ζ(k-1), otherwise}, ξ(k) = {y_k, if (∀x∈E)(x≤y_k); ξ(k-1), otherwise}. By trichotomy, either ζ(k) > ζ(k-1) or ξ(k) < ξ(k-1), and so by construction [ξ(k)-ζ(k)]→0. The application of the above "squeeze theorem" should now be obvious in constructing the least upper bound σ.

This should get you started. Proving that the above construction works as desired is not too difficult. The intuitive idea is that is a purported supremum α is will be outside [ζ(k),ξ(k)] for some k if it is different from σ, causing it to either not be an upper bound or not the lowest upper bound.

[Surlethe]

I remember...

You were in it, too, for a little bit. You got out, though; you're not as dense as I am.

What conditions does O_k fulfill?

The ε_1 you pick for O_k has to be less than 2ε, where this new ε is the one in (∃ε>0)(∃N∈ℕ)(n>N→O_n-o_n>ε. I think. Does that make sense?

Now, choose ω = {o_n} s.t. ω is still a strict upper bound of E, but ω<Ω.

What if Ω is the least upper bound of E (who says that E contains its supremum)? Then ω cannot fulfill these conditions, so your ω does not exist. Indeed, I think that you have to prove that if Ω is not the LUB of E, then some ω fulfills your conditions.

A contingency I neglected; thank you. If Ω is the least upper bound of E, then you're done. Same goes with any of the ωs -- if there doesn't exist any ω^(n)<ω^(n-1), then you've got your LUB right there, and the proof is done. If Ω is not the LUB, then, because the reals are dense, there exists some ω<Ω which is also an upper bound; I think I said that.

[Wyrm]

What conditions does O_k fulfill?

The ε_1 you pick for O_k has to be less than 2ε, where this new ε is the one in (∃ε>0)(∃N∈ℕ)(n>N→O_n-o_n>ε. I think. Does that make sense?

Yeah. That does.

Now, choose ω = {o_n} s.t. ω is still a strict upper bound of E, but ω<Ω.

What if Ω is the least upper bound of E (who says that E contains its supremum)? Then ω cannot fulfill these conditions, so your ω does not exist. Indeed, I think that you have to prove that if Ω is not the LUB of E, then some ω fulfills your conditions.

A contingency I neglected; thank you. If Ω is the least upper bound of E, then you're done. Same goes with any of the ωs -- if there doesn't exist any ω^(n)<ω^(n-1), then you've got your LUB right there, and the proof is done. If Ω is not the LUB, then, because the reals are dense, there exists some ω<Ω which is also an upper bound; I think I said that.

Good boy. (Sorry, but I'm a bit more pedantic than the usual proofer.) Alright, so you got yourself a sequence of monotonically decreasing numbers. However, as the Black-Cat says:

What if E = {x in R: x<0}, Ω = Ω^0 = 1 and Ω^n_k = 1/44+1/n and one just happens to be picking an ω from the set {Ω^n} during the iterations of the above procedure? This satisfies the conditions given for ω, but there resulting sequence is merely a sequence of monotone decreasing upper bounds, never even approaching the least upper bound of zero.

How do you go about pulling down the upper bounds to the true least upper bound? Hint: think about where the LUB lies in relation to any x∈E and any other upper bound of E.

[Surlethe]

Of course the reals are dense. Every set is dense in itself. This is poorly worded, but there's a deeper problem.

Fair enough. ∀a,b∈R∃c∈R a<b<c. Better?

What if E = {x in R: x<0}, Ω = Ω^0 = 1 and Ω^n_k = 1/44+1/n and one just happens to be picking an ω from the set {Ω^n} during the iterations of the above procedure? This satisfies the conditions given for ω, but there resulting sequence is merely a sequence of monotone decreasing upper bounds, never even approaching the least upper bound of zero.

To patch this up, could you note that if the chosen sequence converges to some Ψ, and if there exists some upper bound α<Ψ, would it be possible to buck the tail of Ψ and start choosing beneath it? Or do I need to mess around with how the εs are chosen? Or is this simply unpatchable?

We defined defined a real number ζ to be a Cauchy sequence of rationals, ζ:N→Q. There exist sequences of rationals (a_k), (b_k), (c_k) such that (a_k) and (b_k) are respectively monotone increasing and decreasing, and a_k ≤ b_k ≤ c_k and [c_k-a_k]→0 as k→inf, then b_k is Cauchy. Hence, β = (b_k) is a real number. This analogoue of the squeeze theorem is fairly useful for what you want to do.

It is not too difficult to verify that if a set of real numbers E is bounded from above by a real η, then it is bounded by some rational, which can be picked from the range of η. Pick x_0 in E and define ζ(0) = x_0(0) and ξ(0) = r. Now, for each k>0, let y_k = [ζ(k-1)+ξ(k-1)]/2, and define ζ(k) = {y_k, (∃x∈E)(x≥y_k); ζ(k-1), otherwise}, ξ(k) = {y_k, if (∀x∈E)(x≤y_k); ξ(k-1), otherwise}. By trichotomy, either ζ(k) > ζ(k-1) or ξ(k) < ξ(k-1), and so by construction [ξ(k)-ζ(k)]→0. The application of the above "squeeze theorem" should now be obvious in constructing the least upper bound σ.

Yes; since ξ→ζ and ζ<σ<ξ, σ exists and is the least upper bound. The point of this construction project is to pick a sequence which is guaranteed to remain in E, a sequence guaranteed to remain outside of E, and then continue the sequence with halfway points depending on whether or not the halfway point is inside or outside of E, correct?

Good boy. (Sorry, but I'm a bit more pedantic than the usual proofer.) Alright, so you got yourself a sequence of monotonically decreasing numbers.

Bah. People like you are the reason I lost so many points in my algebraic structures class! In any case, I'm fairly certain the problem Kuroneko pointed out is not insurmountable; I'm just not sure which direction I have to go.

[Kuroneko]

Fair enough. ∀a,b∈R∃c∈R a<b<c. Better?

Yes.

To patch this up, could you note that if the chosen sequence converges to some Ψ, and if there exists some upper bound α<Ψ, would it be possible to buck the tail of Ψ and start choosing beneath it? Or do I need to mess around with how the εs are chosen? Or is this simply unpatchable?

Let E = {x in R: x < 0}, Ω(n;k) = 1/44 + 2^{-n} + 2^{-n-k}. Then pick ω's in {Q(n;k): k>0}, giving the limiting Ψ_n = lim_{k→inf} Ω(n;k) = Ω(n+1;0). Even after countably many iterations of this extra step, no convergence to the least upper bound will occur. No inductive method is possible, although I suppose that if one proves this result for countable bounded sets of reals E, one might be able to extend it to arbitrary sets of bounded reals through transfinite induction...

Hmm, one doesn't actually need transfinite induction. If the rationals are already known to be dense in the reals, one might say F = {p in Q: p≥x for all x in E}, which is easy to prove nonempty (if E is bounded above by a real, it is bounded above by a rational). This reduces everything to the countable rational case, but picking a monotone decreasing sequence in F that is eventually less than or equal to every member of F seems to be no simpler than the approach already posted. Perversely, F is the upper Dedekind cut of the supremum of E if F does not have a minimum. This problem is simple with Dedekind cuts--if we're using lower Dedekind cuts, lub E is the union of all members of E excepting the maximal element of this union if it exists.

Yes; since ξ→ζ and ζ<σ<ξ, σ exists and is the least upper bound. The point of this construction project is to pick a sequence which is guaranteed to remain in E, a sequence guaranteed to remain outside of E, and then continue the sequence with halfway points depending on whether or not the halfway point is inside or outside of E, correct?

Yes, except that strictly speaking ξ will be E iff E contains its own supremum. In that case, ζ = ξ and ζ(k) = ξ(k) for all k>N for some N. That's not really a problem; the idea is simply to have an a sequences of closed intervals of radii tending to 0 of where the supremum must be (and where the tail of any representation of the supremum must be).

Erratum: picking ζ(0) should have been done differently. Simply pick ζ(0) to be any rational less than some member x_0 of E rather than x_0(0). Proving that there is a rational less than any given real is easy.

[Surlethe]

Let E = {x in R: x < 0}, Ω(n;k) = 1/44 + 2^{-n} + 2^{-n-k}. Then pick ω's in {Q(n;k): k>0}, giving the limiting Ψ_n = lim_{k→inf} Ω(n;k) = Ω(n+1;0). Even after countably many iterations of this extra step, no convergence to the least upper bound will occur. No inductive method is possible, although I suppose that if one proves this result for countable bounded sets of reals E, one might be able to extend it to arbitrary sets of bounded reals through transfinite induction...

What does the extra step do? I'm not sure I entirely follow what you're doing by adding a term dependent on k to the sequence.

Hmm, one doesn't actually need transfinite induction. If the rationals are already known to be dense in the reals, one might say F = {p in Q: p≥x for all x in E}, which is easy to prove nonempty (if E is bounded above by a real, it is bounded above by a rational). This reduces everything to the countable rational case, but picking a monotone decreasing sequence in F that is eventually less than or equal to every member of F seems to be no simpler than the approach already posted.

How is this for constructing a sequence out of F?

We are given some upper bound Ω = {o_n}. Choose some ε_0 such that Ω-ε_0 is also an upper bound. Continue to subtract ε_0 n_0+1 times, until Ω-(n_0+1)ε_0 is no longer an upper bound of E. Return to Ω-(n_0)ε_0, and find a new ε_1 s.t. Ω-(n_0)ε_0-ε_1 is an upper bound of E. Repeat the process n_1 times, until you can go no lower and remain an upper bound of E. Now, take Ω-\sum_{i=0}^{1}(n_i)(ε_i) - ε_2, and repeat, assigning n_2 as the maximum number of times you can subtract ε_2 from Ω-\sum_{i=0}^{1}(n_i)(ε_i).

Continue to repeat the process as outlined above. Consider the sequence of partial sums S_n = Ω-\sum_{i=0}^{n}(n_i)(ε_i). Pick a term from the tail of each S_j so that the sequence is of picked terms is decreasing (this is possible since the S_j are strictly decreasing). Each term you've chosen is from F; since the sequence of partial sums is constructed so that if there exists any upper bound α<S_n, new terms will be added, it converges to the infimum of F, and so does the sequence of fractions from F.

[Kuroneko]

What does the extra step do? I'm not sure I entirely follow what you're doing by adding a term dependent on k to the sequence.

The original procedure allows picking a monotone decreasing sequence of upper bounds that does not converge to the least upper bound. Since this sequence will always be bounded below, it must converge to some Ψ, although the fact of this convergence may be difficult to prove at this point. You proposed a modification that in effect 'restarts' the procedure when such an event occurs, to which the above is a counterexample. For the first pass of the procedure, let Ω = 2 and pick ω's in {Ω(0;k): k>0}, giving a monotone decreasing sequence convergent to Ψ_0 = Ω(1;0). Picking new upper bounds below Ψ_0 in {Ω(1;k): k>0}, and so on. In this way, a countable number of monotone decreasing sequences is generated, each sequences with all terms lesser than those of the previous, and yet still without convergence to the least upper bound.

We are given some upper bound Ω = {o_n}. Choose some ε_0 such that Ω-ε_0 is also an upper bound. Continue to subtract ε_0 n_0+1 times, until Ω-(n_0+1)ε_0 is no longer an upper bound of E. Return to Ω-(n_0)ε_0, and find a new ε_1 s.t. Ω-(n_0)ε_0-ε_1 is an upper bound of E. Repeat the process n_1 times, until you can go no lower and remain an upper bound of E. Now, take Ω-\sum_{i=0}^{1}(n_i)(ε_i) - ε_2, and repeat, assigning n_2 as the maximum number of times you can subtract ε_2 from Ω-\sum_{i=0}^{1}(n_i)(ε_i).

Make sure the Archimedean property has already been proven, although that should be fairly simple. But there doesn't seem to be anything here that relies on F = {p in Q: p≥x for all x in E} at all; it might as well be the set of all reals greater than or equal to everything in E rather than a set of rationals.

Continue to repeat the process as outlined above. Consider the sequence of partial sums S_n = Ω-\sum_{i=0}^{n}(n_i)(ε_i). Pick a term from the tail of each S_j so that the sequence is of picked terms is decreasing (this is possible since the S_j are strictly decreasing). Each term you've chosen is from F; since the sequence of partial sums is constructed so that if there exists any upper bound α<S_n, new terms will be added, it converges to the infimum of F, and so does the sequence of fractions from F.

Hold on. Did you prove that every monotone bounded sequence converges independently of the completeness (least upper bound) theorem?

How is this for constructing a sequence out of F?

If the rationals are known to be dense in the reals already, there's actually an easier way that I did not think of at the time of my previous post. Since F = {p in Q: p≥x for all x in E} is countable, let f:N→F be bijective. If F has a minimal element, let ζ(k) = min F for all k. Otherwise, let ζ(0) = f(0) and ζ(k+1) in F∩{p in Q: p<min{ζ(k),p<f(k)}}, which will never be empty or else min{ζ(k),f(k)} is a minimal element of F for some k. Hence, for any given p in F, some tail of ζ is less than or equal to p.

[Surlethe]

The original procedure allows picking a monotone decreasing sequence of upper bounds that does not converge to the least upper bound. Since this sequence will always be bounded below, it must converge to some Ψ, although the fact of this convergence may be difficult to prove at this point. You proposed a modification that in effect 'restarts' the procedure when such an event occurs, to which the above is a counterexample. For the first pass of the procedure, let Ω = 2 and pick ω's in {Ω(0;k): k>0}, giving a monotone decreasing sequence convergent to Ψ_0 = Ω(1;0). Picking new upper bounds below Ψ_0 in {Ω(1;k): k>0}, and so on. In this way, a countable number of monotone decreasing sequences is generated, each sequences with all terms lesser than those of the previous, and yet still without convergence to the least upper bound.

Okay. I was thinking about that last night when I went to bed; I just didn't see what you were saying. You could keep going forever with sequences of sequences of sequences of ... of sequences, and it should keep getting closer, but I couldn't see a way to guarantee that this huge nested monster converges to the LUB.

Make sure the Archimedean property has already been proven, although that should be fairly simple.

The Archimedean property is independent of the existence of the real numbers, correct? Because all you have to do is take n∈Z, assume for contradiction it's the largest integer, and then add one. Then, for any given real r, add one, and there will be an integer between r and r+1.

But there doesn't seem to be anything here that relies on F = {p in Q: p≥x for all x in E} at all; it might as well be the set of all reals greater than or equal to everything in E rather than a set of rationals.

The point is to choose elements of F from the sequence of partial sums being constructed, and the partial sums are being constructed in such a way as to (hopefully) guarantee the chosen elements of F are going to converge to the least upper bound of E.

Hold on. Did you prove that every monotone bounded sequence converges independently of the completeness (least upper bound) theorem?

Perhaps it's not necessary to have the sequence of partial sums converge, since we can show the fractions from the tails of the partial sums converge (it's guaranteed because the ε_j are monotone decreasing and null, and the term from jth tail is chosen to be less than ε_j; thus, for any ε, find ε_k<ε, and pick N>k).

However, for the sake of the exercise, let {a_n} be a sequence of real numbers which is monotone decreasing and bounded below by some real number B. Assume, for contradiction, {a_n} diverges. Then it either oscillates or becomes infinitely large, positively or negative, at some point. It cannot oscillate because it is monotone decreasing; and since {a_0} bounds it above, and B bounds it below, {a_n} cannot blow up in either direction. Therefore, it must converge. To show that its convergence exists, choose some q_n from the tail of each a_n; {q_n} is now a sequence of rationals which is monotone decreasing and bounded below. Would I be correct in stating here that the convergence of the sequence guarantees that it's Cauchy, and therefore {a_n} converges to some real number?

If the rationals are known to be dense in the reals already, there's actually an easier way that I did not think of at the time of my previous post. Since F = {p in Q: p≥x for all x in E} is countable, let f:N→F be bijective. If F has a minimal element, let ζ(k) = min F for all k. Otherwise, let ζ(0) = f(0) and ζ(k+1) in F∩{p in Q: p<min{ζ(k),p<f(k)}}, which will never be empty or else min{ζ(k),f(k)} is a minimal element of F for some k. Hence, for any given p in F, some tail of ζ is less than or equal to p.

That's elegant.

[Kuroneko]

Okay. I was thinking about that last night when I went to bed; I just didn't see what you were saying. You could keep going forever with sequences of sequences of sequences of ... of sequences, and it should keep getting closer, but I couldn't see a way to guarantee that this huge nested monster converges to the LUB.

Right. It remains the case even after a countable infinity of these 'metasteps'.

The Archimedean property is independent of the existence of the real numbers, correct? Because all you have to do is take n∈Z, assume for contradiction it's the largest integer, and then add one. Then, for any given real r, add one, and there will be an integer between r and r+1.

No. The Archimedean property may be simple, but it is not that trivial. It fails, for example, in the surreal numbers, which include the real numbers as a subfield. In the surreals, ω>r for every real r, and 1/ω<1/n for every positive integer n.

The point is to choose elements of F from the sequence of partial sums being constructed, and the partial sums are being constructed in such a way as to (hopefully) guarantee the chosen elements of F are going to converge to the least upper bound of E.

They do, but proving that they do is another matter.

Perhaps it's not necessary to have the sequence of partial sums converge, since we can show the fractions from the tails of the partial sums converge (it's guaranteed because the ε_j are monotone decreasing and null, and the term from jth tail is chosen to be less than ε_j; thus, for any ε, find ε_k<ε, and pick N>k).

If you're referring to the Cauchy criterion, yes, I think it is possible to prove the sequence of partial sums is Cauchy, but that is not the same as proving that it converges.

However, for the sake of the exercise, let {a_n} be a sequence of real numbers which is monotone decreasing and bounded below by some real number B. Assume, for contradiction, {a_n} diverges. Then it either oscillates or becomes infinitely large, positively or negative, at some point.

Why? If one has a monotone decreasing sequence in the rationals, it is not the case that it must become infinitely negative, e.g., let x(n) = 1/n + sum_{k=1}^n[ 1/k² ], so that x(n)→π²/6 and therefore does not converge in the rationals.

It cannot oscillate because it is monotone decreasing; and since {a_0} bounds it above, and B bounds it below, {a_n} cannot blow up in either direction. Therefore, it must converge. To show that its convergence exists, choose some q_n from the tail of each a_n; {q_n} is now a sequence of rationals which is monotone decreasing and bounded below.

You're begging the question. It's even explicit in the last sentence.

[SWPIGWANG]

Okay, I'm just an foolish engineering student here. Does anyone here know any resources on the web that teaches basic and fundamental math proofs and stuff? The creation of the number line from first principles and stuff.

[Talanth]

I could mail you my pure-math notes if you want. I'm sure we at least touched on this proof, if not went through it step by step, but I'll admit I didn't understand much. I'm doing Mathematical Physics: Pure is fun to dabble in but nothing I'd use with much confidence.

[Ender]

I need to go back to college for more math

[Kuroneko]

Surlethe, if you want to make your approach work, make sure the sequence of partial sums consists only of rational numbers as is Cauchy. Then it becomes a real number by definition. Your approach as it stands now does not work because it depends on properties of real numbers that have no yet been proven. The convergence of monotone bounded sequences in the reals depends on the least upper bound axiom (here, theorem), rather than the other way around.

[Surlethe]

No. The Archimedean property may be simple, but it is not that trivial. It fails, for example, in the surreal numbers, which include the real numbers as a subfield. In the surreals, ω>r for every real r, and 1/ω<1/n for every positive integer n.

The Archimedean property is (∀r∈R)(∃n∈ℕ)(n>r), correct? It follows from the upper bound theorem, but doesn't it also follow anyway as a consequence of the infinitude of the natural numbers?

Why? If one has a monotone decreasing sequence in the rationals, it is not the case that it must become infinitely negative, e.g., let x(n) = 1/n + sum_{k=1}^n[ 1/k² ], so that x(n)→π²/6 and therefore does not converge in the rationals.

...

You're begging the question. It's even explicit in the last sentence.

Ah; I see. I was assuming the convergence of a sequence is independent of whether or not the item the sequence converge to exists.

If you're referring to the Cauchy criterion, yes, I think it is possible to prove the sequence of partial sums is Cauchy, but that is not the same as proving that it converges.

That was my mistake.

Surlethe, if you want to make your approach work, make sure the sequence of partial sums consists only of rational numbers as is Cauchy. Then it becomes a real number by definition. Your approach as it stands now does not work because it depends on properties of real numbers that have no yet been proven. The convergence of monotone bounded sequences in the reals depends on the least upper bound axiom (here, theorem), rather than the other way around.

That has been the idea; I've just been excessively sloppy in the execution, hence the failure of the proofs offered thus far. Okay. Here's what I have so far in trying to show this (and it makes a bit more sense, now that I have the notion convergence and existence of some convergee are separate out of my head):

If it can be shown that the partial sums themselves are Cauchy, it follows that a sequence of rationals from the tail of each partial sum is Cauchy: let S_n = (q_{n_j}); then, given that S_n is Cauchy and each (q_{n_j}) is Cauchy, to pick a q_{n_k} from the tail of each S_n, simply let k>J, where J corresponds to an accuracy of ε/4 (to ensure the tails don't overlap).

Now, it need only be shown that S_n is Cauchy. To do this, recall the definition of Cauchy: (∀ε>0)(∃N∈ℕ)(n,m>N→|S_n - S_m|<ε). Recall also that the sequence (ε_j) is null and monotone decreasing, and that S_k = Ω - \sum_{α=0}^{k}(n_α)(ε_α). Since |S_n - S_m| = |\sum_{α=m}^{n}(n_α)(ε_α)| (assuming, arbitrarily, that n≥m), given ε, choose N such that lim_{k→∞}|\sum_{α=N}^{k}(n_α)(ε_α)|<ε (limits are well-defined, I think, since they do not depend on the existence of the number the function tends to). Therefore, because n≥m>N, |\sum_{α=m}^{n}(n_α)(ε_α)|<lim_{k→∞}|\sum_{α=N}^{k}(n_α)(ε_α)|<ε, which establishes the required inequality. Is that better, or is there some fundamental hole I'm still missing?

[Kuroneko]

The Archimedean property is (∀r∈R)(∃n∈ℕ)(n>r), correct? It follows from the upper bound theorem, but doesn't it also follow anyway as a consequence of the infinitude of the natural numbers?

That is the Archimedean property, yes, but notice that it is a statement about the real numbers as well as the natural numbers, so it cannot follow from the properties of natural numbers only. The field of surreal numbers is one example where it fails. As another, consider the 'pseudo-long line' L = Z×R, where the real number r are identified with (0,r), and order is defined lexicographically: (a,b)≤(c,d) iff (a<c) or (a=c and b≤d). Then it is not the case that (∀r∈L)(∃n∈N)(n>r).

Ah; I see. I was assuming the convergence of a sequence is independent of whether or not the item the sequence converge to exists.

To converge is to converge to something, by definition.

If it can be shown that the partial sums themselves are Cauchy, it follows that a sequence of rationals from the tail of each partial sum is Cauchy: let S_n = (q_{n_j}); then, given that S_n is Cauchy and each (q_{n_j}) is Cauchy, to pick a q_{n_k} from the tail of each S_n, simply let k>J, where J corresponds to an accuracy of ε/4 (to ensure the tails don't overlap).

That's fine, but it is better to simply begin with a rational S_n, i.e., start with a rational bound Ω (which exists, since given a real upper bound Ω, there is a rational upper bound Ω'≥Ω) and postulate that the ε_n are all rational. Then all of the partial sums are rational and the lowest upper bound is the real number defined by the rational sequence S_n itself.

Now, it need only be shown that S_n is Cauchy. To do this, recall the definition of Cauchy: (∀ε>0)(∃N∈ℕ)(n,m>N→|S_n - S_m|<ε). Recall also that the sequence (ε_j) is null and monotone decreasing, and that S_k = Ω - \sum_{α=0}^{k}(n_α)(ε_α). Since |S_n - S_m| = |\sum_{α=m}^{n}(n_α)(ε_α)| (assuming, arbitrarily, that n≥m), ..

The summation should be from m+1 to n, but is otherwise correct.

... given ε, choose N such that lim_{k→∞}|\sum_{α=N}^{k}(n_α)(ε_α)|<ε (limits are well-defined, I think, since they do not depend on the existence of the number the function tends to).

This limit is not guaranteed to be well-defined without deeper results of analysis, but what you're trying to do can be easily restated as (∀k>N)[\sum_{α=N}^{k}(n_α)(ε_α) < ε]. This must hold for some N or else the original summation Σ(n) tends to infinity, which cannot be the case because Ω-Σ(n ) is bounded from below by any member of E. If ε_α are postulated to be in a specific form (say, ε_α = 1/2^α, which will also allow n_α = 0, unlike in your construction), then a specific bound for N can be given, but this is not necessary.

Therefore, because n≥m>N, |\sum_{α=m}^{n}(n_α)(ε_α)|<lim_{k→∞}|\sum_{α=N}^{k}(n_α)(ε_α)|<ε, which establishes the required inequality. Is that better, or is there some fundamental hole I'm still missing?

Yes, although again, the limit should be done away with as above. To be formally correct, one should prove that this construction actually gives the lowest upper bound, but that's rather obvious from the fact that ε_α→0.

[Shroom Man 777]

I'm sorry if this is just spam, but holy shit! I can't understand anything and, if I didn't know any better, I'd think you guys were just spouting jibberish to make the rest of us think you're geniuses.

My god, you people are smart! Kuroneko, are you some kind of uber-professor or something?

[Kuroneko]

I can't understand anything and, if I didn't know any better, I'd think you guys were just spouting jibberish... Kuroneko, are you some kind of uber-professor or something?

Er, no. There are some books considered undergraduate-level that do the same kind of thing, e.g., Rudin's Principles of Mathematical Analysis. Although Rudin constructs the reals with Dedekind cuts rather than Cauchy sequences, which makes the least upper bound property extremely easy to prove (at the cost of making arithmetic theorems harder, however--proving the ordinary properties of multiplication requires many special cases), it is analogous. The second edition is better than the third in this regard, since in the third, construction of the reals is relegated to an appendix, whereas in the second, it plays a central role. I recommend that book to anyone interested in real analysis. Or, as a very inexpensive alternative that skips the construction of the reals, Kolmogorov and Fomin's Introductory Real Analysis.

[LMSx]

This thread needs some flames.

No shit sherlock, if Ψ_0 = Ω(1;0), and Ω=-3, of course it will be the upper bound of G.


You goddamn troglodyte.

[Surlethe]

If anyone's curious, here's an approximate translation of our conversation:

Surlethe: So, I've been thinking about proving the least upper bound axiom from the definition. How about this proof? Pick some set such that it's bounded above. You're given the upper bound. Now, pick a smaller upper bound. Keep doing this so that they converge. You've just made a real number; this is the least upper bound, since it's smaller than anything else.

Wyrm: What if there are no upper bounds smaller than the given one?

Surlethe: Then you're done.

Kuroneko: That proof doesn't work at all, because the upper bounds could get closer to some upper bound that isn't small enough. For example, the set {-3} has a least upper bound of -3; however, the sequence 1/n, n>0, are all upper bounds, but they don't converge to the least upper bound.

Incidentally, you can prove the least upper bound theorem by picking a number in the generic bounded set, a number which is an upper bound, and making them both go toward the LUB by making a sequence out of the halfway points.

Surlethe: Ah. Hmm. What if I make a sequence of sequences of upper bounds?

Kuroneko: That doesn't work either. In fact, if you make a sequence of sequences of sequences of ... ad infinitem, you still can't guarantee convergence.

Surlethe: I don't quite get it. Here's a new proof idea, though: what if I take the given upper bound and subtract some small number so until it dips into the bounded set, and then go back a step and subtract a smaller number, ad nauseam? It should converge to a least upper bound.

Kuroneko: Hold on. Have you proven that a sequence that gets smaller and smaller and can't get infinitely small converges?

Oh, by the way, here's a very simple proof: make a bijection from the naturals to the set of rational upper bounds. Identify the minimal element of the set with the LUB (least upper bound), or, if it doesn't exist, always choose a smaller one. This goes to the LUB.

Surlethe: No, but here's a try: since a sequence that diverges has to either blow up or oscillate, if it doesn't oscillate and can't blow up, it must converge.

Kuroneko: That's circular.

Surlethe: ...

Kuroneko: If you want to make it work, you have to prove that your original sequence of subtractions gets closer and closer together as the number you're subtracting gets smaller.

Surlethe: Oh, right. Here's a try. The partial sums get closer together, so, given a particular choice of a small number, you can always find some term in my sequence beyond which the terms are closer together than that small number.

Kuroneko: Okay, that pretty much works. There are a few details off, though.

Kuroneko's latest reply pretty much wrapped up any loose ends in the conversation, though I have been thinking idly about using something along these lines, or at least with the definition of the reals as equivalence classes of Cauchy sequences of rational numbers, to try and show that the reals are equivalent to the power set of the rationals.

[Kuroneko]

Kuroneko's latest reply pretty much wrapped up any loose ends in the conversation, though I have been thinking idly about using something along these lines, or at least with the definition of the reals as equivalence classes of Cauchy sequences of rational numbers, to try and show that the reals are equivalent to the power set of the rationals.

If you want something different from the standard Cantor diagonalization, try filling in gaps in the following. If you do not wish to prove the general theorem, replace 'metric space X' with 'reals R' with the standard Euclidean metric d(x,y) = |x-y|. Unfortunately, it requires some additional concepts, but overall it is a standard result in analysis. If I recall correctly, it is an exercise in Rudin and proven explicitly in Kolmogorov and Fomin.

Let (X,d) be a metric space.
-- Def: The open ball of radius ρ and center x is defined as B(x;ρ) = {y in X: d(x,y)<ρ}. In the reals, open balls are just open intervals with center x.
-- Def: A point x in X is isolated iff B(x;ε) = {x} for some ε>0. The reals have no isolated points.
-- Def: The closure of Y is defined as cl(Y) = {x in X: B(x;ε)∩Y≠φ for every ε>0}. In other words, x in cl(Y) means that every open ball about x always contains some points of Y. For example, if Y is the half-open inteval (0,1], then cl(Y) = [0,1]. For the rationals, cl(Q) = R.
-- Def: The interior of Y is defined as int(Y) = {x in X: B(x;ε)⊂Y for some ε>0}. In other words, x in int(Y) iff some open ball about x is fully contained in Y. For example, if Y = (0,1], then int(Y) = (0,1). For the rationals, int(Q) = φ.
-- Def: Y is nowhere dense in X iff int(cl(Y)) is empty.

Thm 1: Let (X,d) be a complete metric space. Defining the closed ball B'(x;ρ) = {y in X: d(x,y)≤ρ}, a sequence B_n = B'(x_n,r_n) of closed balls in X with r_n→0 and B_{n+1}⊂B_n has nonempty intersection ∩B_n. The converse also holds, but is unnecessary here.
Thm 2: Given a complete metric space (X,d), X is not the union of countably many nowhere dense sets. This can be proven by reductio ad absurdum to the previous theorem.
Corollary: Every complete metric space with no isolated points is uncountable.

The truly beautiful thing about this result is that it requires nothing but the topological properties of the space--no particular dependence on representation (e.g., decimal expansions) is required. There is another version that is entirely topological without any mention of a metric at all. The latter version can be found, e.g., in Munkres' Topology.

Edit: Fixed statement of Thm 1 (B_{n+1}⊂B_n).