Lógica de segundo orden

Forma de lógica que permite la cuantificación de predicados.

En lógica y matemáticas , la lógica de segundo orden es una extensión de la lógica de primer orden , que a su vez es una extensión de la lógica proposicional . ^[1] La lógica de segundo orden se extiende a su vez por la lógica de orden superior y la teoría de tipos .

La lógica de primer orden cuantifica sólo variables que abarcan individuos (elementos del dominio del discurso ); La lógica de segundo orden, además, cuantifica sobre relaciones . Por ejemplo, la oración de segundo orden dice que para cada fórmula P y cada individuo x , Px es verdadero o no ( Px ) es verdadero (esta es la ley del tercero excluido ). La lógica de segundo orden también incluye la cuantificación de conjuntos , funciones y otras variables (consulte la sección siguiente). Tanto la lógica de primer orden como la de segundo orden utilizan la idea de un dominio del discurso (a menudo llamado simplemente "dominio" o "universo"). El dominio es un conjunto sobre el cual se pueden cuantificar elementos individuales. ${\displaystyle \forall P\,\forall x(Px\lor \neg Px)}$

Ejemplos

Graffiti en Neukölln (Berlín) que muestra la frase de segundo orden más simple que admite modelos no triviales, "∃φ φ".

La lógica de primer orden puede cuantificar individuos, pero no propiedades. Es decir, podemos tomar una oración atómica como Cube( b ) y obtener una oración cuantificada reemplazando el nombre con una variable y adjuntando un cuantificador: ^[2]

∃ x Cubo( x )

Sin embargo, no podemos hacer lo mismo con el predicado. Es decir, la siguiente expresión:

∃PP( b )

No es una oración de lógica de primer orden, pero sí es una oración legítima de lógica de segundo orden. Aquí, P es una variable predicada y semánticamente es un conjunto de individuos. ^[2]

Como resultado, la lógica de segundo orden tiene mayor poder expresivo que la lógica de primer orden. Por ejemplo, en lógica de primer orden no hay forma de identificar el conjunto de todos los cubos y tetraedros. Pero la existencia de este conjunto puede afirmarse en lógica de segundo orden como:

∃P ∀ x (Px ↔ (Cubo( x ) ∨ Tet( x ))).

Entonces podemos afirmar las propiedades de este conjunto. Por ejemplo, lo siguiente dice que el conjunto de todos los cubos y tetraedros no contiene ningún dodecaedro:

∀P (∀ x (Px ↔ (Cubo( x ) ∨ Tet( x ))) → ¬ ∃ x (Px ∧ Dodec( x ))).

La cuantificación de segundo orden es especialmente útil porque brinda la capacidad de expresar propiedades de accesibilidad . Por ejemplo, si Parent( x , y ) denota que x es padre de y , entonces la lógica de primer orden no puede expresar la propiedad de que x es antepasado de y . En lógica de segundo orden podemos expresar esto diciendo que cada conjunto de personas que contienen y y están cerradas bajo la relación Padre contiene x :

∀P ((P y ∧ ∀ a ∀ b ((P b ∧ Padre(a, b)) → P a )) → P x ).

Es notable que si bien tenemos variables para predicados en lógica de segundo orden, no tenemos variables para propiedades de predicados. No podemos decir, por ejemplo, que existe una propiedad Forma ( P ) que sea verdadera para los predicados P Cube, Tet y Dodec. Esto requeriría lógica de tercer orden . ^[3]

Sintaxis y fragmentos

La sintaxis de la lógica de segundo orden indica qué expresiones son fórmulas bien formadas . Además de la sintaxis de la lógica de primer orden , la lógica de segundo orden incluye muchos tipos nuevos (a veces llamados tipos ) de variables. Estos son:

• Un tipo de variables que abarcan conjuntos de individuos. Si S es una variable de este tipo y t es un término de primer orden, entonces la expresión t ∈ S (también escrita S ( t ), o St para ahorrar paréntesis) es una fórmula atómica . Los conjuntos de individuos también pueden verse como relaciones unarias en el dominio.
• Para cada número natural k existe un tipo de variables que abarcan todas las k relaciones arias de los individuos. Si R es una variable de relación k -aria y t ₁ ,..., t _k son términos de primer orden, entonces la expresión R ( t ₁ ,..., t _k ) es una fórmula atómica.
• Para cada número natural k hay un tipo de variables que abarcan todas las funciones tomando k elementos del dominio y devolviendo un solo elemento del dominio. Si f es una variable de función k -aria y t ₁ ,..., t _k son términos de primer orden, entonces la expresión f ( t ₁ ,..., t _k ) es un término de primer orden.

Cada una de las variables recién definidas puede ser cuantificada universal y/o existencialmente para construir fórmulas. Por tanto, existen muchos tipos de cuantificadores, dos para cada tipo de variable. Una oración en lógica de segundo orden, como en la lógica de primer orden, es una fórmula bien formada sin variables libres (de ningún tipo).

Es posible prescindir de la introducción de variables de función en la definición dada anteriormente (y algunos autores hacen esto) porque una variable de función n -aria puede representarse mediante una variable de relación de aridad n +1 y una fórmula apropiada para la unicidad de " resultado" en el argumento n +1 de la relación. (Shapiro 2000, pág. 63)

La lógica monádica de segundo orden (MSO) es una restricción de la lógica de segundo orden en la que sólo se permite la cuantificación de relaciones unarias (es decir, conjuntos). Por lo tanto, tampoco se permite la cuantificación de funciones debido a la equivalencia con las relaciones descritas anteriormente. La lógica de segundo orden sin estas restricciones a veces se denomina lógica completa de segundo orden para distinguirla de la versión monádica. La lógica monádica de segundo orden se utiliza particularmente en el contexto del teorema de Courcelle , un metateorema algorítmico en teoría de grafos . La teoría MSO del árbol binario infinito completo ( S2S ) es decidible. Por el contrario, la lógica completa de segundo orden sobre cualquier conjunto infinito (o la lógica MSO sobre, por ejemplo (,+)) puede interpretar la verdadera aritmética de segundo orden . ${\displaystyle \mathbb {N} }$

Al igual que en la lógica de primer orden, la lógica de segundo orden puede incluir símbolos no lógicos en un lenguaje de segundo orden particular. Sin embargo, estos están restringidos en el sentido de que todos los términos que forman deben ser términos de primer orden (que pueden sustituirse por una variable de primer orden) o términos de segundo orden (que pueden sustituirse por una variable de segundo orden de una variable). clasificación adecuada).

Se dice que una fórmula en lógica de segundo orden es de primer orden (y a veces se denota o ) si sus cuantificadores (que pueden ser universales o existenciales) abarcan sólo variables de primer orden, aunque puede tener variables libres de segundo orden. Una fórmula (existencial de segundo orden) es aquella que además tiene algunos cuantificadores existenciales sobre variables de segundo orden, es decir , donde es una fórmula de primer orden. El fragmento de lógica de segundo orden que consta únicamente de fórmulas existenciales de segundo orden se llama lógica existencial de segundo orden y se abrevia como ESO, como o incluso como ∃SO. El fragmento de fórmulas se define dualmente, se llama lógica universal de segundo orden. Los fragmentos más expresivos se definen para cualquier k > 0 mediante recursividad mutua: tiene la forma , donde es una fórmula, y similar, tiene la forma , donde es una fórmula. (Ver jerarquía analítica para la construcción análoga de aritmética de segundo orden ). ${\displaystyle \Sigma _{0}^{1}}$ ${\displaystyle \Pi _{0}^{1}}$ ${\displaystyle \Sigma _{1}^{1}}$ ${\displaystyle \exists R_{0}\ldots \exists R_{m}\phi }$ ${\displaystyle \phi }$ ${\displaystyle \Sigma _{1}^{1}}$ ${\displaystyle \Pi _{1}^{1}}$ ${\displaystyle \Sigma _{k+1}^{1}}$ ${\displaystyle \exists R_{0}\ldots \exists R_{m}\phi }$ ${\displaystyle \phi }$ ${\displaystyle \Pi _{k}^{1}}$ ${\displaystyle \Pi _{k+1}^{1}}$ ${\displaystyle \forall R_{0}\ldots \forall R_{m}\phi }$ ${\displaystyle \phi }$ ${\displaystyle \Sigma _{k}^{1}}$

Semántica

La semántica de la lógica de segundo orden establece el significado de cada oración. A diferencia de la lógica de primer orden, que tiene una sola semántica estándar, existen dos semánticas diferentes que se usan comúnmente para la lógica de segundo orden: la semántica estándar y la semántica de Henkin . En cada una de estas semánticas, las interpretaciones de los cuantificadores de primer orden y los conectivos lógicos son las mismas que en la lógica de primer orden. Sólo los rangos de cuantificadores sobre variables de segundo orden difieren en los dos tipos de semántica (Väänänen 2001).

En la semántica estándar, también llamada semántica completa, los cuantificadores abarcan todos los conjuntos o funciones del tipo apropiado. Así, una vez establecido el dominio de las variables de primer orden, se fija el significado de los cuantificadores restantes. Son estas semánticas las que dan a la lógica de segundo orden su poder expresivo, y se asumirán durante el resto de este artículo.

Leon Henkin (1950) definió un tipo alternativo de semántica para las teorías de segundo orden y de orden superior, en la que el significado de los dominios de orden superior está determinado en parte por una axiomatización explícita, basándose en la teoría de tipos , de las propiedades de los conjuntos. o funciones abarcadas. La semántica de Henkin es una especie de semántica de primer orden de muchos tipos, donde hay una clase de modelos de axiomas, en lugar de que la semántica se fije solo al modelo estándar como en la semántica estándar. Un modelo en semántica de Henkin proporcionará un conjunto de conjuntos o funciones como interpretación de dominios de orden superior, que pueden ser un subconjunto adecuado de todos los conjuntos o funciones de ese tipo. Para su axiomatización, Henkin demostró que el teorema de completitud y el teorema de compacidad de Gödel , que son válidos para la lógica de primer orden, se trasladan a la lógica de segundo orden con la semántica de Henkin. Dado que los teoremas de Skolem-Löwenheim también son válidos para la semántica de Henkin, el teorema de Lindström importa que los modelos de Henkin son simplemente modelos disfrazados de primer orden . ^[4]

Para teorías como la aritmética de segundo orden, la existencia de interpretaciones no estándar de dominios de orden superior no es sólo una deficiencia de la axiomatización particular derivada de la teoría de tipos que utilizó Henkin, sino una consecuencia necesaria del teorema de incompletitud de Gödel : los axiomas de Henkin no se puede complementar más para garantizar que la interpretación estándar sea el único modelo posible. La semántica de Henkin se utiliza habitualmente en el estudio de la aritmética de segundo orden .

Jouko Väänänen (2001) argumentó que la elección entre modelos de Henkin y modelos completos para la lógica de segundo orden es análoga a la elección entre ZFC y V como base para la teoría de conjuntos: "Al igual que con la lógica de segundo orden, realmente no podemos elegir si axiomatizar las matemáticas usando V o ZFC El resultado es el mismo en ambos casos, ya que ZFC es el mejor intento hasta ahora de usar V como una axiomatización de las matemáticas.

poder expresivo

La lógica de segundo orden es más expresiva que la lógica de primer orden. Por ejemplo, si el dominio es el conjunto de todos los números reales , se puede afirmar en lógica de primer orden la existencia de un inverso aditivo de cada número real escribiendo ∀ x ∃ y ( x + y = 0) pero se necesita segundo- Lógica de orden para afirmar la propiedad del límite mínimo superior para conjuntos de números reales, que establece que todo conjunto de números reales acotado y no vacío tiene un supremo . Si el dominio es el conjunto de todos los números reales, la siguiente oración de segundo orden (dividida en dos líneas) expresa la propiedad de límite superior mínimo:

(∀ A) ([ (∃ w ) ( w ∈ A) ∧ (∃ z )(∀ u )( u ∈ A → u ≤ z ) ]

→ (∃ x )(∀ y )([(∀ w )( w ∈ A → w ≤ x )] ∧ [(∀ u )( u ∈ A → u ≤ y )] → x ≤ y ) )

Esta fórmula es una formalización directa de "todo conjunto acotado y no vacío A tiene un límite superior mínimo ". Se puede demostrar que cualquier campo ordenado que satisfaga esta propiedad es isomorfo al campo de números reales. Por otro lado, el conjunto de oraciones de primer orden válidas en los reales tiene modelos arbitrariamente grandes debido al teorema de compacidad. Por tanto, la propiedad del límite mínimo superior no puede expresarse mediante ningún conjunto de oraciones en lógica de primer orden. (De hecho, cada campo real cerrado satisface las mismas oraciones de primer orden en la firma que los números reales). ${\displaystyle \langle +,\cdot ,\leq \rangle }$

En lógica de segundo orden, es posible escribir oraciones formales que digan "el dominio es finito " o "el dominio es de cardinalidad contable ". Para decir que el dominio es finito, use la oración que dice que toda función sobreyectiva desde el dominio hacia sí misma es inyectiva . Para decir que el dominio tiene cardinalidad contable, use la oración que dice que hay una biyección entre cada dos infinitos subconjuntos del dominio. Del teorema de la compacidad y del teorema ascendente de Löwenheim-Skolem se deduce que no es posible caracterizar la finitud o la contabilidad, respectivamente, en lógica de primer orden.

Ciertos fragmentos de la lógica de segundo orden como ESO también son más expresivos que la lógica de primer orden, aunque son estrictamente menos expresivos que la lógica de segundo orden completa. ESO también disfruta de equivalencia de traducción con algunas extensiones de la lógica de primer orden que permiten el ordenamiento no lineal de las dependencias de los cuantificadores, como la lógica de primer orden extendida con los cuantificadores de Henkin , la lógica favorable a la independencia de Hintikka y Sandu , y la lógica de dependencia de Väänänen .

Sistemas deductivos

Un sistema deductivo para una lógica es un conjunto de reglas de inferencia y axiomas lógicos que determinan qué secuencias de fórmulas constituyen pruebas válidas. Se pueden utilizar varios sistemas deductivos para la lógica de segundo orden, aunque ninguno puede ser completo para la semántica estándar (ver más abajo). Cada uno de estos sistemas es sólido , lo que significa que cualquier oración que puedan usarse para demostrar es lógicamente válida en la semántica apropiada.

El sistema deductivo más débil que se puede utilizar consiste en un sistema deductivo estándar para lógica de primer orden (como la deducción natural ) aumentado con reglas de sustitución para términos de segundo orden. ^[5] Este sistema deductivo se utiliza comúnmente en el estudio de la aritmética de segundo orden .

Los sistemas deductivos considerados por Shapiro (1991) y Henkin (1950) añaden al esquema deductivo aumentado de primer orden tanto axiomas de comprensión como axiomas de elección. Estos axiomas son válidos para la semántica estándar de segundo orden. Son válidos para la semántica de Henkin restringida a los modelos de Henkin que satisfacen los axiomas de comprensión y elección. ^[6]

No reducibilidad a la lógica de primer orden

Se podría intentar reducir la teoría de segundo orden de los números reales, con una semántica completa de segundo orden, a la teoría de primer orden de la siguiente manera. Primero expanda el dominio del conjunto de todos los números reales a un dominio de dos tipos, y el segundo tipo contenga todos los conjuntos de números reales. Agregue un nuevo predicado binario al lenguaje: la relación de membresía. Luego, las oraciones que eran de segundo orden se convierten en de primer orden, y los cuantificadores que antes eran de segundo orden abarcan el segundo orden. Esta reducción se puede intentar en una teoría de un solo orden agregando predicados unarios que indiquen si un elemento es un número o un conjunto, y tomando el dominio como la unión del conjunto de números reales y el conjunto potencia de los números reales.

Pero observe que se afirmó que el dominio incluía todos los conjuntos de números reales. Ese requisito no puede reducirse a una oración de primer orden, como muestra el teorema de Löwenheim-Skolem . Ese teorema implica que existe un subconjunto contablemente infinito de los números reales, cuyos miembros llamaremos números internos , y una colección contablemente infinita de conjuntos de números internos, cuyos miembros llamaremos "conjuntos internos", de modo que el dominio que consta de números internos y conjuntos internos satisfacen exactamente las mismas oraciones de primer orden que satisfacen el dominio de los números reales y los conjuntos de números reales. En particular, satisface una especie de axioma de límite mínimo superior que dice, en efecto:

Todo conjunto interno no vacío que tiene un límite superior interno tiene un límite superior interno mínimo.

La contabilización del conjunto de todos los números internos (junto con el hecho de que forman un conjunto densamente ordenado) implica que ese conjunto no satisface completamente el axioma del límite mínimo superior. La contabilidad del conjunto de todos los conjuntos internos implica que no es el conjunto de todos los subconjuntos del conjunto de todos los números internos (ya que el teorema de Cantor implica que el conjunto de todos los subconjuntos de un conjunto contablemente infinito es un conjunto incontablemente infinito). Esta construcción está estrechamente relacionada con la paradoja de Skolem .

Así, la teoría de primer orden de los números reales y de los conjuntos de números reales tiene muchos modelos, algunos de los cuales son contables. Sin embargo, la teoría de segundo orden de los números reales tiene un solo modelo. Esto se desprende del teorema clásico de que sólo hay un campo ordenado completo de Arquímedes , junto con el hecho de que todos los axiomas de un campo ordenado completo de Arquímedes son expresables en lógica de segundo orden. Esto muestra que la teoría de segundo orden de los números reales no puede reducirse a una teoría de primer orden, en el sentido de que la teoría de segundo orden de los números reales tiene un solo modelo, pero la correspondiente teoría de primer orden tiene muchos modelos.

Hay ejemplos más extremos que muestran que la lógica de segundo orden con semántica estándar es más expresiva que la lógica de primer orden. Existe una teoría finita de segundo orden cuyo único modelo son los números reales si se cumple la hipótesis del continuo y que no tiene modelo si la hipótesis del continuo no se cumple (cf. Shapiro 2000, p. 105). Esta teoría consiste en una teoría finita que caracteriza los números reales como un campo ordenado de Arquímedes completo más un axioma que dice que el dominio es de primera cardinalidad incontable. Este ejemplo ilustra que la cuestión de si una oración en lógica de segundo orden es consistente es extremadamente sutil.

En la siguiente sección se describen limitaciones adicionales de la lógica de segundo orden.

Resultados metalógicos

Un corolario del teorema de incompletitud de Gödel es que no existe ningún sistema deductivo (es decir, ninguna noción de demostrabilidad ) para fórmulas de segundo orden que satisfaga simultáneamente estos tres atributos deseados: ^[7]

• ( Solidez ) Cada oración demostrable de segundo orden es universalmente válida, es decir, verdadera en todos los dominios según la semántica estándar.
• ( Integridad ) Toda fórmula de segundo orden universalmente válida, según la semántica estándar, es demostrable.
• ( Efectividad ) Existe un algoritmo de verificación de pruebas que puede decidir correctamente si una secuencia determinada de símbolos es una prueba o no.

Este corolario a veces se expresa diciendo que la lógica de segundo orden no admite una teoría de prueba completa . En este sentido, la lógica de segundo orden con semántica estándar difiere de la lógica de primer orden; Quine (1970, págs. 90-91) señaló la falta de un sistema de prueba completo como una razón para pensar que la lógica de segundo orden no es lógica , propiamente hablando.

Como se mencionó anteriormente, Henkin demostró que el sistema deductivo estándar para la lógica de primer orden es sólido, completo y efectivo para la lógica de segundo orden con la semántica de Henkin , y el sistema deductivo con principios de comprensión y elección es sólido, completo y efectivo para Henkin. semántica utilizando sólo modelos que satisfagan estos principios.

El teorema de compacidad y el teorema de Löwenheim-Skolem no se aplican a modelos completos de lógica de segundo orden. Sin embargo, sí son válidos para los modelos Henkin. ^{[8] : xi}

Historia y valor en disputa

La lógica de predicados fue introducida en la comunidad matemática por CS Peirce , quien acuñó el término lógica de segundo orden y cuya notación es más similar a la forma moderna (Putnam 1982). Sin embargo, hoy en día la mayoría de los estudiantes de lógica están más familiarizados con las obras de Frege , quien publicó su trabajo varios años antes que Peirce pero cuyas obras siguieron siendo menos conocidas hasta que Bertrand Russell y Alfred North Whitehead las hicieron famosas. Frege utilizó diferentes variables para distinguir la cuantificación de objetos de la cuantificación de propiedades y conjuntos; pero no se veía a sí mismo haciendo dos tipos diferentes de lógica. Después del descubrimiento de la paradoja de Russell, se dio cuenta de que algo andaba mal con su sistema. Con el tiempo, los lógicos descubrieron que restringir la lógica de Frege de varias maneras (a lo que ahora se llama lógica de primer orden) eliminaba este problema: los conjuntos y las propiedades no pueden cuantificarse únicamente en la lógica de primer orden. De esta época data la actual jerarquía de órdenes de la lógica.

Se descubrió que la teoría de conjuntos podía formularse como un sistema axiomatizado dentro del aparato de la lógica de primer orden (a costa de varios tipos de completitud , pero nada tan malo como la paradoja de Russell), y así se hizo (ver conjunto de Zermelo-Fraenkel). teoría ), ya que los conjuntos son vitales para las matemáticas . La aritmética , la mereología y una variedad de otras poderosas teorías lógicas podían formularse axiomáticamente sin recurrir a ningún aparato más lógico que la cuantificación de primer orden, y esto, junto con la adhesión de Gödel y Skolem a la lógica de primer orden, condujo a una disminución del trabajo en una lógica de segundo orden (o cualquier superior). ^{[ cita necesaria ]}

Este rechazo fue promovido activamente por algunos lógicos, en particular WV Quine . Quine avanzó la opinión ^{[ cita necesaria ]} de que en oraciones de lenguaje predicado como Fx, la " x " debe considerarse como una variable o nombre que denota un objeto y, por lo tanto, puede cuantificarse, como en "Para todas las cosas, es el caso que." pero la " F " debe considerarse como una abreviatura de una oración incompleta, no como el nombre de un objeto (ni siquiera de un objeto abstracto como una propiedad). Por ejemplo, podría significar "... es un perro". Pero no tiene sentido pensar que podemos cuantificar algo como esto. (Tal posición es bastante consistente con los propios argumentos de Frege sobre la distinción concepto-objeto ). Entonces, usar un predicado como variable es hacer que ocupe el lugar de un nombre, que sólo deberían ocupar las variables individuales. Este razonamiento ha sido rechazado por George Boolos . ^{[ cita necesaria ]}

En los últimos años ^{[ ¿cuándo? ]} la lógica de segundo orden se ha recuperado, impulsada por la interpretación de Boolos de la cuantificación de segundo orden como una cuantificación plural sobre el mismo dominio de objetos que la cuantificación de primer orden (Boolos 1984). Boolos señala además la pretendida no ordenabilidad de frases como "Algunos críticos sólo se admiran entre sí" y "Algunos de los hombres de Fianchetto entraron al almacén sin compañía de nadie más", que, según él, sólo pueden expresarse mediante toda la fuerza de las palabras de segundo orden. cuantificación. Sin embargo, la cuantificación generalizada y la cuantificación parcialmente ordenada (o ramificada) pueden ser suficientes para expresar también una cierta clase de oraciones supuestamente no ordenables en primer orden y éstas no apelan a la cuantificación de segundo orden.

Relación con la complejidad computacional

El poder expresivo de diversas formas de lógica de segundo orden en estructuras finitas está íntimamente ligado a la teoría de la complejidad computacional . El campo de la complejidad descriptiva estudia qué clases de complejidad computacional pueden caracterizarse por el poder de la lógica necesaria para expresar lenguajes (conjuntos de cadenas finitas) en ellas. Una cadena w  =  w ₁ ··· w _n en un alfabeto finito A puede representarse mediante una estructura finita con dominio D  = {1,..., n }, predicados unarios P _​​a para cada a  ∈  A , satisfechos por aquellos índices i tales que w _i  =  a , y predicados adicionales que sirven para identificar de forma única qué índice es cuál (normalmente, se toma la gráfica de la función sucesora en D o la relación de orden <, posiblemente con otros predicados aritméticos). Por el contrario, las tablas de Cayley de cualquier estructura finita (sobre una firma finita ) pueden codificarse mediante una cadena finita.

Esta identificación conduce a las siguientes caracterizaciones de variantes de la lógica de segundo orden sobre estructuras finitas:

• REG (los lenguajes regulares ) es el conjunto de lenguajes definibles mediante fórmulas monádicas de segundo orden ( teorema de Büchi-Elgot-Trakhtenbrot , 1960)
• NP es el conjunto de lenguajes definibles mediante fórmulas existenciales de segundo orden ( teorema de Fagin , 1974).
• co-NP es el conjunto de lenguajes definibles mediante fórmulas universales de segundo orden.
• PH es el conjunto de lenguajes definibles mediante fórmulas de segundo orden.
• PSPACE es el conjunto de lenguajes definibles mediante fórmulas de segundo orden con un operador de cierre transitivo agregado .
• EXPTIME es el conjunto de lenguajes definibles mediante fórmulas de segundo orden con un operador de punto mínimo fijo agregado.

Las relaciones entre estas clases impactan directamente la expresividad relativa de las lógicas sobre estructuras finitas; por ejemplo, si PH  =  PSPACE , agregar un operador de cierre transitivo a la lógica de segundo orden no la haría más expresiva en estructuras finitas.

Ver también

• Portal de filosofía

• Lógica de primer orden
• Lógica de orden superior
• número de lowenheim
• lenguaje omega
• Lógica proposicional de segundo orden
• Lógica monádica de segundo orden

Notas

1. Shapiro (1991) y Hinman (2005) ofrecen introducciones completas al tema, con definiciones completas.
2. Notas de conferencias del profesor Marc Cohen https://faculty.washington.edu/smcohen/120/SecondOrder.pdf
3. Väänänen, Jouko (2021), "Lógica de segundo orden y orden superior", en Zalta, Edward N. (ed.), The Stanford Encyclopedia of Philosophy (edición de otoño de 2021), Metaphysics Research Lab, Universidad de Stanford , recuperado 2022-05-03
4. * Mendelson, Elliot (2009). Introducción a la lógica matemática (tapa dura). Matemáticas discretas y sus aplicaciones (5ª ed.). Boca Ratón: Chapman y Hall/CRC. pag. 387.ISBN​ 978-1-58488-876-5.
5. Hinman (2005) utiliza este sistema sin comentarios.
6. Estos son los modelos estudiados originalmente por Henkin (1950).
7. La prueba de este corolario es que se podría utilizar un sistema de deducción sólido, completo y eficaz para la semántica estándar para producir una finalización recursivamente enumerable de la aritmética de Peano , que el teorema de Gödel muestra que no puede existir.
8. Manzano, M. , Teoría de modelos , trad. Ruy JGB de Queiroz ( Oxford : Clarendon Press , 1999), pág. xi.

Referencias

• Andrews, Pedro (2002). Introducción a la lógica matemática y la teoría de tipos: hacia la verdad a través de la prueba (2ª ed.). Editores académicos de Kluwer.
• Boolos, George (1984). "Ser es ser un valor de una variable (o ser algunos valores de algunas variables)". Revista de Filosofía . 81 (8): 430–50. doi :10.2307/2026308. JSTOR  2026308.. Reimpreso en Boolos, Lógica, Lógica y Lógica , 1998.
• Henkin, L. (1950). "Completitud en la teoría de tipos". Revista de Lógica Simbólica . 15 (2): 81–91. doi :10.2307/2266967. JSTOR  2266967. S2CID  36309665.
• Hinman, P. (2005). Fundamentos de Lógica Matemática . AK Peters. ISBN 1-56881-262-0.
• Putnam, Hilary (1982). "Pierce el lógico". Historia Matemática . 9 (3): 290–301. doi : 10.1016/0315-0860(82)90123-9 .. Reimpreso en Putnam, Hilary (1990), Realismo con rostro humano , Harvard University Press , págs.
• WV Quine (1970). Filosofía de la Lógica. Prentice Hall . ISBN 9780674665637.
• Rossberg, M. (2004). "Lógica de primer orden, lógica de segundo orden y completitud" (PDF) . En V. Hendricks; et al. (eds.). "Revisión de la lógica de primer orden" . Berlín: Logos-Verlag.
• Shapiro, S. (2000) [1991].Fundamentos sin fundacionalismo: un caso a favor de la lógica de segundo orden. Oxford: Prensa de Clarendon. ISBN 0-19-825029-0.
• Väänänen, J. (2001). "Lógica de segundo orden y fundamentos de las matemáticas" (PDF) . Boletín de Lógica Simbólica . 7 (4): 504–520. CiteSeerX  10.1.1.25.5579 . doi :10.2307/2687796. JSTOR  2687796. S2CID  7465054.

Otras lecturas

• Grädel, Erich; Kolaítis, Phokion G.; Libkin, Leónidas ; Martín, Marx; Spencer, Joel ; Vardi, Moshe Y .; Venema, Ydé; Weinstein, Scott (2007). Teoría de modelos finitos y sus aplicaciones . Textos de Informática Teórica. Una serie EATCS. Berlín: Springer-Verlag . ISBN 978-3-540-00428-8. Zbl  1133.03001.

• Väänänen, Jouko. Edward N. Zalta (ed.). Lógica de segundo orden y de orden superior. La Enciclopedia de Filosofía de Stanford (edición de otoño de 2021).