# A set of all strings over {0, 1} and a set of all infinite binary sequences.

For an alphabet $\Sigma = \{0, 1\}$, $\Sigma^{*}$ is a set of all string over the alphabet $\Sigma$.

I know that the set $\Sigma^{*}$ is countably infinite because I can list the members of it. I also know that a set of all infinite binary sequences, $X$, is uncountable. However, I am confused that aren't the members of X also the members of $\Sigma^{*}$?

If yes, how can an uncountable set be a subset of countably infinite set? If no, why is an infinite binary sequence not a member of $\Sigma^{*}$?

• Is $\Sigma^*$ defined to have only finite sequences? If so, then members of $X$ are not members of $\Sigma^*$. Sep 4 '13 at 5:50
No, the members of $X$ are not members of $\Sigma^*$; in fact, $X\cap\Sigma^*=\varnothing$. By definition every $\sigma\in\Sigma^*$ is a finite string of elements of $\Sigma^*$, and every element of $X$ is an infinite string of elements of $\Sigma$. It’s not possible for a string simultaneously to be finite and infinite.