# Cantor's Diagonal Argument

1. Aug 25, 2011

### Kevin_Axion

I was reading this up on Wiki so I'll just give a quick overview and then ask my question.

Let $\cal{S}$ be an infinite sequence of sequences $(s_1,\; s_2,\: s_3,...,\; s_n)$ such that each $s_i$ contains an infinite amount of elements that are either a $0$ or a $1$.

The sequence $\cal{S}$ is countable since every element belonging to the sequence can be mapped to $\mathbb{N}$ i.e it is bijective.

Now for the sake of simplifying, let $n$ represent the sequence number and $m$ be the element of the sequence.

For example let $s_1 = (1,\; 0,\; 0,\; 1,... )$ then $s_{1,\; 1} = 1$

Let there exist a sequence $s_0$ such that the first element of $s_0$ is $0$ if the first element of the first sequence i.e $s_{1,\; 1}$ in $\cal{S}$ is $1$ otherwise let $s_{0, 1}$ be $1$. This rule applies for all elements of $s_0$ such that any $s_{0,\; n} \neq s_{n,\; n}$. This proves that $s_0$ is unique but how does it prove it's uncountable? I mean if $n$ represents the element number of the sequence $s_0$ and every $n$ can be mapped to a subset of $\mathbb{N}$ isn't it countable?

Last edited: Aug 25, 2011
2. Aug 25, 2011

### SteveL27

You just showed that $s_0$ is not any $s_i$ for i > 0. So your original list does not contain ALL of the possible binary sequences. But since your original list S was arbitrary, that shows there is no list that contains all binary sequences. So the number of binary sequences is uncountable.

3. Aug 25, 2011

### Kevin_Axion

Oh, very good. I think I read the conclusion wrong, I get it now. Thanks!