Aritmética de Robinson

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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[editar | editar código-fonte]

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.


  1. Sx0
    • 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)
  6. x0 = 0
  7. xSy = (xy) + x

Axiomatizações Diferentes[editar | editar código-fonte]

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 < ySx = y)
  • x < Sy ↔ (x < yx = y).

Metamatemática[editar | editar código-fonte]

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 Sxx (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[editar | editar código-fonte]

Referências[editar | editar código-fonte]

  • 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 (3rd ed.), New York: Springer Science+Business Media, doi:10.1007/978-1-4419-1221-3, ISBN 978-1-4419-1220-6, http://www.springerlink.com/content/978-1-4419-1220-6/ .
  • 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.