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 ϵ > 0, there is a natural number N such that L − ϵ < x_N ≤ 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 {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 4.05.
On 18 Sep 2014, 21:23.