Chapter IV · Limits of functions of a positive integral variable

Weierstrass’s theorem by bisection

§71 25 min

A second proof that every bounded infinite set has a point of accumulation, in which the nested intervals of repeated bisection give two monotone sequences with a common limit.

Why this matters

In §19 Hardy proved Weierstrass’s theorem: every bounded set with infinitely many points has at least one point of accumulation. That proof used a Dedekind section directly. §71 gives a second proof by repeated bisection, now that monotone sequences are available. The method is worth more than the theorem: the same halving argument proves the intermediate value theorem and the Heine–Borel theorem in Chapter V, and it is the standard way to turn “infinitely many” into “a definite point”.

The idea

Let SS be a set with infinitely many points, all inside an interval PQPQ. Cut PQPQ in half. The two halves together contain infinitely many points of SS, so at least one half does (two finite sets have a finite union). Keep such a half; if both qualify, keep the left one, so that the rule is definite. Now cut that half in two, and repeat for ever. Each interval is half the previous one and still contains infinitely many points of SS.

Explore Halving towards a point of accumulation

Try this. Press Step a few times and watch the kept interval. Then Play, and read the note under each step that says which half was kept and why.

Bisection for a point of accumulation of {1/m+1/n:m,n≥1}\{1/m+1/n : m, n \ge 1\}
−113
  • earlier intervals
  • current interval
  • points of the set
Step 0: [−1, 3][−1,\ 3], width 4; it contains infinitely many points of the set (1830 of the first 1830 drawn). Every interval in the chain has this property, so the point they close on is a point of accumulation.
What to notice

The intervals are nested and their lengths halve every time, so they close in on a single point. That point is a point of accumulation: however small an interval around it you draw, one of the kept intervals fits inside, and that kept interval holds infinitely many points of the set.

What is new in §71 is how we know that the intervals close in on a point at all. Write the kk-th interval as PkQkP_kQ_k. Because each new interval lies inside the old one, the left ends PkP_k can only move right (or stay), and the right ends QkQ_k can only move left (or stay). So PkP_k is an increasing sequence and QkQ_k a decreasing one, and both stay within PQPQ. That is exactly the situation of Monotone sequences.

Explore Two monotone sequences with one limit

Try this. Increase the number of halvings kk from 00 to 2424 and watch the two rows of dots. Try each of the four sets.

Bisection for a point of accumulation of {(−1)n(1+1/n)}\{(-1)^n(1+1/n)\}
kposition
  • Pₖ, left ends (never decrease)
  • Qₖ, right ends (never increase)
  • their common limit T
After k=6k = 6 halvings: P6=−1.0625P_{6} = −1.0625, Q6=−1Q_{6} = −1, width Q6−P6=(4)/26=0.0625Q_{6} - P_{6} = (4)/2^{6} = 0.0625. Both sequences are monotone and bounded, so each has a limit (§69); the widths tend to 00, so the limits are the same point T=−1T = −1.
What to notice

The blue dots (left ends) never go down and the ochre dots (right ends) never go up; the gap between them halves at every step. Two monotone bounded sequences must converge, and since their difference tends to 00 they converge to the same point TT.

Precise statements

Theorem Weierstrass’s theorem Hardy: §19; second proof §71

If a set SS of real numbers is bounded and contains infinitely many points, then SS has at least one point of accumulation: a point ξ\xi such that every interval (ξ−δ,ξ+δ)(\xi - \delta, \xi + \delta) with δ>0\delta > 0 contains infinitely many points of SS.

The proof rests on one lemma, which is worth stating separately because it is used again and again.

Lemma Nested intervals

Let [p0,q0]⊇[p1,q1]⊇[p2,q2]⊇…[p_0, q_0] \supseteq [p_1, q_1] \supseteq [p_2, q_2] \supseteq \dots be closed intervals with qk−pk→0q_k - p_k \to 0. Then pkp_k and qkq_k tend to the same limit TT, and pk≤T≤qkp_k \le T \le q_k for every kk.

Proofs

Proof Nested intervals
Strategy

The left ends form an increasing sequence bounded above, the right ends a decreasing sequence bounded below. Each converges by §69; the difference of the limits is the limit of the differences, which is 00.

The ends are monotone and bounded

[pk+1,qk+1]⊆[pk,qk][p_{k+1}, q_{k+1}] \subseteq [p_k, q_k] means pk≤pk+1p_k \le p_{k+1} and qk+1≤qkq_{k+1} \le q_k. Also pk≤qk≤q0p_k \le q_k \le q_0 and qk≥pk≥p0q_k \ge p_k \ge p_0 for every kk.

Both converge

pkp_k increases and is bounded above by q0q_0, so pk→Tp_k \to T for some TT (Cor. 1 of §69). Likewise qkq_k decreases and is bounded below by p0p_0, so qk→T′q_k \to T'.

The limits agree

T′−T=lim⁡(qk−pk)=0T' - T = \lim (q_k - p_k) = 0 by the rule for differences of limits (Limits of sums, products and quotients).

TT lies in every interval

By Cor. 3 of §69, an increasing sequence is at most its limit: pk≤Tp_k \le T. Similarly qk≥T′=Tq_k \ge T' = T.

Proof Weierstrass’s theorem (second proof)
Strategy

Halve an interval containing SS again and again, always keeping a half with infinitely many points of SS. The nested intervals shrink to a point TT by the lemma, and every neighbourhood of TT swallows one of them.

Start

SS is bounded, so it lies in some interval [p0,q0][p_0, q_0], which therefore contains infinitely many points of SS.

Halve and keep

Given [pk,qk][p_k, q_k] containing infinitely many points of SS, split it at its midpoint. If both halves contained only finitely many points of SS, so would their union [pk,qk][p_k, q_k]. So at least one half contains infinitely many; take the left one if it does, otherwise the right one, and call it [pk+1,qk+1][p_{k+1}, q_{k+1}]. Its length is (q0−p0)/2k+1(q_0 - p_0)/2^{k+1}.

Shrink to a point

The lengths (q0−p0)/2k(q_0 - p_0)/2^k tend to 00 (since 2k≥k2^k \ge k, they are at most (q0−p0)/k(q_0 - p_0)/k). By the lemma, pk→Tp_k \to T and qk→Tq_k \to T, with pk≤T≤qkp_k \le T \le q_k.

TT is a point of accumulation

Let δ>0\delta > 0. Choose kk with (q0−p0)/2k<δ(q_0 - p_0)/2^k < \delta. Since T∈[pk,qk]T \in [p_k, q_k] and the interval is shorter than δ\delta, every point of [pk,qk][p_k, q_k] is within less than δ\delta of TT, so [pk,qk]⊆(T−δ,T+δ)[p_k, q_k] \subseteq (T - \delta, T + \delta). The smaller interval contains infinitely many points of SS, so the larger one does too.

Compare the two proofs. The first (§19) builds a section of the reals and appeals to Dedekind’s theorem directly. The second appeals to it indirectly, through the monotone sequence theorem, which was itself proved with Dedekind’s theorem. Some form of completeness is unavoidable: in the rational numbers the theorem is false. The decimal approximations 1,1.4,1.41,1.414,…1, 1.4, 1.41, 1.414, \dots to 2\sqrt 2 form a bounded infinite set of rationals whose only point of accumulation among the reals is 2\sqrt 2, so among the rationals it has none.

Worked examples and exercises

Exercise Run the bisection by hand ●○○ Hardy: §71

Let S={1/n:n=1,2,3,… }S = \{1/n : n = 1, 2, 3, \dots\} and start with [0,1][0, 1]. Carry out three halvings with Hardy’s rule (prefer the left half), and identify the point of accumulation found.

Solution

[0,12][0, \tfrac12] contains 12,13,14,…\tfrac12, \tfrac13, \tfrac14, \dots, infinitely many: keep it. [0,14][0, \tfrac14] contains 14,15,…\tfrac14, \tfrac15, \dots: keep it. [0,18][0, \tfrac18]: keep it. In general pk=0p_k = 0 and qk=2−kq_k = 2^{-k}, so T=0T = 0. Indeed 00 is the only point of accumulation of SS (the points 1/n1/n themselves are isolated).

Exercise Choosing the right half ●●○ Hardy: §71

Let S={(−1)n(1+1/n)}S = \{(-1)^n(1 + 1/n)\}, with points of accumulation −1-1 and 11. Starting from [−2,2][-2, 2], which point does Hardy’s rule find? Which would the rule “prefer the right half” find? Could a rule ever find a point that is not a point of accumulation?

Solution

The first left half [−2,0][-2, 0] contains the infinitely many points −(1+1/n)-(1 + 1/n) for odd nn, so it is kept, and from then on the intervals close in on −1-1. Preferring the right half gives [0,2][0, 2] first and leads to 11. Every rule finds a point of accumulation, because the proof never used which half was chosen, only that the chosen half contains infinitely many points. Different rules may find different points of accumulation.

Exercise Why the lengths must shrink ●●○ Hardy: §71

Give an example of nested closed intervals whose ends converge to different limits, and say which hypothesis of the lemma fails. Then give nested open intervals (pk,qk)(p_k, q_k) with qk−pk→0q_k - p_k \to 0 that have no point in common.

Solution

[−1−1/k,1+1/k][-1 - 1/k, 1 + 1/k] are nested, with pk→−1p_k \to -1 and qk→1q_k \to 1; the lengths tend to 22, not 00. Every point of [−1,1][-1, 1] lies in all of them. For open intervals, take (0,1/k)(0, 1/k): they are nested and their lengths tend to 00, but no number lies in all of them, since x>0x > 0 fails to be below 1/k1/k once k>1/xk > 1/x, and x≤0x \le 0 is in none. The common limit of the ends, 00, is not in any of the open intervals. Closedness is what puts TT inside every interval (step 4 of the lemma).

Check yourself

Check yourself Choose one

In §71, why does the sequence of left ends PkP_k converge?

Why

An increasing sequence bounded above converges (§69). The lengths tending to 00 is what makes the two limits agree, and that the point is a point of accumulation is the conclusion, not a reason.

Check yourself True or false?

If each half of an interval contains only finitely many points of SS, the whole interval contains only finitely many points of SS.

Why

True: the union of two finite sets is finite. This is why at least one half of an interval containing infinitely many points must itself contain infinitely many.

Check yourself Enter a number

Starting from [0,1][0, 1], what is the length of the interval after 1010 halvings?

Why

Each halving divides the length by 22, so the length is 2−10=1/1024≈0.0009772^{-10} = 1/1024 \approx 0.000977.

Hardy’s language

Summary

Summary
  • Repeated bisection, always keeping a half with infinitely many points, gives nested intervals of length (q0−p0)/2k(q_0 - p_0)/2^k.
  • The left ends increase and the right ends decrease; both are bounded, so both converge (§69), and the shrinking lengths force a common limit TT.
  • Every neighbourhood of TT contains a whole kept interval, hence infinitely many points of SS: TT is a point of accumulation.
  • The nested interval argument is a general tool; it will prove the intermediate value and Heine–Borel theorems in Chapter V.