Cadenas finitas de un alfabeto infinito

Question

¿Es el conjunto de todas las cadenas de longitud finita $\Sigma^*$ de un alfabeto infinito $\Sigma$ no numerable?

El procedimiento usual en este tipo de pruebas es que

listar cadenas de longitud 1
listar cadenas de longitud 2
listar cadenas de longitud 3
.......

.......

.......
y así sucesivamente

Pero ahora incluso la primera línea tiene longitud infinita, por lo que la construcción nunca puede detenerse. ¿Qué está mal?

Answer 1

Si el conjunto de letras es incontable, también lo es el conjunto de palabras. Para un alfabeto finito o numerable infinito, uno puede imitar tu argumento de cerca sin meterse en dificultades.

Enumera el alfabeto como $a_0,a_1,a_2,\dots$. Deja que la complejidad $c(w)$ de una palabra $w$ sea el entero más grande $i$ tal que $a_i$ aparece en $w` más el número de letras en $w`. Claramente, para cualquier $n$ solo hay un número finito de palabras $w` tal que $c(w)=n`.

Escribe la(s) palabra(s) de complejidad $0` (solo hay una, la palabra vacía). Luego escribe la(s) palabra(s) de complejidad $1`, en orden lexicográfico. Después escribe las palabras de complejidad $2`, en orden lexicográfico. Y así sucesivamente.

Concluimos que si el conjunto de letras no está vacío y es finito o numerable infinito, entonces el conjunto de palabras es numerable infinito.

Answer 2

Si tu alfabeto es contablemente infinito y ordenado entonces puedes

• Listar todas las cadenas de longitud $m$ usando letras hasta e incluyendo la $n$-ésima donde $m+n=2$
• Listar todas las cadenas de longitud $m$ usando letras hasta e incluyendo la $n$-ésima donde $m+n=3
• etc.

Si lo deseas, puedes comenzar con la cadena vacía.

Cada una de las sublistas es finita (puedes utilizar tu sugerencia dentro de cada sublista) y así la lista general es contable.

Answer 3

$\Sigma^*$ es infinita numerable. Recordemos,

\begin{equation} \Sigma^* = \bigcup_{n \in \mathbb{N}} \Sigma^n \end{equation}

para cada valor $n \in \mathbb{N}$, el conjunto $\Sigma^n$ es numerable, por lo tanto, $\Sigma^*$ es una unión numerable de conjuntos numerables, por lo tanto, es numerable.

Prueba:

Debemos proporcionar una biyección, un mapeo de cada elemento en $\Sigma^*$ a un elemento único en $\mathbb{N}$, es decir, una función que sea biunívoca.

Sea $\Sigma = \{0, 1\}$ y $ f: \Sigma^* \rightarrow \mathbb{N}$ nuestra biyección.

Ahora empezamos escribiendo todas las cadenas en $\Sigma^*$ en orden creciente. Primero todas las cadenas de longitud $0$, luego todas las cadenas de longitud $1$, todas las cadenas de longitud $2$, todas las cadenas de longitud $3$, y así sucesivamente.

\begin{equation} \Sigma^* = \{\epsilon, 0, 1, 00, 01, 10, 11, 000, 001, 010, 100, 011, 110, 101, 111, ...\}\\ \mathbb{N} = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ... \} \end{equation}

Al inspeccionar lo anterior, claramente tenemos una biyección $f: \Sigma^* \rightarrow \mathbb{N}$, es decir, una función que mapea cada elemento de nuestro alfabeto a un elemento único de los números naturales. Por lo tanto, $\Sigma^*$ es infinita numerable. $\square$

Answer 4

Has caído en una falacia común: una prueba no se generaliza, pero eso no significa que no haya otra prueba. La técnica que utilizas falla aquí pero puede arreglarse fácilmente.

Supongamos que tu alfabeto es contable, es decir, $\Sigma = \{a_0, a_1, a_2, \dots\}$. La idea es que puedes (de forma recursiva) enumerar el conjunto $\Sigma^n = \{w \in \Sigma^* \mid |w| = n\}$ para cualquier $n$ fijo en $\mathbb{N}$ y luego entrelazar todas estas enumeraciones (infinitas contablemente).

Para enumerar $\Sigma^n$, considera la siguiente construcción (nota que $\Sigma^1 = \Sigma$ sirve como punto de anclaje) que entrelaza las enumeraciones de $\Sigma$ y $\Sigma^{n-1}$, concatenando sus elementos con las palabras de $\Sigma^n$:

$\qquad \Sigma^n = \{\ \Sigma_0\Sigma^{n-1}_0,\quad \Sigma_0\Sigma^{n-1}_1, \Sigma_1\Sigma^{n-1}_0,\quad \Sigma_0\Sigma^{n-1}_2, \Sigma_1\Sigma^{n-1}_1, \Sigma_2\Sigma^{n-1}_0,\quad \dots \ \}$

Continuando con este esquema, enumeras todo $\Sigma^n$ (de manera computable).

Ahora, $\Sigma^*$ se puede enumerar de la misma manera:

$\qquad \Sigma^* = \{\ \varepsilon, \quad \Sigma^1_0, \quad \Sigma^1_1, \Sigma^2_0, \quad \Sigma^1_2, \Sigma^2_1, \Sigma^3_0,\quad \dots\ \}$

La técnica utilizada a menudo se llama entrelazado. Si escribes todo el espacio como una tabla, verás que se asemeja mucho al esquema canónico para enumerar los racionales.

Nota que si $\Sigma$ es no contable, $\Sigma^*$ es trivialmente no contable también.