¿Cuáles son las leyes y los problemas que rodean a la *cuantificación de las sentencias*?

Question

¿Cuáles son las leyes y los problemas que rodean ¿Cantifica sobre las frases?

La intuición me dice que si queremos demostrar que $X$ es indemostrable en algún sistema digamos $ZFC$ podríamos desear, en determinadas circunstancias, afirmar que no existe una sentencia $S$ dentro del conjunto de todas las sentencias demostrables en $ZFC$ , de tal manera que $S$ prueba $X$ .

Alguien me exclamó una vez: "Estás cuantificando por encima de las frases", como si esto fuera un sacrilegio. ¿Lo es? Si es así, ¿por qué?

Answer 1

Cuantificación sobre sentencias de una lógica dentro de esa lógica es (normalmente) un sacrilegio. Sin embargo, cuantificar sobre frases en algunas metamatemáticas está (normalmente) bien.

Así, por ejemplo, tiene sentido decir "no hay sentencia $\phi$ tal que $\mathrm{ZFC} \vdash \phi \land \neg \phi$ ". Sin embargo, no es correcto escribir algo como " $\forall \phi(\neg(\phi \land \neg \phi))$ " como una frase en un lenguaje lógico.

Por supuesto, en una teoría tan fuerte como ZFC, podemos formalizar la propia lógica. Es decir, se elige una codificación de cadenas de caracteres como $v,0,1,(,),\neg,\forall,\land,\in$ en números naturales dentro de ZFC, y escribes una definición para cuando dicha cadena representa una fórmula bien formada, y estos elementos de $\mathbb N$ en un subconjunto $\mathrm{Form}$ . Entonces, puedes escribir $\mathrm{ZFC} \vdash \forall \phi \in \mathrm{Form}(...)$ -- sin embargo, lo que sucede en el $...$ no puede ser $\neg(\phi \land \neg \phi)$ porque ahora la carta $\phi$ es una variable en la teoría, y no se pueden aplicar conectivos lógicos a las variables.

De hecho, podría preguntarse si se puede definir una fórmula $\psi$ en el lenguaje de ZFC para que $\psi(\phi)$ corresponde a lo que solemos considerar como "la verdad de $\phi$ " -- entonces podrías engañar lo anterior dejando que ... sea $\neg(\psi(\phi) \land \neg\psi(\phi))$ . Resulta que, esto es imposible por razones estrechamente relacionadas con el teorema de la incompletitud.

Answer 2

La cuantificación sobre variables que representan predicados de la lógica de primer orden se denomina lógica de segundo orden . La cuantificación sobre variables que representan predicados de la lógica de segundo orden se denomina lógica de tercer orden . Al iterar esto se obtiene lógica de orden superior .

Los tipos de lógica son susceptibles de las mismas clases de paradojas que los tipos de teoría de conjuntos; por ejemplo, se permite que los predicados unarios realmente se tengan a sí mismos en su dominio, se podría definir $Q(P) :\equiv \neg P(P)$ y luego $Q(Q)$ es la paradoja del mentiroso.

La formulación de la lógica de orden superior es la principal forma de tratar esto, y recuerda mucho a cómo la ZFC evita las paradojas de la teoría de conjuntos ingenua.

Si se fijan bien los detalles, la lógica de segundo orden no es más que la teoría de primer orden de la lógica de primer orden.

Sin embargo, Cuando se utiliza la lógica de orden superior con la teoría de conjuntos, la gente suele 1 como para restringir los tipos de semántica permitidos. En particular, si $X$ es un tipo, y $\mathcal{P}(X)$ es el tipo de todos los predicados unarios sobre $X$ entonces en una interpretación donde el tipo $X$ se asigna a un conjunto $S$ insisten en que el tipo $\mathcal{P}(X)$ se asigna al conjunto de potencias $\mathcal{P}(S)$ .

Este es el llamado semántica completa para la lógica de orden superior. Hace no tienen las conocidas propiedades lógicas agradables; por ejemplo, el análogo del teorema de completitud de Gödel no se cumple. Por esta razón, se tiende a evitar la lógica de segundo orden cuando se hace lógica formal.

1: Con "a menudo" me refiero al punto en que la gente encuentra raro que no hacerlo, y en su lugar sólo usar lo que normalmente se usaría para la semántica de una teoría de primer orden. O en el caso de la lógica de segundo orden, un intermediario llamado Semántica de Henkin se utiliza más comúnmente, donde la interpretación de $\mathcal{P}(X)$ debe ser un subconjunto de $\mathcal{P}(S)$ .

Answer 3

No se trata de un sacrilegio, sino de "cambiar la conversación". En sí mismo, no hay nada malo en cuantificar sobre las oraciones - es algo que hacemos todo el tiempo en el inglés corriente. El problema es que ninguna de nuestras herramientas matemáticas es aplicable a los problemas que implican cuantificadores de oraciones. Incluso la verdad es un concepto complicado cuando se permiten cuantificadores de oraciones: normalmente, se determina si una oración es verdadera o falsa construyéndola inductivamente y evaluando sus componentes. Pero si podemos cuantificar sobre oraciones, uno de esos componentes puede ser la propia oración - ¿cómo puedo evaluar la verdad de la oración $\forall\varphi P(\varphi)$ cuando esta frase ¿podría ser el contraejemplo?

De hecho, la mayoría de nuestras herramientas más importantes para el análisis de los lenguajes formales se desmoronan cuando se permiten los cuantificadores de oraciones. Ya no tenemos completitud (puede haber oraciones que sean siempre verdaderas, pero que no puedan probarse dentro del sistema) ni compacidad (un conjunto infinito de oraciones puede ser inconsistente aunque cada subconjunto finito sea consistente). En cierto sentido, introducir la cuantificación de oraciones en una conversación sobre lógica es como sacar el tema de la talla de madera en una clase de metalistería: es técnicamente legal, y ciertamente está relacionado, pero estás llevando la conversación a un área de la que nadie sabe mucho.