## Even “More” Infinite Sets

May 20, 2009 17:41 by scibuff

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. $S=\left \{0.1, 0.9, 0.11, 0.99\cdots \right \}$ 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 $S$ into a one-to-one correspondence with the set of natural numbers $\mathbb{N}=\left \{0, 1, 2, 3,\cdots \right \}$. In other words, we can create a list of ALL elements in our set (just as we did before) like so:

$0\rightarrow s_{0}$

$1\rightarrow s_{1}$

$2\rightarrow s_{2}$

$\vdots$

Now, consider any such arbitrary listing of the elements of $S$, for example, this one:

$s_{0}=0.111111\cdots$

$s_{1}=0.999999\cdots$

$s_{2}=0.191919\cdots$

$s_{3}=0.919191\cdots$

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 $s$ in the following way:

• Make the first (decimal) digit of $s$ be different from the first (decimal) digit of $s_{0}$, i.e. 9
• Then make the second (decimal) digit of $s$ be different from the second (decimal) digit of $s_{1}$, 1
• The third (decimal) digit of $s$ to be different from the third (decimal) digit of $s_{2}$, i.e. 9
• The fourth(decimal) digit of $s$ to be different from the fourth (decimal) digit of $s_{3}$, i.e. 1
• etc …

It is relatively easy to show that a number created in such a way as $s$ CANNOT be on our list. If $s$ were on the list then $s = s_{n}$ for some $n\in \mathbb{N}$. So, in particular, the n-th (decimal) digit of $s$ must be equal to the n-th (decimal) digit of $s_{n}$. But that is not possible by the very definition of $s$.

On the other hand, set $S$ is the set of all real numbers between 0 and 1 with decimal representations consisting of 1s or 9s, in particular, $s\in S$.

The assumption that $S$ is countable led us to conclude that $s\notin S$ and at the same time $s\in S$, which is impossible. Therefore $S$ must be uncountable.

On a side note: $S$ 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)