In my previous post (you should read it first before continuing here), I wrote about a little bit about infinite sets and how we can get a sense of size for some of them. This time, I will give a solution to a problem which will, together with the previous result, demonstrate that sets with infinitely many elements have a “measure” of size, and that not all infinite sets are “equally” infinite.
Problem: Show set of real numbers between 0 and 1 with decimal representations consisting of 1s or 9s, i.e. is uncountable.
Solution: To solve this problem we will use a proof by contradiction just as we did before.
Suppose, that similarly as in the last problem, we can put our into a one-to-one correspondence with the set of natural numbers . In other words, we can create a list of ALL elements in our set (just as we did before) like so:
Now, consider any such arbitrary listing of the elements of , for example, this one:
For the following argument the order of the elements on the list is irrelevant. The important thing is we have listed them ALL. Now, suppose with create a number in the following way:
- Make the first (decimal) digit of be different from the first (decimal) digit of , i.e. 9
- Then make the second (decimal) digit of be different from the second (decimal) digit of , 1
- The third (decimal) digit of to be different from the third (decimal) digit of , i.e. 9
- The fourth(decimal) digit of to be different from the fourth (decimal) digit of , i.e. 1
- etc …
It is relatively easy to show that a number created in such a way as CANNOT be on our list. If were on the list then for some . So, in particular, the n-th (decimal) digit of must be equal to the n-th (decimal) digit of . But that is not possible by the very definition of .
On the other hand, set is the set of all real numbers between 0 and 1 with decimal representations consisting of 1s or 9s, in particular, .
The assumption that is countable led us to conclude that and at the same time , which is impossible. Therefore must be uncountable.
On a side note: can actually be put into one-to-one correspondence with the entire set of real numbers (which also true of any open interval of non-zero length)