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.
On
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?
On
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.
Hint: There is in fact a natural correspondence with the natural numbers. Read backwards from the last $1$, and think binary.