## Uncountable Infinity

I think I’m finally ready for an attempt at explaining this proof, but a short background is needed on proofs. Generally a statement is proven by assuming something, and showing that this assumption leads to what you want. These are usually called, if-then statements.

We start with the if part. If blahdy blah is true, then we need to somehow use the fact that blahdy blah is true in order to get the then statement to be true. This proves the entire statement. For a small example consider the statement, “if it is raining, then something is wet.” I would prove this by assuming that it is raining and considering what that implies. Well since it is raining, there must be water coming from some clouds, since there is water coming out of some clouds, this water must be touching something and so that something is wet.

Again this is the normal proof technique, but for the uncountable infinity proof, I need to talk about the technique called proof by contradiction. It involves first assuming the if part just like before, but then instead of finding your way to the end of the proof with that information, you assume that the conclusion is false. Then you use the information given when assuming the if part to be true and the then part to be false in order to show that a contradiction happens eventually. Getting a contradiction means that your assumption of the conclusion was incorrect, so that the true statement will come from assuming the opposite of the conclusion you assumed. An example might clear this up.

To prove that “if it is raining, then something is wet” by contradiction we instead assume that “if it is raining then something is NOT wet.” Then we show that this statement leads to a contradiction which proves that this statement is false so that the original statement must be true. If it is raining, then whatever the rain falls upon is certainly wet, this contradicts that nothing is wet, thus we have a contradiction so that something is indeed wet.

Finally, let’s move on to what I want to talk about. I am going to prove that the irrationals between 0 and 1 are uncountable by contradiction. That is, I am going to show that there are more irrationals between 0 and 1, than there are rational numbers. To do this by contradiction, I assume instead that the irrationals between 0 and 1 are countable.

Remember being countable means that I can match them up with the natural numbers $\mathbb{N} = \{0,1,2,...\}$ This is equivalent to saying that I can write them in a list. Since I’ve assumed the irrationals to be countable, let me try to write them in a list and see if I can get a contradiction.
I’ll label my irrationals in this list by $x_{1},x_{2},x_{3},\ldots$. Since each irrational is a string of infinite digits and between 0 and 1, I’ll have to say each $x = .\text{something}$
To do this in a nice arbitrary and organized way, we construct a table as below.

 $x_{1}=.a_{11}a_{12}a_{13}a_{14} \ldots$ $x_{2}=.a_{21}a_{22}a_{23}a_{24} \ldots$ $x_{3}=.a_{31}a_{32}a_{33}a_{34} \ldots$ $x_{4}=.a_{41}a_{42}a_{43}a_{44} \ldots$ $x_{5}=.a_{51}a_{52}a_{53}a_{54} \ldots$ $\vdots$

Each letter a is sub scripted by it’s position in the list. For example $a_{43}$ is the third digit of the fourth irrational number in the list and $a_{52}$ is the second digit of the fifth irrational in the list. In general $a_{mn}$ is the n’th digit of the m’th irrational number. Where each digit is allowed to be a number 0 through 9.

To get a contradiction, I want to find an irrational number that is not contained in this list by using clever math magic. Doing so will lead to a contradiction because I claimed to be able to list all of the irrationals between 0 and 1 when in fact that was impossible.

I do the following to construct this irrational not on the list. I’ll first call it
$y = .b_{1}b_{2}b_{3}b_{4}\ldots$ and then I choose each digit wisely to ensure it is not on the above list. For each subscript of each b, I look at the matching diagonal subscript in my list.
So for $b_{1}$ I look $a_{11}$, for $b_{2}$ I look $a_{22}$, for $b_{3}$ I look $a_{33}$ and so on forever.
So for each nth digit of the nth number on the list, I pick the digit $b_{n}$ to be something else. By doing this I ensure that $b_{n} \neq a_{nn}$ for every possible n. So then since at least one digit of this new number I made is always different from a digit for every number in the list, this new number can never been equal to a number already on the list. More formally I can write the new number y, like this:

$b_{n} = \left\{ \begin{array}{lr} 1 & : a_{nn} = 2\\ 2 & : a_{nn} \neq 2 \end{array} \right.$

This is saying that for each digit, $b_{n}$, in the new number y, make the digit be 1 if the nth digit of the nth number is 2, but when the nth digit of the nth number on the list is not 2, then make $b_{n}$ be 1. Defining the number in this way ensures that it never equals a number in the list, as stated above.

Therefore it is not on the list, so this proves it is impossible to list all of the irrational numbers, so there are more irrationals than there are natural numbers. Next time I will talk about power sets.