1549901369-Elements_of_Real_Analysis__Denlinger_

2.8 *countable and Uncountable Sets 125

Step 2. By (15) above, and by Theorem 2.7.5 above, {xn} is a Cauchy

sequence. By our hypothesis, every Cauchy sequence converges. Thus, we may

let L = lim Xn·

n-->oo

Step 3. Let x ES. Since each Xn is an upper bound for S, Xn 2: x. Reviewing

the proof of Theorem 2.3.12, we see that the proof does not depend on the

completeness property. Thus, by Theorem 2.3.12, L 2: x. Hence, we conclude

that L is an upper bound for S.

Step 4. Claim: 'Vn, Xn 2: L.

Proof: In Step 3 we concluded that Lis an upper bound for S. Now, suppose

v is also an upper bound for S. To prove: L ::::; v. For contradiction, suppose

v < L.

. 1 1
Let c = L - v. Smee -2n ---+ 0, :3 k EN 31 -k 2 < c. Now recall that in Step 1

we showed that Xk+l -

2

1

k is not an upper bound for S. Hence, :3 x ES 31

1

X > Xk+l -

2

k

1

2: L -

2

k (See Step 4.)

> L - c = v. (Since

2

1

k < c.)

Thus, x > v, contradicting the supposition that v is an upper bound for S.

Therefore, by contradiction, L::::; v. Finally, we have proved that

L = supS. •

2.8 * Countable and Uncountable Sets

Georg Cantor (1845- 1918) in his celebrated scheme for distinguishing between
the relative sizes of infinite sets, introduced the notion of "countable" and
"uncountable" sets. Briefly, he began by observing that two sets "have the same
number of elements" if there is a 1-1 correspondence^16 between the elements
of the two sets. Thus, infinite sets can have the same number of elements as
proper subsets of themselves. For example the set of natural numbers N and the
set of even numbers E = {2, 4, 6, 8, · · · } have the same number of elements,
since the function f:N---+ E, given by f(n) = 2n, is a 1-1 correspondence.
Cantor showed that the set of natural numbers is the "smallest" infinite
set in the sense that every infinite set must have a subset in 1-1 correspondence
with N. According to Cantor's definition, an infinite set is countable if it is

16. A 1-1 correspondence from a set A to a set B is a function f : A --> B that is 1-1 and
    onto; see Appendix B .2.