MthT 430 Notes Chap8a Least Upper Bounds and Binary Expansions
MthT 430 Notes Chap8a Least Upper Bounds and Binary Expansions
Bounds and Least Upper Bounds

Definition. A set A of real numbers is bounded above if there is a number x such that
x ≥ a    for every a in A.
Such a number x is called an upper bound for A.

Definition. A number x is a least upper bound for a set A if
x is an upper bound for A,
(1)
if y is an upper bound for A, then xy
(2)
Such a number x is also called the supremum for A and sometimes denoted by supA or lub A.

Definition. A number x is a greatest element of a non empty set A if




xA,
x is an upper bound for A.
Examples
The set [0, 1] has least upper bound 1.
sup
[0, 1] = 1.
The number 1 is also the greatest element of [0, 1].
If a nonempty set A has a greatest element amax, then
sup
A
= amax.
Let A = (0,1). Then
sup
A
= 1.
The set A has no greatest element.
Let
A
= {x ∈ Q | x2 < 2}
= {x ∈ Q | x22}.
Then A has no greatest element.
Least Upper Bound Property for Real Numbers R
The following property of real numbers cannot be proved from (P1) - (P12).

(P13) or (P13-LUB) Least Upper Bound Property. If A is a non empty set of real numbers, and A is bounded above, then A has a least upper bound.
N.B. A has a least upper bound as to be interpreted as there is a number x such that x is a least upper bound for A .
Note that (P13) does not hold if the only numbers available were Q, the rational numbers. There is no rational number which is the least upper bound of the set
A√2 = {x | xQ and x2 < 2}.
Relation between Least Upper Bound and Binary Expansion
Our starting point is that every binary expansion represents a real number. As we said in MthT 430 Notes Chapter 6a Binary Expansions and Arguments
Every binary expansion represents a real number x:
x
= ±N.binc1c2…,
ck
∈ {0,1}.
This is the statement that every infinite series of the form
c1 2−1 + c2 2−2 + …,     ck ∈ {0,1},
converges.
Constructing the Binary Expansion of a Least Upper Bound
We give a folding string argument to find the binary expansion of supA.
Let A be a nonempty set of real numbers which is bounded above. Without loss of generality (WLG), we assume that A is contained in [0,1) ≡ [a0,b0). Then
There is a an upper bound 1 = b0 for A,
(1)
There is a an x0A, 0 = a0x01 = b0.
(2)
Now we have that y = supA, if it exists, satisfies 0 = 0.bin0 ≤ x0y ≤ b0 = 1.bin0.
If x0 = b0, STOP!
sup
A = b0.
A has a greatest element b0.
If x0 < b0, we divide the interval [a0,b0) into two intervals [0,[1/2]) and [[1/2],1).
Ask the question: Is m0 = (a0 + b0)/2 an upper bound for A?
If the answer is YES, m0 is an upper bound for A, select the left interval [0,[1/2]) = [a1,b1) by
a1
= 0 = a0,
b1
= m0 = 1

21
= a1 + 1

21
.
Then b1 is an upper bound for A. Let c1 = 0 so that
a1
= .binc1,
b1
= a1 + 1

21
.
If the answer is NO, there an x1 ∈ A, such that m0 = 0.bin1 < x1 ≤ b0 = 1.
Select the right interval [[1/2],1) = [a1,b1) by
a1
= m0,
b1
= b0.
Then b1 is an upper bound for A. Let c1 = 1 so that
a1
= .binc1,
b1
= a1 + 1

21
.
In both cases we have constructed an interval [a1,b1) such that
a1
= 0.binc1,
b1
= a1 + 1

21
,
such that




a1any upper bound for A,
b1 is an upper bound for A.
Now suppose that c1, …, ck, ak = 0.binc1 …ck, b1, …,bk have been chosen so that
ak
= 0.binc1…ck,
bk
= ak + 1

2k
,
and




akany upper bound for A,
bk is an upper bound for A.
If bk ∈ A, STOP!
sup
A = bk.
A has a greatest element bk.
If bk ∉ A, divide the interval [ak,bk) into two parts by taking the midpoint
mk
= ak + bk

2
= ak + 1

2k+1
.
Ask the question: Is mk an upper bound for A?
If YES, select the left interval [ak,mk) by defining
ck+1
= 0,
ak+1
= ak
= 0.binc1…ck ck+1,
bk+1
= mk
= ak+1 + 1

2k+1
.
If NO, select the right interval [mk,bk) by defining
ck+1
= 1,
ak+1
= mk
= 0.binc1…ck ck+1
= ak + 1

2k+1
,
bk+1
= bk
= ak+1 + 1

2k+1
.
In both cases c1, …, ck, ck+1, a1, …, ak, ak+1, b1, …, bk, bk+1 have been chosen so that
ak+1
= 0.binc1…ck ck+1,
bk+1
= ak+1 + 1

2k+1
,
and




ak+1any upper bound for A,
bk+1 is an upper bound for A.
Let
s
=
lim
k→∞ 
ak
= 0.binc1 c2
=
lim
k→∞ 
bk.
Then
s is an upper bound for A. Why? Fix x ∈ A. Then for all k, x ≤ bk, and so x ≤ limk→∞bk = s.
s = supA. Why?
N.B. Even if a system of numbers (such as Q), satisfies (P1 - P12), without assuming P13-LUB, the above construction of the sequences c1, …, a1, …, and b1, …, can be accomplished. So - if, in fact, all binary expansions converge to a number in the system , the supremum of the set A has been constructed. We refer to the property all binary expansions converge to a number in the system as (P-13-BIN).
BISHL: Bounded Increasing Sequences Have Limits
A consequence of (P13-LUB) is that Bounded Increasing Sequences Have Limits .

Theorem. Let {xn}n=1 be a bounded monotone nondecreasing sequence; i.e.
x1 ≤ x2 ≤ …,
and there is a number M such that for n = 1,2, …,
xn ≤ M.
Then there is a number L such that

lim
n → ∞ 
xn = L.
Proof using (P13-LUB): Try
L
=
sup
n 
xn.
For all n, xn ≤ L (L is an upper bound). Given ϵ > 0, there is a natural number N such that L − ϵ < xN ≤ N (L − ϵ is not an upper bound!). Then for all n ≥ N,
L −ϵ < xn ≤ L,
or
|xn − L| = L − xn < ϵ.
Convergence (Meaning) of Binary Expansions implies (P13-LUB)
Let us state a variation of (P13-LUB).

(P13-BIN) - Binary Expansions Converge. Every binary expansion represents a real number x: every infinite series of the form
c1 2−1 + c2 2−2 + …,    ck ∈ {0,1},
converges to a real number x, 0 ≤ x ≤ 1.
We write
x
= ±N.binc1c2…,
ck
∈ {0,1}.
Another way to say this is that every infinite series of the form


k = 1 
ck2−k,     ck ∈ {0,1},
converges to a real number x:
x
=
lim
N→∞ 
N

k = 1 
ck2−k.
(P13-BIN) Implies (P13-LUB)
We have shown: If the real numbers (or any number system!) satisfies (P1 - P12) and (P13-BIN), then this set of numbers satisfies (P1 - P12) and (P13-LUB).
LUB2BIN: (P13-LUB) Implies (P13-BIN)
The converse is also true: If the real numbers (or any number system!) satisfies (P1 - P12) and (P13-LUB), then this set of numbers satisfies (P1 - P12) and (P13-BIN). This would follow if we could show that the nondecreasing sequence (partial sums)
sN = N

k = 1 
ck2−k,     ck ∈ {0,1},
is bounded above . Then
x
=
sup
N 
N

k = 1 
ck2−k
=
lim
N→∞ 
N

k = 1 
ck2−k
=

k = 1 
ck2−k.
To show that the sequence of partial sums {sN} is bounded above , we begin with a BARE HANDS calculation on a geometric series.

Lemma: Geometric Series - BARE HANDS. If |r| < 1,
N

k = 0 
rk
= 1 − rN+1

1−r
,
(♣)


k = 0 
rk
= 1

1−r
.
(♠)
Proof: To show (♣),
(1 −r)(1 + …+ rN) = 1 − rN+1,
and for 1 − r ≠ 0, divide by 1 −r.
To show (♠), if |r| < 1,

lim
N → ∞ 
rN+1
= 0,


k = 0 
rk
=
lim
N → ∞ 
1−rN+1

1−r
.
= 1

1−r
.

Theorem. Property (P13-LUB) implies Property (P13-BIN).
Proof: Assuming Property (P13-LUB), and of course Properties (P1 - P12), we show that the non decreasing sequence
sN = N

k = 1 
ck2−k,     ck ∈ {0,1},
is bounded above:
N

k = 1 
ck2−k
N

k = 1 
1 ·2−k


k = 1 
1 ·2−k
= 1

1 − [1/2]
− 1
= 1.
Thus


k = 1 
ck2−k
=
lim
N→∞ 
N

k = 1 
ck2−k
=
sup
N 
N

k = 1 
ck2−k
≤ 1.



File translated from TEX by TTH, version 4.05.
On 18 Sep 2014, 21:23.