Saltar para o conteúdo

Axiomas de Peano

Origem: Wikipédia, a enciclopédia livre.

Em lógica matemática, os axiomas de Peano, também conhecidos como os axiomas de Dedekind-Peano ou postulados de Peano, são um conjunto de axiomas para os números naturais apresentado pelo matemático italiano do século XIX Giuseppe Peano. Esses axiomas vêm sendo utilizados praticamente sem modificações em diversas investigações metamatemáticas, incluindo pesquisas em questões fundamentais de consistência e completude da teoria dos números.

A necessidade do formalismo na Aritmética não era apreciada até o trabalho de Hermann Grassmann, que mostrou na década de 1860 que muitos fatos da aritmética poderiam ser derivados de fatos mais básicos sobre operação de sucessor e indução.[1] Em 1881, Charles Sanders Peirce mostrou uma forma de axiomatização da aritmética de números naturais.[2] Em 1888, Richard Dedekind propôs uma coleção de axiomas sobre os números, e em 1889 Peano publicou uma versão mais precisamente formulada das anteriores, em uma coleção de axiomas no seu livro, "Os princípios da Aritmética apresentados por um novo método" (Em Latim: Arithmetices principia, nova methodo exposita).

Os axiomas de Peano contêm três tipos de declarações. O primeiro axioma afirma a existência de pelo menos um membro no conjunto "números". As quatro seguintes são afirmações gerais a respeito de igualdade; em tratamentos modernos, estes geralmente não são tomados como parte dos axiomas de Peano, mas sim como axiomas da "lógica subjacente".[3] Os próximos três axiomas são declarações da Lógica de primeira ordem sobre números naturais expressando as propriedades fundamentais da operação de sucessor. O nono e último axioma, é uma declaração da lógica de segunda ordem do princípio da indução matemática sobre os números naturais. Um sistema de primeira ordem mais "fraco" chamado aritmética de Peano é obtido ao adicionar os símbolos de adição e multiplicação e substituir o axioma de indução em segunda ordem por um esquema axiomático de primeira ordem.

Quando Peano formulou seus axiomas, a linguagem de lógica matemática ainda era nova. O sistema de notação lógica por ele criado para a apresentação de seus axiomas não se mostrou popular, apesar de ser a gênese da notação moderna de pertinência (∈, derivado do ε utilizado por Peano) e implicação (⊃, derivado do 'C' invertido de Peano). Peano manteve uma distinção clara entre a simbologia lógica e a matemática, o que não era ainda comum na matemática; tal separação foi introduzida pela primeira vez no Begriffsschrift, de Gottlob Frege, publicado em 1879. Peano desconhecia o trabalho de Frege e independentemente recriara suas técnicas lógicas se baseando nos trabalhos de Boole e Schröder.

Os axiomas de Peano definem as propriedades aritméticas de números naturais, geralmente representadas como o conjunto N ou A assinatura (os símbolos não-lógicos de uma linguagem formal) para os axiomas incluem o símbolo de constante 0 e o símbolo de função unária S.

A constante 0 é considerada um número natural:

  1. 0 é um número natural.

Os 4 próximos axiomas descrevem a relação de igualdade.

  1. Para todo natural x, x = x. Isto é, a igualdade é reflexiva.
  2. Para todos os números naturais x e y, se x = y, então y = x. Isto é, a igualdade é simétrica.
  3. Para todos os números naturais x, y, e z, se x = y e y = z, então x = z. Ou seja, a igualdade é transitiva.
  4. Para todos a e b, se a for um número natural e a = b, então b também é um número natural. Isto é, os números naturais são fechados em sua igualdade.

Os axiomas restantes definem as propriedades aritméticas dos números naturais. Os naturais são fechados sob a função unária de sucessor S.

  1. Para todo número natural n, S(n) é um número natural.

As formulações originais dos axiomas de Peano utilizavam o 1 como "primeiro" número natural, ao invés do 0. A escolha é arbitrária, uma vez que o primeiro axioma não concede à constante 0 nenhuma propriedade adicional. No entanto, como 0 é o elemento neutro, a maioria das interpretações modernas dos axiomas de Peano se inicia no 0. Os axiomas 1 e 6 definem uma representação unária dos números naturais: o número 1 pode ser definido como S(0), 2 como S(S(0)) (que também é S(1)) e, no geral, qualquer número natural n como Sn(0). Os dois próximos axiomas definem as propriedades dessa representação.

  1. Para todo número natural n, S(n) = 0 é falso. Isto é, não há nenhum número natural cujo sucessor seja 0.
  2. Para todos os números naturais m e n, se S(m) = S(n), então m = n. Ou seja, S é uma função injetora.

Os axiomas 1, 6 e 7 implicam que o conjunto de números naturais contém os elementos distintos 0, S(0), S(S(0)), e assim por diante; em outras palavras, é informalmente conhecido o fato de que {0, S(0), S(S(0)), …} ⊆ N, de modo que qualquer elemento buscado está contido em N. (Também se sabe que o conjunto dos naturais é infinito, porque contém um subconjunto infinito.) Para mostrar que N = {0, S(0), S(S(0)), …}, deve ser mostrado que N ⊆ {0, S(0), S(S(0)), ...}; ou seja, é necessário ser mostrado que todo número natural está incluso em {0, S(0), S(S(0)), ...}, de modo que o conjunto de números naturais não possua nenhum elemento "indesejado" (por exemplo o decimal 1.7). Para que isso seja feito, no entanto, é necessário mais um axioma, também chamado de axioma da indução. Este axioma gera um método para a racionalização do conjunto de todos os números naturais.

  1. Se K é um conjunto tal que:
    • 0 pertence a K, e
    • para todo natural n, se n pertence a K, então S(n) pertence a K,
    então K contém todos os números naturais.

O axioma da indução é, às vezes, proposto da seguinte maneira:

  1. Se φ é um predicado unário tal que:
    • φ(0) é verdade, e
    • para todo número natural n, se φ(n) é verdadeiro, então φ(S(n)) também o é,
    então φ(n) é verdadeiro para todo número natural n.

Na concepção original de Peano, o axioma da indução é um axioma de segunda-ordem. Atualmente, é comum substituir esse princípio de segunda-ordem por um esquema de indução de primeira-ordem mais fraco. Há importantes diferenças entre formulações de primeira-ordem e segunda-ordem, como discutido nos modelos abaixo. Sem o axioma da indução, os axiomas restantes de Peano geram uma teoria de uma função unária injetora mas não sobrejetora, que pode ser expressa sem lógica de segunda-ordem.

Os axiomas de Peano podem ser expandidos com as operações de soma e multiplicação e a relação de ordem em N. As respectivas funções e relações são construídas em lógica de segunda-ordem, e são únicas ao se usar os axiomas de Peano.

Adição é a função + : N × N → N, definida recursivamente como: Por exemplo,

a + 1 = a + S(0) = S(a + 0) = S(a).

A estrutura (N, +) é um semigrupo comutativo (a ordem das operações não influi no resultado final) com elemento identidade 0. (N, +) é também sujeito à cancelamento (a + x = x + y implica que a = y, depois do cancelamento de x), e pode, por isso, ser contido em um grupo. O menor grupo que contém N é o dos inteiros.

Multiplicação

[editar | editar código-fonte]

Dada a adição, multiplicação é a função definida recursivamente como: É fácil observar que a atribuição do valor 0 a b carrega em si a identidade multiplicativa:

a · 1 = a · S(0) = a + (a · 0) = a + 0 = a

Além disso, multiplicação pode ser distribuída sobre a adição:

a · (b + c) = (a · b) + (a · c).

Assim, (N, +, 0, ·, 1) é um semi-anel.

Desigualdades

[editar | editar código-fonte]

A relação de ordem total ≤ : N × N pode ser definida deste modo, assumindo que 0 é um número natural: Para todo a, b ∈ N, ab se e somente se existe algum c ∈ N de modo que a + c = b. Essa relação se mantém constante sob adição e multiplicação: para a, b, c ∈ N, se ab, então:

  • a + cb + c, e
  • a · cb · c.

Desse modo, a estrutura (N, +, ·, 1, 0, ≤) é um semi-anel ordenado; como não há número natural entre 0 e 1, é um semi-anel discretamente ordenado. O axioma da indução pode ser proposto da seguinte maneira, mais robusta, fazendo uso da ordem ≤: Para qualquer predicado φ, se φ(0) é verdadeiro, e para todo n, k ∈ N, se k ≤ n implica que φ(k) é verdadeiro, então φ(S(n)) é verdade, então para todo n ∈ N, φ(n) é verdadeiro. Este formato do axioma da indução é uma consequência simples da formulação padrão, mas é frequentemente mais adequada para a representação sobre a ordem ≤. Por exemplo, para mostrar que os naturais são bem-ordenados - todo subconjunto não-vazio de N possui um elemento menor - pode-se usar o seguinte argumento. Deixe que um não-vazio X ⊆ N seja dado e assuma que X não possui menor elemento. Como 0 é o menor elemento de N, então temos que O ∉ X. Para qualquer n ∈ N, assuma que para todo k ≤ n, k ∉ X. Então S(n) ∉ X, senão o mesmo seria o menor elemento de X. Desse modo, pelo forte princípio da indução, para todo n ∈ N, n ∉ X. Assim, X ∩ N = ∅, o que contradiz a noção de X ser um subconjunto não-vazio de N. Seguindo a argumentação, X possui um menor elemento.

Um modelo dos axiomas de Peano é triplo (N, 0, S), onde N é um conjunto infinito, 0 ∈ N e S : N → N satisfazem os axiomas acima. Dedekind provou, em seu livro de 1888, Was sind und was sollen die Zahlen ("O que são e o que deveriam ser os números"), que quaisquer dois modelos dos axiomas de Peano (incluindo o axioma da indução de segunda-ordem) são isomórficos. Em particular, dados os dois modelos (NA, 0A, SA) e (NB, 0B, SB), há um homomorfismo único f : NA → NB que satisfaz e é uma bijeção. Os axiomas de segunda-ordem de Peano são então categóricos; este não é o caso com qualquer reformulação dos axiomas de Peano em primeira-ordem, no entanto.

Teoria da aritmética de primeira-ordem

[editar | editar código-fonte]

Teorias de primeira-ordem são comumente melhores que os de segunda-ordem para a análise teorética de provas e modelos. Todos os axiomas de Peano, exceto o nono (o axioma de indução) são afirmações em lógica de primeira-ordem. As operações aritméticas de adição e multiplicação e a relação de ordem também podem ser definidas usando axiomas de primeira-ordem. O axioma da indução de segunda-ordem pode ser transformado em um esquema indutivo de primeira-ordem mais fraco.

Axiomatizações de primeira-ordem da aritmética de Peano possuem uma limitação importante, no entanto. Em lógica de segunda-ordem, é possível definir as operações de adição e multiplicação a partir da operação sucessor, mas isso não pode ser realizado na forma menos abrangente da lógica de primeira-ordem. Consequentemente, as operações de adição e multiplicação são diretamente inclusas na assinatura da aritmética de Peano, e os axiomas que relacionam estas operações umas às outras também estão inclusos.

A lista a seguir de axiomas (junto com os axiomas de igualdade) é suficiente para este propósito:

Em adição à esta lista de axiomas numéricos, a aritmética de Peano contém o esquema de indução, que consiste em um conjunto de axiomas contavelmente infinito. Para cada fórmula φ(x,y1,...,yk) na linguagem de aritmética de Peano, o axioma da indução de primeira-ordem para φ é a sentença onde é uma abreviação de y1,...,yk. O esquema de indução de primeira-ordem inclui todos os casos do axioma de indução de primeira-ordem, isto é, inclui o axioma de indução para toda fórmula φ.

Este esquema evita quantificação sobre conjuntos de números naturais, o que é impossível em lógica de primeira-ordem. Por exemplo, não é possível se dizer, em lógica de primeira-ordem, que qualquer conjunto de números naturais contendo 0 e fechado sob o sucessor é o conjunto inteiro dos naturais. O que pode ser expresso é que qualquer conjunto definível de números naturais possui esta propriedade. Como não é possível quantificar sobre subconjuntos definíveis explicitamente com apenas um axioma, o esquema de indução inclui um caso do axioma de indução para cada definição de um subconjunto dos naturais.

Axiomatizações equivalentes

[editar | editar código-fonte]

Há muitas axiomatizações diferentes, mas equivalentes, da aritmética de Peano. Enquanto algumas axiomatizações, como a que foi descrita há pouco, usam uma assinatura que possui somente símbolos para 0 e as operações de sucessor, adição e multiplicação, outras axiomatizações utilizam a linguagem de semi-anéis ordenados, incluindo um símbolo adicional de relação de ordem. Uma dessas axiomatizações começa com os axiomas a seguir, que descrevem uma ordenação discreta de semi-anéis.

  1. ou seja, a adição é associativa.
  2. ou seja, a adição é comutativa.
  3. ou seja, a multiplicação é associativa.
  4. ou seja, multiplicação é comutativa.
  5. ou seja, a distributividade.
  6. ou seja, zero é o elemento identidade da adição.
  7. ou seja, um é o elemento identidade da multiplicação.
  8. ou seja, o operador '<' é transitivo.
  9. ou seja, o operador '<' é irreflexivo.

A teoria definida por estes axiomas é conhecida como PA–; PA é obtida ao se adicionar o esquema de indução de primeira-ordem.

Uma importante propriedade de PA- é que qualquer estrutura M que satisfaça esta teoria possui um segmento inicial (ordenado por ≤) isomórfico a N. Elementos de M\N são conhecidos como elementos não-padrão.

Modelos não-padrão

[editar | editar código-fonte]

Apesar dos números naturais satisfazerem os axiomas da aritmética de Peano (PA), há outros modelos não-padrão, também; o teorema da compacidade diz que a existência de elementos não-padrão não pode ser excluída na lógica de primeira-ordem. O teorema de Löwenheim–Skolem mostra que existem modelos não-padrão de PA em todas as infinitas cardinalidades. Esse não é o caso dos axiomas originais (segunda-ordem) de Peano, que só possuem um modelo, até o isomorfismo. Isso ilustra um modo no qual o sistema de PA de primeira-ordem é inferior aos axiomas de Peano de segunda-ordem.

Quando interpretada como prova dentro de uma teoria de conjuntos de primeira-ordem, como a teoria dos conjuntos de Zermelo–Fraenkel (ZFC), a prova de categoricidade de Dedekind para PA mostra que cada modelo de uma teoria de conjuntos possui um modelo único dos axiomas de Peano, até o isomorfismo, que é incluído como segmento inicial de todos os outros modelos de PA contidos dentro daquele modelo de teoria de conjuntos. No modelo padrão de teoria dos conjuntos, o menor modelo de PA é o modelo padrão de PA; no entanto, em um modelo não-padrão, essa posição pode ser ocupada por um modelo não-padrão. Essa situação não pode ser evitada com qualquer formalização de primeira-ordem de teoria de conjuntos.

É natural perguntar se um modelo padrão contável pode ser construído explicitamente. O teorema de Tennenbaum, provado em 1959, mostra que não há modelos não-padrão contáveis de PA no qual tanto a multiplicação quanto a adição sejam computáveis. Esse resultado mostra a dificuldade de se ser completamente explícito na descrição das operações de adição e multiplicação de um modelo não-padrão contável de PA. Apesar disso, há somente um tipo de ordem possível de modelo não-padrão contável. Deixando ω ser o tipo de ordem dos números naturais, ζ ser o tipo de ordem dos inteiros, e η ser o tipo de ordem dos racionais, o tipo de ordenação de qualquer modelo não-padrão contável de PA é ω + ζ·η, que pode ser visualizado como cópia dos números naturais seguido de uma ordenação linear e densa de cópias dos inteiros.

Modelos de conjunto teóricos

[editar | editar código-fonte]

Os axiomas de Peano podem ser derivados de construções conjunto-teóricas de números naturais e axiomas de teoria dos conjuntos como a de Zermelo-Fraenkel. A construção padrão dos naturais, devido a John von Neumann, começa com a definição de 0 como conjunto vazio, ∅, e um operador s nos conjuntos definido como:

s(a) = a ∪ { a }.

O conjunto dos números naturais N é definido com a intersecção de todos os conjuntos fechados sob s que contém o conjunto vazio. Cada número natural é igual (como conjunto) ao conjunto de números naturais menor que ele: e assim em diante. O conjunto N, junto com 0 e a função sucessor s : N → N satisfaz os axiomas de Peano.

A aritmética de Peano é equiconsistente com vários sistemas fracos de teoria dos conjuntos. Um desses sistemas é o ZFC com o axioma da infinidade substituído por sua negação. Outro desses sistemas consiste na teoria geral dos conjuntos (extensionalidade, a existência do conjunto vazio, e o axioma da adjunção), expandido por um esquema de axioma que diz que a propriedade que é válida para o conjunto vazio, e que mantém a validade quando uma adjunção é válida para um adjunto tem que se manter válida para todos os conjuntos.

Interpretação em teoria das categorias

[editar | editar código-fonte]

Os axiomas de Peano também podem ser entendidos usando a teoria das categorias. Deixe C ser uma categoria com objeto inicial 1C, e defina a categoria de sistemas unários direcionados, US1(C) como o seguinte: Os objetos de US1(C) são triplos (X, 0X, SX), onde X é um objeto de C, e 0X : 1C → X e SX : X → X são C-morfismos. Um morfismo φ : (X, 0X, SX) → (Y, 0Y, SY) é um C-morfismo φ : X → Y com φ 0X = 0Y e φ SX = SY φ.

Então C satisfaz os axiomas de Dedekind-Peano se US1(C) possui um objeto inicial, este objeto é conhecido como número objeto natural em C. Se (N, 0, S) é esse objeto inicial, e (X, 0X, SX) é qualquer outro objeto, então mapa único u : (N, 0, S) → (X, 0X, SX) é tal que Esta é, precisamente, a definição recursiva de 0X e SX.

Consistência

[editar | editar código-fonte]
Ver artigo principal: Segundo problema de Hilbert

Quando os axiomas de Peano foram propostos pela primeira vez, Bertrand Russel e outros concordaram que esses axiomas definiram implicitamente o que significa um "número natural". Henri Poincaré foi mais cauteloso, dizendo que os números naturais só poderiam ser definidos caso fossem consistentes; se existe uma prova que começa desses axiomas e chega numa contradição como por exemplo 0 = 1, então os axiomas são inconsistentes, e não definem nada. Em 1900, David Hilbert pôs o problema de provar sua consistência usando somente métodos finitários como o segundo dos seus vinte e três problemas. Em 1932, Kurt Gödel provou seu segundo teorema da incompletude, o qual mostra como uma prova de consistência não pode ser formalizada utilizando apenas a aritmética de Peano.

Embora seja sabiamente afirmado que o teorema de Gödel exclui a possibilidade de uma prova de consistência finitária para a aritmética de Peano, isto depende do que exatamente ele quer dizer com "prova finitária". Gödel apontou a possibilidade de dar uma prova de consistência finitária da aritmética de Peano ou de sistemas mais fortes utilizando métodos finitários não formalizáveis na aritmética de Peano, e em 1958 Gödel publicou um método para provar a consistência da aritmética usando a Teoria dos Tipos. Em 1936, Gerhard Gentzen provou a consistência dos axiomas de Peano, usando indução transfinita até um ordinal chamado ε₀. Gentzen explicou: "O objetivo do presente trabalho é provar a consistência da teoria elementar dos números, ou melhor, reduzir a questão da consistência a certos princípios fundamentais". A prova de Gentzen é sem dúvidas finitária, desde que o ordinal transfinito ε₀ possa ser codificado em termos de objetos finitos (por exemplo, como uma máquina de Turing descrevendo uma ordem adequada sobre os números inteiros, ou mais abstratamente como consistindo das árvores finitas, adequadamente linearmente ordenadas). Se a prova de Gentzen atende aos requisitos que Hilbert imaginou não está claro: Não há definição geral aceita do que exatamente se entende por uma prova finitária, e Hilbert nunca deu uma definição precisa.

A vasta maioria dos matemáticos contemporâneos acredita que os axiomas de Peano são consistentes, confiando ou na intuição ou na aceitação de uma prova de consistência tal como a de Gentzen. Os poucos matemáticos que defendem o ultrafinitismo rejeitam os axiomas de Peano, pois os axiomas requerem um conjunto infinito de números naturais.

  • Martin Davis, 1974. Computability. Notes by Barry Jacobs. Courant Institute of Mathematical Sciences, New York University.
  • Richard Dedekind, 1888. Was sind und was sollen die Zahlen? (What are and what should the numbers be?). Braunschweig. Two English translations:
    • 1963 (1901). Essays on the Theory of Numbers. Beman, W. W., ed. and trans. Dover.
    • 1996. In From Kant to Hilbert: A Source Book in the Foundations of Mathematics, 2 vols, Ewald, William B., ed. Oxford University Press: 787–832.
  • Gentzen, G., 1936, Die Widerspruchsfreiheit der reinen Zahlentheorie. Mathematische Annalen 112: 132–213. Reprinted in English translation in his 1969 Collected works, M. E. Szabo, ed. Amsterdam: North-Holland.
  • K. Gödel,1931, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I. Monatshefte für Mathematik und Physik 38: 173–98. See On Formally Undecidable Propositions of Principia Mathematica and Related Systems for details on English translations.
  • --------, 1958, "Über eine bisher noch nicht benüzte Erweiterung des finiten Standpunktes," Dialectica 12: 280–87. Reprinted in English translation in 1990. Gödel's Collected Works, Vol II. Solomon Feferman et al., eds. Oxford University Press.
  • Hermann Grassmann, 1861. Lehrbuch der Arithmetik (A tutorial in arithmetic). Berlin.
  • Hatcher, William S., 1982. The Logical Foundations of Mathematics. Pergamon. Derives the Peano axioms (called S) from several axiomatic set theories and from category theory.
  • David Hilbert,1901, "Mathematische Probleme". Archiv der Mathematik und Physik 3(1): 44–63, 213–37. English translation by Maby Winton, 1902, "Mathematical Problems," Bulletin of the American Mathematical Society 8: 437–79.
  • Kaye, Richard, 1991. Models of Peano arithmetic. Oxford University Press. ISBN 0-19-853213-X.
  • Peirce, C. S. (1881). «On the Logic of Number». American Journal of Mathematics. 4 (1–4). pp. 85–95. JSTOR 2369151. MR 1507856. doi:10.2307/2369151  Reprinted (CP 3.252-88), (W 4:299-309).
  • Paul Shields. (1997), "Peirce’s Axiomatization of Arithmetic", in Houser et al., eds., Studies in the Logic of Charles S. Peirce.
  • Patrick Suppes, 1972 (1960). Axiomatic Set Theory. Dover. ISBN 0-486-61630-4. Derives the Peano axioms from ZFC.
  • Alfred Tarski, and Givant, Steven, 1987. A Formalization of Set Theory without Variables. AMS Colloquium Publications, vol. 41.
  • Edmund Landau, 1965 Grundlagen Der Analysis. AMS Chelsea Publishing. Derives the basic number systems from the Peano axioms. English/German vocabulary included. ISBN 978-0-8284-0141-8
  • Jean van Heijenoort, ed. (1976) [1967]. From Frege to Godel: A Source Book in Mathematical Logic, 1879–1931 3rd ed. Cambridge, Mass: Harvard University Press. ISBN 9780674324497  Contains translations of the following two papers, with valuable commentary:
    • Richard Dedekind, 1890, "Letter to Keferstein." pp. 98–103. On p. 100, he restates and defends his axioms of 1888.
    • Giuseppe Peano, 1889. Arithmetices principia, nova methodo exposita (The principles of arithmetic, presented by a new method), pp. 83–97. An excerpt of the treatise where Peano first presented his axioms, and recursively defined arithmetical operations.

Ligações externas

[editar | editar código-fonte]

Este artigo incorpora material de PA do PlanetMath, que é licenciado sob GFDL.