The Wednesday Morning Math Challenge: Week 12 Answers

Last week’s problem was a question that you might encounter in a college-level math class, but by week 12, we can handle it. If you haven’t had a chance to take a look at it, you can find it here.

---

---

The set of numbers between 0 and 1 is not countable. We’re going to show this using a proof by contradiction.

Let’s suppose that the set of numbers between 0 and 1 is in fact countable. That means that we would be able to make a list of every number between 0 and 1 without leaving anything out (assuming, of course, that we went on forever). We’ll use the decimal expansion of each number. (a1,1 is the digit in the first row, first column; a1,2 is the number in the digit in the first row, second column; a5,2 is the digit in the fifth row, second column; and so on.)

[make subscripts]

1.  0. a1,1 a1,2 a1,3 a1,4 ….

2.  0. a2,1 a2,2 a2,3 …

3.  0. a3,1 a3,2 a3,3 …

4.  0. a4,1 …

5.  0. a5,1 …

….

and so on.

Now we’re going to define a new number, b, between 0 and 1. We can also write our new number as a decimal expansion: 0. b1 b2 b3 b4 b5 …

Now we have to address the digits (which are b1, b2, b3…).

Our aim is to make sure that b is not the same as any number on our list. To make sure b isn’t the same as the first number on the list, we will make sure it doesn’t have the same first digit (in other words, a1,1 does not equal b1). To make it easy on ourselves, we’ll consider binary expansions. (Of course, a1,1 can be any number. We are just making sure that relevant digit in b does not equal the corresponding digit in a.) Let’s say a1,1 is 0, then b1 is 1, and if a1,1 is 1, then b1 is 0. Now let’s make sure b isn’t the same as the second number on the list. If a2,2 is 0, then b2 is 1, and if a2,2 is 1, then b2 is 0. Now we’ll make sure b is not the same as the third number on the list. If a3,3 is 0, then b3 is 1, and vice versa. You get the idea. Each step ensures b is not the same as an nth number on our list. You could do this easily by drawing a diagonal across the digits on list and then changing each digit.

So we know b is not included on our list. And yet b is a real number between 0 and 1. We have a contradiction. Our supposition that the set of numbers between 0 and 1 is countable is incorrect. It is uncountable.

This is called Cantor’s diagonal argument, after the mathematician George Cantor, who used the technique to show that there exist infinite sets that are not the same size as the infinite set of natural numbers.