Mathematics 242 – Principles of Analysis Discussion 2 – Solutions October 7, 2004

Discussion Questions

A) The second defining property of the supremum s = sup(S) above says: if s′ < s, then there exists x ∈ S such that x > s′. Show that this statement is equivalent to saying: If t is any upper bound for S, then t ≥ s. (Note and Hint: In fact, many analysis books define the supremum using this alternate form, because it clearly shows that sup(S) is the “least upper bound” for S. The relation between these statements comes from one of our basic logical equivalences!)

Solution: The form given in question A for saying s = sup(S) is the contrapositive of the book’s definition: Book: If s′ < s, then s′ is not an upper bound for S (that is, there exists an x ∈ S such that x > s′). Contrapositive of this is: If s′ is an upper bound for S, then s′ ≥ s. Replacing s′ by t we get exactly what is here.

B) Let S be a nonempty bounded subset of R. Show that s = sup(S) is unique. Method: Assume that two real numbers s, s′ both satisfy the definition, then deduce that s must equal s′.

Solution: Using the form from problem A, let s and s′ both satisfy the defining properties of sup(S). Since s is sup(S), and s′ is an upper bound for S, we get from A, s ≤ s′. Similarly, since s′ is sup(S) and s is an upper bound for S, s′ ≤ s. These two inequalities show s = s′.

C) Prove that if x < y are any real numbers, then there exist infinitely many rational numbers r with x < r < y. Hint: Last time we showed that there is one such rational number. Try to extend that proof.

Solution: In class we showed that given any reals x < y, there exists a rational number r_{1} with x < r_{1} < y. Repeat the same argument, with r_{1} playing the role of y. There exists a rational number r_{2} with x < r_{2} < r_{1} < y. Continuing in the same way, we can find a sequence of rational numbers r_{n}, n ∈ N such that x < ⋯ < r_{n} < ⋯ < r_{2} < r_{1} < y for all n. The r_{i} are distinct by construction, so there are infinitely many rationals between x and y (a whole denumerable set of them).

D) Let a/b be a rational number written as a fraction in lowest terms with 0 < a/b < 1.

1) Show using the Archimedean Property that there exists an integer n such that

\frac{1}{n + 1} ≤ \frac{a}{b} ≤ \frac{1}{n}.

Solution: Consider the number b/a > 1. By the Archimedean Property of N, there exists a natural number n such that n ≤ b/a ≤ n + 1. Then inverting (and correspondingly reversing the inequalities), we have

\frac{1}{n + 1} ≤ \frac{a}{b} ≤ \frac{1}{n}

as claimed. Note: We cannot have equality in both cases, so we could always write one of these as a strict inequality. If a/b happens to equal the reciprocal of a natural number we could make a = 1/(n + 1), for instance.

2) If n is chosen as in part 1, show that a/b − 1/(n + 1) is a fraction that when written in lowest terms has numerator is less than a.

Solution: We have a/b−1/(n+1) = (a(n+1)−b)/(b(n+1)). If this fraction is not already in lowest terms, then canceling common factors can only make the numerator smaller. Hence to prove what we want here, it suffices to show that

a(n + 1) − b < a.

From the proof of part 1, an < b ≤ a(n + 1), so subtracting a(n + 1) everywhere, −a < b − a(n + 1) < 0. Reversing signs (and switching the inequalities correspondingly), a > a(n + 1) − b, which is what we wanted to show.

3) Use the Principle of Strong Induction from Problem Set 3 to show that every rational number a/b as above can be written as a sum:

\frac{a}{b} = \frac{1}{n_{1}} + ⋯ + \frac{1}{n_{k}}

for some distinct natural numbers n_{i}. (For instance 49/90 = 1/3 + 1/9 + 1/10.)

Solution: The result from part 2 says that if we find the integer n with 1/(n + 1) ≤ a/b < 1/n, then the difference a/b − 1/(n + 1), written in lowest terms, must have a smaller numerator than a/b. This means that we should try to set up an induction argument where the “induction variable”, so to speak, is the integer a in the numerator of the fraction.

The base case for the induction is numbers of the form a/b = 1/b (where a = 1). These are already written in unit fraction, or “Egyptian” form. So the base case requires no proof ( :) ). Now consider any 0 < a/b < 1 in lowest terms. By part 2, there exists an integer n + 1 such that a/b − 1/(n + 1) has numerator < a when written in lowest terms. By strong induction, this means that we can write

\frac{a}{b} − \frac{1}{(n + 1)} = \frac{1}{n_{1}} + ⋯ + \frac{1}{n_{k}}

for some distinct integers n_{1}, …, n_{k}. But then

\frac{a}{b} = \frac{1}{(n + 1)} + \frac{1}{n_{1}} + ⋯ + \frac{1}{n_{k}}

and the only thing left to prove is that n+1, n_{1}, …, n_{k} must all be distinct. Since n_{1}, …, n_{k} are distinct, this just means that we need to show n + 1 ≠ n_{i} for i = 1, …, k. Aiming for a contradiction, suppose on the contrary that n + 1 = n_{i} for some i, and for convenience, renumber so that i = 1. Then a/b − 2/(n + 1) = 1/n_{2} + ⋯ + 1/n_{k} > 0. But for n > 1, we always have 2/(n + 1) > 1/n. This implies that a/b − 1/n > a/b − 2/(n + 1) > 0. But note that n was chosen to make 1/(n + 1) ≤ a/b < 1/n, so a/b − 1/n < 0. Hence, we have found a contradiction because a/b − 1/n cannot be both positive and negative. Hence the denominators n + 1, n_{1}, n_{2}, …, n_{k} are all distinct.