Abstract. This is the second post dedicated to elementary problems with a set-theoretic solution. We discuss the impossibility of an infinite descending chain of sets $\{X_j\}_{j}$ such that $\P(X_{n+1})=X_n$. This is an exercise in Kunen [1].

El logaritmo no se puede iterar infinitamente

Muy fácil: números reales, operaciones usuales. Específicamente, operaciones que achican. Por ejemplo, “restar 1”. Desde que se inventaron los enteros, nadie teme iterar la operación resto-uno. Es decir, empezando en cualquier número (e.g. el 4) puedo aplicar la operación resto-uno arbitrarias veces y obtengo un resultado significativo. Incluso, infinitamente: puedo armarme una sucesión
\[x_0 \doteq 4 \qquad x_{n+1} \doteq x_n – 1,\]
que fácilmente enumeramos así: $4, 3, 2, 1, 0 , -1, -2,\dots$.

También puedo decrecer geométricamente de manera indefinida: la operación aquí es divido-dos.
\[x_0 \doteq 4 \qquad x_{n+1} \doteq \frac{x_n}{2}.\]
En este caso, nuestra sucesión está acotada inferiormente por el $0$: $4, 2, 1, 0.5, 0.25, 0.125,\dots$ y para seguir tendríamos que aprendernos todas las potencias de 5.

La cosa se pone peluda cuando quiero “decrecer logarítmicamente” (es la frase más confusa que haya escrito en este blog) . Un $\epsilon$ más precisamente, no puedo iterar infinitamente el logaritmo. En base dos, para fijar ideas, $x_0 \doteq 4$, $x_{n+1} \doteq \log_2 x_n$:
\[4, 2, 1, 0, ???\]

Hay una cuestión fundamental con esto. Y motiva un hermoso problema, cuando uno lo ve como conjuntos. Es, quizá más simple, hacer las primeras analogías con $\om=\N_0$.

En primer lugar, puedo simular la operación resto-uno sacando elementos de a uno:
\[X_0 \doteq \om \qquad X_{n+1} \doteq X_n \setminus \{n\}.\]Como $\om$ es infinito (tanto como $\R$ hacia la izquierda), todos los $X_n$ están bien definidos (y son infinitos). En segundo lugar, divido-dos se puede pensar así:
\[X_0 \doteq \om \qquad X_{n+1} \doteq X_n \cap 2^{n+1}\Z.\]
(Esto es una analogía ridículamente intuitiva, pero no por eso deja de gustarme.) Ahora, llegados al caso de logaritmo, una forma de plantearlo es que $X$ es un logaritmo de $Y$ si ${}^X{}2$ (i.e., el conjunto de las funciones de $X$ en $\{0,1\}$) es biyectivo con $Y$. Acá $\om$ ya no nos sirve de nada puesto que

Ejercicio. No hay un $X$ tal que ${}^X{}2$ sea biyectivo con $\om$.

Como $\P(X)$ es biyectivo con ${}^X{}2$, está claro que iterando suficientes veces $\P$ puedo iterar el logaritmo (ir marcha atrás) arbitrarias, finitas veces. Planteo el problema:

¿Se puede definir una sucesión de conjuntos $\{X_j\}_{j\in\N}$ tal que $\P(X_{n+1})$ sea biyectivo con $X_n$ (*)?

La respuesta es no. Dos aspectos fascinantes tiene este problema. Primero: su solución no requiere ninguna hipótesis conjuntista estrambótica. No necesita de la hipótesis del continuo, no tiene relación con el axioma de elección (AC). Los atentos, los más informados, o los que simplemente hayan leído el post con los axiomas recordarán el axioma de regularidad, que dice algo sobre sucesiones decrecientes de conjuntos. Tampoco depende esto. Es exactamente al revés, creo que este problema da una motivación para regularidad. Y esto tiene que ver con el segundo aspecto fascinante: su solución depende de desarrollar la teoría de ordinales. Basta recordar que los ordinales están naturalmente bien ordenados por $\in$.

Una solución, esbozada en el ejercicio I(12) de Kunen [1], comienza así. Ante la ausencia de AC, no podemos asegurar que un conjunto $X$ se pueda bien-ordenar. Pero aún así, Hartogs probó que siempre hay un ordinal $\aleph(X)$ que no se puede inyectar en $X$ (recordemos que AC es equivalente a que si no hay $Y\to X$ inyectiva, hay una $X\to Y$). Ahora bien, el ejercicio de Kunen dice que
\[\aleph(X)<\aleph(\P(\P(\P(X))))\]
para todo conjunto $X$. Como no hay sucesiones decrecientes infinitas de ordinales, esto tiene por conclusión (Ejercicio) que es imposible tener una sucesión como en (*).

Según una discusión en Math.SE, desarrollar la función $\aleph(X)$ de Hartogs o similares parece ser la única manera de resolver este problema.

References

@book{kunen1980,
title = "Set theory: An Introduction to Independence Proofs",
author = "Kunen, Kenneth",
series = "Studies in logic and the foundations of mathematics",
publisher = "Elsevier Science",
address = "Amsterdam, Lausanne, New York",
url = "http://opac.inria.fr/record=b1117475",
isbn = "0-444-86839-9",
year = 1980
}