12
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I believe that this question is not a good fit for this site in its current form. Questions should be asked that can conceivably have a 'right' answer. I believe this question can be tweaked by adding some criteria that can be measured: what is the most inutitive way, how can I show this using topology, etc. $\endgroup$ – Brian Rushton Mar 16 '14 at 1:49
  • 10
    $\begingroup$ @BrianRushton I don't agree. A "right" answer to this question would be any answer that argues or proves that the reals are uncountable using methods that are more intuitive than Cantor's diagonal argument, and would be accessible to beginning students. $\endgroup$ – Jim Belk Mar 16 '14 at 2:07
  • $\begingroup$ @JimBelk I see what you mean. Looking more at the other questions on the site, perhaps I was too hasty. $\endgroup$ – Brian Rushton Mar 16 '14 at 2:09
  • $\begingroup$ What’s the repeating decimal annoyance? $\endgroup$ – Wrzlprmft Mar 16 '14 at 11:51
  • 1
    $\begingroup$ @Wrzlprmft If you do it naively, you can generate both 0.100... and 0.011..., which would result in the argument possibly producing a value already in the list. I've seen this be dealt with in several ways. One is using only digits like {5,7} (and then proving that this actually is unique), and another is defining a more complicated function to generate the new value that "obviously" produces a unique value by interspersing 0's. I am not particularly happy with either of these explanations, because they make the argument more complicated to follow. $\endgroup$ – adamblan Mar 16 '14 at 12:14
7
$\begingroup$

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$

$\endgroup$
  • 2
    $\begingroup$ Your comments at the end about "indescribable" (or as I mention below uncomputable) reals is, I think, one of the major reasons the idea of diagonalization is so important to teach early on. My background generally involves teaching this sort of topic to computer scientists, and the idea that you can't write a program to compute every real is a really important point to get across alongside the halting problem. $\endgroup$ – adamblan Mar 17 '14 at 6:42
  • $\begingroup$ @adamblan Still, one has to be careful, as sequences like $1,2,3,1,2,3,1,2,3,\ldots$ or $0,0,1,0,1,2,0,1,2,3,\ldots$ might seem to contain infinite information (i.e. the intuition in the post wouldn't work here), but are in fact describable (well, I just did it, didn't I?). The concept of "indescribability" might pose some problems. On the other hand, it is one of these rewarding things that when done correctly "lights up" the minds of students ;-) $\endgroup$ – dtldarek Mar 30 '14 at 19:58
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It's interesting; all of the proofs of this fact use essentially this argument. Baire proofs, measure proofs like mine below, diagonalization, and yours all depend on showing that you can exclude a neighborhood around each rational point and still have something left over. They all are fundamentally equivalent. $\endgroup$ – Brian Rushton Mar 17 '14 at 3:13
  • 1
    $\begingroup$ I'm not sure if this fits the "more intuitive" criteria. It didn't take me long to figure out Cantor's but this one is giving me issues. This could be because of allergy medicine though. $\endgroup$ – David G Mar 17 '14 at 4:13
  • 1
    $\begingroup$ @Skytso, if the proof gives you issues, maybe try it as an algorithm. E.g. if your enumeration starts with $q_1=1/1, q_2=2/1, q_3=1/2, q_4=3/1, ...$, you can see what the $x$'s are. $\endgroup$ – user173 Mar 17 '14 at 4:26
  • 1
    $\begingroup$ I don't disagree that ignoring repeating decimals results in a bad proof. But as, Skytso pointed out...I don't think this is any more intuitive. $\endgroup$ – adamblan Mar 17 '14 at 6:40
  • 1
    $\begingroup$ You should replace "rationals" by "reals" in your second paragraph: as written, this only proves that there are irrational reals. $\endgroup$ – Benoît Kloeckner Mar 30 '14 at 9:27
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Neat. Too bad that it doesn't translate to a proof of the halting problem for Turing machines. $\endgroup$ – vonbrand Mar 17 '14 at 16:38
  • 2
    $\begingroup$ In between steps 1 and 2 there are certain assumptions about the $\sigma$-additivity of the Lebesgue measure introduced. This may or may not be intuitive. As to your final sentence, the set $\{\pi\} = \mathbb{R} \setminus [(-\infty,\pi)\cup (\pi,\infty)]$ satisfies your description and is arguably easier to draw. $\endgroup$ – Willie Wong Mar 18 '14 at 12:25
  • $\begingroup$ @WillieWong Your example may in fact be slightly essier to draw than the Cantor set :) $\endgroup$ – Brian Rushton Mar 18 '14 at 12:27
  • $\begingroup$ A student might ask: Why is the "size" of the real numbers infinite? Your claim is that the "size" of e.g. the rational numbers is finite (right?). But clearly you don't mean "cardinality" when you say "size", for neither of these sets in finite. I can imagine how to push the argument along (something like: suppose the "size" of the real numbers is finite with length $N \in \mathbb{R}$; note that $[0, N+1] \subset \mathbb{R}$, so the real numbers must be of "size" greater than $N$ - contradiction). Still, it all seems a bit confusing and circular; more so than Cantor's argument, at least. $\endgroup$ – Benjamin Dickman Mar 30 '14 at 3:19
  • $\begingroup$ @BenjaminDickman Here I am using 'size' as an analogy for measure. $\endgroup$ – Brian Rushton Mar 30 '14 at 3:21
4
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ Sorry, the proof doesn't convince me at second read of the game. Perhaps I'm just tired... $\endgroup$ – vonbrand Mar 30 '14 at 3:33
  • $\begingroup$ @vonbrand Maybe on a third read! $\endgroup$ – Benjamin Dickman Mar 31 '14 at 2:56
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Just to be clear, it does no harm to the argument to include duplications in the putative "list of all reals", so there is no need to choose one convention or the other for reals that have more than one decimal representation (i.e., terminating decimals). It is only in the act of constructing a "new" real that one has to beware of constructing a sequence of digits that is different from any in the list, but nevertheless represents a real number that is already in the list. And as you say, it is simple enough to avoid this by just avoiding 9s. (There really isn't any reason to avoid 0s.) $\endgroup$ – mweiss Mar 31 '14 at 1:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.