Cardinality of a uncountable set.

[R.P.F.]

Homework Statement

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.

Homework Equations

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.

 

[Raskolnikov]

Homework Statement

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.

Homework Equations

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.

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.

 

[Raskolnikov]

Here, I even found a decent explanation of this method. However, before you click the following link, please try and think of such a method by yourself. Just imagine how great you'll feel afterwards if you get it all by yourself!

Spoiler

http://en.wikipedia.org/wiki/Cantor's_diagonal_argument[/SPOILER]

 

[R.P.F.]

Thanks a lot! I know how to do this now! :)