Lógica de segundo orden

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 mediante la lógica de orden superior y la teoría de tipos .

La lógica de primer orden cuantifica únicamente 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 medio excluido ). La lógica de segundo orden también incluye la cuantificación sobre conjuntos , funciones y otras variables (ver la sección a continuación). Tanto la lógica de primer orden como la de segundo orden utilizan la idea de un dominio del discurso (a menudo llamado simplemente el "dominio" o el "universo"). El dominio es un conjunto sobre el cual se pueden cuantificar elementos individuales. $\para todo P\,\para todo x(Px\lor \neg Px)$

Ejemplos

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

\exists x Cubo(x)

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

\existsPP(b)

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

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

\existsP \forall x (Px \leftrightarrow (Cubo(x) \lor Tet(x))).

Podemos entonces afirmar las propiedades de este conjunto. Por ejemplo, la siguiente expresión dice que el conjunto de todos los cubos y tetraedros no contiene ningún dodecaedro:

\forallP (\forall x (Px \leftrightarrow (Cubo(x) \lor Tet(x))) \to \neg \exists x (Px \land Dodec(x))).

La cuantificación de segundo orden es especialmente útil porque permite expresar propiedades de alcanzabilidad . Por ejemplo, si Parent( x , y ) denota que x es un padre de y , entonces la lógica de primer orden no puede expresar la propiedad de que x es un ancestro de y . En la lógica de segundo orden podemos expresar esto diciendo que todo conjunto de personas que contiene y y está cerrado bajo la relación Parent contiene x :

\forallP ((P y \land \forall a \forall b ((P b \land Padre(a, b)) \to P a)) \to P x).

Cabe destacar 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 Shape( 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 de variables. Estos son:

Un tipo de variables que se extienden sobre 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 considerarse como relaciones unarias en el dominio.
Para cada número natural k existe una especie de variables que abarcan todas las relaciones k -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 existe una especie de variables que abarcan todas las funciones que toman k elementos del dominio y devuelven un único 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 que acabamos de definir puede cuantificarse universalmente y/o existencialmente para construir fórmulas. Por lo tanto, hay muchos tipos de cuantificadores, dos para cada tipo de variable. Una oración en lógica de segundo orden, como en 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 lo hacen) 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 del "resultado" en el argumento n +1 de la relación. (Shapiro 2000, p. 63)

La lógica monádica de segundo orden (MSO) es una restricción de la lógica de segundo orden en la que solo se permite la cuantificación sobre relaciones unarias (es decir, conjuntos). La cuantificación sobre funciones, debido a la equivalencia con las relaciones descritas anteriormente, tampoco está permitida. La lógica de segundo orden sin estas restricciones a veces se denomina lógica de segundo orden completa 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 la teoría de grafos . La teoría MSO del árbol binario infinito completo ( S2S ) es decidible. Por el contrario, la lógica de segundo orden completa sobre cualquier conjunto infinito (o la lógica MSO sobre, por ejemplo, (,+)) puede interpretar la verdadera aritmética de segundo orden . $\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 en particular. Sin embargo, estos símbolos 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 un tipo apropiado).

Una fórmula en lógica de segundo orden se dice que es de primer orden (y a veces se denota o ) si sus cuantificadores (que pueden ser universales o existenciales) abarcan solo variables de primer orden, aunque puede tener variables libres de segundo orden. Una fórmula (existencial de segundo orden) es una 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 consiste solo en 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. Se definen fragmentos más expresivos para cualquier k > 0 por recursión mutua: tiene la forma , donde es una fórmula, y similar, tiene la forma , donde es una fórmula. (Véase la jerarquía analítica para la construcción análoga de la aritmética de segundo orden ). $\Sigma _{0}^{1}$ $Estilo de visualización: Pi _{0}^{1}}$ $\Sigma _{1}^{1}$ $\existe R_{0}\ldots \existe R_{m}\phi$ ${\estilo de visualización \phi}$ $\Sigma _{1}^{1}$ $Estilo de visualización: Pi _{1}^{1}}$ $Estilo de visualización: Sigma _{k+1}^{1}}$ $\existe R_{0}\ldots \existe R_{m}\phi$ ${\estilo de visualización \phi}$ $Estilo de visualización: Pi _{k}^{1}}$ $\Pi _{k+1}^{1}$ $\para todos R_{0}\ldots \para todos R_{m}\phi$ ${\estilo de visualización \phi}$ $Estilo de visualización: 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 solo una 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. Solo 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. Un modelo con esta condición se denomina modelo completo, y son lo mismo que los modelos en los que el rango de los cuantificadores de segundo orden es el conjunto potencia de la parte de primer orden del modelo. (2001) Por lo tanto, una vez que se establece el dominio de las variables de primer orden, el significado de los cuantificadores restantes es fijo. Es esta semántica la que le da a la lógica de segundo orden su poder expresivo, y se asumirá en 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, basada en la teoría de tipos , de las propiedades de los conjuntos o funciones que abarca. La semántica de Henkin es un tipo de semántica de primer orden de múltiples tipos, donde hay una clase de modelos de los 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 la semántica de Henkin proporcionará un conjunto de conjuntos o un conjunto de funciones como la interpretación de los 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 de Gödel y el teorema de compacidad , 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 implica que los modelos de Henkin son simplemente modelos de primer orden disfrazados . ^[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 solo 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 pueden complementarse más para garantizar que la interpretación estándar sea el único modelo posible. La semántica de Henkin se utiliza comúnmente en el estudio de la aritmética de segundo orden .

Jouko Väänänen (2001) argumentó que la distinción entre la semántica de Henkin y la semántica completa para la lógica de segundo orden es análoga a la distinción entre demostrabilidad en ZFC y verdad en V , en el sentido de que la primera obedece a propiedades de teoría de modelos como el teorema de Lowenheim-Skolem y la compacidad, y la segunda tiene fenómenos de categoricidad. Por ejemplo, "no podemos preguntar de manera significativa si el tal como se define en es el real . Pero si reformalizamos dentro de , entonces podemos notar que el reformalizado ... tiene modelos contables y, por lo tanto, no puede ser categórico". ${\estilo de visualización V}$ $\mathrm {ZFC}$ ${\estilo de visualización V}$ $\mathrm {ZFC}$ $\mathrm {ZFC}$ $\mathrm {ZFC}$

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 lógica de segundo orden para afirmar la propiedad de límite superior mínimo para conjuntos de números reales, que establece que todo conjunto acotado y no vacío de números reales 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:

(\forall A) ([@media screen{html.skin-theme-clientpref-night .mw-parser-output div:not(.notheme)>.tmp-color,html.skin-theme-clientpref-night .mw-parser-output p>.tmp-color,html.skin-theme-clientpref-night .mw-parser-output table:not(.notheme) .tmp-color{color:inherit!important}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output div:not(.notheme)>.tmp-color,html.skin-theme-clientpref-os .mw-parser-output p>.tmp-color,html.skin-theme-clientpref-os .mw-parser-output table:not(.notheme) .tmp-color{color:inherit!important}} (\exists w) (w \in A) \land (\exists z)(\forall u)(u \in A \to u \leq z)]

\to (\exists x)(\forall y)([(\forall w)(w \in A \to w \leq x)] \land [(\forall u)(u \in A \to u \leq y)] \to x \leq y))

Esta fórmula es una formalización directa de "todo conjunto A no vacío y acotado tiene un límite superior mínimo ". Se puede demostrar que cualquier cuerpo ordenado que satisfaga esta propiedad es isomorfo al cuerpo de números reales. Por otra parte, el conjunto de oraciones de primer orden válidas en los números reales tiene modelos arbitrariamente grandes debido al teorema de compacidad. Por lo tanto, la propiedad del límite superior mínimo no puede expresarse mediante ningún conjunto de oraciones en lógica de primer orden. (De hecho, todo cuerpo real cerrado satisface las mismas oraciones de primer orden en la signatura que los números reales). $\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 numerable ". Para decir que el dominio es finito, se usa la oración que dice que toda función sobreyectiva del dominio hacia sí mismo es inyectiva . Para decir que el dominio tiene cardinalidad numerable, se usa la oración que dice que hay una biyección entre cada dos subconjuntos infinitos del dominio. Del teorema de compacidad y del teorema de Löwenheim-Skolem ascendente se deduce que no es posible caracterizar la finitud o la numerabilidad, respectivamente, en lógica de primer orden.

Ciertos fragmentos de lógica de segundo orden como ESO también son más expresivos que la lógica de primer orden, aunque estrictamente son menos expresivos que la lógica de segundo orden completa. ESO también disfruta de equivalencia de traducción con algunas extensiones de lógica de primer orden que permiten la ordenación no lineal de dependencias de cuantificadores, como la lógica de primer orden extendida con 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 se pueda utilizar para probar 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 la lógica de primer orden (como la deducción natural ) ampliado 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 de primer orden ampliado 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 semántica completa de segundo orden, a la teoría de primer orden de la siguiente manera. Primero se expande el dominio del conjunto de todos los números reales a un dominio de dos ordenaciones, con la segunda ordenación conteniendo todos los conjuntos de números reales. Se agrega un nuevo predicado binario al lenguaje: la relación de pertenencia. Luego, las oraciones que eran de segundo orden se convierten en de primer orden, con los cuantificadores que antes eran de segundo orden en su lugar abarcando la segunda ordenación. Esta reducción se puede intentar en una teoría de una ordenación 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 nótese 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 lo demuestra el teorema de Löwenheim-Skolem . Ese teorema implica que existe un subconjunto numerablemente infinito de los números reales, cuyos miembros llamaremos números internos , y una colección numerablemente infinita de conjuntos de números internos, cuyos miembros llamaremos "conjuntos internos", tales que el dominio que consiste en números internos y conjuntos internos satisface 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 superior mínimo 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 numerabilidad del conjunto de todos los números internos (en conjunción con el hecho de que estos forman un conjunto densamente ordenado) implica que ese conjunto no satisface por completo el axioma del límite superior mínimo. La numerabilidad 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 infinito numerable es un conjunto infinito incontable). 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 solo hay un cuerpo completo ordenado de Arquímedes , junto con el hecho de que todos los axiomas de un cuerpo completo ordenado de Arquímedes son expresables en lógica de segundo orden. Esto demuestra 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 teoría de primer orden correspondiente tiene muchos modelos.

Existen ejemplos más extremos que demuestran 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 no se cumple la hipótesis del continuo (cf. Shapiro 2000, p. 105). Esta teoría consiste en una teoría finita que caracteriza a los números reales como un cuerpo ordenado de Arquímedes completo más un axioma que dice que el dominio es de la 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 un sistema deductivo (es decir, no existe una noción de demostrabilidad ) para fórmulas de segundo orden que satisfaga simultáneamente estos tres atributos deseados: ^[7]

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

Este corolario se expresa a veces 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, pp. 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 la semántica de Henkin usando solo modelos que satisfacen estos principios.

El teorema de compacidad y el teorema de Löwenheim-Skolem no se cumplen para los modelos completos de lógica de segundo orden, pero sí para los modelos de Henkin. ^[8]^{: xi}

Historia y valor en disputa

La lógica de predicados fue introducida a la comunidad matemática por CS Peirce , quien acuñó el término lógica de segundo orden y cuya notación es la más similar a la forma moderna (Putnam 1982). Sin embargo, hoy 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 cuyos trabajos fueron menos conocidos hasta que Bertrand Russell y Alfred North Whitehead los hicieron famosos. Frege usó diferentes variables para distinguir la cuantificación sobre objetos de la cuantificación sobre propiedades y conjuntos; pero no se vio 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 estaba mal con su sistema. Finalmente, 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 se pueden cuantificar solo en la lógica de primer orden. La jerarquía de órdenes de lógica ahora estándar data de esta época.

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 esto se hizo (véase la teoría de conjuntos de Zermelo-Fraenkel ), ya que los conjuntos son vitales para las matemáticas . La aritmética , la mereología y una variedad de otras teorías lógicas poderosas podían formularse axiomáticamente sin apelar 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 general en el trabajo en lógica de segundo (o cualquier orden superior). ^{[ cita requerida ]}

Este rechazo fue defendido activamente por algunos lógicos, en particular W. V. Quine . Quine propuso la idea ^{[ cita requerida ]} 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 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 sobre algo como esto. (Esta posición es bastante consistente con los propios argumentos de Frege sobre la distinción concepto-objeto ). Por lo tanto, utilizar un predicado como una variable es hacer que ocupe el lugar de un nombre, que solo las variables individuales deberían ocupar. Este razonamiento ha sido rechazado por George Boolos . ^{[ cita requerida ]}

En los últimos años ^{[ ¿cuándo? ]} la lógica de segundo orden ha experimentado una cierta recuperación, impulsada por la interpretación de Boolos de la cuantificación de segundo orden como 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 oraciones como "Algunos críticos se admiran sólo entre sí" y "Algunos de los hombres de Fianchetto entraron en el almacén sin la compañía de nadie más", que, según él, sólo se pueden expresar con toda la fuerza de la cuantificación de segundo orden. 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 lugar y éstas no apelan a la cuantificación de segundo orden.

Relación con la complejidad computacional

El poder expresivo de varias formas de lógica de segundo orden sobre 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 el gráfico de la función sucesora en D o la relación de orden <, posiblemente con otros predicados aritméticos). A la inversa, 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 ( 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 por 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 idiomas definibles mediante fórmulas de segundo orden con un operador de punto fijo mínimo agregado .

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

Véase también

Notas

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

Referencias

Andrews, Peter (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.). Kluwer Academic Publishers.
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, Logic, Logic and Logic , 1998.
Henkin, L. (1950). "Completitud en la teoría de tipos". Journal of Symbolic Logic . 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). "Peirce el lógico". Historia Mathematica . 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. 252–260.
WV Quine (1970). Filosofía de la lógica. Prentice Hall . ISBN 9780674665637.
Rossberg, M. (2004). "First-Order Logic, Second-Order Logic, and Completeness" (PDF) . En V. Hendricks; et al. (eds.). La lógica de primer orden revisitada . Berlín: Logos-Verlag.
Shapiro, S. (2000) [1991].Fundamentos sin fundacionalismo: un argumento a favor de la lógica de segundo orden. Oxford: Clarendon Press. 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.

Lectura adicional

Grädel, Erich; Kolaitis, Phokion G.; Libkin, Leonid ; Maarten, Marx; Spencer, Joel ; Vardi, Moshe Y .; Venema, Yde; Weinstein, Scott (2007). Teoría de modelos finitos y sus aplicaciones . Textos en 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. The Stanford Encyclopedia of Philosophy (edición de otoño de 2021).