¿Qué ganamos con lógicas de orden superior?

Question

Gödel de la velocidad de hasta teoremas parecen decir que de orden superior de la lógica de la oferta más corto más corto pruebas de diversas propuestas en la teoría de números. Explícitamente, dio el siguiente

Teorema. Deje $n>0$ ser un número natural. Si $f$ es una función computable, entonces hay infinitamente muchas fórmulas $A$, comprobable en $S_n$ ($n$-ésimo orden de la lógica), de tal forma que si $k$ es la longitud de la menor prueba de $A$ en $S_n$ e $l$ es la longitud de la menor prueba de $A$ en $S_{n+1}$, a continuación, $k>f(l)$.

Yo no soy muy versado en funciones computables, pero creo que la identidad de la función es computable, por lo que la desigualdad anterior para simplificar para decirnos que la más corta de las pruebas se hacen más cortos a medida que nos movemos en un aumento de la lógica.

¿Cómo funciona este conciliar con la siguiente cita de la Campana y Machover de "Un curso de Lógica Matemática":

Sin embargo, la mayoría de los lógicos de acuerdo en que [la segunda y de orden superior] son las lenguas, al menos en principio, prescindible. De hecho, vamos a $\mathfrak{U}$ ser cualquier estructura y deje $\mathfrak{B}$ ser una estructura obtenida a partir de $\mathfrak{U}$ , de la siguiente manera. El universo de $\mathfrak{B}$ se compone de todos los undividuals de $\mathfrak{U}$ además de todos los conjuntos de individuos de $\mathfrak{U}$. Las operaciones básicas de $\mathfrak{B}$ están definidos de tal manera que cuando se restringe el universo de $\mathfrak{U}$ se comportan exactamente como las correspondientes operaciones básicas de $\mathfrak{U}$. Por último, las relaciones básicas de $\mathfrak{B}$ son todas las relaciones básicas de $\mathfrak{U}$ además de otras dos relaciones: la propiedad de ser un individuo de $\mathfrak{U}$, y la relación de pertenencia entre un individuo de $\mathfrak{U}$ y un conjunto de individuos de $\mathfrak{U}$. Entonces cualquier declaración acerca de $\mathfrak{U}$ expresado en un segundo idioma con el fin de establecer las variables, puede fácilmente ser "traducido" a una declaración acerca de la $\mathfrak{B}$ en el primer fin de lenguaje. Un argumento similar se aplica a otros de orden superior de idiomas. Por lo tanto, no perder mucho por confinar nuestra atención a la primera orden idiomas.

Desde el argumento de que el contorno parece que se pierde nada por restringir su atención a la primera orden idiomas, pero esto va en contra de la veta de la velocidad hasta los teoremas a menos que me estoy perdiendo algo - ¿la "traducción" de un segundo orden de declaración de más de $\mathfrak{U}$ a una de primer orden de la sentencia sobre el $\mathfrak{B}$ requieren más símbolos? Esto va en contra de lo que parece ser la traducción implícita, donde podemos interpretar los símbolos de los subconjuntos del universo de $\mathfrak{U}$ como los símbolos en $\mathfrak{B}$ añadido para indicar estos subconjuntos, que parece que podría producir una traducción de la misma longitud.

Giorgio Mossa la respuesta aquí parece indicar que la diferencia radica en el estándar de la semántica de las lenguas en cuestión, no de su sintaxis, pero esto es algo claro para mí como la semántica de un lenguaje que se fija tan pronto como elegimos una estructura para interpretar el idioma en el que parece que se ha hecho en la cita anterior. Cualquier ayuda es muy apreciada.

Answer 1

El debate acerca de primer orden y de orden superior, la lógica es un poco de un tema religioso. Hay muchas maneras de argumentar de una manera o de la otra: la lógica de primer orden tiene una buena meta-teórico de las propiedades, de orden superior, la lógica logra categoricity, etc., y uno siempre puede producir un argumento en su favor.

La Stanford Encyclopedia en la Aparición de la Lógica de Primer orden se asegura de que los lógicos que estableció la importancia de la lógica de primer orden se utiliza de orden superior de la lógica durante muchos años después de la lógica de primer orden fue identificado como un objeto de interés. Cuando la meta fundamental de la teoría de teoremas acerca de la lógica de primer orden fueron descubiertos, a veces fueron tomados como evidencia de deficiencia de la lógica de primer orden. Mientras que hoy en día muchos piensan que es obvio que la lógica de primer orden es la Verdadera Lógica para gobernarlos a todos (como ya he dicho, es un asunto de religión), este no fue el caso en el pasado.

Realmente depende de lo que quieras hacer con la lógica.

Si eres un lógico que quiera estudio meta-teórico de las propiedades de los sistemas formales, a continuación, la lógica de primer orden es un punto dulce. Es muy expresivo, pero también tiene muy buena meta-teórico (de las características deintegridad teorema, el teorema de compacidad, Lindström del teorema). De orden superior, la lógica es aún más expresiva, pero carece de algunas de las propiedades de la lógica de primer orden.

Si eres un categórico lógico, entonces usted está interesado en las conexiones entre los sistemas formales y estructura, como se percibe en la categoría de teoría. En este caso su punto de vista podría ser que la lógica es dictada por la semántica. Por ejemplo, el lenguaje interno de toposes es totalmente de orden superior, mientras que la lógica interna de variedades algebraicas es regular la lógica (sólo ecuaciones, conjunciones, y $\exists$). Y si sólo se preocupan por Grothendieck toposes y geométricas de morfismos, geométrico lógica es para usted.

Si eres matemático, probablemente atención principalmente sobre el uso de la lógica como una herramienta, en cuyo caso, la principal preocupación es la expresividad. Usted no desea ser informado de que algunos muy natural de la idea matemática no puede ser declarado formalmente, por lo que naturalmente gravitan hacia el orden superior de la lógica. Sin embargo, es sabido que se necesita para expresividad en gran medida pueden ser satisfechas mediante la combinación de la lógica de primer orden con la teoría de conjuntos. Y ya que la lógica y la teoría de conjuntos son enseñadas por los lógicos, que prefieren la lógica de primer orden para sus propios fines, la alta prevalencia en el sistema formal defendido hoy en día es la lógica de primer orden con la teoría de conjuntos. Pero en última instancia, para un matemático ordinario no importa mucho que uno se utilice.

Equipo-los científicos tienen sus propias ideas acerca de la lógica y normalmente se toma un punto de vista de ingeniería: use la herramienta apropiada para la situación en cuestión. Por ejemplo, cuando nos formalizar la matemática con una prueba de auxiliar de software que ayuda y supervisa la escritura de pruebas), buscamos un formalismo que nos permite hacer el trabajo tan directamente como sea posible. Para proyectos de gran escala que la principal preocupación se convierte en prueba de la ingeniería: cómo organizar las grandes bibliotecas de las definiciones y teoremas, cómo buscar, cómo escribir pruebas, de modo que son robustos con respecto a los pequeños cambios, etc. Lógica tradicional no tiene casi nada que decir sobre estos temas, y, en consecuencia, no influye mucho en la elección de formalismo utilizado en la prueba de los asistentes. Para muchos la prueba de los asistentes al tipo de utilización de la teoría, que podría ser caracterizado como "predicativo de orden superior", un razonable término medio entre de primer orden y sin restricciones de orden superior.

Answer 2

Su error es simplemente asumir que sólo hay un tipo de orden superior de la lógica (HOL). Contrario a tu último párrafo, hay por lo menos 2 tipos principales, que corresponden a 2 diferentes semántica:

En semántica completa, una vez que arreglar el dominio (de los individuos), no podrá elegir la interpretación de la orden superior de la clase, a partir de los subconjuntos de individuos), debido a que es determinado por el reiterado de energía conjuntos de dominio (más precisamente, el meta-sistema piensa que son los power-conjuntos). Por el teorema de la incompletitud de PA, incluso de segundo orden de la lógica (SOL) con la semántica completa no puede ser capturado por una computable sistema formal.

En la semántica general, usted no sólo debe elegir el dominio, sino que también debe elegir la interpretación de cada una de orden superior de la especie, y, normalmente, la única restricción es que debe respetar la comprensión de los axiomas que usted desea tener. Por ejemplo, si quieres tener mayor orden de la comprensión, entonces usted tiene el axioma ( $∃x∈S_{k+1}\ ∀t∈S_k\ ( t∈x ⇔ φ(t) )$ ) para cada uno (de orden superior) propiedad $φ$ , con un parámetro de $S_k$, donde $S_k$ denota el nivel-$k$ tipo. En el SOL que nos suelen requerir sólo predicativo de la comprensión, es decir, donde $φ$ sólo cuantifica en más de $S_0$ (es decir, los individuos), que corresponden a las de primer orden definibles subconjuntos del dominio.

Tenga en cuenta que HOL con la semántica general, puede ser capturado por el multi-ordenados FOL, y por lo tanto, por uno de los ordenados-FOL (simplemente por el uso de predicado-símbolos para representar el tipo). Es en este preciso sentido técnico que nosotros "no perder mucho por confinar nuestra atención a la primera orden idiomas". Pero es erróneo inferir que "sería una traducción de igual duración". Incluso más que la ampliación de un FOL sistema para el sistema SOL con predicativo comprensión es equivalente a tener interno definitorial de expansión, lo que permite evitar la repetición de largo fórmulas.

Tenga en cuenta que múltiples ordenados FOL (y el único ordenado de la traducción) es semánticamente completa para HOL con la semántica general, pero por supuesto no semánticamente completa para HOL con semántica completa. Por otra parte, la Henkin la construcción muestra que si una contables HOL sistema de $T$ (es decir, con contables idioma) tiene un modelo general, entonces también tiene una contables del modelo general.

Además, el speedup teorema usted vinculados a la realidad no muestran una aceleración atribuible a la utilización de HOL más de FOL! Tenga en cuenta que la prueba en que SEP artículo utiliza supuestos adicionales, a saber, el orden superior de la inducción de esquema en lugar de sólo el primer orden de la inducción de esquemas. Que speedup es debido a la ω-incompletitud de PA, más que nada para hacer con HOL, como se muestra claramente por la prueba. Esto también es evidente en el hecho de que si PA demuestra Q, PA+Q es todavía un FOL sistema y resulta Q es muy corta, a prueba de...

Answer 3

Bell y Machover no decir (en el presupuesto) nada acerca de la instrucción de longitud, por lo que esto no se contradicen necesariamente Gödel.

Yo no puedo hablar de (universal) más corta de la prueba, pero "traducción" entre el superior y el inferior de la lógica puede ser difícil de manejar. Este papel por Shapiro [1] podría ser de interés general para la cuestión, sino también, específicamente, un ejemplo por Boolos discutido en la página 46 (no tengo acceso a la Boolos de papel [2])

Si la lógica se completa, puede ser natural suponer que el matemático ingresos, o podría seguir (o debería proceder), deducir consecuencias de la axiomatization. Este pesaría en favor de la lógica de primer orden, ya que es completa. Sin embargo, este pensamiento es problemático. Boolos [1987] da un ejemplo de un argumento válido $I$ en un primer orden lenguaje y bocetos de un corto derivación de la conclusión de $I$ desde sus instalaciones en un segundo orden deductivo sistema. Una ligera variación en el argumento de que se obtiene un modelo de la teoría de la prueba de que $I$ es válido en el modelo de la teoría de la semántica. Desde $I$ es de primer orden, y la lógica de primer orden es completa, no es una derivación de la conclusión de $I$ desde sus instalaciones en un estándar de primer orden deductivo sistema. Boolos muestra, sin embargo, que el menor de primer orden de la derivación de $I$ tiene más líneas que hay partículas en el universo conocido.$^1$ Nosotros no podemos saber que $I$ es válida a través de una derivación de ella en un primer orden deductivo sistema. Boolos concluye que

... el hecho de que tan fácilmente reconocer la validez de $I$ parece proporcionar como de fuerte es una prueba de como podrían ser razonablemente ser preguntado por que no hay una norma de primer orden lógico del sistema puede ser llevado a ser satisfactoria la idealización de la... de los procesos de... cual hemos de reconocer (de primer orden!) las consecuencias lógicas.

Claramente, si una de primer orden argumento es válido, entonces, en principio, un agente epistémico puede aprender a través de una derivación de un estándar, de primer orden deductivo sistema. Sin embargo, ejemplos como estos deben hacer un cuidado de la epistémica importancia de estos "en principio", declaraciones

$^1$ Ver mi [Fundaciones sin Fundacionalismo], Capítulo 5, Sección 5.3.4 para este y otros casos de 'speed-up'

Creo Shapiro y Boolos tienen diferentes puntos de vista ("no sé") relativa a la finitism de Campana y Machover ("por lo tanto, no perder mucho"), pero que está un poco fuera de tema. El ejemplo, creo que sigue siendo relevante, aunque.

Por supuesto, el ejemplo no significa que todas esas declaraciones de "blow up" de una manera similar.

[1] Stewart Shapiro. "No dicen Mucho: de Segundo orden, la Lógica y la Lógica de Primer orden" Philosophia Mathematica, Volumen 7, número 1, febrero de 1999, Páginas 42-64, https://doi.org/10.1093/philmat/7.1.42

[2] Boolos, G. [1987]: "La consistencia de Frege los Fundamentos de la Aritmética", en Judith Jarvis Thomson (ed.), En el ser y diciendo: Ensayos de Richard Cartwright.Cambridge: MIT Press, pp 3-20.

Answer 4

Creo que mi tema de disertación da una distinción desde la perspectiva de una de tipo funcional. Aunque se trata de una especialización, a mí me parece natural. Para un cartel que se amplía en algunos detalles, ver http://arxiv.org/abs/1408.2784 .

Uno puede expresar hyperassociativity, la declaración de "Todo el plazo de las operaciones son asociativas", por medio de un hyperidentity, que es una (en un sentido lingüístico) objeto compacto en un cierto segundo orden del lenguaje, y esto se aplica a las diferentes clases de universal álgebras. En el caso de que el correspondiente de primer orden lenguaje sólo tiene una operación binaria símbolo, no es otra representación compacta: la conjunción de los cinco frases que afirman que los cinco binario plazo en las operaciones b(x,x), b(x,y), b(x,b(x,y)),b(x,b(y,y)), y b(x,b(y,x)) son asociativos. También hay una similar y menos interesante versión cuando la lengua tiene sólo un número finito de unario símbolos de función.

Sin embargo, si el lenguaje incorpora más símbolos de función, ya no esta: hyperassociativity no es lógicamente equivalente a un conjunto finito de primer orden identidades. No parece ser una manera compacta presente hyperassociativity para este tipo de estructuras. Así de segundo orden que aquí significa más corto de una manera significativa.

Gerhard "Las Muchas Maneras De Hyperassociativity" Paseman, 2019.05.30.

Answer 5

Creo que la diferencia radica en las estructuras específicas. Lo que la segunda declaración se dice que es "Para el segundo fin de fórmula $\phi$, hay algunos de primer orden de la fórmula $\hat\phi$ tal que $(\mathfrak U, R_0...R_n)\vDash\phi \leftrightarrow (\mathfrak V, Q_0...Q_n,\in,\mathfrak U)\vDash\hat\phi$." Esto es bastante fácil de comprobar, como $\mathfrak U\vDash R_n(x_0...x_n) \leftrightarrow\mathfrak B\vDash Q_n(x_0...x_n)\land x_0\in\mathfrak U...x_n\in\mathfrak U$. Lo que la primera declaración que dice es que la lógica de segundo orden puede aportar pruebas de teoremas en primer orden de la lógica en general más rápido. Esto podría ser confuso si $\mathfrak U$ e $\mathfrak B$ fueron las mismas estructuras, sin embargo, son diferentes. Una prueba usando la relación de los símbolos de $\mathfrak U$ no es nesscarily tan rápido como una prueba usando la relación de los símbolos de $\mathfrak B$, como $\mathfrak B$ adicional predicado unario $\mathfrak U$ y la relación símbolo $x\in X$. El punto de la segunda cita, es que para una estructura más grande $(\mathfrak W,E)$ tal que $E$ puede interpretar $Q_0...Q_n,\in,\mathfrak U$, $(V,\in)$ por ejemplo, cada segundo fin de instrucción acerca de la $(\mathfrak U, R_0...R_n)$ puede ser reducido a un primer pedido de declaración sobre la $(\mathfrak V, Q_0...Q_n,\in,\mathfrak U)$. Sin embargo, desde la perspectiva de $(\mathfrak V, Q_0...Q_n,\in,\mathfrak U)$, es mucho más grande, a continuación, $(\mathfrak U, R_0...R_n)$.