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 x £ y (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

ì ï í ï î x Î A, 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 a_max, 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 | x2 £ 2}.

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 | x Î Q 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) º [a₀,b₀). Then

There is a an upper bound 1 = b0 for A, (1) There is a an x0 Î A, 0 = a0 £ x0 £ 1 = b0. (2)

Now we have that [^y] = supA, if it exists, satisfies 0 = 0._bin0 £ x₀ £ [^y] £ b₀ = 1._bin0.

If x₀ = b₀, STOP!

sup A = b0.

A has a greatest element b₀.

If x₀ < b₀, we divide the interval [a₀,b₀) into two intervals [0,[1/2]) and [[1/2],1).

Ask the question: Is m₀ = (a₀ + b₀)/2 an upper bound for A?

If the answer is YES, m₀ is an upper bound for A, select the left interval [0,[1/2]) = [a₁,b₁) by

a1 = 0 = a0, b1 = m0 = 1 21 = a1 + 1 21 .

Then b₁ is an upper bound for A. Let c₁ = 0 so that

a1 = .binc1, b1 = a1 + 1 21 .

If the answer is NO, there an x₁ Î A, such that m₀ = 0._bin1 < x₁ £ b₀ = 1.

Select the right interval [[1/2],1) = [a₁,b₁) by

a1 = m0, b1 = b0.

Then b₁ is an upper bound for A. Let c₁ = 1 so that

a1 = .binc1, b1 = a1 + 1 21 .

In both cases we have constructed an interval [a₁,b₁) such that

a1 = 0.binc1, b1 = a1 + 1 21 ,

such that

ì ï í ï î a1 £ any upper bound for A, b1 is an upper bound for A.

Now suppose that c₁, ¼, c_k, a_k = 0._binc₁ ¼c_k, b₁, ¼,b_k have been chosen so that

ak = 0.binc1¼ck, bk = ak + 1 2k ,

and

ì ï í ï î ak £ any upper bound for A, bk is an upper bound for A.

If b_k Î A, STOP!

sup A = bk.

A has a greatest element b_k.

If b_k Ï A, divide the interval [a_k,b_k) into two parts by taking the midpoint

mk = ak + bk 2 = ak + 1 2k+1 .

Ask the question: Is m_k an upper bound for A?

If YES, select the left interval [a_k,m_k) 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 [m_k,b_k) 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 c₁, ¼, c_k, c_k+1, a₁, ¼, a_k, a_k+1, b₁, ¼, b_k, b_k+1 have been chosen so that

ak+1 = 0.binc1¼ck ck+1, bk+1 = ak+1 + 1 2k+1 ,

and

ì ï í ï î ak+1 £ any 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 £ b_k, and so x £ lim_k®¥b_k = 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 c₁, ¼, a₁, ¼, and b₁, ¼, 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 {x_n}_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, x_n £ L (L is an upper bound). Given e > 0, there is a natural number N such that L - e < x_N £ N (L - e is not an upper bound!). Then for all n ³ N,

L -e < xn £ L,

or

|xn - L| = L - xn < e.

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 {s_N} 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 T_EX by T_TH, version 3.78.
On 29 Oct 2007, 19:08.