1
$\begingroup$

Is the union of finite and countably infinite sequence over alphabet $\Sigma=\{1\}$, countably infinite as well?

I understand this is similar a question to the one of finite and countably infinite strings over $\{0,1\}$, however I think that the previous argument is not valid in this case.

Now, countably infinite strings over $\{0,1\}$ can be of any kind, e.g.

$$e_i \in \Sigma^*, e_i=100000...$$ $$e_k \in \Sigma^*, e_k=110000...$$

However, I noticed that if I pose the same question with an alphabet of a character only, say $\{1\}$, there is only 1 infinite sequence that I can generate $11.....$, hence:

$$S = \Sigma^* \cup \{111..\}$$

From this assumption, I could map $0$ to the infinite $11...$ and assume that this set S is uncountable. Is this a valid argument? Can someone help me formalize this?

$\endgroup$
2
$\begingroup$

You haven't defined what you mean by "finite or countably infinite sequence" over an alphabet $\Sigma$, so let me assume that a "finite sequence" is a word over $\Sigma$, while a "countably infinite sequence" is an $\omega$-word over $\Sigma$, that is, a mapping from $\omega$ (the set of natural numbers) to $\Sigma$.

In your case, there is exactly one word of each length $0,1,2,\ldots,\omega$, so the set of "finite and countably infinite sequences" is countable, since the set $\omega + 1 = \omega \cup \{\omega\}$ of possible lengths (which is in one-to-one correspondence with the possible "finite and countable infinite sequences") is countable.

If you want to be very formal, you can show that $\omega + 1$ is countable by giving an explicit bijection between $\omega$ and $\omega + 1$, such as $$ 0 \mapsto \omega, \quad n+1 \mapsto n \text{ for all } n \geq 0. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.