Mathematics 242 – Principles of Analysis Discussion 2 – More on Cardinality and Countability Friday, September 16

Background

In class last time we introduced the following ideas:

• Two sets A, B have the same cardinality (written A ∼ B) if there is a 1-1 and onto function f : A → B. (The intuitive meaning of this is that the two sets have the “same number” of elements. But of course if the sets are infinite, then we don’t actually have a usual number that represents the size of the set! And moreover, some strange things are possible. For instance, A ∼ B while A ⊂ B but A ≠ B is definitely possible. Think of A = N and B = Z.)

• A set A is countable if N ∼ A.

We also showed that N and R do not have the same cardinality by a proof based on the Nested Interval Property.

Today, we will look at a different way to see that N and R do not have the same cardinality following an idea of the 19th century German mathematician Georg Cantor. We will also see another slightly tricky case of sets with the same cardinality.

Discussion Questions

A) (The “Cantor Diagonalization Argument”). In this problem you will work through a proof that the set of real numbers in the open interval (0, 1) is not countable. (This implies that the whole set of real numbers isn’t countable either, of course.) Here’s the basic idea of Cantor’s proof. Again, we argue by contradiction. Suppose the set (0, 1) was countable. In other words, suppose we can list all of the real numbers in (0, 1) as x_{n} = f(n) for n ∈ N for some 1-1, onto function f. Write each x_{n}’s decimal expansion in the form

(2)  \begin{aligned}x_{1} & = .d_{11}d_{12}d_{13} ⋯ \\ x_{2} & = .d_{21}d_{22}d_{23} ⋯ \\ ⋮ & =  ⋮ \\ x_{n} & = .d_{n1}d_{n2}d_{n3} ⋯ \\ ⋮ & =  ⋮ \end{aligned}

(That is, d_{nm} is the mth decimal digit in the decimal form of the nth number in the list: d_{nm} ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} for all n, m.) Make a new decimal number x = .b_{1}b_{2}b_{3} ⋯ from the expansions above by the rule:

b_{n} = \{ \begin{matrix}2 & if d_{nn} ≠ 2 \\ 3 & if d_{nn} = 2 \end{matrix}

(note: the d_{nn} are the diagonal entries in the big, infinite array of digits in the table above).

1) Suppose the table (2) above looked like

\begin{aligned}x_{1} & = .25443523 ⋯ \\ x_{2} & = .13403005 ⋯ \\ x_{3} & = .99893299 ⋯ \\ x_{4} & = .84723464 ⋯ \end{aligned}

How does the decimal expansion of the number x start out here?

2) Explain in general why the real number represented by x cannot be the same as any of the x_{n} in the list. Explain how this establishes the statement we are trying to show: The set of real numbers in the open interval (0, 1) is not countable

3) (“Not so fast!”) Some possible “objections” to the proof sketched above are:

a) Some real numbers have more than one decimal expansion. (For example, what’s another way to write .31\overline{9} = .31999999 ⋯ ?) Doesn’t that cause a problem?

b) Can’t we apply the same argument to the set of rational numbers in (0, 1) – (0, 1) ∩ Q. That set is countable (it’s a subset of a countable set) so we could list it as the {x_{1}, x_{2}, x_{3}, …}. Doesn’t that mean there’s something wrong with the proof?

These objections in fact don’t invalidate the proof. Why not?

B) We saw in class that (0, 1) ∼ R via the 1-1, onto function f(x) = cot(πx) mapping f : (0, 1) → R. What if we include one of the endpoints of the finite interval? Do [0, 1) R have the same cardinality? If so, how can we construct a 1-1, onto function g : [0, 1) → R? Some observations:

• We can try to use the function f(x) = cot(πx) as much as we can to get g.

• But g(0) must be some real number, so the “trick” is to figure out where g(0) goes.

• Suppose x_{n} = 1/(n + 1) for n ∈ N. We could try making g(0) = f(x_{1}) = f(1/2) (whatever that number is) and g(x) = f(x) for x ∈ (0, 1). But then g is not 1-1 because g(0) = f(1/2) = g(1/2). What if we then make g(1/2) = g(x_{1}) = f(x_{2}). That fixes one problem but it creates another. (Why?) Can we fix it?