Are all binary sequences that terminate with $0$s countable? Consider a subset of binary sequences that contains all binary sequences that terminate with a $0$. For example, $001000...$ and $111100000...$. Is this set countable? I think it is not because the number of such sequences don't correspond with the natural numbers, but I don't have a clear idea. Can someone show a proof?
Thanks.
 A: Hint: There is in fact a natural correspondence with the natural numbers. Read backwards from the last $1$, and think binary.
A: If you prepend a $1$ on the sequence and cut off all the trailing zeros, can you convince yourself that the resulting sequences are all distinct?  Can you find a natural injection from these sequences to the naturals?
A: Let $A$ be the set of all binary sequences which terminate with $0$s. Define a map
$$f:A\to [0,1],\quad f(x_1,x_2,\dots)=\sum_{n=1}^\infty x_n2^{-n}$$
We claim that $f$ is injective. Let $x=(x_1,x_2,\dots)$ and $y=(y_1,y_2,\dots)$ be two distinct binary sequences in $A$. Let $n_0\in \mathbb{N}$ be such that
$$x_n=y_n,\quad \forall n<n_0\text{ and }x_{n_0}\neq y_{n_0}$$
Note that such an $n_0$ must exists because $x,y$ are distinct sequences. Without loss of generality assume
$$x_{n_0}=1,\quad y_{n_0}=0.$$
Then it follows that
$$f(x)\geq \sum_{n=1}^{n_0-1}x_n2^{-n}+2^{-n_0}.$$
On the other hand, as $y$ terminates with $0$s, this means it only has finitely many $1$s. Hence there exists $n_1\in\mathbb{N}$ with $n_1>n_0$ and $y_n=0$ for all $n>n_1$. It follows that
$$\begin{aligned}f(y)&= \sum_{n=1}^{n_0-1}y_n2^{-n}+\sum_{n=n_0+1}^{n_1} y_n2^{-n}\\
&=\sum_{n=1}^{n_0-1}x_n2^{-n}+\sum_{n=n_0+1}^{n_1} y_n2^{-n}\\
&<\sum_{n=1}^{n_0-1}x_n2^{-n}+\sum_{n=n_0+1}^{\infty} 2^{-n}\\
&=\sum_{n=1}^{n_0-1}x_n2^{-n}+2^{-n_0}\\
&\leq f(x)\end{aligned}$$
Hence we have shown that $f(x)\neq f(y)$ whenever $x\neq y$, so $f$ in injective.
Furthermore, for $x\in A$, $x$ only has finitely many $1$s. Thus it is easy to see that $f(x)$ is a rational number for each $x\in A$. It follows that $A$ is countable because the set of rationals is countable.
A: Note that every such sequence can be written as a tuple: $(a_1,\dots, a_n)$ where $a_n$ corresponds to the last $1$.
Now, the set $T$ of such tuples is obviously a subset of $$\bigcup_{n\in \Bbb N} \Bbb N^n$$
Which is a countable union of countable sets.
A: Replace the last 0 with a 1.  Reverse the number.  Subtract 1.  That is a bijection to the MST-first binary representation of natural numbers.
Example, 01010 to 01011 to 11010 to 11001 or 25.
Or, if you want to be even more direct:
$$f(x) = \text{The smallest sequence larger than x ending in zero, under a lexicographical ordering}$$
That works for pretty much every countable set.
