Is the Number of Binary Sequences Countable or Uncountable?

  • Thread starter Thread starter Kevin_Axion
  • Start date Start date
  • Tags Tags
    Argument
AI Thread Summary
The discussion centers on the countability of binary sequences, specifically whether the set of all binary sequences is countable or uncountable. It is established that while the sequence of sequences \cal{S} is countable, the construction of a unique sequence s_0 demonstrates that not all binary sequences can be listed. This leads to the conclusion that there is no complete list of binary sequences, proving their uncountability. The participants clarify that the existence of s_0, which differs from all sequences in \cal{S}, shows that \cal{S} does not encompass all possible binary sequences. The final consensus is that the number of binary sequences is indeed uncountable.
Kevin_Axion
Messages
912
Reaction score
3
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:
Physics news on Phys.org
Kevin_Axion said:
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.
 
SteveL27 said:
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!
 
I was reading documentation about the soundness and completeness of logic formal systems. Consider the following $$\vdash_S \phi$$ where ##S## is the proof-system making part the formal system and ##\phi## is a wff (well formed formula) of the formal language. Note the blank on left of the turnstile symbol ##\vdash_S##, as far as I can tell it actually represents the empty set. So what does it mean ? I guess it actually means ##\phi## is a theorem of the formal system, i.e. there is a...
Back
Top