Demostrar que el conjunto de las sucesiones estrictamente crecientes de números naturales no es enumerable.

Question

¿Cómo se demostraría esta afirmación?

El conjunto de las sucesiones estrictamente crecientes de números naturales no es enumerable.

Llevo bastante tiempo intentando resolver esto, sin embargo no sé ni por dónde empezar.

Answer 1

Como se indica en otras respuestas, hay muchas formas de demostrarlo. Pero siempre podemos volver a lo básico. Basta con una sencilla prueba de diagonalización por contradicción. Supongamos que existe tal enumeración. Tal vez sea ésta:

1 --> 1, 2, 3, 5, ...
2 --> 4, 5, 7, 100, ...
3 --> 1, 2, 3, 8, ...
4 --> 2, 4, 5, 6, ...

Ahora toma el primer número de la secuencia uno y súmale uno. Ese es nuestro primer número: 2.

Ahora toma el segundo número de la secuencia dos - 5 - y el número del paso anterior - 2. Toma el mayor y súmale uno: 6.

Ahora toma el tercer número de la secuencia tres -3- y el número del paso anterior -6-. Tome el mayor y añadir uno: 7.

Ahora toma el cuarto número de la secuencia cuatro -6- y el número del paso anterior -7-. Toma el mayor y súmale uno: 8.

Sigue haciéndolo y construye la secuencia de naturales crecientes monótonos:

2, 6, 7, 8, ...

Por suposición, esta secuencia está en nuestra enumeración, pero ¿dónde puede estar? No puede estar en el punto n para ningún n porque por su construcción el elemento n de esta secuencia es mayor que el elemento en el punto n de la secuencia n.

Eso es una contradicción, y por lo tanto no puede haber tal enumeración.

Answer 2

Podemos definir una inyección muy simple a partir de los números reales en el intervalo $[1,10)$ a su conjunto asignando $x \in [1,10)$ a la secuencia $$\lfloor x \rfloor, \lfloor 10x \rfloor, \lfloor 100x \rfloor, \lfloor 1000x \rfloor, \dots.$$ Por ejemplo, $\pi$ correspondería a la secuencia $$3, 31, 314, 3141, 31415, 314159, \dots.$$ Hay algunas comprobaciones sencillas para hacerlo

• la secuencia resultante es creciente, y
• dos números reales diferentes corresponden a secuencias diferentes.

Una vez hecho esto, este argumento muestra que las secuencias estrictamente crecientes tienen al menos la cardinalidad del conjunto $[1,10)$ que es continuo.

Answer 3

Trazar cualquier secuencia estrictamente creciente $(a_n)$ a una secuencia $(b_n)$ de sus incrementos módulo $2$ : $$\{0,1\}\ni b_n \equiv a_{n+1}-a_n \pmod 2$$ Esto, por supuesto, no es biyectivo ni siquiera inyectivo, pero es un mapeo suryectivo, de ahí que la cardinalidad del conjunto de $a$ secuencias no es inferior a la de $b$ secuencias.

Y se sabe que este último es estrictamente mayor que $|\mathbb N|$ porque $b$ son secuencias binarias, que son la representación uno a uno de $2^\mathbb N$ . También pueden asignarse biyectivamente a $\mathbb R$ .

Answer 4

El mapa de $\{0,1\}^{\mathbb N}$ en el conjunto de secuencias estrictamente crecientes de números naturales dadas por

$$(a_n) \to (1+a_1,3+a_2, 5+a_3,7+a_4, \dots)$$

es inyectiva. Dado que $\{0,1\}^{\mathbb N}$ es incontable, hemos terminado.

Answer 5

Para cualquier subconjunto infinito de los números naturales, se pueden enumerar sus miembros en orden creciente, y entonces se tiene una secuencia que es estrictamente creciente.

Además, si se toman dos subconjuntos infinitos distintos de los números naturales, se obtienen dos secuencias diferentes. (Hay algún número $k$ que está en uno de los subconjuntos y no en el otro, y este número aparece en una secuencia y no en la otra).

Así que el número de secuencias estrictamente crecientes de números naturales es al menos tan grande como el número de subconjuntos infinitos de números naturales.