Na Lógica matemática, aritmética de segunda ordem é uma coleção de sistemas axiomáticos que formalizam os números naturais e seus subconjuntos. É uma alternativa para a teoria axiomática dos conjuntos como fundamentos, mas não tudo, da matemática. Foi introduzida por David Hilbert e Paul Bernays em seu livro Grundlagen der Mathematik. A axiomatização padrão da aritmética de segunda ordem é denotada Z2.

Aritmética de segunda ordem inclui, mas é significativamente mais forte do que, a aritmética de Peano. Ao contrário da aritmética de Peano, aritmética de segunda ordem permite a quantificação sobre conjuntos de números, bem como os próprios números. Como os números reais podem ser representados como conjuntos (infinitos) de números naturais de maneiras bem conhecidas, e dado que a aritmética de segunda ordem permite a quantificação sobre esses conjuntos, é possível formalizar os números reais em aritmética de segunda ordem. Por esta razão, a aritmética de segunda ordem é chamada algumas vezes de "análise".

Aritmética de segunda ordem pode também ser vista como uma versão fraca da teoria dos conjuntos, em que cada elemento seja um número natural ou um conjunto de números naturais. Embora seja muito mais fraca do que a teoria axiomática de Zermelo-Fraenkel, a aritmética de segunda ordem pode provar essencialmente todos os resultados de matemática clássica expressível em sua linguagem.

Um subsistema de aritmética de segunda ordem é uma teoria na linguagem da aritmética de segunda ordem onde cada axioma é um teorema da aritmética de segunda ordem plena (Z2). Esses subsistemas são essenciais para a matemática reversa, um programa de pesquisa que investiga o quanto a matemática clássica pode ser derivada em certos subsistemas fracos de intensidade variável. A maior parte do núcleo da matemática pode ser formalizada por esses subsistemas fracos, alguns dos quais são definidos a seguir. Matemática reversa também esclarece o âmbito e as modalidades em que a matemática clássica é não-construtiva.

Definição

Sintaxe

A linguagem da aritmética de segunda ordem é dividida em duas partes. A primeira parte de termos e variáveis, geralmente indicados por letras minúsculas, é composta por indivíduos, cuja interpretação pretendida é como números naturais. A outra parte de variáveis, chamadas "variáveis de ajuste", "variáveis de classe", ou mesmo "predicados" são normalmente indicados por letras maiúsculas. Eles se referem a classes/predicados/propriedades dos indivíduos, e por isso pode ser pensado como conjuntos de números naturais. Ambos os indivíduos e as variáveis definidas podem ser quantificadas universalmente ou existencialmente. Uma fórmula sem variáveis de conjuntos livres (ou seja, nenhum quantificador sobre variáveis de conjuntos) é chamado aritmético. Uma fórmula matemática pode ter conjuntos de variáveis livres e variáveis individuais limitadas.

Termos individuais são formados a partir da constante 0, a função unária S (função sucessor), e as operações binárias + e • (adição e multiplicação). A função sucessor adiciona 1 (=S0) para a entrada. As relações = (igualdade) e < (comparação dos números naturais) relacionam dois indivíduos, enquanto que a relação ∈ (pertence) relaciona um indivíduo e um conjunto (ou classe). Por exemplo, , é uma fórmula bem formada da aritmética de segunda ordem, tem um conjunto variável livre X e uma variável individual n (porém sem conjuntos finitos de variáveis, como é exigido em uma fórmula aritmética) enquanto é uma fórmula bem formada que não é aritmética com um conjunto de variáveis finitas X e uma variável individual finita n.

Semântica

Várias interpretações diferentes dos quantificadores são possíveis. Se a aritmética de segunda ordem for estudada usando a semântica plena da lógica de segunda ordem, então os quantificadores sobre conjuntos variam sobre todos os subconjuntos de variáveis de núméros. Se a aritmética de segunda ordem for formalizada através da semântica da lógica de primeira ordem, então qualquer modelo inclui um domínio para o conjunto de variáveis, e esse domínio pode ser um subconjunto próprio do conjunto pleno do conjunto das partes do domínio de variáveis de n´umeros.

Embora a aritmética de segunda ordem tenha sido estudada inicialmente usando a semântica plena de segunda ordem, a grande maioria das pesquisas atuais trata a aritmética de segunda ordem no cálculo de predicados de primeira ordem. Isto é porque a teoria de modelos de subsistemas da aritmética de segunda ordem é mais interessante no seio da lógica de primeira ordem.

Axiomas

Básico

Os seguintes axiomas são conhecidos como os axiomas básicos, ou, por vezes, os axiomas de Robinson. A teoria de primeira ordem resultante, conhecida como aritmética de Robinson, é essencialmente a aritmética de Peano sem indução. O universo de discurso para as variáveis quantificadas são os números naturais, denotado coletivamente por N, e incluindo o membro destacado , chamado de "zero".

As funções primitivas são a função unária sucessor, denotada pelo prefixo , e duas operações binárias, adição e multiplicação, denotadas pelos infixos "+" e "", respectivamente. Existe também uma relação binária chamada ordem, denotada pelo infixo "<".

Axiomas que regem a função sucessor e zero: 1. (“o sucessor de um número natural nunca é zero”) 2. (“a função sucessor é injetora”) 3. (“cada número natural é zero ou um sucessor”)

Adição definida recursivamente:

4. 5.

Multiplicação definida recursivamente:

6. 7.

Axiomas que regem a relação de ordem "<": 8. (“nenhum número natural é menor do que zero”) 9. 10. (“todo número natural é zero ou maior do que zero”) 11.

Estes axiomas são todos enunciados de primeira ordem. Ou seja, todas as variáveis são definidas sobre os números naturais e não conjuntos do mesmo, um fato ainda mais forte do que ser aritmético. Além disso, há apenas um quantificador existencial, em axioma 3. Axiomas 1 e 2, juntamente com um esquema de axioma de indução compõem a definição Peano-Dedekind usual de N. Somando-se a estes axiomas qualquer tipo de esquema de axioma da indução torna redundante os axiomas 3, 10 e 11.

Indução e esquema de compreensão Se φ(n) for uma fórmula aritmética de segunda ordem com uma variável de número livre n e possívelmente outro número livre ou conjunto de variáveis (escrito m• e X•), o axioma de indução para φ é o axioma:

O esquema (completo) de indução de segunda ordem consiste em todas as instâncias desse axioma, sobre todas as fórmulas de segunda ordem.

Um exemplo particularmente importante do regime de indução é quando φ é a fórmula "" expressar o fato de que n é um membro de X (X é um conjunto de variável livre): neste caso, o axioma de indução para φ é:

Esta sentença é chamada de axioma de indução de segunda ordem.

Voltando ao caso em que φ (n) é uma fórmula com um n variável livre e possivelmente outras variáveis livres, definimos o axioma compreensão para φ sendo:

Essencialmente, isso nos permite formar o conjunto dos números naturais satisfazendo φ (n). Não existe uma restrição técnica para que a fórmula φ não possa conter a variável Z, pois caso contrário a fórmula levaria ao axioma da compreensão : , o que é inconsistente. Esta convenção é assumida no restante deste artigo.

O sistema completo A teoria formal da aritmética de segunda ordem (na linguagem da aritmética de segunda ordem) é composta pelos axiomas básicos, o axioma de compreensão para cada fórmula φ (aritmética ou não), e o axioma da indução de segunda ordem. Esta teoria é às vezes chamada de aritmética de segunda ordem completa para distingui-la de seus subsistemas, definidos abaixo. Semântica de segunda ordem elimina a necessidade para o axioma da compreensão, porque estas semânticas implicam que cada conjunto possível exista.

Na presença do esquema da compreensão sem restrições, o único axioma da indução de segunda ordem implica cada instância do regime de indução completa. Subsistemas que limitam a compreensão de alguma forma pode compensar essa limitação, incluindo parte do esquema de indução. Exemplos de tais sistemas são fornecidos abaixo.

Modelos da aritmética de segunda ordem Vamos lembrar que nós vemos a aritmética de segunda ordem como uma teoria no cálculo de predicados de primeira ordem. Assim um modelo da linguagem da aritmética de segunda ordem é constituído por um conjunto M (que forma o contradomínio de variáveis individuais), juntamente com uma constante 0 (um elemento de M), uma função S de M para M, duas operações binárias + e . em M, uma relação binária < em M, e uma coleção D de subconjuntos de M, que é o contradomínio das variáveis definidas. Ao omitir D obtemos um modelo da linguagem de primeira ordem aritmética. Quando D é o conjunto das partes de M, o modelo é chamado modelo pleno. O uso da semantica de segunda ordem completa é equivalente a limitar os modelos de aritmética de segunda ordem a modelos plenos. De fato, os axiomas da aritmética de segunda ordem têm apenas um único modelo pleno. Isto segue do fato de que axiomas da aritmética de Peano com o axioma de indução de segunda ordem têm um único modelo pela semântica de segunda ordem. Quando M é um conjunto usual de números naturais com operações usuais, M é chamado de um modelo ω. Neste caso podemos identificar o modelo com D, sua coleção de conjuntos naturais, porque este conjunto é suficiente para determinar completamente um modelo ω. O único modelo ω pleno que é o conjunto usual de números naturais com sua estrutura usual e todos seus subconjuntos é chamado o modelo pretendido ou modelo padrão da aritmética de segunda ordem.

Funções definíveis da aritmética de segunda ordem As funções de primeira ordem, que são totalmente comprovadas aritméticas de segunda ordem são precisamente as mesmas que foram representadas no sistema F (Girard et al., 1987, pp. 122–123). Quase de forma equivalente, sistema F é a teoria de funcionais correspondentes a aritmética de segunda ordem de uma forma paralela à forma como o sistema T de Gödel corresponde a aritmética de primeira ordem na interpretação Dialética.

Subsistemas da aritmética de segunda ordem Artigo principal : matemática reversa Há muitos subsistemas chamados de aritmética de segunda ordem.

Um índice 0 em nome de um subsistema indica que só inclui uma porção restrita do regime de indução de segunda ordem completa (Friedman, 1976). Essa restrição diminui a força da prova teórica do sistema de forma significativa. Por exemplo, o sistema descrito abaixo ACA0 é equivalente com a aritmética de Peano. A teoria correspondente ACA, consistindo de ACA0 mais o esquema completo da indução de segunda ordem, é mais forte do que a aritmética de Peano.

Compreensão artitmética

Muitos dos subsistemas bem estudados estão relacionados com as propriedades de fecho de modelos. Por exemplo, pode-se mostrar que cada ω-modelo da aritmética de segunda ordem completa é fechada sob salto de Turing, mas nem todo modelo ω fechada sob o salto de Turing é um modelo da aritmética de segunda ordem completa. Podemos perguntar se existe um subsistema da aritmética de segunda ordem satisfeito por cada modelo ω que é fechado sob o salto de Turing e que satisfaz algumas outras, mais leves, condições de fechamento. O subsistema que acabamos de descrever é chamado .

é definido como uma teoria que consiste nos axiomas básicos, o esquema do axioma da compreensão aritmética, em outras palavras, o axioma da compreensão para cada fórmula φ aritmética, e o axioma da indução de segunda ordem normal; novamente, nós também podemos optar por incluir o esquema do axioma da indução aritmética, em outras palavras, o axioma da indução para cada fórmula φ aritmética, sem fazer diferença.

Pode-se observar que uma coleção S de subconjuntos de ω determina um modelo de ω se e somente se S é fechado sob o salto de Turing, redutibilidade de Turing, e a inicialização de Turing.