Prove that the set R of all real numbers is uncountable and also prove that any open
Answers
Answer:
Theorem 1 (Reals are Uncountable). |R| 6= |N|
Proof. We will instead show that (0, 1) is not countable. This implies the theorem because if there were a
bijection from R to N, one could compose it with a bijection we have from (0, 1) to R, and get that (0, 1) is
countable.
We will go by contradiction. Suppose that (0, 1) is countable. Then, fix a bijection f : N → (0, 1). Then,
for each natural number n we have some decimal sequence that n maps to
0 7→ 0. a0,0 a0,1 a0,2 a0,3 a0,4 . . .
1 7→ 0. a1,0 a1,1 a1,2 a1,3 a1,4 . . .
2 7→ 0. a2,0 a2,1 a2,2 a2,3 a2,4 . . .
3 7→ 0. a3,0 a3,1 a3,2 a3,3 a3,4 . . .
4 7→ 0. a4,0 a4,1 a4,2 a4,3 a4,4 . . .
.
.
.
.
.
.
.
.
.
What we’d like to show this is not actually a bijection. Motivated by the idea that N is the “smallest”
infinity, we must have that (0, 1) is “larger” if it’s not equal. Therefore, we will try to argue this is not a
surjection. To do this, we must find something that the number doesn’t hit.
Well, we will construct a decimal which represents something “new” which is not hit. So we build our
number at different stages, one for each natural number. At stage i, we will define the ith decimal digit of
our number, and we will do it in such a way that f(i) is not going to equal the number we have in question.
We hit our first snag when we realize that decimal numbers do not unique represent real numbers. That
is to say, the following reals are equal, but have different decimal representations.
.49999 . . . = .50000 . . .
Therefore, in representing our numbers about we choose the convention if a number terminates in that way,
we will pick the representation which terminates in infinitely many 0’s, and not 9’s.
Let’s begin defining our sequence. First, for i = 0, we define the 0th digit of our number, which we will
denote b0. Well, a0,0 is some decimal number. We will make it so b0 6= a0,0. To do this, let’s just take b0 to
be 1 if a0,0 is not 1, and 2 otherwise. Therefore, b0 is taken to be different than a0,0.
Now, the choices of what I changed it to was arbitrary, except that I wanted to avoid defining things
in my sequence 9’s since then I may accidently make a sequence terminating in all 9’s which will equal a
sequence on the list.
We continue in this way; to define bi
, I look at ai,i; that is the ith digit of the decimal representation of
f(i). And I change it in the same way; if ai,i is not 1, we will make bi equal to 1, and otherwise we will let
it be 2.
0 7→ 0. a0,0 a0,1 a0,2 a0,3 a0,4 . . .
1 7→ 0. a1,0 a1,1 a1,2 a1,3 a1,4 . . .
2 7→ 0. a2,0 a2,1 a2,2 a2,3 a2,4 . . .
3 7→ 0. a3,0 a3,1 a3,2 a3,3 a3,4 . . .
4 7→ 0. a4,0 a4,1 a4,2 a4,3 a4,4 . . .
.
.
.
.
.
.
.
.
.
As the end we will have defined a sequence b0, b1, b2, . . .. We can read this as a decimal, which we call b:
b := 0. b0 b1 b2 b3 b4 . . .
We claim this is not on our list. For, if it were f(i) = b for some i ∈ N. But, the ith decimal digit of f(i) is
different then the ith decimal digit of b by the way we defined b, which means they are different numbers.
Thus b is not on our list.