Lógica de orden superior

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 30 de junio de 2021; las comprobaciones requieren 2 ediciones .

La lógica de orden superior en matemáticas y lógica es una forma de lógica de predicados que difiere de la lógica de primer orden en predicados adicionales sobre predicados, cuantificadores sobre ellos y, en consecuencia, una semántica más rica . Las lógicas de orden superior con su semántica estándar son más expresivas, pero sus propiedades teóricas de modelo son mucho más difíciles de estudiar y aplicar en comparación con la lógica de primer orden.

La lógica de primer orden solo cuantifica variables; la lógica de segundo orden también permite la cuantificación de predicados y símbolos de funciones (sobre conjuntos); la lógica de tercer orden usa y cuantifica predicados sobre predicados (conjuntos de conjuntos), y así sucesivamente. Por ejemplo, una oración de segundo orden

expresa el principio de inducción matemática . La lógica de orden superior incluye todas las lógicas de orden inferior; en otras palabras, la lógica de orden superior permite declaraciones con predicados (sobre conjuntos) de menor profundidad de anidamiento.

Ejemplos y propiedades

La lógica de orden superior incluye derivaciones de la teoría de tipo simple de Church [1] y varias formas de teoría de tipo intuicionista. Gerard Huet demostró que el problema de la unificación es algorítmicamente irresoluble en la variedad intuicionista de la lógica de tercer orden [2] [3] [4] , es decir, no hay ningún algoritmo que determine si una ecuación arbitraria tiene una solución sobre el tercer orden. términos (y más aún por términos de orden arbitrario por encima del tercero).

Teniendo en cuenta el concepto de isomorfismo, la operación booleana se define en lógica de segundo orden. Usando esta observación, Hintikka estableció en 1955 que las lógicas de orden superior pueden ser representadas por la lógica de segundo orden en el sentido de que para cada fórmula de lógica de orden superior uno puede encontrar una fórmula lógica de segundo orden igualmente válida [5] .

En algunos contextos, se supone que el concepto de lógica de orden superior se refiere a la lógica clásica de orden superior. Sin embargo, también se ha estudiado la lógica modal de orden superior . Según algunos lógicos, la prueba ontológica de Gödel se estudia (desde un punto de vista técnico) en este contexto ] .

Véase también

• Lógica de primer orden
• Lógica de segundo orden
• Gramática superior
• Teoría de tipos intuicionista
• Lógica
• Cálculo lambda escrito
• lógica modal

Notas

1. ↑ Church, Alonzo , Una formulación de la teoría simple de tipos Archivado el 15 de noviembre de 2018 en Wayback Machine , The Journal of Symbolic Logic 5(2):56–68 (1940)
2. ↑ Huet, Gérard P.  La indecidibilidad de la unificación en la lógica de tercer orden  // Información y control : diario. - 1973. - vol. 22 , núm. 3 . - pág. 257-267 . -doi : 10.1016 / s0019-9958(73)90301-x .
3. ↑ Huet, Gerard (septiembre de 1976). Resolution d'Equations dans des Langages d'Ordre 1,2,...ω (Ph.D.). Universidad de París VII.
4. ↑ Huet, Gerard. Unificación del Orden Superior 30 años después // Actas, 15th International Conference TPHOL  (Inglés) / Carreño, V.; Muñoz, C.; Tahar, S. - Springer, 2002. - vol. 2410. - Pág. 3-12. — (LNCS).
5. ↑ Artículo de la Enciclopedia de Filosofía de Stanford sobre lógica de orden superior . Consultado el 9 de agosto de 2016. Archivado desde el original el 17 de junio de 2016. (indefinido)
6. ↑ Montaje, MelvinTipos, Tableaus y el Dios de Gödel. - Springer Science & Business Media , 2002. - P. 139. - ISBN 978-1-4020-0604-3 . . — “El argumento de Godel es modal y al menos de segundo orden, ya que en su definición de Dios hay una cuantificación explícita sobre propiedades. [...] [AG96] mostró que se podía ver una parte del argumento no como de segundo orden, sino de tercer orden".

Literatura

• Andrews, Peter B. (2002). Introducción a la lógica matemática y la teoría de tipos: a la verdad a través de la prueba , 2.ª ed., Kluwer Academic Publishers, ISBN 1-4020-0763-9
• Stewart Shapiro, 1991, "Fundamentos sin fundacionalismo: un caso a favor de la lógica de segundo orden". Prensa de la Universidad de Oxford ISBN 0-19-825029-0
• Stewart Shapiro, 2001, "Lógica clásica II: Lógica de orden superior", en Lou Goble, ed., The Blackwell Guide to Philosophical Logic . Blackwell, ISBN 0-631-20693-0
• Lambek, J. y Scott, PJ, 1986. Introducción a la lógica categórica de orden superior , Cambridge University Press, ISBN 0-521-35653-9
• Jacobs, Bart. Lógica Categórica y Teoría de Tipos . - Holanda Septentrional, Elsevier, 1999. - (Estudios de Lógica y Fundamentos de las Matemáticas 141). - ISBN 0-444-50170-3 .
• Benzmüller, Christoph; Miller, Dale. Automatización de la lógica de orden superior // Manual de historia de la lógica, Volumen 9: Lógica computacional  (inglés) / Gabbay, Dov M.; Siekmann, George H.; Woods, Juan. - Elsevier , 2014. - ISBN 978-0-08-093067-1 .

Enlaces

• Andrews, Peter B, Teoría de tipos de Church en la Enciclopedia de Filosofía de Stanford .
• Miller, Dale, 1991, " Logic: Higher-order " , Encyclopedia of Artificial Intelligence , 2ª ed.
• Herbert B. Enderton, Second-order and Higher-order Logic en Stanford Encyclopedia of Philosophy , publicado el 20 de diciembre de 2007; sustancialmente revisado el 4 de marzo de 2009.

Lógicas
Filosofía • Semántica • Sintaxis • Historia
Grupos lógicos	lógica clásica lógica aristotélica Lógica proposicional Lógica de primer orden Lógica de segundo orden lógica de orden superior lógica matemática teoría de conjuntos Teoría del modelo teoría de la computabilidad Teoría de la prueba y matemáticas constructivas lógica lineal sistema formal conclusión natural cálculo de secuencias Álgebra de la lógica Lógica relevante lógica deóntica lógica intuicionista cálculo de Lambek Lógica no clásica intuicionismo lógica difusa Lógica subestructural lógica Descripción lógica Lógica multivaluada Síntesis lógica Lógica vinculante Lógica temporal Lógica modal ( Lógica híbrida ) lógica epistémica lógica filosófica Pensamiento crítico lógica informal razonamiento deductivo
Componentes	Abducción (lógica) Probabilidad declaración Deducción / Inducción / Traducción La realidad razonamiento inductivo inferencia constante booleana Verdadero seguimiento lógico Forma lógica Condiciones necesarias y suficientes Descripción Definición Sustitución Paquete Controversia ( Antinomia ) Juicio sintético / Juicio analítico Enlace
Lista de símbolos booleanos