7
$\begingroup$

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^{*}$?

Thank you in advance.

$\endgroup$
1
  • $\begingroup$ Is $\Sigma^*$ defined to have only finite sequences? If so, then members of $X$ are not members of $\Sigma^*$. $\endgroup$ Sep 4, 2013 at 5:50

1 Answer 1

7
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .