Es el conjunto de todas las secuencias finitas de las letras del alfabeto latino contables/incontables? Cómo probar?

Question

Hoy en la Codificación/Criptografía de clase, estábamos hablando de definiciones básicas, y el profesor mencionó que para un conjunto $A=\left \{ \left. a, b, \dots, z \right \} \right.$ (el alfabeto) se puede definir un conjunto $A^{*}=\left \{ \left. a, ksdjf, blocks, coffee, maskdj, \dots, asdlkajsdksjfs \right \} \right.$ (palabras) como un conjunto que consta de todas las secuencias finitas de los elementos/cartas de nuestros $A$/alfabeto. Mi pregunta es, es este conjunto $A^{*}$ countably o uncountably infinito? No importa cuántas letras hay en el alfabeto? Si lo era, digamos, $A=\left \{ \left. a \right \} \right.$, entonces las palabras en $A^{*}$ sería de la forma $a, aa, aaa, \dots$, lo que, creo, podría permitir a un bijection $\mathbb{N} \to A^{*}$ donde un entero significaría el número de una en una palabra. Algo análogo puede hacerse con un alfabeto que se compone de 26 letras (alfabeto latino), o puede countability/uncountability ser que se demuestre lo contrario? Y como se mencionó antes, me pregunto si el número de elementos en el alfabeto de los asuntos, o si todo lo que hace es cambiar la fórmula para un bijection.

P. S. Ahora que lo pienso, tal vez podríamos biject de $\underset{n}{\underbrace{\mathbb{N}\times\mathbb{N}\times\mathbb{N}\times\dots\times\mathbb{N}}}$ a un conjunto de palabras $A^{*}$ cuyo alfabeto $A$ $n$ elementos? Gracias!

Answer 1

Supongamos que el 26 letras son "dígitos" en base-26. Cualquier finito cadena de letras que puede ser pensado como un único entero positivo en la base-26. Los enteros positivos son contables, por lo que su conjunto de cadenas debe ser así.

(En realidad, para ser más precisos: dejar que los símbolos en su conjunto de ser distinto de cero dígitos establece un bijection entre su conjunto y un subconjunto de los números naturales, por lo que la cardinalidad del conjunto sea igual o inferior a la de los números naturales; dejar que los símbolos en su conjunto se dígitos, incluyendo un "cero" de dígitos, establece un surjection de su conjunto en los números naturales [ceros a la izquierda de la causa de múltiples dígitos cadenas de golpe el mismo número natural], por lo que la cardinalidad del conjunto es mayor que o igual a la de los números naturales; por lo que desde la cardinalidad del conjunto de se ≥ y ≤ que el de los números naturales, que son iguales en cardinalidad, por lo que su conjunto es contable.)

Answer 2

La proposición. Si el alfabeto $A$ es contable, el conjunto $A^*$ de todos finito de cadenas en que el alfabeto es también contables.

Prueba. $A, A^2 = A \times A, A^3 = A \times A \times A$, etc. son todos contables y bien ordenado (en virtud de la orden lexicográfico inducida por el buen orden de $A$), y $$A^* = \bigcup_{n=0}^{\infty} A^n$$ and the union of countably many well-ordered countable sets is again countable, so $Un^*$ es contable. Nota esto no requiere el axioma de (contables) la elección.

Sin embargo, el conjunto $A^{\mathbb{N}}$ de todos los countably-infinito de cadenas es contable si y sólo si $A$ está vacío o es un 1-letra del alfabeto.