# Aritmética de Robinson

Na matemática, a Aritmética de Robinson, ou Q, é um fragmento finitamente axiomatizado da Aritmética de Peano (AP), estabelecida pela primeira vez por Raphael Mitchel Robinson (1950). Q é essencialmente a AP sem os esquemas dos Axiomas da indução. Como Q é mais fraco que AP mas possui a mesma linguagem, ele também é incompleto. Q é importante e interessante por que é um fragmento finitamente axiomatizado da AP que é recursivamente incompletável e essencialmente indecidivel.

## Axiomas

A lógica de fundo de Q é de primeira ordem com identidade, denotada pelo infixo '='. Os individuais, chamados de números naturais, são membros de um conjunto chamado N com um destaque de 0, chamado zero. Existe três operações sobre N:
* Uma operação unária chamada sucessor e denotada pelo prefixo S;
* Duas operações binarias, adição e multiplicação, denotadas pelo infixo + e a pela concatenação, respectivamente.
O seguinte axioma para Q são Q1-Q7 de Burgess (2005: 56), e também são os primeiros sete axiomas de aritmetica de segunda ordem. Variáveis não são restritas por qualificador existencial são restritas por um qualificador universal implícito.
* Sx ≠ 0
** 0 não é o sucessor de nenhum numero.
* (Sx = Sy) → x = y
** Se o successor de x é igual ao successor de y, então x e y são iguais. (1) e (2) fornecem o mínimo de fatos sobre N (N é um conjunto infinito restrito por 0) e S (S é uma função injetora cujo domínio é N) é necessário para a não-trivialidade. A reciprocidade de (2) segue as propriedades da função identidade.
* y=0 ∨ ∃x (Sx = y)
** Todo numero ou é 0 ou é o sucessor de algum numero. O esquema dos Axiomas da indução presente na aritmética mais forte que Q torna o axioma em um teorema.
* x + 0 = x
* x + Sy = S(x + y)
** (4) e (5) são a definição recursiva da adição.
* x0 = 0
* xSy = (xy) + x
** (6) e (7) são a definição recursiva da multiplicação.

### Axiomatizações Diferentes

Os Axiomas de Robinson (1950) são (1)-(13) de Mendelson (1997: 201). Os primeiros 6 dos 13 axiomas de Robinson são necessários quando, ao contrario desses, a lógica de fundo não inclui a identidade. Machover (1996:256-57) não necessita do axioma (3).
A normalmente estrita ordem total em N, "menor que" (denotado por "<"), pode ser definido em termos da adição através da regra x < y ↔ ∃z (x + Sz = y) (Burgess 2005:230, fn. 24).
Levando "<" como primitiva requer a adição de quatro axiomas (1)-(7) acima:
* ¬(x < 0)
* 0 = x ∨ 0 < x
* x < y ↔ (Sx < y ∨ Sx = y)
* x < Sy ↔ (x < y ∨ x = y).

## Metamatemática

Sobre a Metamatematica de Q, veja Boolos et al. (2002: Capt. 14), Tarski, Mostowski, e Robinson (1953), Smullyan (1991), Mendelson (1997:201–03), e Burgess (2005:§§1.5a, 2.2). A Interpretação pretendida de Q são os números naturais e sua aritmética. Por isso adição e multiplicação possuindo seu significado habitual, identidade é igualdade, Sx = x + 1, e 0 é o numero natural zero.
Q, como nos Axiomas de Peano, tem modelo não-padrão de todos infinitos cardinais. Entretanto, diferente da Aritmética de Peano, o Teorema de Tennenbaum não se aplica à Q, e ele tem modelos não-padrão computáveis. Por exemplo, existe um modelo computável Q constituído por polinômios inteiros-coeficientes com os coeficientes principais positivos, mais o zero polinomial, com sua aritmética habitual.
A característica definidora de Q é a falta dos esquemas axiomáticos da indução. Por isso é possível prover em Q todas as instancias de um fato sobre números naturais, mas não o teorema geral associado. Por exemplo, 5 + 7 = 7 + 5 é provável em Q, mas a sentença x + y = y + x não é. Similarmente, não se pode provar que Sx ≠ x (Burgess 2005:56).
Q é interpretável em um fragmento da Teoria axiomática dos conjuntos de Zermelo, consistindo da extensionalidade, a existência de conjunto vazio, e o axioma da adjunção. Essa teoria é S' em Tarski et al. (1953:34) e ST em Burgess (2005: 90–91; 223). Leia sobre a Teoria Geral dos Conjuntos para mais informações.
Q fascina pois é uma teoria de primeira ordem finitamente axiomatizada que é consideravelmente mais fraca que a aritmética de Peano, e cujo axiomas contem só um quantificador existencial, mas como a aritmética de Peano é incompleta e incompletavel no sentido da Teoria da Incompletude de Peano, e essencialmente indecifrável. Robinson (1950) derivou os axiomas (1)-(7) de Q acima através de observações sobre o que os axiomas da aritmética de Peano precisam para provar que todas as funções computáveis são representáveis na aritmética de Peano. O único uso que essa prova faz do esquema axiomatizado da aritmética de Peano é a prova da sentença que é o axioma (3) acima, e então, todas as funções computáveis são representáveis em Q (Mendelson 1997: Th. 3.33, Rautenberg 2010: 246). A conclusão do segundo teorema da incompletude de Gödel também suporta Q: Nenhuma extensão de Q consistente e recursivamente axiomatizada pode provar a sua própria consistência, mesmo se nós adicionalmente restringirmos os números de provas de Gödel para uma parte definível.(Bezboruah e Shepherdson 1976; Pudlák 1985; Hájek & Pudlák 1993:387).
O primeiro teorema da incompletude se aplica somente para sistemas axiomáticos definindo aritmética suficiente para cumprir as construções de codificação necessárias (das quais números de Gödel fazem parte). O axioma de Q foram especificamente escolhidos para garantir que eles são fortes o bastante para esse proposito. Assim, a prova habitual do primeiro teorema da incompletude pode ser usado para mostrar que Q é incompleto e indecidivel. Isso indica que a incompletude e a indecibilidade da Aritmética de Peano não podem ser associado com o único aspecto que diferencia AP de Q, como o esquema axiomatizado da indução;
Os Teoremas de Gödel não se mantem se qualquer um dos axiomas acima são removido. Esses fragmentos de Q se mentem indecidivez, mas eles não são mais essencialmente indecidiveis: eles possuem extensões consistentes decidiveis, como também modelos não interessantes (isso é, modelos que não são extensões dos números naturais).