subconjunto del espacio binario contables?

Question

Sé que el conjunto de todas las secuencias binarias es incontable. Ahora consideremos el subconjunto de este conjunto, que cada vez que un dígito es $1$, su próximo dígito debe ser $0$. Es este conjunto contables?

Creo que no es porque es como "la mitad" de la serie de secuencias binarias. Por eso me refiero a que si acabo de eliminar las secuencias con un $1$, seguido por una $1$, entonces me quedo con la secuencia requerida. Pero no estoy seguro de cómo se muestran claramente. Alguien puede pensar en un bijection que probar esto? O estoy equivocado? Por favor, ayudar.

Gracias

Answer 1

Si insisten en tener un bijection, aquí va uno. Su conjunto $S$ es el conjunto de todos binario infinito palabras que no contiene factor de $11$. Cualquier palabra puede ser el único escrito como un infinito palabra sobre el alfabeto $\{0, 10\}$, $S = \{0, 10\}^\omega$. Por ejemplo, $$0100100010010(100)^\omega = \color{blue}{0}\color{red}{10}\color{blue}{0}\color{red}{10}\color{blue}{0}\color{blue}{0}\color{red}{10}0\color{red}{10}(\color{red}{10}\color{blue}{0})^\omega$$

De ello se desprende que el mapa de $\{0,1\}^\omega \to S$ consiste en reemplazar cada $1$ $\color{red}{10}$ es un bijection. No hay necesidad de Cantor-Bernstein-Schroeder teorema.

Answer 2

Usted puede escribir explícitamente una función inyectiva de un conjunto de todas las secuencias binarias para el conjunto está considerando: solo mapa de cada secuencia de un con $0$ insertado en cualquier otra posición.

Así que no, definitivamente no es contable.

Answer 3

Su conjunto tiene un incontable subconjunto: considerar las secuencias infinitas de $a$ $b$ donde$a=10$$b=00$, el conjunto de estas secuencias tiene la misma cardinalidad del conjunto de secuencias de $0$ $1$ (sólo el mapa de $a \mapsto 0$$b \mapsto 1$), y es que claramente es un subconjunto del conjunto.

Answer 4

He aquí otro (posiblemente) interesante manera de demostrar uncountability, ya que has etiquetado a esta como una topología de que se trate. Usted puede inyectar su conjunto en $[0,1]$ en la evaluación mapa

$$ (x_i) \mapsto \sum_{i = 1}^\infty \frac{x_i}{2^i} $$

Este es inyectiva en su conjunto (pero no el conjunto de todas las secuencias binarias, ya que $0.0111\dots = 0.100\dots$). Vamos a mostrar la imagen de este mapa es un conjunto perfecto, y por lo tanto incontable (ver Rudin, o alguna otra fuente en espacios métricos). Seguramente no hay ningún punto en el conjunto está aislado, porque si tenemos una expansión $x = 0.a_0 a_1 \dots a_2$, y si esta expansión no finalmente terminan en ceros, se puede truncar la expansión encontrar otro número en la imagen, que es lo más cercano a este número como sea posible. Si el número no terminan en ceros, usted puede agregar una a una posición arbitraria para obtener otro número tan cerrado como sea posible. Ahora supongamos $\lim x_i = x$, donde cada una de las $x_i$ es en la imagen de la evaluación. Debemos tener $0 < x < 1$, para los si $x = 1$, $x_i$ el tiempo debe ser de la forma $0.11\dots$, lo cual es imposible. Escribir $x = 0.a_0 a_1 \dots$. Supongamos $a_k = 1$. Si forzamos $|x_i - x| < 1/2^{k+2}$, luego la primera a la $k+2$ dígitos de $x_i$ debe ser el mismo que el primer $k+1$ dígitos de $x$, por lo tanto $a_{k+1} = 0$. Por lo tanto la imagen es perfecta, y el conjunto es incontable.

La intuición me dice que este conjunto es, probablemente, fractal, similar a la del conjunto de Cantor, pero no puedo visualizar muy bien.

Answer 5

Usted puede inyectar el conjunto de todas las secuencias de enteros en este su conjunto ($A$): $$ (n_i)_{i<\omega} \mapsto (1 + 0^{n_0+1} + 1 + 0^{n_1+1} + \dotsc)\colon \omega^\omega\A. $$ donde el valor se entiende como un infinito de expresiones regulares. Es decir, el $i$-th $1$ es seguido por $n_i+1$ muchas $0$s. ("$+ 1$" Garantiza que el valor de esta función es un miembro de A.)

Por lo tanto, $A$ tiene cardinalidad $\lvert A\rvert \ge |\omega^\omega| = \lvert\Bbb R\rvert$. Pero $A\subseteq 2^\omega$, lo $\lvert A\rvert \le \lvert 2^\omega\rvert = \lvert\Bbb R\rvert$. Por el Cantor-Schroeder-Teorema de Bernstein, $\lvert A\rvert = \lvert\Bbb R\rvert$.