STEP III 2000 Q7 (Analysis)

OP

coffeym

Quite a nice question, despite using the idea that every bounded sequence converges, which I'm sure is not immediately obvious (i.e. easily provable) to an A-Level student. Your work looks fine to me, although I only gave it a quick look.

Hmm. The idea is intuitively obvious, but I have never thought about the proof. But I think you have a strange definition of "obvious" - there are quite a few results in mathematics which I think are "obvious" but rather difficult to prove! For example: you have two uncountable infinite sets, and you have an injective mapping in both directions. Intuitively, there should exist a bijective mapping, hence, the two sets have the same cardinality. But apparently this is very difficult to prove.

Reply 3

coffeym

10

Zhen Lin

Hmm. The idea is intuitively obvious, but I have never thought about the proof. But I think you have a strange definition of "obvious" - there are quite a few results in mathematics which I think are "obvious" but rather difficult to prove! For example: you have two uncountable infinite sets, and you have an injective mapping in both directions. Intuitively, there should exist a bijective mapping, hence, the two sets have the same cardinality. But apparently this is very difficult to prove.

Well that's the Schroder-Bernstein Theorem which is actually not that hard to prove, but yes I take your point (of course the sets need not be uncountable - for example this theorem is useful in proving

\mathbb{Q}

is countable by finding two injections between

\mathbb{N}

and

\mathbb{Q}

in both directions) . What I was trying to say was: in this question, they assume that you can see that an increasing sequence bounded above converges. Although that is plainly obvious using common sense, I'm one of these people who thinks students shouldn't be forced into using theorems they don't fully understand. Here, for example, you would need to do a reasonable amount of work on sequences and completeness to formulate a good proof of the statement, yet STEP examiners expect you to apply the result anyway.

Reply 4

coffeym

Quite a nice question, despite using the idea that every bounded sequence converges, which I'm sure is not immediately obvious (i.e. easily provable) to an A-Level student. Your work looks fine to me, although I only gave it a quick look.

I haven't looked at the question, but, as it stands on its own, that statement is not true. Surely you actually meant to type something else?
.

Reply 5

coffeym

10

Lusus Naturae

I haven't looked at the question, but, as it stands on its own, that statement is not true. Surely you actually meant to type something else?
.

Haha yes, MONOTONIC. Excuse me :wink:

Reply 6

Zhen Lin

Hmm. The idea is intuitively obvious, but I have never thought about the proof.The result (with the missing word monotone inserted) is only actually true over the real numbers, it's not true over the rationals. Which means any proof is "automatically" somewhat deeper than A-level. I also don't (personally) think it's so obviously true that a good A-level student should realise they can assume it.

I do agree with Coffeym here not liking this aspect of the question. Because it's probably the better students who will get to this part, think "It feels like this must be true. But I don't see how to prove it" (*), and either give up or spend lots of time worrying about it.

I have to say, if I was marking this, and someone actually wrote (*), I'd be inclined to give them bonus marks, even if they didn't complete the question. (I seem to recall hearing about something like this actually happening in the IMO: a student realised a problem needed a result that everyone had thought obviously true but was actually not at all obvious, and he got special credit for it spotting it even though he couldn't prove it).

Reply 7

OP

DFranklin

The result (with the missing word monotone inserted) is only actually true over the real numbers, it's not true over the rationals. Which means any proof is "automatically" somewhat deeper than A-level. I also don't (personally) think it's so obviously true that a good A-level student should realise they can assume it.

Hrm. I suppose the proof of this hinges on the fact that the reals are complete. Or is the proof equivalent to the fact that the reals are complete? Hmm.

If I may assume that the reals are complete, and if the result that every strictly increasing sequence (which is what we're dealing with in the context of this question) with an upper bound has a limit is a non-trivial corollary of that fact, how may I go about proving it?

Reply 8

To prove the "non-trivial corollary" for some bounded, increasing sequence,

a_n

,show that there exists an

a_N

such that

supA - a_N < \epsilon

, and show this implies

a_n \to supA

Reply 9

OP

Ah. Thank you. I had suspected something along those lines, but I thought it was verging on the tautological.

Reply 10

For your other question: We define a complete ordered field as an ordered field in which every nonempty set which is bounded above has a least upper bound. From this property we can derive a number of statements about sequences in complete ordered fields, including the one about bounded, increasing sequences (and also one about the Cauchy property). Such a statement was the focus of your other question. But can we say they are equivalent? Let

S

be a nonempty set. Because some function:

\mathbb{N} \to S

is increasing and bounded (i.e. is ordered), and it also converges, does that mean the ordered set is a complete field? Well, for it to be increasing and convergent, there must be some value which it converges to... but, unfortunately I cannot currently think how to finish this proof that they are equivalent. :blushing:

Maybe someone can clarify?
.

Reply 11

I think it would be sufficient to finish by saying that in some cases their increasing, bounded and convergent sequence tends to a limit, but in the extreme case that it gets as close as possible to the upper bound, it is necessary for the field to contain a least upper bound, so that all possible sequences which satisfy our definition of a limit do indeed have a limit, whether it be in S or, in the extreme case, the LUB of

S

.

\Box

Reply 12

Zhen Lin

Hrm. I suppose the proof of this hinges on the fact that the reals are complete. Or is the proof equivalent to the fact that the reals are complete? Hmm.What definition are you using of "complete"?

Reply 13

OP

I... have no idea. The only definition I know is the one that goes something like "the limit of every (Cauchy?) sequence in S is also in S".

Reply 14

Zhen Lin

I... have no idea. The only definition I know is the one that goes something like "the limit of every (Cauchy?) sequence in S is also in S".

Yeah - my definition would be "every Cauchy sequence converges" as well. I think Lusus has a different definition in mind though.

Reply 15

DFranklin

Yeah - my definition would be "every Cauchy sequence converges" as well. I think Lusus has a different definition in mind though.

I was working from "Every nonempty subset of R which is bounded above has a least upper bound."

Reply 16

I've not had time to do a detailed reply 'til now, but here goes...

Using the Cauchy Definition, it's not hard to show that "every bounded monotone sequence converges in R" implies R is complete. (N.B. the obvious example is when R is the reals, but it doesn't actually have to be).

Sketch proof: Any Cauchy sequence is bounded. And it's not too hard to show every bounded infinite sequence has a monotonic subsequence (it's not totally obvious, you might want to look it up). Then by assumption that subsequence converges, and then the Cauchy criterion tells us the sequence converges to the same limit as any subsequence. So every Cauchy sequence is convergent, so R is complete.

I'm less familiar with how to go from "every bounded monotone sequence converges in R" to "every non-empty bounded set S has a LUB" (Lusus's definition of complete).

Here's one (intuitive) approach. For any real number x, define

F_n(x) = \lfloor 10^n x \rfloor / 10^x

. For example,

F_3(\pi) = 3.141

. Then we have

x-10^{-n} < F_n \leq x

.

Now take a non-empty bounded set S, with

s \in S \implies |S| < M

. Define

S_n = \{F_n(x): x \in S\}

. Each S_n is finite, so has a greatest element

s_n

.

It's now not hard to show that

s_n

is monotonic and bounded. So if we're assuming every bounded monotone sequence converges, then

s_n

converges to a limit L. And then it's not hard to show L is a LUB for S.

Reply 17

I guess, instead, we would just need to show that my definition was equivalent to the Cauchy criterion. Clearly it is necessary for there to be a LUB of a non-empty bounded set , otherwise the Cauchy criterion does not hold. The example my teacher used was the sequence

a_n := \sqrt{2} \text{to n decimal places}

. I think we can all agree that this sequence tends to a limit, but somebody working in the incomplete

\mathbb{Q}

would be adamant that it doesn't converge!

Reply 18