Monotone Sequences, Bolzano-Weierstrass, and Cauchy Completeness

Throughout, $\mathbb{R}$ is the complete ordered field (Complete ordered field (least-upper-bound property), Ordered field) with its order (Order on the reals).

A subset $I\subseteq \mathbb{R}$ is order-convex when

$x,y\in I\text{ and }x\le z\le y⟹z\in I\mathrm{.}$

The intervals of $\mathbb{R}$ are the sets of the following nine forms, where $a,b\in \mathbb{R}$:

An interval is open when both of its written endpoints are excluded, that is for the forms $(a,b)$, $(a,\mathrm{\infty })$, $(-\mathrm{\infty },b)$ and $(-\mathrm{\infty },\mathrm{\infty })$; it is closed when both written endpoints are included, that is for $[a,b]$, $[a,\mathrm{\infty })$, $(-\mathrm{\infty },b]$ and $(-\mathrm{\infty },\mathrm{\infty })$. The forms $[a,b)$ and $(a,b]$ are half-open.

The symbols $\pm \mathrm{\infty }$ are notation and not elements of $\mathbb{R}$. They mark which side carries no endpoint condition at all; the five forms in the right column are defined by the displayed conditions on $x$ alone, and no arithmetic is ever performed with $\mathrm{\infty }$. This is the same refusal to extend $\mathbb{R}$ silently that Conventions: $\sup \mathrm{\varnothing }$, unbounded sets, and the extended reals records for suprema.

Every one of the nine forms is order-convex. Each is defined by a conjunction of at most two conditions, each of the shape $a<x$, $a\le x$, $x<b$ or $x\le b$, and each such condition is inherited by an intermediate point: if $a<x$ and $x\le z$ then $a<z$, and if $z\le y$ and $y<b$ then $z<b$, by transitivity of the order (Ordered field). Applying this to whichever one or two conditions define the form in question gives $z\in I$ whenever $x,y\in I$ and $x\le z\le y$.

Bounded intervals. An interval is bounded (Lower bound, bounded below, bounded set) exactly when it is of one of the four forms in the left column: for those, $a$ is a lower bound and $b$ an upper bound. The other five forms are unbounded, on the side or sides written with $\mathrm{\infty }$; the verification is in the remarks below.

Nondegeneracy. An interval is degenerate when it has at most one element, and nondegenerate when it has at least two. For the four bounded forms with endpoints $a$ and $b$:

• $[a,b]$ is nonempty exactly when $a\le b$, and it is nondegenerate exactly when $a<b$. It is the singleton $\{a\}$ when $a=b$.
• $(a,b)$, $[a,b)$ and $(a,b]$ are nonempty exactly when $a<b$, and then each is nondegenerate.

The only assertion here that is not immediate from the defining conditions is that $a<b$ makes $(a,b)$ nonempty with at least two points. It holds because $a<(a+b)\mathrm{/}2<b$, which follows from $a<b$ by adding $a$, respectively $b$, to both sides and halving (Ordered field); repeating the halving inside $(a,(a+b)\mathrm{/}2)$ produces a second point.

Closed bounded intervals. These are the sets $[a,b]$ with $a\le b$, which is exactly the condition making them nonempty. They are the intervals the nested interval property is stated for, and the phrase closed bounded interval always carries the hypothesis $a\le b$ in this library.

Length. The length of a bounded interval presented by its endpoints $a\le b$ is

$\mathrm{\ell }=b-a\ge 0.$

Length is attached to the presentation by endpoints and is not recovered from the set: $(a,b)$, $[a,b)$ and $(a,b]$ are all empty when $a=b$, and so is $(c,c)$ for any other $c$, while each of these presentations has length $0$, so nothing inconsistent arises; but the endpoints are named explicitly at every point where a length is used in this library, and never inferred from the set. Unbounded intervals are assigned no length.

• Why the five unbounded forms really are unbounded. Take $[a,\mathrm{\infty })$ and suppose $u\in \mathbb{R}$ were an upper bound of it. The element $x=a+\mathrm{\mid }u-a\mathrm{\mid }+1$ satisfies $x\ge a$, so $x\in [a,\mathrm{\infty })$, and $x\ge a+(u-a)+1=u+1>u$, since $\mathrm{\mid }t\mathrm{\mid }\ge t$ (Basic properties of the absolute value) and $1>0$ (The multiplicative identity is positive). That contradicts $x\le u$. The same computation with $a$ replaced by any element of $(a,\mathrm{\infty })$ handles the open form, and reflecting through the origin handles $(-\mathrm{\infty },b)$ and $(-\mathrm{\infty },b]$; $\mathbb{R}$ itself is unbounded on both sides for the same reason. Note that this uses no Archimedean property: it is the failure of a single bound, not the cofinality of the naturals.

• The converse classification is not asserted here. It is true that every order-convex subset of $\mathbb{R}$ is empty or one of the nine forms, and the proof runs through suprema and infima, but nothing in this library needs it and it is not proved anywhere here. What is used is only the direction proved above: each of the nine forms is order-convex.

• Degenerate intervals are kept, not excluded. $[a,a]=\{a\}$ and $(a,a)=\mathrm{\varnothing }$ are intervals under this definition. Excluding them would force a nonemptiness hypothesis into every statement that produces an interval, and the nested interval property is a good illustration: its conclusion is that the intersection is nonempty, and in the equality case the intersection is the degenerate interval $[a,a]$, which is exactly the single point.

Let $(x_k)$ be a sequence of reals (Sequences of reals: bounded, eventually, frequently, tails, subsequences), with $\mathbb{R}$ ordered as in Order on the reals and Complete ordered field (least-upper-bound property), and with $\mathbb{N}$ ordered as in Order on the natural numbers. The sequence is:

• nondecreasing when $x_j\le x_k$ for all $j\le k$;
• increasing (or strictly increasing) when $x_j<x_k$ for all $j<k$;
• nonincreasing when $x_j\ge x_k$ for all $j\le k$;
• decreasing (or strictly decreasing) when $x_j>x_k$ for all $j<k$;
• monotone when it is nondecreasing or nonincreasing;
• strictly monotone when it is increasing or decreasing;
• eventually monotone when some tail $x^{(K)}$ (Sequences of reals: bounded, eventually, frequently, tails, subsequences) is monotone, that is when there is $K\in \mathbb{N}$ such that the restriction of the comparison to indices $\ge K$ is one-signed.

An increasing sequence is nondecreasing and a decreasing sequence is nonincreasing, since $j\le k$ means $j<k$ or $j=k$ and the second case gives equality. A sequence that is both nondecreasing and nonincreasing is constant.

Consecutive comparisons suffice, and that is an induction. The four conditions above quantify over all pairs of indices, but what one checks in practice, and what a recursive construction delivers, is the comparison of consecutive terms. The two agree:

$(x_k)$ is nondecreasing if and only if $x_k\le x_{\sigma (k)}$ for every $k\in \mathbb{N}$, and $(x_k)$ is increasing if and only if $x_k<x_{\sigma (k)}$ for every $k\in \mathbb{N}$; likewise, with the inequalities reversed, for nonincreasing and decreasing.

The forward implications are the instances $j=k$, $k=\sigma (k)$ of the definitions, using $k<\sigma (k)$ (Discreteness: $\sigma (n)$ is the immediate successor). For the converse, suppose $x_i\le x_{\sigma (i)}$ for every $i$ and fix $k$; we show by induction on $k$ (The principle of mathematical induction) that $x_j\le x_k$ for every $j\le k$. For $k=0$: $j\le 0$ forces $j=0$, and $x_0\le x_0$. Assume the statement for $k$ and let $j\le \sigma (k)$. If $j=\sigma (k)$ then $x_j\le x_{\sigma (k)}$ by reflexivity. Otherwise $j<\sigma (k)$, and then $j\le k$: were $k<j$ we would have $k<j<\sigma (k)$, which Discreteness: $\sigma (n)$ is the immediate successor excludes, so $j\le k$ by totality of the order on $\mathbb{N}$ ($\le$ is a linear order on $\mathbb{N}$). The induction hypothesis gives $x_j\le x_k$, and $x_k\le x_{\sigma (k)}$ by assumption, so $x_j\le x_{\sigma (k)}$ by transitivity. This completes the induction. The three remaining equivalences are the same argument with $\le$ replaced by $<$, $\ge$ or $>$, transitivity of the strict order being used in the same place.

Boundedness of a monotone sequence is one-sided. A nondecreasing sequence is bounded below by its first term $x_0$, and a nonincreasing sequence is bounded above by $x_0$, both immediately from the definition with $j=0$. So for a nondecreasing sequence the only substantive question is whether it is bounded above, and for a nonincreasing sequence whether it is bounded below. The range of $(x_k)$ is the set $\{x_k:k\in \mathbb{N}\}$ (Sequences of reals: bounded, eventually, frequently, tails, subsequences), and it is bounded above, bounded below or bounded in the sense of Lower bound, bounded below, bounded set exactly when the sequence is.

• The naming is the one that keeps "increasing" strict. Some texts use increasing for what is called nondecreasing here and strictly increasing for what is called increasing. This library follows the convention in which the unqualified word is strict, and always writes nondecreasing when equality is allowed, so that no statement on this page depends on which convention a reader arrives with. Where a proof needs the weak form it says nondecreasing, and where it needs the strict form it says increasing.

• Eventual monotonicity is exactly monotonicity of a tail, and by Convergence depends only on the tail a sequence and its tails converge to the same limits and are Cauchy together. So every convergence statement about monotone sequences on this page extends verbatim to eventually monotone sequences, with the limit unchanged; only statements about specific terms, such as the identification of the limit as the supremum of the whole range, need the hypothesis at every index. The monotone convergence theorem is a case in point: an eventually nondecreasing bounded sequence converges, but to the supremum of the range of the monotone tail, which may be smaller than the supremum of the whole range.

• Monotone is strictly weaker than strictly monotone, and neither is generic. A constant sequence is monotone and not strictly monotone; the sequence with terms $1$ and $-1$ alternating (The even and odd index maps and the alternating sequence: strictly increasing $e,o$ with $\mathbb{N}$ their disjoint union, and the unique $(s_k)$ with $s_0=1$, $s_{\sigma (k)}=-s_k$, which satisfies $\mathrm{\mid }{s}_k\mathrm{\mid }=1$, $s\circ e\equiv 1$ and $s\circ o\equiv -1$) is not monotone and not eventually monotone, since every tail contains both values infinitely often. That sequence is bounded, so boundedness alone gives neither form of monotonicity; what it does give is a monotone subsequence (Every real sequence has a monotone subsequence (the peak / rising-sun lemma)), and that is the route to Bolzano-Weierstrass.

Let $(x_k)$ be a sequence of reals (Sequences of reals: bounded, eventually, frequently, tails, subsequences) and let $S=\{x_k:k\in \mathbb{N}\}$ be its range.

1. If $(x_k)$ is nondecreasing (Nondecreasing, increasing, nonincreasing, decreasing, monotone, and eventually monotone sequences) and $S$ is bounded above (Lower bound, bounded below, bounded set), then $(x_k)$ converges (Limits and Cauchy sequences of reals) and ${\lim }_k{x}_k=\sup S\mathrm{.}$
2. If $(x_k)$ is nonincreasing and $S$ is bounded below, then $(x_k)$ converges and ${\lim }_k{x}_k=\inf S\mathrm{.}$

Both suprema and infima exist under the stated hypotheses: $S$ is nonempty, so the least-upper-bound property (Complete ordered field (least-upper-bound property)) supplies the first and Every nonempty set bounded below has an infimum the second, and each is unique (Suprema and infima are unique).

This is the first place in this track where the least-upper-bound property produces a limit. Everything on the sequences page held in any Archimedean ordered field; the theorem below does not, and the sequence of decimal truncations of $\sqrt{2}$ inside $\mathbb{Q}$ is the standard witness of its failure there.

• Only one half is proved twice. Claim 2 could instead be deduced from claim 1 by reflection, since $(-y_k)$ is nondecreasing and bounded above and $\inf T=-\sup (-T)$ (Every nonempty set bounded below has an infimum). The direct argument is written out because it is no longer, and because it puts Epsilon characterisation of the infimum to work in the place it was proved for, rather than routing an infimum statement through a supremum statement and a sign change.

• The limit is the supremum of the range, not merely some upper bound. That identification is what Epsilon characterisation of the supremum supplies and it is the useful part of the theorem: it is how a limit is computed from a monotone construction, as in the recursive sequences of the examples page, rather than merely shown to exist.

• Boundedness on the other side is automatic and is not a hypothesis. A nondecreasing sequence is bounded below by $x_0$ (Nondecreasing, increasing, nonincreasing, decreasing, monotone, and eventually monotone sequences), so "nondecreasing and bounded above" already means "nondecreasing and bounded"; this is what makes A monotone sequence converges if and only if it is bounded an equivalence rather than a one-sided statement.

• Without the hypothesis of boundedness the conclusion fails completely, and fails in a describable way: a nondecreasing sequence that is not bounded above diverges to $+\mathrm{\infty }$ (A nondecreasing sequence that is not bounded above diverges to $+\mathrm{\infty }$), so a nondecreasing sequence either converges to the supremum of its range or runs away, with no third possibility.

Let $(x_k)$ be a nondecreasing sequence of reals (Sequences of reals: bounded, eventually, frequently, tails, subsequences, Nondecreasing, increasing, nonincreasing, decreasing, monotone, and eventually monotone sequences) whose range $S=\{x_k:k\in \mathbb{N}\}$ is not bounded above (Lower bound, bounded below, bounded set). Then $(x_k)$ diverges to $+\mathrm{\infty }$ (Divergence to $+\mathrm{\infty }$ and to $-\mathrm{\infty }$): for every $M\in \mathbb{R}$ there is $K\in \mathbb{N}$ with $x_k>M$ for all $k\ge K$.

Read together with the monotone convergence theorem this says that a nondecreasing sequence has exactly two possible behaviours, with nothing in between: it converges to the supremum of its range, or it runs away to $+\mathrm{\infty }$.

• Only "not bounded above" is used, not unboundedness of the sequence. For a nondecreasing sequence the two coincide, since such a sequence is bounded below by $x_0$ (Nondecreasing, increasing, nonincreasing, decreasing, monotone, and eventually monotone sequences), so a nondecreasing sequence is unbounded exactly when its range is not bounded above. The hypothesis is stated in the one-sided form because that is the form the proof consumes.

• The dual statement holds with the same proof: a nonincreasing sequence whose range is not bounded below diverges to $-\mathrm{\infty }$. Reflecting through the origin turns one into the other.

• $+\mathrm{\infty }$ is not a limit. Divergence to $+\mathrm{\infty }$ and to $-\mathrm{\infty }$ is deliberately not a case of Limits and Cauchy sequences of reals: a sequence diverging to $+\mathrm{\infty }$ is unbounded, hence not convergent (Every convergent sequence is bounded), and the arrow in $x_k\to +\mathrm{\infty }$ is an abbreviation for the displayed quantifier statement and never an equation.

• The companion statement is A nondecreasing sequence bounded above converges to the supremum of its range, and a nonincreasing sequence bounded below to the infimum: between them, a nondecreasing sequence converges to the supremum of its range or diverges to $+\mathrm{\infty }$, with no third possibility.

Let $(x_k)$ be a monotone sequence of reals (Sequences of reals: bounded, eventually, frequently, tails, subsequences, Nondecreasing, increasing, nonincreasing, decreasing, monotone, and eventually monotone sequences). Then $(x_k)$ converges if and only if it is bounded, that is if and only if there is $M\in \mathbb{R}$ with $\mathrm{\mid }{x}_k\mathrm{\mid }\le M$ for every $k\in \mathbb{N}$.

The forward implication holds for every sequence and is Every convergent sequence is bounded. What monotonicity buys is the converse, which is false for sequences in general.

• The limit is named, not merely asserted to exist. In the nondecreasing case it is $\sup S$ and in the nonincreasing case $\inf S$, by A nondecreasing sequence bounded above converges to the supremum of its range, and a nonincreasing sequence bounded below to the infimum. The equivalence is stated without the value only because the value depends on which of the two cases holds.

• This is the form in which the result is used. Bolzano-Weierstrass (Bolzano-Weierstrass: every bounded real sequence has a convergent subsequence) extracts a monotone subsequence of a bounded sequence and then needs exactly this corollary, since what is available about the subsequence is boundedness, inherited from the sequence, and not a bound on a particular side.

• Monotonicity cannot be dropped. Without it the converse direction fails, by FALSE: every bounded sequence converges. The forward direction is not in the same position: it holds for every sequence, monotone or not, so there is no hypothesis to drop from it. What monotonicity adds there is sharpness rather than validity, and the sharpened form is recorded by A nondecreasing sequence that is not bounded above diverges to $+\mathrm{\infty }$: an unbounded nondecreasing sequence does not merely fail to converge, it diverges to $+\mathrm{\infty }$.

For each $k\in \mathbb{N}$ let $I_k=[a_k,b_k]$ be a closed bounded interval with $a_k\le b_k$ (Intervals of $\mathbb{R}$: the nine order-convex forms, nondegeneracy, and length), and suppose the family is nested:

$I_{k+1}\subseteq I_k(k\in \mathbb{N})\mathrm{.}$

Write ${\mathrm{\ell }}_k=b_k-a_k\ge 0$ for the length of $I_k$. Then:

1. ${\displaystyle \bigcap _{k\in \mathbb{N}}{I}_k}$ is nonempty. More precisely, with $a=\sup \{a_k:k\in \mathbb{N}\}$ and $b=\inf \{b_k:k\in \mathbb{N}\}$, both of which exist, one has $a\le b$ and ${\bigcap }_{k\in \mathbb{N}}{I}_k=[a,b]\mathrm{.}$
2. ${\displaystyle \bigcap _{k\in \mathbb{N}}{I}_k}$ is a single point if and only if ${\mathrm{\ell }}_k\to 0$ (Limits and Cauchy sequences of reals).

Every hypothesis is load bearing. Dropping closedness makes the intersection empty; dropping boundedness does the same; and dropping nonemptiness of the individual intervals is vacuously fatal.

• No Archimedean input is needed. The lengths are handled entirely by the algebra of limits and the uniqueness of limits: ${\mathrm{\ell }}_k$ always converges, to $b-a$, and the two directions of claim 2 are then the two directions of "$b-a=0$". A proof that instead argues "if $b-a>0$ then some ${\mathrm{\ell }}_k$ is smaller" does need the Archimedean property (For every $\epsilon >0$ in a complete ordered field there is a natural $n\ge 1$ with $1\mathrm{/}n<\epsilon$), and it is avoidable, so it is avoided.

• Nestedness gives more than it is usually stated to give. The intersection is not merely nonempty; it is the closed interval $[a,b]$, and $a$ and $b$ are the limits of the endpoint sequences. The single-point case is exactly the case in which those two limits agree, and that is what makes the nested interval property usable as a construction of a real number, as in The nested intervals $[0,1\mathrm{/}k]$ intersect in exactly $\{0\}$ ↗.

• This is one of the standard equivalents of completeness. Nested intervals together with the Archimedean property imply the least-upper-bound property, so the implication proved here is not reversible for free: it is half of an equivalence whose other half needs the Archimedean hypothesis separately. Two independent proofs that $\mathbb{R}$ is Cauchy complete, and why the library records both records where this library stands on those routes.

• The witnesses for the two deleted hypotheses are The nested open intervals $(0,1\mathrm{/}k)$ have empty intersection ↗, which keeps boundedness and drops closedness, and The nested closed unbounded sets $[k,\mathrm{\infty })$ have empty intersection, so boundedness cannot be dropped ↗, which keeps closedness and drops boundedness. Neither is used above; each shows that the corresponding hypothesis cannot be removed.

Let $(x_k)$ be a sequence of reals (Sequences of reals: bounded, eventually, frequently, tails, subsequences) and let $L\in \mathbb{R}$. Then $L$ is a subsequential limit of $(x_k)$ when some subsequence of $(x_k)$ converges to $L$: that is, when there is a strictly increasing $n:\mathbb{N}\to \mathbb{N}$ such that

$x_{n_j}⟶L(j\to \mathrm{\infty })$

in the sense of Limits and Cauchy sequences of reals. The subsequential limit set of $(x_k)$ is

$\mathrm{SL}(x):=\{L\in \mathbb{R}:L\text{ is a subsequential limit of }(x_k)\}\subseteq \mathbb{R}\mathrm{.}$

Both pieces of the definition are already fixed elsewhere and are only combined here: strictly increasing and subsequence are Sequences of reals: bounded, eventually, frequently, tails, subsequences, and converges is Limits and Cauchy sequences of reals. Nothing about $(x_k)$ itself is assumed; in particular $(x_k)$ is not assumed to converge, and $\mathrm{SL}(x)$ may be empty, a single point, or larger.

A subsequence looks arbitrarily far out. A strictly increasing index map satisfies $n_j\ge j$ for every $j$ (A strictly increasing index map satisfies $n_k\ge k$), so the indices $n_j$ are cofinal in $\mathbb{N}$ and a subsequential limit is determined by the behaviour of $(x_k)$ at arbitrarily large indices. Consequently no finite initial segment of $(x_k)$ affects $\mathrm{SL}(x)$: a sequence and each of its tails have the same subsequential limits.

Terminology. Some texts say cluster point, limit point or accumulation value of the sequence for the same notion. This library says subsequential limit throughout, reserving limit point for the topological notion of a limit point of a set, which is a different thing: the set $\{x_k\}$ of values of the constant sequence $x_k=0$ has no limit point, while $0$ is a subsequential limit of that sequence.

• A convergent sequence has exactly one subsequential limit, its limit. If $x_k\to x$ then every subsequence converges to $x$ (Subsequences inherit the limit), so every subsequential limit equals $x$ by uniqueness of limits (A sequence has at most one limit); and $x$ itself is one, taking $n_j=j$, which is strictly increasing. So $\mathrm{SL}(x)=\{x\}$. The converse fails: $\mathrm{SL}$ being a single point does not force convergence, as the unbounded sequence of The sequence $1,1,2,1,3,1,4,\dots$ is unbounded and has a convergent subsequence ↗ shows.

• The subsequential limit set can be empty. The sequence $x_k=k$ has no subsequential limit at all, since every subsequence is unbounded and an unbounded sequence does not converge (Every convergent sequence is bounded). Bolzano-Weierstrass (Bolzano-Weierstrass: every bounded real sequence has a convergent subsequence) says exactly that boundedness is what rules this out: for a bounded sequence, $\mathrm{SL}(x)\mathrm{\ne }\mathrm{\varnothing }$.

• It can also be large. The alternating sequence of The even and odd index maps and the alternating sequence: strictly increasing $e,o$ with $\mathbb{N}$ their disjoint union, and the unique $(s_k)$ with $s_0=1$, $s_{\sigma (k)}=-s_k$, which satisfies $\mathrm{\mid }{s}_k\mathrm{\mid }=1$, $s\circ e\equiv 1$ and $s\circ o\equiv -1$ has subsequential limit set $\{-1,1\}$, and The sequence $(-1{)}^k(1+1\mathrm{/}k)$ is bounded with subsequential limit set exactly $\{-1,1\}$ ↗ carries out that computation for a sequence that converges to neither. The systematic study of $\mathrm{SL}(x)$, in particular that it has a greatest and a least element for a bounded sequence, belongs to the $\mathrm{lim\hspace{0.17em}sup}$ page and is not begun here.

Every sequence of reals has a monotone subsequence: for every sequence $(x_k)$ of reals (Sequences of reals: bounded, eventually, frequently, tails, subsequences) there is a strictly increasing $n:\mathbb{N}\to \mathbb{N}$ such that the subsequence $(x_{n_j})$ is monotone (Nondecreasing, increasing, nonincreasing, decreasing, monotone, and eventually monotone sequences).

No hypothesis whatever is placed on $(x_k)$: it need not be bounded, and it need not converge. Combined with the corollary later on this page, which converts monotone plus bounded into convergent, this is the whole content of the Bolzano-Weierstrass theorem.

Call an index $n\in \mathbb{N}$ a peak of $(x_k)$ when

$x_m\le x_n\text{for every }m\ge n,$

that is, when no later term ever exceeds $x_n$. The proof splits on whether peaks occur arbitrarily late or stop occurring, and produces a nonincreasing subsequence in the first case and an increasing one in the second. The picture behind the name is the rising sun shining from the right: the peaks are the points that are not put in shadow by anything to their right.