3 Real Numbers 25Thenx 1 >1andx 12 >a,since(a− 1 )^2 >0. Define the sequence{xn}recursively by
xn+ 1 =(xn+a/xn)/ 2 (n≥ 1 ).It is easily verified that ifxn>1andx^2 n>a,thenxn+ 1 >1,xn^2 + 1 >aandxn+ 1 <xn.
Since the inequalities hold forn=1, it follows that they hold for alln. Thus the
sequence{xn}is nonincreasing and bounded, and therefore convergent. Ifxn→b,
thena/xn→a/bandxn+ 1 →b. Henceb=(b+a/b)/2, which simplifies tob^2 =a.
We consider now sequences of real numbers which are not necessarily monotonic.
Lemma 23Any sequence{an}of real numbers has a monotonic subsequence.
Proof LetMbe the set of all positive integersmsuch thatam≥anfor everyn>m.
IfMcontains infinitely many positive integersm 1 <m 2 <···,then{amk}is a
nonincreasing subsequence of{an}.IfMis empty or finite, there is a positive integer
n 1 such that no positive integern≥n 1 is inM.Thenan 2 >an 1 for somen 2 >n 1 ,
an 3 >an 2 for somen 3 >n 2 , and so on. Thus{ank}is a nondecreasing subsequence of
{an}.
It is clear from the proof that Lemma 23 also holds for sequences of elements of
any totally ordered set. In the case ofR, however, it follows at once from Lemma 23
and Proposition 22 that
Proposition 24Any bounded sequence of real numbers has a convergent subse-
quence.
Proposition 24 is often called the Bolzano–Weierstrass theorem. It was stated by
Bolzano (c. 1830) in work which remained unpublished until a century later. It became
generally known through the lectures of Weierstrass (c. 1874).
A sequence{an}of real numbers is said to be afundamental sequence, or ‘Cauchy
sequence’, if for eachε>0 there exists a positive integerN=N(ε)such that
−ε<ap−aq<ε for allp,q≥N.Any fundamental sequence{an}is bounded, since any finite set is bounded andaN−ε<ap<aN+ε forp≥N.Also, any convergent sequence is a fundamental sequence. For supposean →las
n→∞. Then, for anyε>0, there exists a positive integerNsuch that
l−ε/ 2 <an<l+ε/2foreveryn≥N.It follows that
−ε<ap−aq<ε forp≥q≥N.The definitions of convergent sequence and fundamental sequence, and the preced-
ing result that ‘convergent’ implies ‘fundamental’, hold also for sequences of rational
numbers, and even for sequences with elements from any ordered field. However, for
sequences of real numbers there is a converse result: