# Cardinality of a uncountable set.

1. Jul 11, 2010

### R.P.F.

1. The problem statement, all variables and given/known data

Let S be the set consisting of all sequences of 0's and 1's.

S = {(a_1, a_2, a_3,...):a_n = 0 or 1 }

Show that S is uncountable.

2. Relevant equations

3. The attempt at a solution

I'm not sure where to start. I think I should either assume that S~N and use proof by contradiction. Or maybe I could show that S has the same cardinality with R which means there is a bijective map between those two. Both of them don't seem easy.
I would really appreciate it if anyone could show me where to start.

2. Jul 11, 2010

We can use the same classic approach as the one used for proving that the set of all real numbers is uncountable, namely, Cantor's diagonal argument. BWOC, suppose the set is countable. List all these sequences in some order. Then generate a sequence of your own by a method that excludes it from this list, thus arriving at a contradiction, i.e., proving S is uncountable.

3. Jul 11, 2010