Lógica de segunda ordem - Second-order logic

Em lógica e matemática , a lógica de segunda ordem é uma extensão da lógica de primeira ordem , que por sua vez é uma extensão da lógica proposicional . A lógica de segunda ordem é, por sua vez, estendida pela lógica de ordem superior e pela teoria dos tipos .

A lógica de primeira ordem quantifica apenas variáveis ​​que abrangem indivíduos (elementos do domínio do discurso ); a lógica de segunda ordem, além disso, também quantifica sobre as relações. Por exemplo, a sentença de segunda ordem diz que para toda fórmula P e todo indivíduo x , Px é verdadeiro ou não ( Px ) é verdadeiro (esta é a lei do meio excluído ). A lógica de segunda ordem também inclui a quantificação de conjuntos , funções e outras variáveis ​​(consulte a seção abaixo ). Tanto a lógica de primeira quanto a de segunda ordem usam a ideia de um domínio de discurso (freqüentemente chamado simplesmente de "domínio" ou "universo"). O domínio é um conjunto sobre o qual os elementos individuais podem ser quantificados.

Exemplos

Graffiti em Neukölln (Berlim) mostrando a frase de segunda ordem mais simples admitindo modelos não triviais, "∃φ φ".

A lógica de primeira ordem pode quantificar sobre os indivíduos, mas não sobre as propriedades. Ou seja, podemos pegar uma sentença atômica como o Cubo ( b ) e obter uma sentença quantificada substituindo o nome por uma variável e anexando um quantificador:

x Cubo ( x )

Mas não podemos fazer o mesmo com o predicado. Ou seja, a seguinte expressão:

∃PP ( b )

não é uma frase de lógica de primeira ordem. Mas esta é uma frase legítima da lógica de segunda ordem.

Como resultado, a lógica de segunda ordem tem muito mais “poder expressivo” do que a lógica de primeira ordem. Por exemplo, não há como dizer na lógica de primeira ordem que a e b têm alguma propriedade em comum; mas na lógica de segunda ordem, isso seria expresso como

∃P (P ( a ) ∧ P ( b )).

Suponha que gostaríamos de dizer que um e b têm a mesma forma. O melhor que poderíamos fazer na lógica de primeira ordem é algo assim:

(Cubo ( a ) ∧ Cubo ( b )) ∨ (Tet ( a ) ∧ Tet ( b )) ∨ (Dodec ( a ) ∧ Dodec ( b ))

Se as únicas formas são cubo, tetraedro, e dodecaedro, para um e b a ter a mesma forma é por eles quer seja os dois cubos, tanto tetraedros, ou ambos dodecaedros. Mas esta frase lógica de primeira ordem não parece significar muito a mesma coisa que a sentença Inglês é a tradução, por exemplo, ele não diz nada sobre o fato de que é forma que um e b têm em comum.

Na lógica de segunda ordem, por outro lado, poderíamos adicionar um predicado Forma que é verdadeiro precisamente para as propriedades correspondentes aos predicados Cubo, Tet e Dodec. Isso é,

Forma (cubo) ∧ Forma (Tet) ∧ Forma (Dodec)

Então, poderíamos escrever:

∃P (Forma (P) ∧ P (a) ∧ P ( b ))

E isso é verdade exatamente quando um e b são ambos cubos, tanto tetraedros, ou ambos dodecahedra. Assim, na lógica de segunda ordem, podemos expressar a ideia da mesma forma usando identidade e o predicado de segunda ordem Forma; podemos fazer sem o predicado especial SameShape.

Da mesma forma, podemos expressar a afirmação de que nenhum objeto tem todas as formas de uma forma que traga o quantificador em todas as formas :

¬∃ x ∀P (Forma (P) → P ( x ))

Na lógica de primeira ordem, um bloco é um dos seguintes: um cubo, um tetraedro ou um dodecaedro:

¬∃ x (Cubo ( x ) ∧ Tet ( x ) ∧ Dodec ( x ))

Sintaxe e fragmentos

A sintaxe da lógica de segunda ordem informa quais expressões são fórmulas bem formadas . Além da sintaxe da lógica de primeira ordem , a lógica de segunda ordem inclui muitas novas classificações (às vezes chamadas de tipos ) de variáveis. Estes são:

  • Uma espécie de variáveis ​​que variam em conjuntos de indivíduos. Se S é uma variável desse tipo e t é um termo de primeira ordem, então a expressão tS (também escrita S ( t ), ou St para salvar os parênteses) é uma fórmula atômica . Conjuntos de indivíduos também podem ser vistos como relações unárias no domínio.
  • Para cada número natural k existe um tipo de variável que abrange todas as relações k -ary nos indivíduos. Se R é uma variável de relação k -ary e t 1 , ..., t k são termos de primeira ordem, então a expressão R ( t 1 , ..., t k ) é uma fórmula atômica.
  • Para cada número natural k, há um tipo de variável que abrange todas as funções, pegando k elementos do domínio e retornando um único elemento do domínio. Se f é uma variável de função k -ary e t 1 , ..., t k são termos de primeira ordem, então a expressão f ( t 1 , ..., t k ) é um termo de primeira ordem.

Cada uma das variáveis ​​que acabamos de definir pode ser quantificada universal e / ou existencialmente, para construir fórmulas. Portanto, existem muitos tipos de quantificadores, dois para cada tipo de variável. Uma frase na lógica de segunda ordem, como na lógica de primeira ordem, é uma fórmula bem formada sem variáveis ​​livres (de qualquer tipo).

É possível renunciar à introdução de variáveis ​​de função na definição dada acima (e alguns autores fazem isso) porque uma variável de função n -ary pode ser representada por uma variável de relação de aridade n +1 e uma fórmula apropriada para a unicidade do " result "no argumento n +1 da relação. (Shapiro 2000, p. 63)

A lógica monádica de segunda ordem (MSO) é uma restrição da lógica de segunda ordem na qual apenas a quantificação sobre relações unárias (isto é, conjuntos) é permitida. A quantificação sobre funções, devido à equivalência de relações conforme descrito acima, também não é permitida. A lógica de segunda ordem sem essas restrições às vezes é chamada de lógica completa de segunda ordem para distingui-la da versão monádica. A lógica monádica de segunda ordem é particularmente usada no contexto do teorema de Courcelle , um meta-teorema algorítmico na teoria dos grafos .

Assim como na lógica de primeira ordem, a lógica de segunda ordem pode incluir símbolos não lógicos em uma linguagem de segunda ordem particular. Estes são restritos, no entanto, em que todos os termos que eles formam devem ser termos de primeira ordem (que podem ser substituídos por uma variável de primeira ordem) ou termos de segunda ordem (que podem ser substituídos por uma variável de segunda ordem de um tipo apropriado).

Uma fórmula na lógica de segunda ordem é dita de primeira ordem (e às vezes denotada ou ) se seus quantificadores (que podem ser universais ou existenciais) abrangem apenas variáveis ​​de primeira ordem, embora possa ter variáveis ​​livres de segunda ordem. Uma fórmula (existencial de segunda ordem) é aquela que possui adicionalmente alguns quantificadores existenciais sobre variáveis ​​de segunda ordem, ou seja , onde é uma fórmula de primeira ordem. O fragmento da lógica de segunda ordem consistindo apenas em fórmulas existenciais de segunda ordem é chamado de lógica existencial de segunda ordem e abreviado como ESO, como , ou mesmo como ∃SO. O fragmento de fórmulas é definido duplamente, é chamado de lógica universal de segunda ordem. Fragmentos mais expressivos são definidos para qualquer k > 0 por recursão mútua: tem a forma , onde é uma fórmula, e semelhante, tem a forma , onde é uma fórmula. (Veja hierarquia analítica para a construção análoga da aritmética de segunda ordem .)

Semântica

A semântica da lógica de segunda ordem estabelece o significado de cada frase. Ao contrário da lógica de primeira ordem, que tem apenas uma semântica padrão, existem duas semânticas diferentes que são comumente usadas para a lógica de segunda ordem: semântica padrão e semântica de Henkin . Em cada uma dessas semânticas, as interpretações dos quantificadores de primeira ordem e dos conectivos lógicos são as mesmas que na lógica de primeira ordem. Apenas os intervalos de quantificadores sobre variáveis ​​de segunda ordem diferem nos dois tipos de semântica (Väänänen 2001) .

Na semântica padrão, também chamada de semântica completa, os quantificadores variam em todos os conjuntos ou funções do tipo apropriado. Assim, uma vez que o domínio das variáveis ​​de primeira ordem é estabelecido, o significado dos quantificadores restantes é fixo. É essa semântica que dá à lógica de segunda ordem seu poder expressivo, e elas serão assumidas no restante deste artigo.

Na semântica de Henkin, cada tipo de variável de segunda ordem tem um domínio particular próprio para ser abrangido, que pode ser um subconjunto apropriado de todos os conjuntos ou funções desse tipo. Leon Henkin (1950) definiu essa semântica e provou que o teorema da completude e o teorema da compactação de Gödel , que valem para a lógica de primeira ordem, são transportados para a lógica de segunda ordem com a semântica de Henkin. Isso ocorre porque a semântica de Henkin é quase idêntica à semântica de primeira ordem de classificação múltipla, em que tipos adicionais de variáveis ​​são adicionados para simular as novas variáveis ​​da lógica de segunda ordem. A lógica de segunda ordem com semântica de Henkin não é mais expressiva do que a lógica de primeira ordem. A semântica de Henkin é comumente usada no estudo da aritmética de segunda ordem .

Jouko Väänänen ( 2001 ) argumentou que a escolha entre os modelos de Henkin e os modelos completos para a lógica de segunda ordem é análoga à escolha entre ZFC e V como base para a teoria dos conjuntos: "Tal como acontece com a lógica de segunda ordem, não podemos realmente escolher se nós axiomatize matemática usando V ou ZFC. O resultado é o mesmo em ambos os casos, como ZFC é a melhor tentativa até agora de usar V como uma axiomatização da matemática. "

Poder expressivo

A lógica de segunda ordem é mais expressiva do que a lógica de primeira ordem. Por exemplo, se o domínio é o conjunto de todos os números reais , pode-se afirmar na lógica de primeira ordem a existência de um inverso aditivo de cada número real escrevendo ∀ xy ( x + y = 0), mas é necessário segundo- ordenar a lógica para afirmar a propriedade do limite superior mínimo para conjuntos de números reais, o que afirma que todo conjunto limitado e não vazio de números reais tem um supremo . Se o domínio é o conjunto de todos os números reais, a seguinte frase de segunda ordem (dividida em duas linhas) expressa a propriedade de limite superior mínimo:

(∀ A) ([ (∃ w ) ( w ∈ A)(∃ z ) (∀ u ) ( u ∈ A → uz ) ]
: → (∃ x ) (∀ y ) ([(∀ w ) ( w ∈ A → wx )] ∧ [(∀ u ) ( u ∈ A → uy )] → xy ) )

Essa fórmula é uma formalização direta de "todo conjunto A não vazio e limitado tem um limite superior mínimo ". Pode-se mostrar que qualquer campo ordenado que satisfaça essa propriedade é isomórfico ao campo de número real. Por outro lado, o conjunto de sentenças de primeira ordem válidas em reais possui modelos arbitrariamente grandes devido ao teorema da compacidade. Assim, a propriedade do limite superior mínimo não pode ser expressa por nenhum conjunto de sentenças na lógica de primeira ordem. (Na verdade, todo campo real fechado satisfaz as mesmas sentenças de primeira ordem na assinatura que os números reais.)

Na lógica de segunda ordem, é possível escrever sentenças formais que digam "o domínio é finito " ou "o domínio é de cardinalidade contável ". Para dizer que o domínio é finito, use a frase que diz que toda função sobrejetiva do domínio para si mesma é injetiva . Para dizer que o domínio tem cardinalidade contável, use a frase que diz que há uma bijeção entre cada dois subconjuntos infinitos do domínio. Segue-se do teorema da compactação e do teorema de Löwenheim-Skolem ascendente que não é possível caracterizar finitude ou contabilidade, respectivamente, na lógica de primeira ordem.

Certos fragmentos da lógica de segunda ordem, como o ESO, também são mais expressivos do que a lógica de primeira ordem, embora sejam estritamente menos expressivos do que a lógica de segunda ordem completa. ESO também desfruta de equivalência de tradução com algumas extensões de lógica de primeira ordem que permitem ordenação não linear de dependências de quantificador, como lógica de primeira ordem estendida com quantificadores de Henkin , lógica de independência amigável de Hintikka e Sandu e lógica de dependência de Väänänen .

Sistemas dedutivos

Um sistema dedutivo para uma lógica é um conjunto de regras de inferência e axiomas lógicos que determinam quais sequências de fórmulas constituem provas válidas. Vários sistemas dedutivos podem ser usados ​​para lógica de segunda ordem, embora nenhum possa ser completo para a semântica padrão (veja abaixo). Cada um desses sistemas é sólido , o que significa que qualquer sentença que eles possam provar é logicamente válida na semântica apropriada.

O sistema dedutivo mais fraco que pode ser usado consiste em um sistema dedutivo padrão para lógica de primeira ordem (como a dedução natural ) acrescido de regras de substituição para termos de segunda ordem. Esse sistema dedutivo é comumente usado no estudo da aritmética de segunda ordem .

Os sistemas dedutivos considerados por Shapiro (1991) e Henkin (1950) adicionam ao esquema dedutivo de primeira ordem aumentado os axiomas de compreensão e de escolha. Esses axiomas são válidos para a semântica de segunda ordem padrão. Eles são válidos para a semântica de Henkin restrita aos modelos de Henkin que satisfazem os axiomas de compreensão e escolha.

Não redutibilidade para lógica de primeira ordem

Pode-se tentar reduzir a teoria de segunda ordem dos números reais, com semântica completa de segunda ordem, à teoria de primeira ordem da seguinte maneira. Primeiro, expanda o domínio do conjunto de todos os números reais para um domínio de duas classificações, com a segunda classificação contendo todos os conjuntos de números reais. Adicione um novo predicado binário ao idioma: a relação de associação. Então, as sentenças de segunda ordem tornam-se de primeira ordem, com os quantificadores de segunda ordem que variam em vez da segunda ordem. Essa redução pode ser tentada em uma teoria de classificação única adicionando predicados unários que dizem se um elemento é um número ou um conjunto, e tomando o domínio como a união do conjunto de números reais e o conjunto de potência dos números reais.

Mas observe que o domínio foi declarado para incluir todos os conjuntos de números reais. Esse requisito não pode ser reduzido a uma sentença de primeira ordem, como mostra o teorema de Löwenheim-Skolem . Esse teorema implica que existe algum subconjunto infinito contável dos números reais, cujos membros chamaremos de números internos , e alguma coleção infinita contável de conjuntos de números internos, cujos membros chamaremos de "conjuntos internos", de modo que o domínio consistindo em números internos e conjuntos internos satisfazem exatamente as mesmas sentenças de primeira ordem que são satisfeitas pelo domínio de números reais e conjuntos de números reais. Em particular, ele satisfaz um tipo de axioma de limite superior mínimo que diz, de fato:

Cada conjunto interno não vazio que possui um limite superior interno tem um limite superior interno mínimo .

A capacidade de contagem do conjunto de todos os números internos (em conjunto com o fato de que aqueles formam um conjunto densamente ordenado) implica que esse conjunto não satisfaz o axioma do limite mínimo superior completo. Contabilidade do conjunto de todos os conjuntos internos implica que não é o conjunto de todos os subconjuntos do conjunto de todos os números internos (uma vez que o teorema de Cantor implica que o conjunto de todos os subconjuntos de um conjunto infinito contável é um conjunto infinito incontável). Essa construção está intimamente relacionada ao paradoxo de Skolem .

Assim, a teoria de primeira ordem de números reais e conjuntos de números reais tem muitos modelos, alguns dos quais são contáveis. A teoria de segunda ordem dos números reais tem apenas um modelo, entretanto. Isso segue do teorema clássico de que há apenas um campo ordenado completo arquimediano , junto com o fato de que todos os axiomas de um campo ordenado completo arquimediano são expressos na lógica de segunda ordem. Isso mostra que a teoria de segunda ordem dos números reais não pode ser reduzida a uma teoria de primeira ordem, no sentido de que a teoria de segunda ordem dos números reais tem apenas um modelo, mas a teoria de primeira ordem correspondente tem muitos modelos.

Existem exemplos mais extremos mostrando que a lógica de segunda ordem com semântica padrão é mais expressiva do que a lógica de primeira ordem. Há uma teoria finita de segunda ordem cujo único modelo são os números reais se a hipótese do contínuo for válida e que não tem modelo se a hipótese do contínuo não for válida (cf. Shapiro 2000, p. 105). Esta teoria consiste em uma teoria finita que caracteriza os números reais como um campo ordenado arquimediano completo mais um axioma dizendo que o domínio é da primeira cardinalidade incontável. Este exemplo ilustra que a questão de saber se uma frase na lógica de segunda ordem é consistente é extremamente sutil.

Limitações adicionais da lógica de segunda ordem são descritas na próxima seção.

Resultados metalógicos

É um corolário do teorema da incompletude de Gödel que não há sistema dedutivo (ou seja, nenhuma noção de provabilidade ) para fórmulas de segunda ordem que satisfazem simultaneamente esses três atributos desejados:

  • ( Solidez ) Cada sentença de segunda ordem comprovável é universalmente válida, ou seja, verdadeira em todos os domínios sob a semântica padrão.
  • ( Completude ) Todas as fórmulas de segunda ordem universalmente válidas, sob a semântica padrão, são prováveis.
  • ( Eficácia ) Existe um algoritmo de verificação que pode decidir corretamente se uma dada sequência de símbolos é uma prova ou não.

Esse corolário às vezes é expresso dizendo que a lógica de segunda ordem não admite uma teoria de prova completa . Nesse aspecto, a lógica de segunda ordem com semântica padrão difere da lógica de primeira ordem; Quine (1970, pp. 90-91 ) apontou para a falta de um sistema de prova completo como uma razão para pensar na lógica de segunda ordem como não lógica , propriamente falando.

Como mencionado acima, Henkin provou que o sistema dedutivo padrão para lógica de primeira ordem é sólido, completo e eficaz para lógica de segunda ordem com semântica de Henkin , e o sistema dedutivo com princípios de compreensão e escolha é sólido, completo e eficaz para Henkin semântica usando apenas modelos que satisfaçam esses princípios.

O teorema da compactação e o teorema de Löwenheim-Skolem não são válidos para modelos completos de lógica de segunda ordem. No entanto, eles são válidos para os modelos Henkin.

História e valor disputado

A lógica dos predicados foi introduzida na comunidade matemática por CS Peirce , que cunhou o termo lógica de segunda ordem e cuja notação é mais semelhante à forma moderna (Putnam 1982). No entanto, hoje a maioria dos estudantes de lógica está mais familiarizada com as obras de Frege , que publicou sua obra vários anos antes de Peirce, mas cujas obras permaneceram menos conhecidas até que Bertrand Russell e Alfred North Whitehead as tornaram famosas. Frege usou variáveis ​​diferentes para distinguir a quantificação sobre objetos da quantificação sobre propriedades e conjuntos; mas ele não se via fazendo dois tipos diferentes de lógica. Após a descoberta do paradoxo de Russell, percebeu-se que algo estava errado com seu sistema. Por fim, os lógicos descobriram que restringir a lógica de Frege de várias maneiras - ao que agora é chamado de lógica de primeira ordem - eliminou esse problema: conjuntos e propriedades não podem ser quantificados apenas na lógica de primeira ordem. A hierarquia agora padrão de ordens de lógicas data dessa época.

Foi descoberto que a teoria dos conjuntos poderia ser formulada como um sistema axiomatizado dentro do aparato da lógica de primeira ordem (ao custo de vários tipos de completude , mas nada tão ruim quanto o paradoxo de Russell), e isso foi feito (ver conjunto Zermelo-Fraenkel teoria ), pois os conjuntos são vitais para a matemática . Aritmética , mereologia e uma variedade de outras teorias lógicas poderosas poderiam ser formuladas axiomaticamente sem recorrer a nenhum aparato mais lógico do que a quantificação de primeira ordem, e isso, junto com a adesão de Gödel e Skolem à lógica de primeira ordem, levou a uma visão geral declínio no trabalho na lógica de segunda ordem (ou qualquer superior).

Essa rejeição foi ativamente promovida por alguns lógicos, principalmente WV Quine . Quine defendeu a visão de que em sentenças de linguagem de predicado como Fx o " x " deve ser pensado como uma variável ou nome que denota um objeto e, portanto, pode ser quantificado, como em "Para todas as coisas, é o caso que... . " mas o " F " deve ser pensado como uma abreviatura de uma frase incompleta, não o nome de um objeto (nem mesmo de um objeto abstrato como uma propriedade). Por exemplo, pode significar "... é um cachorro". Mas não faz sentido pensar que podemos quantificar algo assim. (Tal posição é bastante consistente com os próprios argumentos de Frege sobre a distinção objeto-conceito ). Portanto, usar um predicado como variável é fazer com que ele ocupe o lugar de um nome, que apenas variáveis ​​individuais devem ocupar. Esse raciocínio foi rejeitado por George Boolos .

Nos últimos anos, a lógica de segunda ordem fez uma espécie de recuperação, impulsionada pela interpretação de Boolos da quantificação de segunda ordem como quantificação plural sobre o mesmo domínio de objetos como quantificação de primeira ordem (Boolos 1984). Boolos, além disso, aponta para a alegada não- ordenação de frases como "Alguns críticos admiram apenas uns aos outros" e "Alguns dos homens de Fianchetto foram para o depósito desacompanhados de qualquer outra pessoa", que ele argumenta que só podem ser expressas pela força total da segunda ordem. quantificação. No entanto, a quantificação generalizada e a quantificação parcialmente ordenada (ou ramificada) podem ser suficientes para expressar uma certa classe de sentenças supostamente não ordenáveis ​​também e estas não apelam para a quantificação de segunda ordem.

Relação com a complexidade computacional

O poder expressivo de várias formas de lógica de segunda ordem em estruturas finitas está intimamente ligado à teoria da complexidade computacional . O campo dos estudos de complexidade descritiva cujas classes de complexidade computacional podem ser caracterizadas pelo poder da lógica necessária para expressar linguagens (conjuntos de cadeias finitas) nelas. Uma string w  =  w 1 ··· w n em um alfabeto finito A pode ser representada por uma estrutura finita com domínio D  = {1, ..., n }, predicados unários P a para cada a  ∈  A , satisfeitos por aqueles índices i tais que w i  =  a , e predicados adicionais que servem para identificar exclusivamente qual índice é qual (normalmente, toma-se o gráfico da função sucessora em D ou a relação de ordem <, possivelmente com outros predicados aritméticos). Por outro lado, as tabelas de Cayley de qualquer estrutura finita (sobre uma assinatura finita ) podem ser codificadas por uma string finita.

Essa identificação leva às seguintes caracterizações de variantes da lógica de segunda ordem sobre estruturas finitas:

  • REG (o conjunto de linguagens regulares ) é definível por fórmulas monádicas de segunda ordem (teorema de Büchi, 1960)
  • NP é o conjunto de linguagens definíveis por fórmulas existenciais de segunda ordem ( teorema de Fagin , 1974).
  • co-NP é o conjunto de linguagens definíveis por fórmulas universais de segunda ordem.
  • PH é o conjunto de linguagens definíveis por fórmulas de segunda ordem.
  • PSPACE é o conjunto de linguagens definíveis por fórmulas de segunda ordem com um operador de fechamento transitivo adicionado .
  • EXPTIME é o conjunto de idiomas definíveis por fórmulas de segunda ordem com um operador de ponto fixo mínimo adicionado .

Os relacionamentos entre essas classes impactam diretamente a expressividade relativa das lógicas sobre estruturas finitas; por exemplo, se PH  =  PSPACE , adicionar um operador de fechamento transitivo à lógica de segunda ordem não o tornaria mais expressivo sobre estruturas finitas.

Veja também

Notas

Referências

  • Andrews, Peter (2002). Uma Introdução à Lógica Matemática e Teoria dos Tipos: To Truth Through Proof (2ª ed.). Kluwer Academic Publishers.
  • Boolos, George (1984). "Ser é ser um valor de uma variável (ou ser alguns valores de algumas variáveis)". Journal of Philosophy . 81 (8): 430–50. doi : 10.2307 / 2026308 . JSTOR  2026308 .. Reimpresso em Boolos, Logic, Logic and Logic , 1998.
  • Henkin, L. (1950). "Completude na teoria dos tipos". Journal of Symbolic Logic . 15 (2): 81–91. doi : 10.2307 / 2266967 . JSTOR  2266967 .
  • Hinman, P. (2005). Fundamentos da Lógica Matemática . AK Peters. ISBN 1-56881-262-0.
  • Putnam, Hilary (1982). “Peirce o lógico” . Historia Mathematica . 9 (3): 290–301. doi : 10.1016 / 0315-0860 (82) 90123-9 .. Reimpresso em Putnam, Hilary (1990), Realism with a Human Face , Harvard University Press , pp. 252–260 .
  • WV Quine (1970). Filosofia da lógica . Prentice Hall .
  • Rossberg, M. (2004). "Lógica de primeira ordem, lógica de segunda ordem e integridade" (PDF) . Em V. Hendricks; et al. (eds.). Lógica de primeira ordem revisitada . Berlim: Logos-Verlag.
  • Shapiro, S. (2000) [1991].Fundações sem Fundacionalismo: Um Caso para Lógica de Segunda Ordem. Oxford: Clarendon Press. ISBN 0-19-825029-0.
  • Väänänen, J. (2001). "Lógica de segunda ordem e fundamentos da matemática" (PDF) . Boletim de lógica simbólica . 7 (4): 504–520. CiteSeerX  10.1.1.25.5579 . doi : 10.2307 / 2687796 . JSTOR  2687796 .

Leitura adicional