Aritmética de segunda ordem
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.
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.
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
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 0 {\displaystyle \ 0} , chamado de "zero". As funções primitivas são a função unária sucessor, denotada pelo prefixo S {\displaystyle \ S} , e duas operações binárias, adição e multiplicação, denotadas pelos infixos "+" e " ⋅ {\displaystyle \cdot } ", respectivamente. Existe também uma relação binária chamada ordem, denotada pelo infixo "<".
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.
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 M {\displaystyle {\mathcal {M}}} 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 M {\displaystyle {\mathcal {M}}} é 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.
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.
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 A C A 0 {\displaystyle \mathrm {ACA} _{0}} . A C A 0 {\displaystyle \mathrm {ACA} _{0}} é 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.
A hierarquia aritmética para fórmulas
Para definir um segundo subsistema, vamos precisar de um pouco mais de terminologia. Uma fórmula é chamada de aritmética limitada, ou Δ00, quando todas os seus quantificadores são da forma ∀n<t ou ∃n<t (onde n é a variável individual a ser quantificada e t é um termo individual), onde Uma fórmula é chamada de Σ01 (ou, por vezes, Σ1), respectivamente Π01(ou, por vezes, Π1) quando a forma de ∃m•(φ), respectivamente ∀m•(φ onde φ é uma fórmula aritmética limitada e m é uma variável individual (que é livre em φ). De modo mais geral, uma fórmula é chamada Σ0n, respectivamente Π0n quando ele é obtido através da adição de existenciais, respectivamente, quantificadores universais individuais para um Π0n−1, respectivamente Σ0n−1 fórmula (e Σ00 e Π00 são todas equivalentes Δ00). Observe que, por construção todas essas fórmulas são aritmética (não variáveis de classe são sempre ligada) e, de fato, ao colocar a fórmula em forma prenex Skolem pode-se ver que cada fórmula aritmética é equivalente a uma fórmula Σ0n ou Π0n para todos suficientemente grande n .
Compreensão Recursiva
O subsistema R C A 0 {\displaystyle \mathrm {RCA} _{0}} é um sistema ainda mais fraca do A C A 0 {\displaystyle \mathrm {ACA} _{0}} que e é freqüentemente usado como o sistema básico em matemática reversa. É constituída por: os axiomas básicos, o esquema Σ01 indução, e o esquema de compreensão Δ01. O primeiro termo é claro: o esquema de indução Σ01 é o axioma de indução para cada Σ01 fórmula φ. O termo "compreensão Δ01" requer um pouco mais de explicação, no entanto: não há tal coisa como uma fórmula Δ01 (o significado pretendido é uma fórmula que seja Σ01 e Π01), mas em vez disso estão postulando o axioma de compreensão para cada Σ01 fórmula sujeita à condição de que é equivalente a uma fórmula Π01, em outras palavras, para cada Σ01 fórmula φ e cada Π01 fórmula ψ que postulamos.
Sistemas mais fracos
Às vezes, um sistema ainda mais fraca do que R C A 0 {\displaystyle \mathrm {RCA} _{0}} é desejado. Um tal sistema é definida como se segue: um primeiro deve aumentar o idioma de aritmética com uma função exponencial (em sistemas mais fortes o exponencial pode ser definida em termos de adição e multiplicação pelo truque habitual, mas quando o sistema torna-se muito fraca isto não é mais possível) e os axiomas básicos por parte dos axiomas evidentes definem exponenciação indutivamente da multiplicação; em seguida, o sistema é composto pelos (enriquecidos) axiomas básicos, além de Δ01 compreensão mais indução de Δ00.
Sistemas mais fortes
Por mais que nós definimos Σn e Πn (ou, mais precisamente, Σ0n e Π0n) fórmulas, podemos definir fórmulas Σ1n e Π1n da seguinte maneira: a fórmula Δ10 (ou Σ10 ou Π10) é apenas uma fórmula aritmética e a fórmula Σ1n , respectivamente Π1n, é obtida pela adição de, respectivamente existenciais universais, quantificadores de classe em frente de um Π1n−1, respectivamente Σ1n−1. Não é muito difícil ver que mais de um sistema não muito fraco, qualquer fórmula aritmética de segunda ordem é equivalente a uma fórmula Σ1n or Π1n para todo n suficientemente grande. O sistema Π11-compreensão é o sistema que consiste nos axiomas básicos, além da indução axioma segunda ordem ordinário e o axioma compreensão para cada Π11 fórmula φ. É um exercício fácil mostrar que isso é realmente equivalente a Σ11-compreensão (por outro lado, Δ11-compreensão, definida pelo mesmo truque como apresentado anteriormente para Δ01-compreensão, é realmente mais fraca).
Determinância Projetiva é a afirmação de que todo jogo perfeito de informações entre dois jogadores, com movimentos sendo inteiros, tamanho de jogo ω e um conjunto de payoffs projetivos é determinado, ou seja, um dos jogadores tem uma estratégia vencedora. (O primeiro jogador ganha o jogo se a jogada pertence ao conjunto de payoffs; de outra forma, o segundo jogador ganha). Um conjunto é projetivo se e somente se (como um predicado) ele é expressível por uma fórmula na linguagem da aritmética de segunda ordem, permitindo números reais como parâmetros, assim a determinância projetiva é expressível como um esquema na linguagem de Z2 Muitar proposições naturais expressíveis na linguagem da aritmética de segunda ordem são independentes de Z2 e ainda ZFC, mas podem ser provadas pela determinância projetiva. Exemplos incluem a coanalítica propriedade do conjunto perfeito, mensurabilidade e a Teorema da categoria de Baire para os conjuntos Σ 2 1 {\displaystyle \Sigma _{2}^{1}} , uniformização Π 3 1 {\displaystyle \Pi _{3}^{1}} , etc. Sobre uma fraca base teórica (assim como RCA0), determinância projetiva implica compreensão e provê uma teoria completa da aritmética de segunda ordem — Sentenças naturais na linguagem de Z2 que são independentes de Z2 com determinância projetiva são difíceis de encontrar.
A aritmética de segunda ordem nos permite falar diretamente (sem codificar) de números naturais e conjuntos de números naturais. Pares de números naturais podem ser codificados da maneira usual como números naturais, então inteiros arbitrários ou números racionais são os habitantes de primeira-classe da mesma forma que números naturais. Funções entre esses conjuntos podem ser codificadas como conjuntos de pares, e portanto, como subconjuntos dos números naturais, sem dificuldade. Números reais podem ser definidos como sequências de cauchy de números racionais, mas por razões técnicas não discutidas aqui, é preferível (no axioma fraco de sistemas acima) constranger a taxa de convergência (ou seja, dizer que a distância entre o n-ésimo e (n+1)-ésimo termo seja menor que 2−n). Esses sistemas não podem se referir à funções reais, ou subconjuntos dos reais. Não obstante, funções contínuas reais são legítimos objetos de estudo, desde que elas são definidas pelos seus valores nos racionais. Além disso, um truque relacionado faz isso se possível se referir à subconjuntos abertos dos reais. Mesmo o Conjunto de Borel dos reais podem ser codificados na linguagem da aritmética de segunda ordem, embora seja um pouco complicado fazê-lo.
