Is the Number of Binary Sequences Countable or Uncountable?

[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?

 

[SteveL27]

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 n represents the element number of the sequence s_0 and every n can be mapped to a subset of \mathbb{N}.

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.

 

[Kevin_Axion]

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.

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