En la teoría de conjuntos ZFC si definimos el ordinal de Church-Kleene como es habitual, es el menor límite superior de un conjunto contable de ordinales contables, entonces es contable él mismo porque $\aleph_1$ es regular, pero si no tenemos en cuenta el axioma de choiche qué pasa (sé que $\aleph_1$ no es necesariamente más regular)? ¿Es siempre cierto que el ordinal de Church-Kleene es contable?
Respuestas
¿Demasiados anuncios?
La posibilidad de contar con $\omega_1^{CK}$ no tiene nada que ver con el axioma de elección: considere el mapa $\omega_1^{CK}\rightarrow\omega$ enviando $\alpha$ al menor índice de una máquina de Turing que calcula una copia de $\alpha$ . Esto es claramente una inyección, por lo tanto $\omega_1^{CK}$ es contable.
En general, para cualquier noción "simple" de definibilidad, el menor ordinal no definible en ese sentido es contable, y esto lo atestigua el mapa que envía un ordinal definible al menor número que representa una definición para ese ordinal. Si está interesado en tales "primeros ordinales indefinibles", puede encontrar este resumen de Madore que vale la pena.
(¿Por qué he dicho "simple" en lo anterior? Bueno, resulta que podemos encontrarnos con algunos fenómenos Impares en general - véase por ejemplo este artículo de Hamkins, Linetsky y Reitz . Pero esto no es un problema aquí).
DanV
Puntos
281
Permítanme darles un argumento diferente -y un poco más enrevesado- que el directo dado por Noé, con la esperanza de presentar una manera diferente de ver este tipo de problemas.
Las máquinas de Turing son absolutas entre $V$ y $L$ . Esto significa que todo lo computable $\alpha$ también es computable en $L$ . En particular, cada $\alpha<\omega_1^{CK}$ es contable en $L$ .
Todo lo computable $\alpha$ en $L$ también es computable en $V$ . Por lo tanto, la definición de $\omega_1^{CK}$ en $L$ debe ser el mismo que en $V$ . Desde $L$ satisface la elección, se trata de un ordinal contable en $L$ por lo que debe ser contable en $V$ .
El punto clave aquí es la combinación de estas dos partes:
-
Tenemos un modelo interno que satisface la elección, que está de acuerdo con $V$ sobre lo que significa ser computable,
-
y ser contable es una $\Sigma_1$ por lo que es absoluta hacia arriba.
Se puede utilizar en infinidad de situaciones. Por ejemplo, cuando queremos argumentar que la intersección diagonal de $\kappa$ subconjuntos cerrados y no limitados de un regular $\kappa$ forman un subconjunto cerrado e ilimitado de $\kappa$ Podemos hacer esto comprobando manualmente que la prueba habitual funciona, o podemos argumentar en algún modelo interno de elección que capture nuestra secuencia de palos, y utilizar el hecho de que no se puede destruir un subconjunto de palos de un cardinal regular para argumentar que la intersección diagonal en el modelo interno sigue siendo un palo en $V$ .
