Lógica matemática

Lógica matemática é o estudo da lógica formal dentro da matemática. As principais subáreas incluem teoria do modelo, teoria da prova, teoria dos conjuntos e teoria da recursão. A pesquisa em lógica matemática geralmente aborda as propriedades matemáticas de sistemas formais de lógica, como seu poder expressivo ou dedutivo. No entanto, também pode incluir usos da lógica para caracterizar o raciocínio matemático correto ou para estabelecer os fundamentos da matemática.

Desde a sua criação, a lógica matemática tem contribuído e sido motivada pelo estudo dos fundamentos da matemática. Este estudo começou no final do século 19 com o desenvolvimento de estruturas axiomáticas para geometria, aritmética e análise. No início do século 20, foi moldado pelo programa de David Hilbert para provar a consistência das teorias fundamentais. Os resultados de Kurt Gödel, Gerhard Gentzen e outros forneceram uma solução parcial para o programa e esclareceram as questões envolvidas na comprovação da consistência. O trabalho na teoria dos conjuntos mostrou que quase toda a matemática comum pode ser formalizada em termos de conjuntos, embora existam alguns teoremas que não podem ser provados em sistemas de axiomas comuns para a teoria dos conjuntos. O trabalho contemporâneo sobre os fundamentos da matemática geralmente se concentra em estabelecer quais partes da matemática podem ser formalizadas em sistemas formais específicos (como na matemática reversa), em vez de tentar encontrar teorias nas quais toda a matemática possa ser desenvolvida.

Subcampos e escopo

O Handbook of Mathematical Logic em 1977 faz uma divisão grosseira da lógica matemática contemporânea em quatro áreas:

1. teoria dos conjuntos
2. teoria do modelo
3. teoria da recursão, e
4. teoria da prova e matemática construtiva (considerada como partes de uma única área).

Além disso, às vezes o campo da teoria da complexidade computacional também é incluído como parte da lógica matemática. Cada área tem um foco distinto, embora muitas técnicas e resultados sejam compartilhados entre várias áreas. As fronteiras entre esses campos e as linhas que separam a lógica matemática e outros campos da matemática nem sempre são nítidas. O teorema da incompletude de Gödel marca não apenas um marco na teoria da recursão e na teoria da prova, mas também levou ao teorema de Löb na lógica modal. O método de forçamento é empregado na teoria dos conjuntos, teoria dos modelos e teoria da recursão, bem como no estudo da matemática intuicionista.

O campo matemático da teoria das categorias usa muitos métodos axiomáticos formais e inclui o estudo da lógica categórica, mas a teoria das categorias não é normalmente considerada um subcampo da lógica matemática. Devido à sua aplicabilidade em diversos campos da matemática, matemáticos, incluindo Saunders Mac Lane, propuseram a teoria das categorias como um sistema fundamental para a matemática, independente da teoria dos conjuntos. Esses fundamentos usam toposes, que se assemelham a modelos generalizados de teoria dos conjuntos que podem empregar lógica clássica ou não clássica.

História

A lógica matemática surgiu em meados do século XIX como um subcampo da matemática, refletindo a confluência de duas tradições: a lógica filosófica formal e a matemática. "Lógica matemática, também chamada de 'logística', 'lógica simbólica', a 'álgebra da lógica' e, mais recentemente, simplesmente ' lógica formal', é o conjunto de teorias lógicas elaboradas no decorrer do século XIX passado com o auxílio de uma notação artificial e um método rigorosamente dedutivo." Antes desse surgimento, a lógica era estudada com retórica, com calculationes, através do silogismo e com a filosofia. A primeira metade do século 20 viu uma explosão de resultados fundamentais, acompanhada por um vigoroso debate sobre os fundamentos da matemática.

História inicial

As teorias da lógica foram desenvolvidas em muitas culturas ao longo da história, incluindo China, Índia, Grécia e o mundo islâmico. Os métodos gregos, particularmente a lógica aristotélica (ou lógica do termo) encontrada no Organon, encontraram ampla aplicação e aceitação na ciência e matemática ocidentais por milênios. Os estóicos, especialmente Crisipo, começaram o desenvolvimento da lógica de predicados. Na Europa do século XVIII, tentativas de tratar as operações da lógica formal de maneira simbólica ou algébrica foram feitas por matemáticos filosóficos, incluindo Leibniz e Lambert, mas seus trabalhos permaneceram isolados e pouco conhecidos.

Século XIX

Em meados do século XIX, George Boole e depois Augustus De Morgan apresentaram tratamentos matemáticos sistemáticos da lógica. Seu trabalho, baseado no trabalho de algebristas como George Peacock, ampliou a tradicional doutrina aristotélica da lógica em uma estrutura suficiente para o estudo dos fundamentos da matemática. Em 1847. Vatroslav Bertić fez um trabalho substancial na algebrização da lógica, independentemente de Boole. Charles Sanders Peirce posteriormente baseou-se no trabalho de Boole para desenvolver um sistema lógico para relações e quantificadores, que publicou em vários artigos de 1870 a 1885.

Gottlob Frege apresentou um desenvolvimento independente da lógica com quantificadores em seu Begriffsschrift, publicado em 1879, um trabalho geralmente considerado como um marco na história da lógica. O trabalho de Frege permaneceu obscuro, no entanto, até Bertrand Russell começar a promovê-lo perto da virada do século. A notação bidimensional desenvolvida por Frege nunca foi amplamente adotada e não é utilizada em textos contemporâneos.

De 1890 a 1905, Ernst Schröder publicou Vorlesungen über die Algebra der Logik em três volumes. Este trabalho resumiu e estendeu o trabalho de Boole, De Morgan e Peirce, e foi uma referência abrangente à lógica simbólica como era compreendida no final do século XIX.

Teorias fundamentais

A preocupação de que a matemática não havia sido construída sobre uma base adequada levou ao desenvolvimento de sistemas axiomáticos para áreas fundamentais da matemática, como aritmética, análise e geometria.

Na lógica, o termo aritmética refere-se à teoria dos números naturais. Giuseppe Peano publicou um conjunto de axiomas para aritmética que passou a levar seu nome (axiomas de Peano), usando uma variação do sistema lógico de Boole e Schröder, mas acrescentando quantificadores. Peano desconhecia a obra de Frege na época. Na mesma época, Richard Dedekind mostrou que os números naturais são caracterizados exclusivamente por suas propriedades de indução. Dedekind propôs uma caracterização diferente, que carecia do caráter lógico formal dos axiomas de Peano. O trabalho de Dedekind, no entanto, provou teoremas inacessíveis no sistema de Peano, incluindo a unicidade do conjunto de números naturais (até o isomorfismo) e as definições recursivas de adição e multiplicação da função sucessora e indução matemática.

Em meados do século 19, as falhas nos axiomas de Euclides para a geometria tornaram-se conhecidas. Além da independência do postulado das paralelas, estabelecido por Nikolai Lobachevsky em 1826, os matemáticos descobriram que certos teoremas tidos como certos por Euclides não eram de fato demonstráveis a partir de seus axiomas. Entre eles está o teorema de que uma linha contém pelo menos dois pontos, ou que círculos de mesmo raio cujos centros são separados por aquele raio devem se cruzar. Hilbert desenvolveu um conjunto completo de axiomas para geometria, com base no trabalho anterior de Pasch. O sucesso na axiomatização da geometria motivou Hilbert a buscar axiomatizações completas de outras áreas da matemática, como os números naturais e a reta real. Esta viria a ser uma importante área de pesquisa na primeira metade do século 20.

O século 19 viu grandes avanços na teoria da análise real, incluindo teorias de convergência de funções e séries de Fourier. Matemáticos como Karl Weierstrass começaram a construir funções que expandiam a intuição, como funções contínuas não diferenciáveis em nenhum lugar. As concepções anteriores de uma função como uma regra para computação, ou um gráfico suave, não eram mais adequadas. Weierstrass começou a defender a aritmetização da análise, que buscava axiomatizar a análise usando as propriedades dos números naturais. A definição moderna (ε, δ) de limite e funções contínuas já foi desenvolvida por Bolzano em 1817, mas permaneceu relativamente desconhecida. Cauchy em 1821 definiu a continuidade em termos de infinitesimais (ver Cours d'Analyse, página 34). Em 1858, Dedekind propôs uma definição dos números reais em termos de cortes de números racionais de Dedekind, uma definição ainda empregada em textos contemporâneos.

Georg Cantor desenvolveu os conceitos fundamentais da teoria dos conjuntos infinitos. Seus primeiros resultados desenvolveram a teoria da cardinalidade e provaram que os números reais e naturais têm diferentes cardinalidades. Nos vinte anos seguintes, Cantor desenvolveu uma teoria dos números transfinitos em uma série de publicações. Em 1891, ele publicou uma nova prova da incontabilidade dos números reais que introduziu o argumento da diagonal e usou esse método para provar o teorema de Cantor de que nenhum conjunto pode ter a mesma cardinalidade que seu conjunto de potências. Cantor acreditava que todo conjunto poderia ser bem ordenado, mas não conseguiu produzir uma prova para esse resultado, deixando-o como um problema em aberto em 1895.

Século 20

Nas primeiras décadas do século XX, as principais áreas de estudo eram a teoria dos conjuntos e a lógica formal. A descoberta de paradoxos na teoria informal dos conjuntos fez com que alguns se perguntassem se a própria matemática é inconsistente e procurassem provas de consistência.

Em 1900, Hilbert apresentou uma famosa lista de 23 problemas para o próximo século. Os dois primeiros foram para resolver a hipótese do contínuo e provar a consistência da aritmética elementar, respectivamente; a décima era produzir um método que pudesse decidir se uma equação polinomial multivariada sobre os números inteiros tem solução. O trabalho subsequente para resolver esses problemas moldou a direção da lógica matemática, assim como o esforço para resolver o Entscheidungsproblem de Hilbert, proposto em 1928. Esse problema exigia um procedimento que decidiria, dado um formalizado afirmação matemática, seja a afirmação verdadeira ou falsa.

Conjunto de teoria e paradoxos

Ernst Zermelo deu uma prova de que todos os conjuntos podem ser bem ordenados, um resultado que Georg Cantor não conseguiu obter. Para conseguir a prova, Zermelo introduziu o axioma da escolha, que atraiu acalorados debates e pesquisas entre os matemáticos e os pioneiros da teoria dos conjuntos. A crítica imediata ao método levou Zermelo a publicar uma segunda exposição de seu resultado, abordando diretamente as críticas à sua prova. Este artigo levou à aceitação geral do axioma da escolha na comunidade matemática.

O ceticismo sobre o axioma da escolha foi reforçado por paradoxos recentemente descobertos na teoria ingênua dos conjuntos. Cesare Burali-Forti foi o primeiro a enunciar um paradoxo: o paradoxo de Burali-Forti mostra que a coleção de todos os números ordinais não pode formar um conjunto. Logo depois disso, Bertrand Russell descobriu o paradoxo de Russell em 1901, e Jules Richard descobriu o paradoxo de Richard.

Zermelo forneceu o primeiro conjunto de axiomas para a teoria dos conjuntos. Esses axiomas, juntamente com o axioma adicional de substituição proposto por Abraham Fraenkel, são agora chamados de teoria dos conjuntos de Zermelo-Fraenkel (ZF). Os axiomas de Zermelo incorporaram o princípio da limitação de tamanho para evitar o paradoxo de Russell.

Em 1910, o primeiro volume de Principia Mathematica de Russell e Alfred North Whitehead foi publicado. Este trabalho seminal desenvolveu a teoria das funções e cardinalidade em uma estrutura completamente formal da teoria dos tipos, que Russell e Whitehead desenvolveram em um esforço para evitar os paradoxos. Principia Mathematica é considerado um dos trabalhos mais influentes do século 20, embora a estrutura da teoria dos tipos não tenha se mostrado popular como uma teoria fundamental para a matemática.

Fraenkel provou que o axioma da escolha não pode ser provado a partir dos axiomas da teoria dos conjuntos de Zermelo com urelementos. O trabalho posterior de Paul Cohen mostrou que a adição de urelementos não é necessária, e o axioma da escolha é improvável em ZF. A prova de Cohen desenvolveu o método de forçamento, que agora é uma ferramenta importante para estabelecer resultados de independência na teoria dos conjuntos.

Lógica simbólica

Leopold Löwenheim e Thoralf Skolem obtiveram o teorema de Löwenheim–Skolem, que diz que a lógica de primeira ordem não pode controlar as cardinalidades de estruturas infinitas. Skolem percebeu que esse teorema se aplicaria a formalizações de primeira ordem da teoria dos conjuntos e que isso implica que tal formalização tenha um modelo contável. Esse fato contra-intuitivo ficou conhecido como o paradoxo de Skolem.

Em sua tese de doutorado, Kurt Gödel provou o teorema da completude, que estabelece uma correspondência entre sintaxe e semântica na lógica de primeira ordem. Gödel usou o teorema da completude para provar o teorema da compacidade, demonstrando a natureza finitária da consequência lógica de primeira ordem. Esses resultados ajudaram a estabelecer a lógica de primeira ordem como a lógica dominante usada pelos matemáticos.

Em 1931, Gödel publicou On Formally Undecidable Propositions of Principia Mathematica and Related Systems, que provou a incompletude (em um significado diferente da palavra) de todas as teorias de primeira ordem suficientemente fortes e eficazes. Este resultado, conhecido como teorema da incompletude de Gödel, estabelece severas limitações nos fundamentos axiomáticos da matemática, desferindo um forte golpe no programa de Hilbert. Mostrou a impossibilidade de fornecer uma prova de consistência da aritmética dentro de qualquer teoria formal da aritmética. Hilbert, entretanto, não reconheceu a importância do teorema da incompletude por algum tempo.

O teorema de Gödel mostra que uma prova de consistência de qualquer sistema de axioma suficientemente forte e eficaz não pode ser obtida no próprio sistema, se o sistema for consistente, nem em qualquer sistema mais fraco. Isso deixa em aberto a possibilidade de provas de consistência que não podem ser formalizadas dentro do sistema que consideram. Gentzen provou a consistência da aritmética usando um sistema finito juntamente com um princípio de indução transfinita. O resultado de Gentzen introduziu as ideias de eliminação de cortes e ordinais da teoria da prova, que se tornaram ferramentas-chave na teoria da prova. Gödel deu uma prova de consistência diferente, que reduz a consistência da aritmética clássica à da aritmética intuicionista em tipos superiores.

O primeiro livro sobre lógica simbólica para leigos foi escrito por Lewis Carroll, autor de Alice no País das Maravilhas, em 1896.

Início dos outros ramos

Alfred Tarski desenvolveu os fundamentos da teoria dos modelos.

A partir de 1935, um grupo de proeminentes matemáticos colaborou sob o pseudônimo de Nicolas Bourbaki para publicar Éléments de mathématique, uma série de textos matemáticos enciclopédicos. Esses textos, escritos em estilo austero e axiomático, enfatizavam a apresentação rigorosa e os fundamentos teóricos dos conjuntos. A terminologia cunhada por esses textos, como as palavras bijeção, injeção e sobrejeção, e os fundamentos da teoria dos conjuntos empregados pelos textos, foram amplamente adotados em toda a matemática.

O estudo da computabilidade veio a ser conhecido como teoria da recursão ou teoria da computabilidade, porque as primeiras formalizações de Gödel e Kleene dependiam de definições recursivas de funções. Quando essas definições foram mostradas equivalentes à formalização de Turing envolvendo máquinas de Turing, ficou claro que um novo conceito – a função computável – havia sido descoberto e que essa definição era robusta o suficiente para admitir inúmeras caracterizações independentes. Em seu trabalho sobre os teoremas da incompletude em 1931, Gödel carecia de um conceito rigoroso de um sistema formal eficaz; ele imediatamente percebeu que as novas definições de computabilidade poderiam ser usadas para esse fim, permitindo-lhe enunciar os teoremas da incompletude em geral que só poderiam estar implícitos no artigo original.

Numerosos resultados na teoria da recursão foram obtidos na década de 1940 por Stephen Cole Kleene e Emil Leon Post. Kleene introduziu os conceitos de computabilidade relativa, prenunciada por Turing, e a hierarquia aritmética. Kleene posteriormente generalizou a teoria da recursão para funcionais de ordem superior. Kleene e Georg Kreisel estudaram versões formais da matemática intuicionista, particularmente no contexto da teoria da prova.

Sistemas lógicos formais

Na sua essência, a lógica matemática lida com conceitos matemáticos expressos usando sistemas lógicos formais. Esses sistemas, embora difiram em muitos detalhes, compartilham a propriedade comum de considerar apenas expressões em uma linguagem formal fixa. Os sistemas de lógica proposicional e lógica de primeira ordem são os mais amplamente estudados hoje, por causa de sua aplicabilidade aos fundamentos da matemática e por causa de suas desejáveis propriedades teóricas de prova. Lógicas clássicas mais fortes, como lógica de segunda ordem ou lógica infinitária, também são estudadas, juntamente com lógicas não clássicas, como lógica intuicionista.

Lógica de primeira ordem

Lógica de primeira ordem é um sistema formal particular de lógica. Sua sintaxe envolve apenas expressões finitas como fórmulas bem formadas, enquanto sua semântica é caracterizada pela limitação de todos os quantificadores a um domínio fixo de discurso.

Os primeiros resultados da lógica formal estabeleceram limitações da lógica de primeira ordem. O teorema de Löwenheim-Skolem (1919) mostrou que se um conjunto de sentenças em uma linguagem contável de primeira ordem tem um modelo infinito, então ele tem pelo menos um modelo de cada cardinalidade infinita. Isso mostra que é impossível para um conjunto de axiomas de primeira ordem caracterizar os números naturais, os números reais ou qualquer outra estrutura infinita até o isomorfismo. Como o objetivo dos primeiros estudos fundamentais era produzir teorias axiomáticas para todas as partes da matemática, essa limitação era particularmente rígida.

O teorema da completude de Gödel estabeleceu a equivalência entre as definições semânticas e sintáticas de consequência lógica na lógica de primeira ordem. Mostra que se uma sentença particular é verdadeira em todo modelo que satisfaça um conjunto particular de axiomas, então deve haver uma dedução finita da sentença a partir dos axiomas. O teorema da compacidade apareceu pela primeira vez como um lema na prova de Gödel do teorema da completude, e levou muitos anos até que os lógicos compreendessem seu significado e começassem a aplicá-lo rotineiramente. Ela diz que um conjunto de sentenças tem um modelo se e somente se todo subconjunto finito tem um modelo, ou em outras palavras que um conjunto inconsistente de fórmulas deve ter um subconjunto inconsistente finito. Os teoremas de completude e compacidade permitem uma análise sofisticada da consequência lógica na lógica de primeira ordem e o desenvolvimento da teoria do modelo, e são uma razão fundamental para a proeminência da lógica de primeira ordem na matemática.

Os teoremas da incompletude de Gödel estabelecem limites adicionais para axiomatizações de primeira ordem. O primeiro teorema da incompletude afirma que, para qualquer sistema lógico consistente e efetivamente dado (definido abaixo) que seja capaz de interpretar a aritmética, existe uma afirmação que é verdadeira (no sentido em que vale para os números naturais) mas não demonstrável dentro desse sistema lógico (e que de fato pode falhar em alguns modelos não padronizados de aritmética que podem ser consistentes com o sistema lógico). Por exemplo, em todo sistema lógico capaz de expressar os axiomas de Peano, a sentença de Gödel vale para os números naturais, mas não pode ser provada.

Aqui diz-se que um sistema lógico é efetivamente dado se for possível decidir, dada qualquer fórmula na linguagem do sistema, se a fórmula é um axioma, e aquele que pode expressar os axiomas de Peano é chamado de "suficientemente forte." Quando aplicado à lógica de primeira ordem, o primeiro teorema da incompletude implica que qualquer teoria de primeira ordem suficientemente forte, consistente e eficaz tem modelos que não são elementarmente equivalentes, uma limitação mais forte do que aquela estabelecida pelo teorema de Löwenheim-Skolem. O segundo teorema da incompletude afirma que nenhum sistema de axioma suficientemente forte, consistente e eficaz para aritmética pode provar sua própria consistência, o que foi interpretado para mostrar que o programa de Hilbert não pode ser alcançado.

Outras lógicas clássicas

Muitas lógicas além da lógica de primeira ordem são estudadas. Isso inclui lógicas infinitárias, que permitem que as fórmulas forneçam uma quantidade infinita de informações, e lógicas de ordem superior, que incluem uma parte da teoria dos conjuntos diretamente em sua semântica.

A lógica infinitária mais bem estudada é Lω ω 1,ω ω Não. _{1},omega). Nesta lógica, os quantificadores só podem ser aninhados em profundidades finitas, como na lógica de primeira ordem, mas as fórmulas podem ter conjunções e disjunções infinitas finitas ou contáveis dentro deles. Assim, por exemplo, é possível dizer que um objeto é um número inteiro usando uma fórmula de Lω ω 1,ω ω Não. _{1},omega) como

(x= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =0)∨ ∨ (x= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1)∨ ∨ (x= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =2)∨ ∨ ⋯ ⋯ .(x=0)lor (x=1)lor (x=2)lor cdots.}

As lógicas de ordem superior permitem a quantificação não apenas de elementos do domínio do discurso, mas também de subconjuntos do domínio do discurso, conjuntos de tais subconjuntos e outros objetos de tipo superior. A semântica é definida de modo que, em vez de ter um domínio separado para cada quantificador de tipo superior, os quantificadores abrangem todos os objetos do tipo apropriado. As lógicas estudadas antes do desenvolvimento da lógica de primeira ordem, por exemplo, a lógica de Frege, tinham aspectos similares da teoria dos conjuntos. Embora as lógicas de ordem superior sejam mais expressivas, permitindo axiomatizações completas de estruturas como os números naturais, elas não satisfazem os análogos dos teoremas de completude e compacidade da lógica de primeira ordem e, portanto, são menos passíveis de análise de prova teórica.

Outro tipo de lógica é lógica de ponto fixos que permitem definições indutivas, como se escreve para funções recursivas primitivas.

Pode-se definir formalmente uma extensão da lógica de primeira ordem — uma noção que abrange todas as lógicas nesta seção porque elas se comportam como lógica de primeira ordem de certas maneiras fundamentais, mas não abrange todas as lógicas em geral, por exemplo não abrange lógica intuicionista, modal ou difusa.

O teorema de Lindström implica que a única extensão da lógica de primeira ordem que satisfaz tanto o teorema da compacidade quanto o teorema descendente de Löwenheim-Skolem é a lógica de primeira ordem.

Lógica não clássica e modal

As lógicas modais incluem operadores modais adicionais, como um operador que afirma que uma fórmula específica não é apenas verdadeira, mas necessariamente verdadeira. Embora a lógica modal não seja frequentemente usada para axiomatizar a matemática, ela tem sido usada para estudar as propriedades da demonstrabilidade de primeira ordem e forçamento da teoria dos conjuntos.

A lógica intuicionista foi desenvolvida por Heyting para estudar o programa de intuicionismo de Brouwer, no qual o próprio Brouwer evitou a formalização. A lógica intuicionista especificamente não inclui a lei do terceiro excluído, que afirma que cada sentença é verdadeira ou sua negação é verdadeira. O trabalho de Kleene com a teoria da prova da lógica intuicionista mostrou que informações construtivas podem ser recuperadas de provas intuicionistas. Por exemplo, qualquer função comprovadamente total na aritmética intuicionista é computável; isso não é verdade nas teorias clássicas da aritmética, como a aritmética de Peano.

Lógica algébrica

A lógica algébrica usa os métodos da álgebra abstrata para estudar a semântica da lógica formal. Um exemplo fundamental é o uso de álgebras booleanas para representar valores de verdade na lógica proposicional clássica e o uso de álgebras de Heyting para representar valores de verdade na lógica proposicional intuicionista. Lógicas mais fortes, como lógica de primeira ordem e lógica de ordem superior, são estudadas usando estruturas algébricas mais complicadas, como álgebras cilíndricas.

Teoria dos conjuntos

Teoria dos conjuntos é o estudo dos conjuntos, que são coleções abstratas de objetos. Muitas das noções básicas, como números ordinais e cardinais, foram desenvolvidas informalmente por Cantor antes que as axiomatizações formais da teoria dos conjuntos fossem desenvolvidas. A primeira dessas axiomatizações, devido a Zermelo, foi estendida ligeiramente para se tornar a teoria dos conjuntos de Zermelo-Fraenkel (ZF), que agora é a teoria fundamental mais amplamente usada para a matemática.

Outras formalizações da teoria dos conjuntos foram propostas, incluindo a teoria dos conjuntos de von Neumann–Bernays–Gödel (NBG), a teoria dos conjuntos de Morse–Kelley (MK) e as Novas Fundações (NF). Destes, ZF, NBG e MK são semelhantes na descrição de uma hierarquia cumulativa de conjuntos. A New Foundations adota uma abordagem diferente; ele permite objetos como o conjunto de todos os conjuntos ao custo de restrições em seus axiomas de existência de conjunto. O sistema da teoria dos conjuntos de Kripke-Platek está intimamente relacionado com a teoria da recursão generalizada.

Duas declarações famosas na teoria dos conjuntos são o axioma da escolha e a hipótese do contínuo. O axioma da escolha, declarado pela primeira vez por Zermelo, foi provado independente de ZF por Fraenkel, mas passou a ser amplamente aceito pelos matemáticos. Ele afirma que, dada uma coleção de conjuntos não vazios, existe um único conjunto C que contém exatamente um elemento de cada conjunto na coleção. Diz-se que o conjunto C "escolhe" um elemento de cada conjunto da coleção. Embora a capacidade de fazer tal escolha seja considerada óbvia por alguns, uma vez que cada conjunto na coleção não é vazio, a falta de uma regra geral e concreta pela qual a escolha pode ser feita torna o axioma não construtivo. Stefan Banach e Alfred Tarski mostraram que o axioma da escolha pode ser usado para decompor uma bola sólida em um número finito de peças que podem ser reorganizadas, sem escala, para fazer duas bolas sólidas do tamanho original. Este teorema, conhecido como paradoxo de Banach-Tarski, é um dos muitos resultados contra-intuitivos do axioma da escolha.

A hipótese do contínuo, proposta pela primeira vez como uma conjectura por Cantor, foi listada por David Hilbert como um de seus 23 problemas em 1900. Gödel mostrou que a hipótese do contínuo não pode ser refutada pelos axiomas da teoria dos conjuntos de Zermelo–Fraenkel (com ou sem o axioma da escolha), desenvolvendo o universo construtível da teoria dos conjuntos em que a hipótese do contínuo deve se sustentar. Em 1963, Paul Cohen mostrou que a hipótese do contínuo não pode ser provada a partir dos axiomas da teoria dos conjuntos de Zermelo-Fraenkel. Este resultado de independência não resolveu completamente a questão de Hilbert, no entanto, pois é possível que novos axiomas para a teoria dos conjuntos possam resolver a hipótese. Trabalhos recentes nesse sentido foram conduzidos por W. Hugh Woodin, embora sua importância ainda não esteja clara.

A pesquisa contemporânea em teoria dos conjuntos inclui o estudo de grandes cardeais e determinação. Grandes cardinais são números cardinais com propriedades particulares tão fortes que a existência de tais cardinais não pode ser provada em ZFC. A existência do menor cardeal grande tipicamente estudado, um cardeal inacessível, já implica a consistência de ZFC. Apesar do fato de grandes cardinais terem cardinalidade extremamente alta, sua existência tem muitas ramificações para a estrutura da linha real. Determinação refere-se à possível existência de estratégias vencedoras para certos jogos de dois jogadores (diz-se que os jogos são determinados). A existência dessas estratégias implica propriedades estruturais da linha real e de outros espaços poloneses.

Teoria do modelo

teoria dos modelos estuda os modelos de várias teorias formais. Aqui, uma teoria é um conjunto de fórmulas em uma lógica e assinatura formais particulares, enquanto um modelo é uma estrutura que dá uma interpretação concreta da teoria. A teoria dos modelos está intimamente relacionada à álgebra universal e à geometria algébrica, embora os métodos da teoria dos modelos se concentrem mais em considerações lógicas do que nesses campos.

O conjunto de todos os modelos de uma teoria particular é chamado de classe elementar; a teoria clássica dos modelos busca determinar as propriedades dos modelos em uma classe elementar particular, ou determinar se certas classes de estruturas formam classes elementares.

O método de eliminação de quantificadores pode ser usado para mostrar que conjuntos definíveis em teorias particulares não podem ser muito complicados. Tarski estabeleceu a eliminação do quantificador para corpos reais fechados, um resultado que também mostra que a teoria do corpo de números reais é decidível. Ele também notou que seus métodos eram igualmente aplicáveis a campos algebricamente fechados de características arbitrárias. Um subcampo moderno que se desenvolve a partir disso diz respeito às estruturas o-minimais.

O teorema da categoricidade de Morley, provado por Michael D. Morley, afirma que se uma teoria de primeira ordem em uma linguagem contável é categórica em alguma cardinalidade incontável, ou seja, todos os modelos dessa cardinalidade são isomórficos, então ela é categórica em todas as cardinalidades incontáveis.

Uma consequência trivial da hipótese do contínuo é que uma teoria completa com menos de um contínuo muitos modelos contáveis não isomórficos pode ter apenas muitos contáveis. A conjectura de Vaught, em homenagem a Robert Lawson Vaught, diz que isso é verdade mesmo independentemente da hipótese do contínuo. Muitos casos especiais dessa conjectura foram estabelecidos.

Teoria da recursão

teoria da recursão, também chamada de teoria da computabilidade, estuda as propriedades das funções computáveis e os graus de Turing, que dividem as funções incomputáveis em conjuntos que têm o mesmo nível de incomputabilidade. A teoria da recursão também inclui o estudo da computabilidade generalizada e definibilidade. A teoria da recursão cresceu a partir do trabalho de Rózsa Péter, Alonzo Church e Alan Turing na década de 1930, que foi bastante ampliada por Kleene e Post na década de 1940.

A teoria clássica da recursão concentra-se na computabilidade de funções dos números naturais aos números naturais. Os resultados fundamentais estabelecem uma classe robusta e canônica de funções computáveis com numerosas caracterizações independentes e equivalentes usando máquinas de Turing, cálculo λ e outros sistemas. Resultados mais avançados dizem respeito à estrutura dos graus de Turing e à rede de conjuntos recursivamente enumeráveis.

A teoria da recursão generalizada estende as ideias da teoria da recursão para computações que não são mais necessariamente finitas. Inclui o estudo da computabilidade em tipos superiores, bem como áreas como a teoria da hiperaritmética e a teoria da α-recursão.

A pesquisa contemporânea em teoria da recursão inclui o estudo de aplicações como aleatoriedade algorítmica, teoria do modelo computável e matemática reversa, bem como novos resultados na teoria da recursão pura.

Problemas algoritmicamente insolúveis

Um subcampo importante da teoria da recursão estuda a insolubilidade algorítmica; um problema de decisão ou problema de função é algoritmicamente insolúvel se não houver um algoritmo computável possível que retorne a resposta correta para todas as entradas legais para o problema. Os primeiros resultados sobre insolubilidade, obtidos independentemente por Church e Turing em 1936, mostraram que o Entscheidungsproblem é algoritmicamente insolúvel. Turing provou isso estabelecendo a insolubilidade do problema da parada, um resultado com implicações de longo alcance tanto na teoria da recursão quanto na ciência da computação.

Existem muitos exemplos conhecidos de problemas indecidíveis da matemática comum. O problema da palavra para grupos foi provado algoritmicamente insolúvel por Pyotr Novikov em 1955 e independentemente por W. Boone em 1959. O problema do castor ocupado, desenvolvido por Tibor Radó em 1962, é outro exemplo bem conhecido.

O décimo problema de Hilbert pedia um algoritmo para determinar se uma equação polinomial multivariada com coeficientes inteiros tem uma solução nos inteiros. O progresso parcial foi feito por Julia Robinson, Martin Davis e Hilary Putnam. A insolubilidade algorítmica do problema foi provada por Yuri Matiyasevich em 1970.

Teoria de prova e matemática construtiva

Teoria da prova é o estudo de provas formais em vários sistemas de dedução lógica. Essas provas são representadas como objetos matemáticos formais, facilitando sua análise por técnicas matemáticas. Vários sistemas de dedução são comumente considerados, incluindo sistemas de dedução no estilo de Hilbert, sistemas de dedução natural e o cálculo seqüencial desenvolvido por Gentzen.

O estudo da matemática construtiva, no contexto da lógica matemática, inclui o estudo de sistemas em lógica não clássica, como a lógica intuicionista, bem como o estudo de sistemas predicativos. Um dos primeiros proponentes do predicativismo foi Hermann Weyl, que mostrou que é possível desenvolver uma grande parte da análise real usando apenas métodos predicativos.

Como as provas são inteiramente finitas, enquanto a verdade em uma estrutura não é, é comum que o trabalho em matemática construtiva enfatize a provabilidade. A relação entre provabilidade em sistemas clássicos (ou não construtivos) e provabilidade em sistemas intuicionistas (ou construtivos, respectivamente) é de particular interesse. Resultados como a tradução negativa de Gödel-Gentzen mostram que é possível incorporar (ou traduzir) lógica clássica em lógica intuicionista, permitindo que algumas propriedades sobre provas intuicionistas sejam transferidas de volta para provas clássicas.

Desenvolvimentos recentes na teoria da prova incluem o estudo da mineração de provas por Ulrich Kohlenbach e o estudo de ordinais da teoria da prova por Michael Rathjen.

Aplicativos

"A lógica matemática foi aplicada com sucesso não apenas à matemática e seus fundamentos (G. Frege, B. Russell, D. Hilbert, P. Bernays, H. Scholz, R. Carnap, S. Lesniewski, T. Skolem), mas também para a física (R. Carnap, A. Dittrich, B. Russell, C. E. Shannon, A. N. Whitehead, H. Reichenbach, P. Fevrier), para a biologia (J. H. Woodger, A. Tarski), para a psicologia (F. B. Fitch, C. G. Hempel), para direito e moral (K. Menger, U. Klug, P. Oppenheim), para economia (J. Neumann, O. Morgenstern), para questões práticas (E. C. Berkeley, E. Stamm) e mesmo à metafísica (J. [Jan] Salamucha, H. Scholz, J. M. Bochenski). Suas aplicações à história da lógica têm se mostrado extremamente frutíferas (J. Lukasiewicz, H. Scholz, B. Mates, A. Becker, E. Moody, J. Salamucha, K. Duerr, Z. Jordan, P. Boehner, J. M. Bochenski, S. [Stanislaw] T. Schayer, D. Ingalls)." "Aplicações também foram feitas à teologia (F. Drewnowski, J. Salamucha, I. Thomas)."

Conexões com a ciência da computação

O estudo da teoria da computabilidade na ciência da computação está intimamente relacionado ao estudo da computabilidade na lógica matemática. Há uma diferença de ênfase, no entanto. Os cientistas da computação geralmente se concentram em linguagens de programação concretas e na computabilidade viável, enquanto os pesquisadores em lógica matemática geralmente se concentram na computabilidade como um conceito teórico e na não-computabilidade.

A teoria da semântica das linguagens de programação está relacionada à teoria do modelo, assim como a verificação do programa (em particular, a verificação do modelo). A correspondência de Curry-Howard entre provas e programas relaciona-se com a teoria da prova, especialmente a lógica intuicionista. Cálculos formais como o cálculo lambda e a lógica combinatória são agora estudados como linguagens de programação idealizadas.

A ciência da computação também contribui para a matemática desenvolvendo técnicas para a verificação automática ou até mesmo para a descoberta de provas, como prova automatizada de teoremas e programação lógica.

A teoria da complexidade descritiva relaciona a lógica com a complexidade computacional. O primeiro resultado significativo nessa área, o teorema de Fagin (1974), estabeleceu que NP é justamente o conjunto de linguagens expressáveis por sentenças de lógica existencial de segunda ordem.

Fundamentos da matemática

No século 19, os matemáticos perceberam as lacunas lógicas e inconsistências em seu campo. Foi demonstrado que os axiomas de Euclides para geometria, que foram ensinados por séculos como um exemplo do método axiomático, estavam incompletos. O uso de infinitesimais, e a própria definição de função, foram questionados na análise, pois exemplos patológicos como o de Weierstrass' funções contínuas não diferenciáveis em nenhum lugar foram descobertas.

O estudo de Cantor sobre conjuntos infinitos arbitrários também atraiu críticas. Leopold Kronecker fez a famosa declaração “Deus fez os números inteiros; tudo o mais é obra do homem," endossando um retorno ao estudo de objetos finitos e concretos em matemática. Embora o argumento de Kronecker tenha sido levado adiante pelos construtivistas no século 20, a comunidade matemática como um todo os rejeitou. David Hilbert argumentou a favor do estudo do infinito, dizendo "Ninguém nos expulsará do Paraíso que Cantor criou."

Os matemáticos começaram a procurar sistemas de axiomas que pudessem ser usados para formalizar grandes partes da matemática. Além de remover a ambigüidade de termos anteriormente ingênuos, como função, esperava-se que essa axiomatização permitisse provas de consistência. No século XIX, o principal método de provar a consistência de um conjunto de axiomas era fornecer um modelo para ele. Assim, por exemplo, a geometria não-euclidiana pode ser provada consistente definindo ponto como um ponto em uma esfera fixa e linha como um grande círculo na esfera. A estrutura resultante, um modelo de geometria elíptica, satisfaz os axiomas da geometria plana, exceto o postulado das paralelas.

Com o desenvolvimento da lógica formal, Hilbert questionou se seria possível provar que um sistema de axiomas é consistente analisando a estrutura de provas possíveis no sistema e mostrando por meio dessa análise que é impossível provar uma contradição. Essa ideia levou ao estudo da teoria da prova. Além disso, Hilbert propôs que a análise fosse inteiramente concreta, usando o termo finitário para se referir aos métodos que ele permitiria, mas não definindo-os com precisão. Este projeto, conhecido como programa de Hilbert, foi seriamente afetado pelos teoremas da incompletude de Gödel, que mostram que a consistência das teorias formais da aritmética não pode ser estabelecida usando métodos formalizáveis nessas teorias. Gentzen mostrou que é possível produzir uma prova da consistência da aritmética em um sistema finitário aumentado com axiomas de indução transfinita, e as técnicas que ele desenvolveu para fazer isso foram seminais na teoria da prova.

Um segundo fio condutor na história dos fundamentos da matemática envolve a lógica não clássica e a matemática construtiva. O estudo da matemática construtiva inclui muitos programas diferentes com várias definições de construtivo. Na extremidade mais flexível, as provas na teoria dos conjuntos de ZF que não usam o axioma da escolha são chamadas de construtivas por muitos matemáticos. Versões mais limitadas do construtivismo limitam-se a números naturais, funções teóricas de números e conjuntos de números naturais (que podem ser usados para representar números reais, facilitando o estudo da análise matemática). Uma ideia comum é que um meio concreto de calcular os valores da função deve ser conhecido antes que se possa dizer que a própria função existe.

No início do século 20, Luitzen Egbertus Jan Brouwer fundou o intuicionismo como parte da filosofia da matemática. Essa filosofia, mal compreendida no início, afirmava que, para que uma afirmação matemática seja verdadeira para um matemático, essa pessoa deve ser capaz de intuir a afirmação, não apenas acreditar em sua verdade, mas entender a razão pela sua verdade. Uma consequência dessa definição de verdade foi a rejeição da lei do terceiro excluído, pois há afirmações que, segundo Brouwer, não poderiam ser consideradas verdadeiras enquanto suas negações também não poderiam ser consideradas verdadeiras. A filosofia de Brouwer foi influente e a causa de amargas disputas entre matemáticos proeminentes. Mais tarde, Kleene e Kreisel estudariam versões formalizadas da lógica intuicionista (Brouwer rejeitou a formalização e apresentou seu trabalho em linguagem natural não formalizada). Com o advento da interpretação de BHK e dos modelos de Kripke, o intuicionismo tornou-se mais fácil de conciliar com a matemática clássica.