¿Por qué el ZFC no "conoce" a todos los ordinales?

Question

Entiendo que existen ordinales que la ZFC no puede probar realmente son ordinales, es decir, que están bien fundadas.

No entiendo cómo puede ser esto. ¿La construcción iterativa de los ordinales de Von Neumann no llega a todos los ordinales? Me refiero a la prueba de que todo conjunto bien ordenado tiene una bijección con un ordinal de von Neumann.

Tal vez prueba que todo conjunto bien ordenado es un ordinal, pero no conoce la extensión de "los conjuntos bien ordenados"?

Answer 1

Hay varias cuestiones aquí.

Una obvia es que hay sólo un número limitado de pruebas y muchos más ordinales, por lo que hay ordinales a los que ni siquiera podemos referirnos dentro de la teoría, por lo que, por supuesto, la teoría no puede probar nada sobre ellos.

Esto es algo sutil, ya que hay modelos de teoría de conjuntos que son definibles por puntos, de modo que cualquier $x$ en el modelo es definible en el modelo. En particular, cada ordinal del modelo es definible. Pero no podemos expresar esto en el lenguaje de la teoría de conjuntos, así que para simplificar las cosas, asumamos aquí que nuestra metateoría ambiental es lo suficientemente poderosa como para que podamos discutir la definibilidad en la teoría de conjuntos. Para ilustrar por qué esto es sutil, el hecho de que hay una fórmula $ \phi $ que en el modelo define un ordinal (es decir, el modelo $M$ satisface que hay una única $x$ de tal manera que $ \phi (x)$ y que $x$ es un ordinal) no significa que $ \mathsf {ZFC}$ prueba que $ \phi $ define un objeto único, e incluso si lo hace, no significa que $ \mathsf {ZFC}$ prueba que ese objeto es un ordinal. Para empeorar las cosas, el modelo ni siquiera tiene que estar bien fundado, o incluso un $ \omega $ -Modelo.

Pero hay más: si ese modelo definible puntualmente está bien fundado, entonces su altura es un ordinal que seguramente no podemos ni siquiera describir en $ \mathsf {ZFC}$ de manera que podamos probar su existencia (¡si pudiéramos, el modelo lo vería!). Por otro lado, si el modelo está mal fundado, entonces hay un ordinal $ \gamma $ que es un segmento inicial adecuado de los ordinales del modelo y, sin embargo, es indescriptible dentro del modelo ( $ \gamma $ podría incluso ser $ \omega $ y, sin embargo, lo que el modelo piensa es $ \omega $ sería otra cosa).

Sin embargo, lo que creo que es la verdadera cuestión, es que lo que realmente se quiere es hablar de ordenamientos bien explícitos de (subconjuntos de) los números naturales que son, digamos, recursivos. Ser recursivo es lo suficientemente robusto como para que podamos hablar de ello en la teoría. Podemos hablar del ordenamiento de los pozos porque podemos hablar de la máquina de Turing que lo enumera. La pregunta es entonces si $ \mathsf {ZFC}$ puede probar el fundamento de tal ordenamiento. Obsérvese que esto también es un tema sutil, ya que no estamos hablando de ordenamientos sino de formas específicas de representarlos: El mismo ordenamiento puede ser enumerado por muchas máquinas Turing diferentes. De algunas de ellas, $ \mathsf {ZFC}$ puede ser capaz de probar que el ordenamiento lineal que describe está bien fundado. De algunos otros, $ \mathsf {ZFC}$ puede que ni siquiera sea capaz de probar que lo que está siendo listado es un ordenamiento lineal. Incluso si nos limitamos a las máquinas que $ \mathsf {ZFC}$ puede probar la lista de ordenamientos lineales, hay algunos que $ \mathsf {ZFC}$ no probará que se trata de un pedido bien fundado. Esto es sólo una consecuencia del hecho de que $ \mathsf {ZFC}$ está sujeto al teorema de la incompletitud: no es una cuestión que podamos resolver aunque cambiemos la teoría a algo mucho más fuerte, aunque restrinjamos nuestra atención a las máquinas que sólo tienen la lista 0. Para ver esto, piense por ejemplo en una máquina que en cada etapa $n$ simplemente lista 0, a menos que haya algún $m \le n$ de tal manera que $m$ codifica una prueba de una inconsistencia en su teoría, en cuyo caso a partir de ese momento procede a enumerar una infinita cadena decreciente ordenada como los números enteros negativos.

Puede parecer que esto es algo insatisfactorio ya que sabemos que el 0 está bien fundado y sólo elegimos la máquina equivocada para hablar de ello. Es un punto justo, pero no resuelve mucho. Tratar de impulsar estas ideas y ver hasta dónde nos llevan nos lleva al análisis ordinal, que es un tema que recomiendo investigar para aclarar más estos asuntos. Por ejemplo, la Aritmética de Peano no puede probar que el ordenamiento de $ \omega $ del tipo $ \varepsilon_0 $ están bien fundadas. Algo similar sucede con $ \mathsf {ZFC}$ y su ordinal teórico de prueba. Pero la verdad es que entendemos muy poco del análisis ordinal a este nivel de generalidad. Lo poco que sabemos es que, por un argumento bastante similar al del final del párrafo anterior, hay funciones recursivas totales cuya totalidad no es demostrable dentro del sistema.

Esta es una de las razones por las que nos preocupamos por los buenos sistemas de notación para los ordinales: nos permitirían definir una jerarquía (¡larga!) de rápido crecimiento de las funciones recursivas totales $f_ \alpha\ !: \omega\to\omega $ de tal manera que cualquier función recursiva total cuya totalidad sea demostrable en $ \mathsf {ZFC}$ es eventualmente dominado por (es decir, crece más lentamente que) uno de los $f_ \alpha $ . Esto nos da una forma de medir las formas en que $ \mathsf {ZFC}$ no describe un ordinal: sería un índice $ \alpha $ de una función $f_ \alpha $ no se puede probar que sea total en la teoría. Esto es precisamente lo que sucede en la aritmética de Peano con $ \varepsilon_0 $ . De nuevo, algo de esto es especulativo ya que los actuales sistemas de notación no llegan a las alturas que se requieren aquí.

Answer 2

Este es un tema sutil, y Noah Schweber vendrá pronto para escribir mucho más de lo que yo podría. Pero déjame darte una versión abreviada.

Dentro de un modelo de ZFC tenemos una colección fija de ordinales, y estos ordinales existen todos allí, y están bien fundados. Pero los modelos son semánticos. Se trata de objetos reales en una interpretación particular. Y diferentes modelos podrían tener diferentes ordinales, de hecho algunos modelos podrían estar completamente infundados!

Pero la probabilidad es sobre las pruebas. Esta es una cuestión sintáctica ahora, no sobre un modelo particular con una colección particular de ordinales. Sólo en el papel, ¿qué se puede probar para ser un buen ordenamiento.

El punto es que en una meta-teoría dada, podemos preguntar qué relaciones en $ \Bbb N$ puede probarse que está bien fundada. Pero como sólo hay muchas pruebas, sólo hay muchos ordinales que son Se ha demostrado que bien fundado.

Si quieres pensarlo, piensa en ello así: toma un modelo contable de ZFC. ¿Cuántos ordinales conoce? ¿Cuántos ordinales podemos definir sobre ese modelo? Aún así, sólo muchos contables. ¿Cómo encaja eso con el hecho de que los ordinales hacen una clase adecuada?