¿Se puede decidir la hipótesis del continuo en el ZFC de segundo orden?

Question

De esta pregunta He encontrado que algunos lógicos afirmaron que el CH se decide en el ZFC de segundo orden, a saber $(ZFC_2 \vdash CH) \vee (ZFC_2 \vdash\neg CH)$ . G. Kreisel's "Pruebas informales de rigor e integridad" de 1967 contiene el resultado relativo a la teoría de conjuntos de Zermelo, aunque no he profundizado en detalles y podría malinterpretar la smth. También T.S. Weston declaró lo contrario en su trabajo de 1977.

¿Es un resultado ampliamente conocido? ¿Es considerado correcto por los lógicos? ¿O aceptan los argumentos de Weston? No he encontrado ninguna discusión moderna sobre ello, aunque parece interesante ya que proporciona una forma natural de definir el valor de verdad del CH y de hecho reabrir el problema del CH.

Answer 1

Hay varios problemas con esto:

En primer lugar, la lógica de segundo orden no es completa. Esto significa que aunque $\varphi$ es cierto en todos los modelos de $T$ no significa que $T$ prueba $\varphi$ .

En segundo lugar, la lógica de segundo orden requiere algún tipo de metateoría de conjuntos, ya que al permitir la cuantificación de segundo orden, la noción de conjunto debe ser preexistente.

Si $\sf ZFC_2$ tiene un modelo entonces es necesariamente isomorfo a $V_\kappa$ para un cardenal fuertemente inaccesible $\kappa$ . En particular, dicho modelo contiene todos los reales, todos los conjuntos de reales, etc. Así que $\sf CH$ es verdadera en todos los modelos de $\sf ZFC_2$ o es falso en todos ellos. En ese sentido, sí, el segundo orden $\sf ZFC$ sí "decide" la hipótesis del continuo. Pero no es la teoría de segundo orden la que decide el valor, sino que lo hereda de la metateoría.

Una de las cosas buenas de la lógica de primer orden es que, en gran medida, es agnóstica respecto a su metateoría. Se puede formalizar en $\sf ZFC$ o en $\sf PA$ o $\sf PRA$ o cualquier sistema que proporcione una inducción suficiente. Con la lógica de segundo orden, hay que heredar algunas de las propiedades de la metateoría. Así que diferentes personas, trabajando en diferentes metateorías, podrían estar en desacuerdo sobre lo que son los "conjuntos" para empezar. Y así, si yo trabajo en una metateoría donde $\sf CH$ es cierto, los resultados serían diferentes a los de alguien que trabaja en una metateoría donde $\sf CH$ es falso.

Answer 2

Versión corta: no hay contradicción, Weston y Kreisel et al quieren decir cosas diferentes cuando dicen "de segundo orden", y (en mi opinión) el artículo de Weston es engañoso en este punto; y la lógica de segundo orden es absolutamente inútil para atacar la CH.

---

El documento de Weston En mi opinión, es bastante engañoso: lo que él llama "ZF de segundo orden" es en realidad una teoría de primer orden que se asemeja a ZF de segundo orden. Sí, se trata de una cosa diferente a la propia ZF - y el quid de la cuestión, si no lo has visto antes, es la distinción entre la semántica estándar y la semántica de Henkin .

El hecho de que Weston se refiera a la semántica de Henkin, y no a la estándar, para la lógica de segundo orden se insinúa cuando escribe

Esta nota presenta una prueba de que en el sentido habitual (teórico de la prueba) de "decidido", la teoría de conjuntos de Zermelo-Frankel de segundo orden (ZF $^2$ ) no decide CH. $\quad$ (El énfasis es mío)

y queda claro en sus argumentos. Por el contrario, Kreisel et al se refieren a la realmente de segundo orden teoría (y ver la parte 2 de esta respuesta para una explicación de lo que están hablando).

Esta distinción es enorme. Lógica de segundo orden completa no tiene un sistema de pruebas completo (y por eso el comentario de Weston deja claro que está tratando una versión de primer orden de ZF de segundo orden; también, esto significa que es engañoso usar " $\vdash$ " en lugar de " $\models$ " cuando se habla de la lógica de segundo orden completa). La "primera ordenación" natural de la ZF de segundo orden, en la que incluimos variables de predicado pero, a pesar de las apariencias, trabajamos con la semántica de Henkin (por tanto, primer orden disfrazado), está sujeta a todas las restricciones habituales de la lógica de primer orden.

Por el contrario, verdadero la lógica de segundo orden (es decir, la lógica de segundo orden con la "semántica estándar") está íntimamente ligada a la teoría de conjuntos: para saber si una estructura satisface una sentencia de segundo orden dada, tenemos que mirar el conjunto de potencias completo de esa estructura, y por supuesto las propiedades del conjunto de potencias completo pueden depender en gran medida de la teoría de conjuntos del entorno (y esto ha llevado a una crítica bastante razonable de la lógica de segundo orden, por ejemplo, el famoso comentario de Quine de que es "teoría de conjuntos con piel de cordero", aunque otros, como Boolos, no están de acuerdo - véase, por ejemplo. este documento para ver algún debate sobre el tema).

Weston es claramente crítico con la lógica completa de segundo orden (EDIT: esto puede ser una interpretación errónea, véase el comentario de Carl más abajo) . Esto es bastante razonable, y de hecho desde una perspectiva teórica de la prueba es difícil ver cómo se no pudo objetar a la lógica de segundo orden completa, dado que no tiene un sistema de pruebas completo. Sin embargo, me parece bastante inexcusable que en ningún momento declare explícitamente que está trabajando en la semántica de Henkin, y en su lugar deje que el lector lo descubra (lo que lleva a posibles confusiones bastante razonables).

---

Entonces, ¿cómo decide la "verdadera" ZF de segundo orden la hipótesis del continuo? Pues bien, argumentamos lo siguiente.

• En primer lugar, observe que hay una frase de segundo orden $\varphi_\mathbb{N}$ que caracteriza la estructura $(\mathbb{N}; <)$ hasta el isomorfismo (esto se debe a que "no tiene una secuencia descendente infinita" es expresable en la lógica de segundo orden, si utilizamos la semántica estándar).

• Ahora considere el lenguaje $\Sigma=\{U, V, <, E,\prec\}$ donde

  • $U, V$ son símbolos de predicado unario (que consideramos como clasifica ), y

  • $<$ , $\prec$ y $E$ son relaciones binarias.

• Vamos a construir una $\Sigma$ -sentencia $\tau$ , que consiste en la conjunción de las siguientes frases:

  • $U$ y $V$ dividir el dominio.

  • $\varphi_\mathbb{N}$ tiene relativizado a $U$ (por lo que la reducción a $\{<\}$ de la $U$ -parte de un modelo de $\tau$ es una copia de $(\mathbb{N}; <)$ ). Este es uno de los tres conjuntos de primer orden en $\tau$ .

  • $E\subseteq U\times V$ (pensada como " $x\in y$ "), $<\subseteq U^2$ (pensada como, bueno, " $<$ "), y $\prec\subseteq V^2$ (se considera que da una ordenación de los elementos del $V$ -parte).

  • Cada subconjunto del $U$ -está representado por un elemento del $V$ -parte: $\forall A\exists b(b\in V\wedge\forall x\in U(x\in A\iff xEb))$ . (Por supuesto " $b\in V$ " y " $x\in U$ "son abreviaturas). Esta es la conjunción de segundo orden número dos.

  • Por último, que para cada $v\in V$ hay una inyección de $\{w\in V: w\prec v\}$ a $\mathbb{N}$ . Esta es la tercera conjunción verdaderamente de segundo orden .

Es fácil comprobar que $\tau$ tiene un modelo si y sólo si se cumple la hipótesis del continuo. Por lo tanto, si se sabe qué oraciones de segundo orden son satisfacibles, entonces se puede averiguar si CH es verdadera es en este sentido que la lógica de segundo orden (¡ni siquiera necesitamos ZF de segundo orden!) "decide" la CH.

Podemos hacer algo peor: podemos cocinar una frase de segundo orden $\psi$ que es verdadera (en la semántica estándar) en toda estructura (= es válida para la lógica de segundo orden completa) si el hipótesis de continuidad generalizada se mantiene; o si no hay un cardinal medible; o etc.

---

Bien, permítanme terminar con un último punto. Usted escribe

parece interesante ya que proporciona una forma natural de definir el valor de verdad de la CH y de hecho reabre el problema de la CH.

Desgraciadamente, este no es el caso. En primer lugar, la afirmación "la lógica de segundo orden decide la CH" requiere que ya creamos que el conjunto de potencias completo de una estructura arbitraria existe; este nivel de realismo teórico de conjuntos ya nos compromete con la afirmación de que la hipótesis del continuo tiene un valor de verdad definido. Así que esta observación no nos acerca a responder a la pregunta de si la CH tiene un valor de verdad definido, porque implícitamente ya lo asume.

En segundo lugar, está el hecho de que la lógica de segundo orden no tiene un buen sistema de pruebas: en general, no hay manera de averiguar que una sentencia de segundo orden dada es satisfacible sin conocer ya los hechos sobre el universo teórico de conjuntos. Así que para saber si la CH es una validez en la lógica de segundo orden completa, necesitaríamos saber si la CH es verdadera. $^1$

(Para un ejemplo más de cómo la lógica de segundo orden depende de la teoría de conjuntos, véase por ejemplo esta pregunta de mathoverflow .)

Por lo tanto, la lógica de segundo orden, aunque es tentadora al principio, no es en última instancia una herramienta útil . En su lugar, es mejor pensar en ello como un interesante objeto de estudio .

$^1$ Vale, está bien, hay formas de evitarlo. Por ejemplo, un conjunto teórico-multiversista argumentaría que la versión de cada universo de la lógica completa de segundo orden decide CH en ese modelo . Pero esto no ayuda realmente, porque entonces la lógica de segundo orden puede decidir CH de diferentes maneras en diferentes universos, y requiere que nos comprometamos a que CH tenga un valor de verdad definido en cada universo (lo que hace la visión del multiverso de todos modos). Así que yo diría que esto no evita realmente mi punto anterior.

Answer 3

Los puntos planteados acerca de mi documento fueron discutidos, 'en su día, en otro artículo: Journal of Philosophical Logic, mayo de 1976, volumen 5, número 2, pp 281-298,Kreisel, la hipótesis del continuo y la teoría de conjuntos de segundo orden. En particular, se distinguen los resultados semánticos y sintácticos, y se incluye allí una "prueba" semántica de que la CH se decide en la ZF de segundo orden y también, creo, se desacredita. Tom Weston