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.
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: 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.
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:
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).
