What different ways do people use to show students that $\mathbb{R}$ is uncountable?

Question

In particular, if you use Cantor's diagonalization argument, do you ignore the repeating decimal annoyance? Or prove that it's not a problem?

Is there another clean way that gives students intuition on the uncountability of the reals?

Answer 1

I think that the set of reals isn't the one you would like to start with. The problem with it is that they have their quirks and for many it is counter-intuitive that any open interval is of uncountable size. On the other hand, there are many other objects with which the Cantor's diagonal argument works as well (sometimes it works even better). To name a few:

• Infinite binary sequences, functions $\mathbb{N} \to 2$ or $\mathcal{P}(\mathbb{N})$. We define $g(k) = f_k(k) \oplus 1$.
• Unbounded functions $\mathbb{N} \to \mathbb{N}$. We define $g(k) = f_k(k)+k+1$.
• Strictly increasing functions $\mathbb{N} \to \mathbb{N}$. We define $g(k) = \max_{i = 0}^{k}f_i(k)+1$.
• Infinite subsets of $\mathbb{N}$. We sort them and proceed as with strictly increasing functions/sequences.

To make the appearance even stronger, make the case how any natural number contains a finite amount of information (e.g. you can write it down in finite, even if arbitrarily long time), while some of the above objects hold infinite amount of information (functions/sequences $\mathbb{N} \to \mathbb{N}$ are perfect for this). This could be done by show how you can take any finite amount of information from it, and it is still the same (in a sense):

• if you take some bits from natural number, it will get smaller, and eventually, after finite number of steps, will decrease to zero,
• similar thing happens to sequences which have only finitely many non-zero entries,
• on the other hand, if you truncate some prefix from a sequence of infinite support, the rest still retains an infinite amount of information.

Now you can move to reals, perhaps using continued fractions (where rationals are exactly the fractions of finite length), or some other methods and show that there are at least as many reals as the aforementioned objects. Then, you could make an analogy between truncating the prefix and taking an arbitrarily small open interval. Also, note that we take bits of information from the element itself, not the set. For example the set of rationals would still look similar after we would take some elements from it, but no rational number would keep all its information after truncating some of its bits. On the other hand, there are some real numbers which could be written down completely, but more importantly there are those which wouldn't fit on any piece of paper ever.

In fact, the numbers which make $\mathbb{R}$ uncountable are inaccessible to us, because as humans we can write down only finite strings and it's not enough. This changes if we had an access to an alphabet of uncountable size, e.g. by assuming that the world and our behavior is continuous and specifying the number as the length between two dots drawn on a sheet of paper. However, this gets disturbingly close to philosophy, so I shall not continue further.

I hope this helps $\ddot\smile$

Answer 2

If you ignore repeating decimals, you aren't giving a good proof. As an alternative, ignore decimals altogether.

Let $q_n$ be an enumeration of real numbers, starting with $n=1$.

Let $x_0=0$. For each $i$, set: $$x_{i+1}=x_i \ \ \ \ \ \ \ \ \ \ \ \text{ if } q_{i+1} \ge x_i + 4^{-i}/2$$ $$x_{i+1}=x_i + 4^{-i} \ \text{ if } q_{i+1} < x_i + 4^{-i}/2$$

Let $x$ be the limit of the $x_i$. Then $|x-x_{i+1}| \le 4^{-i}/3$ and $|q_{i+1}-x_{i+1}| \ge 4^{-i}/2$.

So $|q_{i+1}-x| \ge 4^{-i}/6$, and $x$ is distinct from all the $q$'s.

Answer 3

One way is to show that no countable set can represent what we think of as the number line.

1.See if your students agree that an open interval $(a,b)$ has 'size' $b-a$.

1. Ask them if the size of a union of sets is less than or equal to the sum of their individual sizes (better done by drawing an exampke of overlapping intervals than by just talking).

2. For any countable set, put an interval of size one around the first element, size 1/2 around the second, and so on. The sum of the individual interval sizes is 2, but the size of the real numbers is infinite.

If they have difficulty visualizng the remaining set, you can show a picture of the Cantor set or the Sierpinski carpet to show how removing a dense set of intervals or disks can still leave points behind.

Answer 4

There might be better or worse choices depending on how you actually build up $\mathbb{R}$. Are you using Dedekind cuts? Are you using (Cauchy) convergent sequences of rational numbers modded out by the appropriate equivalence relation? Are you using an axiomatization with the completeness axiom?

In any event, one way to prove the reals are uncountable that I find somewhat fun is via the game described here. You will have to check through the proof to see what concepts need to be discussed in your class (e.g., intervals, convergence of increasing sequences that are bounded above, perhaps some game theory around "winning strategies").

You can find the original article on this game in an arXiv article, which includes generalizations beyond the uncountability of $[0,1]$ (hence $\mathbb{R}$). It also concludes the uncountability proof by remarking:

This argument is in many ways much simpler than Cantor’s original proof!

(You can decide whether or not this is the case.)

Answer 5

A lot of attempts at avoiding the "non-unique decimal representation" problem from the start have the 'problem' of being less visual. How the normal construction is supposed to work is immediately apparent once you see the attempt at a list being made--or at least much more apparent than dodging around explicitly writing any numbers out. So I generally don't avoid it, at least not at the beginning, and just correct for it afterward. So this essentially goes

1. Convince class that reals in $[0,1]$ are almost the infinite bit strings, but the repeated representations of some numbers are an issue.
2. Based on the 'almost', start by proving the uncountability of the infinite bitstrings through Cantor's argument normally. You're now most of the way there.
3. Show that the 'repeated representation' cases are merely countable, and use basic results about unions of countable and uncountable sets to show that the reals are uncountable as well.

So you show that an easy argument (if you consider the normal diagonal argument easy) almost gets you what you want, and correct for the 'almost' later. I still haven't settled on a "best" way of doing 3 though. Alex Becker gives a nice one here.

I like this for a couple reasons. Firstly because it advocates the proof "technique" of pressing onward with close but not exact arguments and seeing how one can try to continue. Beginning proof students often subconsciously think that a proof must be clear in their head from the very start, and it's useful to see that playing around with similarities can be properly productive. The second is because it shifts the messy part of the proof to resolving a technical detail, and leaves the main thrust of the proof as a clear separate step. So it divides the process clearly into "this is the main idea", and "these are the technical issues you need to resolve", rather than potentially losing the main point behind such technical issues.

Answer 6

I may be misunderstanding the question, but I assume that by the "repeating decimal annoyance" you mean that the diagonalization process may end up producing a bit string that eventually becomes an infinite sequence of 1s, which is equal to a terminating bit string, and therefore the "new" real number that the diagonalization process is supposed to produce might actually replicate a real number that already appears in your enumeration but in a different form.

If that is what you mean, it seems to me that the problem is not intrinsic to the diagonalization argument itself, but rather is an artifact of the (unnecessary) decision to represent real numbers as binary sequences. If instead you represent real numbers in the customary way as decimal sequences, the diagonalization construction protocol can be easily designed so avoid repeating sequences of 9s.

Explicitly: Let $ \{ r_i \}$ be any enumeration of real numbers in the interval $(0,1)$. Let each $r_i$ have the decimal expansion $0. a_{i1} a_{i2} ....$ where each $a_{ij}$ is a digit from the set {0, 1, ... , 9}. We construct a real number $s= 0. b_1 b_2 b_3 ...$ as follows: We let $b_i = 5$ unless $a_{ii}=5$, in which case we let $b_i=1$. Then $s$ has a decimal expansion consisting only of 1s and 5s, but $s$ cannot be the same as any of the decimal expansions in the set $ \{ r_i \}$, because it differs from each $r_i$ in the $i$th decimal place.

The "repeating decimal annoyance" is avoided altogether because in base 10 repeating decimals only lead to different decimal representations of the same real number if the repeating digit is 9, and we have avoided 9s completely in this process.

Of course there's nothing special about 1 and 5; any two digits will work as long as we avoid 9. And there's nothing special about base 10 either; the argument will work fine in any base 3 or higher. The only base in which this doesn't work is base 2, because we are limited to only two digits, and there is therefore no way to pre-empt the possibility of ending up with a string of repeating 1s.

I think the reason people prefer to use the binary representation for this proof is because it provides a tight connection (via the use of characteristic functions for subsets) between this result (that the reals are uncountable) and the more general result that the power set of any set $S$ is always larger than $S$ itself. But depending on your audience and the purpose of the class, that more general result may be both more general than you really need, and too abstract for people to follow.

Answer 7

I use Cantor's diagonal argument. To avoid non-uniqueness issues (which I certainly discuss) I first restrict to $[0,1]$, then agree to always write the expansion with infinitely many 9's rather than 0's. Then when constructing the not listed element I just make sure to use digits other than '0' and '9'. I then wait for the better students to ask "why did you use '4' and '7'?" and I explain that it is arbitrary as long as we don't choose '0' or '9'.

I find this to be an extremely visual argument and most students cope well with it.