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.

1. Sx ≠ 0
   • 0 não é o sucessor de nenhum numero.
2. (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.
3. 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.
4. x + 0 = x
5. x + Sy = S(x + y)
   • (4) e (5) são a definição recursiva da adição.
6. x0 = 0
7. 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).

Ver também

• Teoria dos conjuntos
• Teoremas da incompletude de Gödel
• Lista de teorias de primeira ordem
• Axiomas de Peano

Referências

• A. Bezboruah and John C. Shepherdson, 1976. Gödel’s Second Incompleteness Theorem for Q. Journal of Symbolic Logic v. 41 n. 2, pp. 503–512.
• George Boolos, John P. Burgess, and Richard Jeffrey, 2002. Computability and Logic, 4th ed. Cambridge University Press.
• Burgess, John P., 2005. Fixing Frege. Princeton University Press.
• Petr Hájek e Pavel Pudlák (1998) [1993]. Metamathematics of first-order arithmetic, 2nd ed. Springer-Verlag.
• Lucas, J. R., 1999. Conceptual Roots of Mathematics. Routledge.
• Machover, Moshe, 1996. Set Theory, Logic, and Their Limitation. Cambridge University Press.
• Mendelson, Elliott, 1997. Introduction to Mathematical Logic, 4th ed. Chapman & Hall.
• Pavel Pudlák, 1985. "Cuts, consistency statements and interpretations". Journal of Symbolic Logic v. 50 n. 2, pp. 423–441.
• W. Rautenberg (2010), A Concise Introduction to Mathematical Logic, ISBN 978-1-4419-1220-6 3rd ed. , New York: Springer Science+Business Media, doi:10.1007/978-1-4419-1221-3 .
• R. M. Robinson, 1950, "An Essentially Undecidable Axiom System" em Proceedings of the International Congress of Mathematics 1950, pp. 729–730.
• Raymond Smullyan, 1991. Gödel's Incompleteness Theorems. Oxford University Press.
• Alfred Tarski, A. Mostowski, and R. M. Robinson, 1953. Undecidable theories. North Holland.