Lógica de segundo orden - Second-order logic

En lógica y matemáticas, la lógica de segundo orden es una extensión de la lógica de primer orden , que en sí misma es una extensión de la lógica proposicional . 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 solo las variables que se extienden sobre los individuos (elementos del dominio del discurso ); La lógica de segundo orden, además, también cuantifica sobrerelaciones. Por ejemplo, la oración de segundo orden dice que para cada fórmula P , y cada individuo x , o 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 de conjuntos , funciones y otras variables (consulte la sección siguiente ). Tanto la lógica de primer orden como la de segundo orden usan la idea de un dominio del discurso (a menudo llamado simplemente el "dominio" o el "universo"). El dominio es un conjunto sobre el que se pueden cuantificar elementos individuales. ${\ Displaystyle \ forall P \, \ forall x (Px \ lor \ neg Px)}$

Ejemplos de

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

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

\exists x Cubo (x)

Pero 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 esta es una frase legítima de lógica de segundo orden.

Como resultado, la lógica de segundo orden tiene mucho más "poder expresivo" que la lógica de primer orden. Por ejemplo, no hay manera en la lógica de primer orden para decir que una y b tienen alguna propiedad en común; pero en la lógica de segundo orden esto se expresaría como

\existsP (P (a) \land P (b)).

Supongamos que nos gustaría decir que una y B tienen la misma forma. Lo mejor que podríamos hacer en lógica de primer orden es algo como esto:

(Cubo (a) \land Cubo (b)) \lor (Tet (a) \land Tet (b)) \lor (Dodec (a) \land Dodec (b))

Si las únicas formas son cubo, tetraedro, y dodecaedro, por una y b para tener la misma forma es para ellos ya sea para ser ambos cubos, tetraedros tanto, o ambos dodecaedros. Sin embargo, no parece que esta frase lógica de primer orden para significar exactamente lo mismo que la frase Inglés se traduce, por ejemplo, que no dice nada sobre el hecho de que es la forma que una y b tienen en común.

En la lógica de segundo orden, por el contrario, podríamos agregar un predicado Shape que sea verdadero precisamente para las propiedades correspondientes a los predicados Cube, Tet y Dodec. Es decir,

Forma (cubo) \land Forma (Tet) \land Forma (Dodec)

Entonces podríamos escribir:

\existsP (Forma (P) \land P (a) \land P (b))

Y esto es verdad exactamente cuando un y b son ambos cubos, tetraedros tanto, o ambos dodecaedros. Entonces, en la lógica de segundo orden podemos expresar la idea de la misma forma usando identidad y el predicado de segundo orden Forma; podemos prescindir del predicado especial SameShape.

De manera similar, podemos expresar la afirmación de que ningún objeto tiene todas las formas de una manera que resalte el cuantificador en todas las formas :

\neg\exists x \forallP (Forma (P) \to P (x))

En la lógica de primer orden, se dice que un bloque es uno de los siguientes: un cubo, un tetraedro o un dodecaedro:

\neg\exists x (Cubo (x) \land Tet (x) \land Dodec (x))

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:

Una especie 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 guardar 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 hay una especie de variables que se extienden sobre todas las relaciones k -ary de los individuos. Si R es una variable de relación k -ary 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 una especie 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 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 cuantificarse universal y / o existencialmente, para construir fórmulas. Por tanto, hay muchos tipos de cuantificadores, dos para cada tipo de variable. Una oración en la 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 renunciar a 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 ser representada por 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 solo se permite la cuantificación sobre relaciones unarias (es decir, conjuntos). La cuantificación de funciones, debido a la equivalencia de 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 usa particularmente en el contexto del teorema de Courcelle , un metateorema algorítmico en la teoría de grafos .

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. Estos están restringidos, sin embargo, en el sentido de que todos los términos que forman deben ser términos de primer orden (que pueden ser sustituidos por una variable de primer orden) o términos de segundo orden (que pueden ser sustituidos por una variable de segundo orden de una variable). tipo apropiado).

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 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 las variables de segundo orden, es decir , donde es una fórmula de primer orden. El fragmento de lógica de segundo orden que consta solo 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 por recursión 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 \ existe R_ {0} \ ldots \ existe R_ {m} \ phi}$ ${\ Displaystyle \ phi}$ ${\ Displaystyle \ Sigma _ {1} ^ {1}}$ ${\ Displaystyle \ Pi _ {1} ^ {1}}$ ${\ Displaystyle \ Sigma _ {k + 1} ^ {1}}$ ${\ Displaystyle \ existe R_ {0} \ ldots \ existe 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 solo una semántica estándar, hay dos semánticas diferentes que se utilizan 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. Así, una vez que se establece el dominio de las variables de primer orden, se fija el significado de los cuantificadores restantes. 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.

En la semántica de Henkin, cada tipo de variable de segundo orden tiene un dominio particular propio sobre el que abarcar, que puede ser un subconjunto adecuado de todos los conjuntos o funciones de ese tipo. Leon Henkin (1950) definió esta semántica y 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. Esto se debe a que la semántica de Henkin es casi idéntica a la semántica de primer orden de muchos ordenamientos, donde se agregan tipos adicionales de variables para simular las nuevas variables de la lógica de segundo orden. La lógica de segundo orden con la semántica de Henkin no es más expresiva que la lógica de primer orden. La semántica de Henkin se usa comúnmente 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, no podemos realmente 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 la 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- orden lógica para afirmar la propiedad de límite superior mínimo 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 del límite superior mínimo:

(\forall A) ([(\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 campo ordenado que satisfaga esta propiedad es isomorfo al campo de número real. Por otro lado, el conjunto de oraciones de primer orden válidas en los reales tiene modelos arbitrariamente grandes debido al teorema de la compacidad. Por tanto, la propiedad del límite superior mínimo no puede expresarse mediante ningún conjunto de oraciones en la lógica de primer orden. (De hecho, cada campo cerrado real satisface las mismas oraciones de primer orden en la firma que los números reales). ${\ Displaystyle \ langle +, \ cdot, \ leq \ rangle}$

En la 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 cada función sobreyectiva del dominio a 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 subconjuntos infinitos del dominio. Se deduce del teorema de la compacidad y del teorema ascendente de Löwenheim-Skolem que no es posible caracterizar la finitud o la contabilidad, 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 son estrictamente menos expresivos que la lógica de segundo orden completa. ESO también disfruta de la equivalencia de traducción con algunas extensiones de la lógica de primer orden que permiten el ordenamiento no lineal de las dependencias de cuantificadores, como la lógica de primer orden extendida con cuantificadores de Henkin , la lógica amigable con 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 usar 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 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 ) aumentado con reglas de sustitución para términos de segundo orden. Este sistema deductivo se usa 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 sólidas para la semántica de Henkin restringidas a los modelos de Henkin que satisfacen los axiomas de comprensión y elección.

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 expanda el dominio del conjunto de todos los números reales a un dominio de dos ordenamientos, con el segundo tipo que contiene todos los conjuntos de números reales. Agregue un nuevo predicado binario al lenguaje: la relación de pertenencia. Luego, las oraciones que eran de segundo orden se vuelven de primer orden, con los cuantificadores de segundo orden que se encuentran en su lugar por encima del segundo tipo. Esta reducción se puede intentar en una teoría de un solo orden agregando predicados unarios que dicen 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 de potencias de los números reales.

Pero observe que se afirmó que el dominio incluye 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 hay algún subconjunto numerablemente infinito de los números reales, cuyos miembros llamaremos números internos , y alguna colección numerablemente infinita de conjuntos de números internos, cuyos miembros llamaremos "conjuntos internos", de manera que el dominio que consta de Los números internos y los 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 superior mínimo que dice, en efecto:

Cada 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 el axioma completo del límite mínimo superior. La contabilización 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 números reales y 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 sigue del teorema clásico de que solo 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 los números reales de segundo orden no puede reducirse a una teoría de primer orden, en el sentido de que la teoría de los números reales de segundo orden tiene un solo modelo, pero la teoría de primer orden correspondiente 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 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 campo completo ordenado de Arquímedes 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.

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

Resultados metalogicos

Es un corolario del teorema de incompletitud de Gödel que no existe un sistema deductivo (es decir, no hay noción de demostrabilidad ) para fórmulas de segundo orden que satisfagan simultáneamente estos tres atributos deseados:

( Solidez ) Toda oración demostrable de segundo orden 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, 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 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 . A este respecto, 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 , hablando con propiedad.

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 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 solo modelos que satisfacen estos principios.

El teorema de la compacidad y el teorema de Löwenheim-Skolem no se aplican a los modelos completos de lógica de segundo orden. Sin embargo, son válidos para los modelos Henkin.

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 obra 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 sobre objetos de la cuantificación sobre 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 en 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 únicamente en la lógica de primer orden. La jerarquía ahora estándar de órdenes de lógica 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 (ver el 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 podrí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 teoría general. Disminución del trabajo en lógica de segundo orden (o superior).

Este rechazo fue promovido activamente por algunos lógicos, sobre todo WV Quine . Quine avanzó la opinión de que en oraciones de lenguaje predicado como Fx, la " x " debe pensarse como una variable o nombre que denota un objeto y, por lo tanto, puede cuantificarse, como en "Para todas las cosas, se da el caso de 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 algo como esto. (Esta 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 solo deben ocupar las variables individuales. Este razonamiento ha sido rechazado por George Boolos .

En los últimos años, la lógica de segundo orden se ha recuperado, 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 apunta además a la supuesta falta de ordenación de oraciones como "Algunos críticos solo se admiran entre sí" y "Algunos de los hombres de Fianchetto entraron al almacén sin la compañía de nadie más", lo que, según él, solo puede expresarse con toda la fuerza de las 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 lugar y estas 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 las clases de complejidad computacional que pueden caracterizarse por el poder de la lógica necesaria para expresar los lenguajes (conjuntos de cadenas finitas) en ellos. Una cadena w = w ₁ ··· w _n en un alfabeto finito A puede ser representada por 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 unívocamente qué índice es cuál (típicamente, 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 lógica de segundo orden sobre estructuras finitas:

REG (el conjunto de lenguajes regulares ) se puede definir mediante fórmulas monádicas de segundo orden (teorema de Büchi, 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 por 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 por fórmulas de segundo orden con un operador de cierre transitivo agregado .
EXPTIME es el conjunto de idiomas definibles por fórmulas de segundo orden con un operador de punto fijo mínimo agregado .

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

Ver también

Notas

Referencias

Andrews, Peter (2002). Una 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.). 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, Logic, Logic and Logic , 1998.
Henkin, L. (1950). "Integridad en la teoría de tipos". Revista de lógica simbólica . 15 (2): 81–91. doi : 10.2307 / 2266967 . JSTOR 2266967 .
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), Realism with a Human Face , Harvard University Press , págs. 252-260 .
WV Quine (1970). Filosofía de la lógica . Prentice Hall .
Rossberg, M. (2004). "Lógica de primer orden, lógica de segundo orden e integridad" (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 para 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 .

Otras lecturas

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 . La Enciclopedia de Filosofía de Stanford (edición de otoño de 2021).

Languages

In other projects