Axiomas de Peano - Peano axioms

Na lógica matemática , os axiomas de Peano , também conhecidos como axiomas de Dedekind – Peano ou postulados de Peano , são axiomas para os números naturais apresentados pelo matemático italiano do século 19, Giuseppe Peano . Esses axiomas têm sido usados ​​quase inalterados em várias investigações metamatemáticas , incluindo pesquisas sobre questões fundamentais para saber se a teoria dos números é consistente e completa .

A necessidade de formalizar a aritmética não foi bem avaliada até o trabalho de Hermann Grassmann , que mostrou na década de 1860 que muitos fatos na aritmética podiam ser derivados de fatos mais básicos sobre a operação e indução do sucessor . Em 1881, Charles Sanders Peirce forneceu uma axiomatização da aritmética dos números naturais. Em 1888, Richard Dedekind propôs outra axiomatização da aritmética de números naturais e, em 1889, Peano publicou uma versão simplificada deles como uma coleção de axiomas em seu livro, Os princípios da aritmética apresentados por um novo método ( latim :Arithmetices principia, nova methodo exposita ).

Os nove axiomas de Peano contêm três tipos de afirmações. O primeiro axioma afirma a existência de pelo menos um membro do conjunto de números naturais. Os próximos quatro são declarações gerais sobre igualdade ; nos tratamentos modernos, muitas vezes não são considerados como parte dos axiomas de Peano, mas sim como axiomas da "lógica subjacente". Os próximos três axiomas são declarações de primeira ordem sobre números naturais que expressam as propriedades fundamentais da operação sucessora. O nono axioma final é uma declaração 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 adicionando explicitamente os símbolos de operação de adição e multiplicação e substituindo o axioma de indução de segunda ordem por um esquema de axioma de primeira ordem .

Formulação

Quando Peano formulou seus axiomas, a linguagem da lógica matemática estava em sua infância. O sistema de notação lógica que ele criou para apresentar os axiomas não se provou popular, embora tenha sido a gênese da notação moderna para membros do conjunto (∈, que vem do ε de Peano) e implicação (⊃, que vem do reverso 'de Peano C '.) Peano manteve uma distinção clara entre símbolos matemáticos e lógicos, que ainda não era 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 recriou independentemente seu aparato lógico baseado no trabalho de Boole e Schröder .

Os axiomas Peano definir as propriedades aritméticas de números naturais , geralmente representados como um conjunto de N ou os símbolos não-lógicos para os axiomas consistem de um símbolo constante 0 e um símbolo de função unária S .

O primeiro axioma afirma que a constante 0 é um número natural:

  1. 0 é um número natural.

Os próximos quatro axiomas descrevem a relação de igualdade . Como são logicamente válidos na lógica de primeira ordem com igualdade, não são considerados parte dos "axiomas de Peano" nos tratamentos modernos.

  1. Para cada número natural x , x = x . Ou seja, a igualdade é reflexiva .
  2. Para todos os números naturais x e y , se x = y , em seguida, y = x . Ou seja, 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 um e b , se b é um número natural e uma = b , em seguida, um também é um número natural. Ou seja, os números naturais são fechados por igualdade.

Os axiomas restantes definem as propriedades aritméticas dos números naturais. Os naturais são assumidos para ser fechada sob um único valor " sucessor " função S .

  1. Para cada número natural n , S ( n ) é um número natural. Ou seja, os números naturais são fechados sob S .
  2. Para todos os números naturais m e n , m = n se e somente se S ( m ) = S ( n ) . Ou seja, S é uma injeção .
  3. Para cada número natural n , S ( n ) = 0 é falso. Ou seja, não há número natural cujo sucessor seja 0.

A formulação original dos axiomas de Peano usava 1 em vez de 0 como o "primeiro" número natural. No entanto, como 0 é a identidade aditiva em aritmética, a maioria das formulações modernas dos axiomas de Peano começa em 0.

A cadeia de dominós leves, começando com o mais próximo, pode representar N , no entanto, os axiomas 1–8 também são satisfeitos pelo conjunto de todos os dominós claros e escuros. O nono axioma ( indução ) limita N à cadeia de peças leves ("sem lixo"), pois apenas os dominós leves cairão quando o mais próximo for derrubado.

Os axiomas 1, 6, 7, 8 definem uma representação unária da noção intuitiva de números naturais: o número 1 pode ser definido como S (0), 2 como S ( S (0)), etc. No entanto, considerando a noção de números naturais como sendo definidos por esses axiomas, os axiomas 1, 6, 7, 8 não implicam que a função sucessora gere todos os números naturais diferentes de 0. Em outras palavras, eles não garantem que todo número natural diferente de zero deva suceder a algum outro número natural.

A noção intuitiva de que cada número natural pode ser obtido aplicando o sucessor com freqüência suficiente a zero requer um axioma adicional, que às vezes é chamado de axioma de indução .

  1. Se K for um conjunto tal que:
    • 0 está em K , e
    • para todo número natural n , sendo n em K implica que S ( n ) está em K ,
    então K contém todos os números naturais.

O axioma de indução às vezes é declarado da seguinte forma:

  1. Se φ for um predicado unário tal que:
    • φ (0) é verdadeiro, e
    • para cada número natural n , φ ( n ) sendo verdadeiro implica que φ ( S ( n )) é verdadeiro,
    então φ ( n ) é verdadeiro para todo número natural n .

Na formulação original de Peano, o axioma de indução é um axioma de segunda ordem . Agora é comum substituir este princípio de segunda ordem por um esquema de indução de primeira ordem mais fraco . Existem diferenças importantes entre as formulações de segunda e de primeira ordem, conforme discutido na seção § Teoria da aritmética de primeira ordem a seguir.

Aritmética

Os axiomas Peano pode ser aumentada com as operações de adição e multiplicação e o habitual ordenação total (linear) em N . As respectivas funções e relações são construídas na teoria dos conjuntos ou lógica de segunda ordem e podem ser mostradas como únicas usando os axiomas de Peano.

Adição

Adição é uma função que mapeia dois números naturais (dois elementos de N ) para outro. É definido recursivamente como:

Por exemplo:

A estrutura ( N , +) é um conmutativo monóide com elemento identidade 0. ( N , +) é também um cancellative magma , e, assim, nivelado num grupo . O menor grupo que incorpora N são os inteiros .

Multiplicação

Da mesma forma, a multiplicação é uma função que mapeia dois números naturais para outro. Além disso, é definido recursivamente como:

É fácil ver que (ou "1", na linguagem familiar da representação decimal ) é a identidade correta multiplicativa :

Para mostrar que também é a identidade multiplicativa à esquerda, é necessário o axioma da indução devido à forma como a multiplicação é definida:

  • é a identidade esquerda de 0: .
  • Se é a identidade esquerda do (que é ), então também é a identidade esquerda de : .

Portanto, pelo axioma da indução é a identidade esquerda multiplicativa de todos os números naturais. Além disso, pode-se mostrar que a multiplicação é comutativa e se distribui sobre a adição:

.

Assim, é uma semirregação comutativa .

Desigualdades

A relação normal de ordem total ≤ em números naturais pode ser definida da seguinte forma, assumindo que 0 é um número natural:

Para todo a , bN , ab se e somente se existe algum cN tal que a + c = b .

Esta relação é estável sob adição e multiplicação: pois , se ab , então:

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

Assim, a estrutura ( N , +, ·, 1, 0, ≤) é uma semifiação ordenada ; como não existe um número natural entre 0 e 1, é uma semifiação ordenada discreta.

O axioma de indução às vezes é afirmado da seguinte forma que usa uma hipótese mais forte, fazendo uso da relação de ordem "≤":

Para qualquer predicado φ , se
  • φ (0) é verdadeiro, e
  • para todo n , kN , se kn implica que φ ( k ) é verdadeiro, então φ ( S ( n )) é verdadeiro,
então, para todo nN , φ ( n ) é verdadeiro.

Esta forma do axioma de indução, chamada indução forte , é uma consequência da formulação padrão, mas é freqüentemente mais adequada para raciocinar sobre a ordem ≤. Por exemplo, para mostrar que os naturais são bem ordenados - todo subconjunto não vazio de N tem um elemento mínimo - pode-se raciocinar da seguinte maneira. Seja um XN não vazio e suponha que X não tenha o menor elemento.

  • Uma vez que 0 é o menos elemento de N , deve ser que 0 ∉ X .
  • Para qualquer nN , suponhamos que para todos os kn , kX . Em seguida, S ( n ) ∉ X , pois de outra forma seria o menos elemento de X .

Assim, por princípio a indução forte, para cada nN , NX . Assim, XN = ∅ , que contradiz X ser um subconjunto não vazio de N . Portanto, X tem um elemento mínimo.

Teoria da aritmética de primeira ordem

Todos os axiomas de Peano, exceto o nono axioma (o axioma de indução) são afirmações na 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 está em segunda ordem , uma vez que quantifica sobre predicados (equivalentemente, conjuntos de números naturais em vez de números naturais), mas pode ser transformado em um esquema de axioma de indução de primeira ordem . Tal esquema inclui um axioma por predicado definível na linguagem de primeira ordem da aritmética de Peano, tornando-o mais fraco do que o axioma de segunda ordem. A razão de ser mais fraco é que o número de predicados na linguagem de primeira ordem é contável, enquanto o número de conjuntos de números naturais é incontável. Assim, existem conjuntos que não podem ser descritos em linguagem de primeira ordem (na verdade, a maioria dos conjuntos possui essa propriedade).

As axiomatizações de primeira ordem da aritmética de Peano têm outra limitação técnica. Na lógica de segunda ordem, é possível definir as operações de adição e multiplicação a partir da operação sucessora , mas isso não pode ser feito na configuração mais restritiva da lógica de primeira ordem. Portanto, as operações de adição e multiplicação são incluídas diretamente na assinatura da aritmética de Peano, e são incluídos axiomas que relacionam as três operações entre si.

A seguinte lista de axiomas (junto com os axiomas usuais de igualdade), que contém seis dos sete axiomas da aritmética de Robinson , é suficiente para este propósito:

Além dessa lista de axiomas numéricos, a aritmética de Peano contém o esquema de indução, que consiste em um conjunto recursivamente enumerável de axiomas . Para cada fórmula φ ( x , y 1 , ..., y k ) na linguagem da aritmética de Peano, o axioma de indução de primeira ordem para φ é a sentença

onde é uma abreviatura para y 1 , ..., y k . O esquema de indução de primeira ordem inclui todas as instâncias do axioma de indução de primeira ordem, ou seja, inclui o axioma de indução para cada fórmula φ .

Axiomatizações equivalentes

Existem muitas axiomatizações diferentes, mas equivalentes, da aritmética de Peano. Enquanto algumas axiomatizações, como a que acabamos de descrever, usam uma assinatura que só tem símbolos para 0 e as operações de sucessor, adição e multiplicação, outras axiomatizações usam a linguagem de semirings ordenados , incluindo um símbolo de relação de ordem adicional. Uma dessas axiomatizações começa com os seguintes axiomas, que descrevem uma semifiação discreta ordenada.

  1. , ou seja, a adição é associativa .
  2. , ou seja, a adição é comutativa .
  3. , ou seja, a multiplicação é associativa.
  4. , ou seja, a multiplicação é comutativa.
  5. , ou seja, a multiplicação distribui sobre a adição.
  6. , ou seja, zero é uma identidade para adição e um elemento absorvente para multiplicação (na verdade, supérfluo).
  7. , ou seja, um é uma identidade para multiplicação.
  8. , ou seja, o operador '<' é transitivo .
  9. , ou seja, o operador '<' é irreflexivo .
  10. , ou seja, o pedido satisfaz a tricotomia .
  11. , ou seja, a ordem é preservada com a adição do mesmo elemento.
  12. , ou seja, a ordem é preservada sob a multiplicação pelo mesmo elemento positivo.
  13. , isto é, dados quaisquer dois elementos distintos, o maior é o menor mais outro elemento.
  14. , ou seja, zero e um são distintos e não há nenhum elemento entre eles. Em outras palavras, 0 é coberto por 1, o que sugere que os números naturais são discretos.
  15. , ou seja, zero é o elemento mínimo.

A teoria definida por esses axiomas é conhecida como PA - ; a teoria PA é obtida adicionando o esquema de indução de primeira ordem. Uma propriedade importante de PA - é que qualquer estrutura que satisfaça esta teoria tem um segmento inicial (ordenado por ) isomorfo a . Os elementos nesse segmento são chamados de elementos padrão , enquanto outros elementos são chamados de elementos não padronizados .

Modelos

Um modelo dos axiomas de Peano é um triplo ( N , 0, S ) , onde N é um conjunto (necessariamente infinito), 0 ∈ N e S : NN satisfaz os axiomas acima. Dedekind provou em seu livro de 1888, The Nature and Meaning of Numbers ( alemão : Was sind und was sollen die Zahlen?, Ou seja, "Quais são os números e para que servem?") Que quaisquer dois modelos dos axiomas de Peano ( incluindo o axioma de indução de segunda ordem) são isomórficos . Em particular, dados dois modelos ( N A , 0 A , S A ) e ( N B , 0 B , S B ) dos axiomas de Peano, há um homomorfismo único f  : N AN B que satisfaz

e é uma bijeção . Isso significa que os axiomas de Peano de segunda ordem são categóricos . Este não é o caso com qualquer reformulação de primeira ordem dos axiomas de Peano, entretanto.

Modelos teóricos de conjuntos

Os axiomas de Peano podem ser derivados de construções teóricas de conjuntos dos números naturais e axiomas da teoria de conjuntos, como ZF . A construção padrão dos naturais, devido a John von Neumann , começa a partir de uma definição de 0 como o conjunto vazio, ∅, e um operador s em conjuntos definidos como:

O conjunto de números naturais N é definido como a interseção de todos os conjuntos fechados sob s que contêm o conjunto vazio. Cada número natural é igual (como um conjunto) ao conjunto de números naturais menores que ele:

e assim por diante. O conjunto N junto com 0 e a função sucessora s  : NN satisfaz os axiomas de Peano.

A aritmética de Peano é equiconsistente com vários sistemas fracos da teoria dos conjuntos. Um desses sistemas é ZFC com o axioma do infinito substituído por sua negação. Outro sistema consiste na teoria geral dos conjuntos ( extensionalidade , existência do conjunto vazio e o axioma da adjunção ), acrescida de um esquema axiomático afirmando que uma propriedade que vale para o conjunto vazio e vale para um adjunto sempre que vale para o adjunto deve valer para todos os conjuntos.

Interpretação na teoria das categorias

Os axiomas de Peano também podem ser entendidos usando a teoria das categorias . Seja C uma categoria com objeto terminal 1 C , e defina a categoria de sistemas unários pontiagudos , US 1 ( C ) da seguinte forma:

  • Os objetos de US 1 ( C ) são triplos ( X , 0 X , S X ) onde X é um objeto de C , e 0 X  : 1 CX e S X  : XX são C- morfismos.
  • Um morfismo φ  : ( X , 0 X , S X ) → ( Y , 0 Y , S Y ) é um C- morfismo φ  : XY com φ 0 X = 0 Y e φ S X = S Y φ .

Então C é dito para satisfazer os axiomas Dedekind-Peano se US 1 ( C ) tem um objecto inicial; este objecto inicial é conhecida como um objecto número natural em C . Se ( N , 0, S ) é este objeto inicial, e ( X , 0 X , S X ) é qualquer outro objeto, então o mapa único u  : ( N , 0, S ) → ( X , 0 X , S X ) é tal que

Esta é precisamente a definição recursiva de 0 X e S X .

Modelos fora do padrão

Embora os números naturais usuais satisfaçam os axiomas de PA , também existem outros modelos (chamados de " modelos não padronizados "); o teorema da compactação implica que a existência de elementos não padronizados não pode ser excluída na lógica de primeira ordem. O teorema de Löwenheim – Skolem ascendente mostra que existem modelos não padronizados de PA de todas as cardinalidades infinitas. Este não é o caso dos axiomas de Peano originais (de segunda ordem), que têm apenas um modelo, até o isomorfismo. Isso ilustra uma maneira pela qual o sistema PA de primeira ordem é mais fraco do que os axiomas de Peano de segunda ordem.

Quando interpretada como uma prova dentro de uma teoria dos conjuntos de primeira ordem , como ZFC , a prova de categoricidade de Dedekind para PA mostra que cada modelo da teoria dos conjuntos tem um modelo único dos axiomas de Peano, até o isomorfismo, que se incorpora como um segmento inicial de todos outros modelos de PA contidos nesse modelo de teoria dos conjuntos. No modelo padrão da teoria dos conjuntos, este menor modelo de PA é o modelo padrão de PA; entretanto, em um modelo não padronizado de teoria dos conjuntos, pode ser um modelo não padronizado de AP. Esta situação não pode ser evitada com qualquer formalização de primeira ordem da teoria dos conjuntos.

É natural perguntar se um modelo não padronizado contável pode ser explicitamente construído. A resposta é afirmativa, pois Skolem em 1933 forneceu uma construção explícita desse modelo não padronizado . Por outro lado, o teorema de Tennenbaum , provado em 1959, mostra que não existe um modelo não padronizado contável de PA em que a operação de adição ou multiplicação seja computável . Este resultado mostra que é difícil ser completamente explícito na descrição das operações de adição e multiplicação de um modelo não padronizado contável de AP. Existe apenas um tipo de pedido possível de um modelo não padrão contável. Supondo que ω seja o tipo de ordem dos números naturais, ζ seja o tipo de ordem dos inteiros e η seja o tipo de ordem dos racionais, o tipo de ordem de qualquer modelo não padronizado contável de PA é ω + ζ · η , que pode ser visualizado como uma cópia dos números naturais seguida por uma ordenação linear densa de cópias dos inteiros.

Overspill

Um corte em um modelo não padrão M é um subconjunto não vazio C de M de forma que C é fechado para baixo ( x < y e yCxC ) e C é fechado sob o sucessor. Um corte adequado é um corte que representa um subconjunto apropriado de M . Cada modelo fora do padrão tem muitos cortes adequados, incluindo um que corresponde aos números naturais padrão. No entanto, o esquema de indução na aritmética de Peano impede que qualquer corte adequado seja definível. O lema do transbordamento, provado pela primeira vez por Abraham Robinson, formaliza esse fato.

Lema transbordamento  -  Let M ser um modelo fora do padrão de PA e deixe C ser um corte adequado de M . Suponha que seja uma tupla de elementos de M e uma fórmula na linguagem da aritmética para que

para todos bC .

Então, há um c em M que é maior do que todos os elementos de C, de modo que

Consistência

Quando os axiomas de Peano foram propostos pela primeira vez, Bertrand Russell e outros concordaram que esses axiomas definiam implicitamente o que entendemos por "número natural". Henri Poincaré foi mais cauteloso, dizendo que eles só definiam números naturais se fossem consistentes ; se houver uma prova que começa apenas com esses axiomas e deriva uma contradição como 0 = 1, então os axiomas são inconsistentes e não definem nada. Em 1900, David Hilbert apresentou o problema de provar sua consistência usando apenas métodos finitísticos como o segundo de seus vinte e três problemas . Em 1931, Kurt Gödel provou seu segundo teorema da incompletude , que mostra que tal prova de consistência não pode ser formalizada dentro da própria aritmética de Peano.

Embora seja amplamente afirmado que o teorema de Gödel exclui a possibilidade de uma prova de consistência finitística para a aritmética de Peano, isso depende exatamente do que se entende por uma prova finitística. O próprio Gödel apontou a possibilidade de dar uma prova de consistência finitística da aritmética de Peano ou sistemas mais fortes usando métodos finitísticos que não sã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 deu uma prova da consistência dos axiomas de Peano, usando indução transfinita até um ordinal chamado ε 0 . Gentzen explicou: "O objetivo do presente artigo é provar a consistência da teoria dos números elementares ou, melhor, reduzir a questão da consistência a certos princípios fundamentais". A prova de Gentzen é indiscutivelmente finita, uma vez que o ordinal transfinito ε 0 pode ser codificado em termos de objetos finitos (por exemplo, como uma máquina de Turing descrevendo uma ordem adequada nos inteiros, ou mais abstratamente como consistindo nas árvores finitas , adequadamente ordenadas linearmente) . Se a prova de Gentzen atende ou não aos requisitos que Hilbert imaginou, não está claro: não há uma definição geralmente aceita do que se entende exatamente por uma prova finitística, e o próprio Hilbert nunca deu uma definição precisa.

A grande maioria dos matemáticos contemporâneos acredita que os axiomas de Peano são consistentes, baseando-se na intuição ou na aceitação de uma prova de consistência como a prova de Gentzen . Um pequeno número de filósofos e matemáticos, alguns dos quais também defendem o ultrafinitismo , rejeitam os axiomas de Peano porque aceitar os axiomas equivale a aceitar a coleção infinita de números naturais. Em particular, a adição (incluindo a função sucessora) e a multiplicação são consideradas totais . Curiosamente, existem teorias de autoverificação que se assemelham ao PA, mas possuem subtração e divisão em vez de adição e multiplicação, que são axiomatizadas de forma a evitar a comprovação de sentenças que correspondem à totalidade da adição e multiplicação, mas que ainda podem para provar todos os teoremas verdadeiros de PA, e ainda pode ser estendido para uma teoria consistente que prova sua própria consistência (declarada como a inexistência de uma prova do estilo de Hilbert de "0 = 1").

Veja também

Notas

Referências

Citações

Fontes

Leitura adicional

links externos

Este artigo incorpora material do PA no PlanetMath , que é licenciado pela Creative Commons Attribution / Share-Alike License .