¿Existe una relación entre los conjuntos incontables y el crecimiento exponencial?

Question

Dejemos que $S_n$ sea la colección de todas las cadenas binarias de longitud $n$ . Parece que como $n$ va al infinito, $S_n$ se convierte en el conjunto de todas las cadenas binarias infinitas. Cada vez que incrementamos $n$ El tamaño de $S_n$ dobles, así que $|S_n|$ está experimentando un "crecimiento exponencial" con respecto a $n$ .

Del mismo modo, dejemos que $C_0$ sea el conjunto $\{0, 1\}$ , dejemos que $C_1$ sea el conjunto $\{0, \frac{1}{3}, \frac{2}{3}, 1\}$ , dejemos que $C_3$ sea el conjunto $\{0, \frac{1}{9}, \frac{2}{9}, \frac{1}{3}, \frac{2}{3}, \frac{7}{9}, \frac{8}{9}, 1\}$ y así sucesivamente. Parece que como $n$ va al infinito, $C_n$ se convierte en el conjunto de Cantor. De nuevo, cada vez que incrementamos $n$ El tamaño de $C_n$ dobles, así que $|C_n|$ está experimentando un "crecimiento exponencial" con respecto a $n$ .

En ambos casos, el "resultado límite" del "crecimiento exponencial" es un conjunto incontable.

Por el contrario, dejemos que $K_n$ sea el conjunto de $k$ -tuplas de $\{1, 2, ..., n\}$ . El tamaño de $K_n$ sólo experimenta un "crecimiento polinómico", y en este caso, el "resultado límite" (conjunto de todos los $k$ -de enteros positivos) es un conjunto contable.

¿Existe una relación entre los conjuntos incontables y el crecimiento exponencial?

En particular, me pregunto si hay algún resultado interesante que generalice o amplíe las observaciones que hice anteriormente.

Answer 1

Se equivoca en su primera apreciación. El caso límite es contable.

El caso límite de $S_n$ no es $2^\omega$ el conjunto de cadenas binarias infinitas, sino $2^{<\omega}$ el conjunto de cadenas finitas de longitud arbitraria. De manera similar, $C_n$ no limitan como el conjunto de Cantor, sino como el conjunto de los puntos finales de los intervalos eliminados, que es simplemente un conjunto contable.

La cuestión aquí es la misma en todos los casos, $$\sup n^k\neq n^{\sup k}.$$

Answer 2

He aquí un ejemplo de conexión entre los conjuntos incontables y el crecimiento exponencial. Consideremos un árbol binario de profundidad infinita. Cada camino hacia abajo del árbol codifica una cadena binaria de longitud infinita, y todas las posibles cadenas binarias de longitud infinita se contabilizan en los caminos del árbol. El argumento de la diagonal de Cantor demuestra que el conjunto de todos los caminos posibles no puede ponerse en correspondencia 1 a 1 con los números naturales, es decir, no es contable. El recuento de ramas/nodo crece exponencialmente a medida que se desciende en el árbol (se duplica en cada nivel posterior del árbol).