Is the set of the specific sequences of 0's and 1's countable?

Question

The allowable sequences of 1's and 0's are such that all 1's must appear before any 0 if it is to be allowed as a sequence in the set. Moreover, a 0 can appear alone, but a 1 cannot. The sequences can be finite or infinite. So the following are allowable sequences:

• 00
• 10
• 11000

While these are not:

• 1
• 01
• 1010

My thoughts are that the sequence can be enumerated in a similar way to ordered pairs of positive integers which are themselves countable. That is, we represent the pairs as (no. of 1's, no. of 0's) and then since the set of ordered pairs of positive integers are countable, so is this set.

Just wondering if my thought process is correct or if others have a better method of justifying whether this set is countable or not.

Answer 1

Yes, it is countable. There is only one such sequence with infinitely many $1$'s, which is the sequence consisting only of $1$'s. Then, for each $n\in\mathbb N$, you can consider the set $S_n$ of all sequences, such that the $n$^th is $1$ and no term after that one is $1$. But your set is the union of the $S_n$'s (and each $S_n$ is countable), the only sequence with infinitely many $1$'s and the seuence which consist only of $0$'s (there are only countably many such sequences).

Answer 2

Any sequence is uniquely defined by the number of all elements in it and by the number of ones in it. So it is parametrized by $2$ numbers(extended). Therefore, you have an injection in $\left(\mathbb{N}\cup\{\infty\}\right)\times \left(\mathbb{N}\cup\{\infty\}\right)$ which is countable. Thus, your set of all allowable sequences must also be countable.

Answer 3

Another way to count those sequences:

First notice that you have both finite and infinite sequences. Since the set of all finite sequences is countable, the set of finite sequences fulfilling your condition obviously cannot be larger. So we only have to look at the infinite such sequences.

There's exactly one such sequence with infinitely many $1$s, namely the sequence consisting only of $1$s.

The sequences with finitely many $1$s are completely determine by the number of $1$s; for each $n\in\mathbb N$ (taken to include $0$) there's exactly one such sequence, which starts out with $n$ $1$s and continues with infintely many $0$s. Since we thus have a bijection between $\mathbb N$ and the set of those sequences, that set is countable.

Therefore the set of all those sequences is also countable, since it is the union of two countable sets and one singleton set.