Encontrar la cardinalidad de una secuencia infinita creciente de cadenas binarias

Question

Una "secuencia infinita creciente de cadenas binarias" es una serie $w1, w2, …$ de cadenas binarias finitas, tal que para cada número $i$ , cadena $w_i$ es un prefijo de $w_{i+1}$ .

Por ejemplo, $“101”, “10100”, “101001”,“1010010111”, … $

Dejemos que $S$ sea el conjunto de infinitas secuencias crecientes de cadenas binarias. ¿Cuál es la cardinalidad de $S$ ? Demuestra tu respuesta. $$$$

Sé que la cardinalidad de las cadenas binarias finitas es $_0$ y la cardinalidad de las cadenas binarias infinitas es $$ . Every sequence in $ S $ is:$$ {{0,1}}^{0} \N - Flecha derecha 2^{0} = $$

$S$ es una unión contable de infinitas secuencias crecientes de cadenas binarias, por lo que tengo $|S|\leq $ .

¿Cómo puedo demostrar que $ \leq|S|$ ¿Y es correcta mi primera dirección?

Gracias.

Answer 1

Para mostrar $\aleph \le |S|$ se puede establecer una biyección entre las infinitas cadenas binarias y el subconjunto de $S$ que consiste en aquellas secuencias que aumentan un bit cada vez con sólo leer la secuencia.
Como ejemplo, la cadena $1011000101\ldots$ correspondería a $1,10,101,1011,10110,101100,1011000,101100010,1011000101,\ldots$

Para demostrar que $|S| \le \aleph$ Me inyectaría $S$ en $\aleph \times \aleph$ . Cada secuencia en $S$ se puede emparejar con una cadena binaria para los bits y una cadena binaria que muestra dónde dejamos de añadir bits en cada etapa. Dejamos que a $1$ significa "parar aquí" por lo que la secuencia $1,101,1011,10110001,101100010,1011000101\ldots$ tendría la misma cadena que la anterior como primera entrada y $1011000111\ldots$ como su segunda entrada. Ahora bien, si tiene $|\aleph \times \aleph|=\aleph$ ya está hecho.