Axiomas de Peano
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.
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 N . {\displaystyle \mathbb {N} .} 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.
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
Adição é a função + : N × N → N, definida recursivamente como: a + 0 = a , a + S ( b ) = S ( a + b ) . {\displaystyle {\begin{aligned}a+0&=a,\\a+S(b)&=S(a+b).\end{aligned}}} Por exemplo, 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
Dada a adição, multiplicação é a função ⋅ : N × N → N {\displaystyle \cdot :\mathbb {N} \times \mathbb {N} \to \mathbb {N} } definida recursivamente como: a ⋅ 0 = 0 , a ⋅ S ( b ) = a + ( a ⋅ b ) . {\displaystyle {\begin{aligned}a\cdot 0&=0,\\a\cdot S(b)&=a+(a\cdot b).\end{aligned}}} É fácil observar que a atribuição do valor 0 a b carrega em si a identidade multiplicativa: Além disso, multiplicação pode ser distribuída sobre a adição:
Desigualdades
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, a ≤ b 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 a ≤ b, então: 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 f ( 0 A ) = 0 B f ( S A ( n ) ) = S B ( f ( n ) ) {\displaystyle {\begin{aligned}f(0_{A})&=0_{B}\\f(S_{A}(n))&=S_{B}(f(n))\end{aligned}}} 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
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.
Axiomatizações equivalentes
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. 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
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.
Modelos de conjunto teóricos
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: 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: 0 = ∅ 1 = s ( 0 ) = s ( ∅ ) = ∅ ∪ { ∅ } = { ∅ } = { 0 } 2 = s ( 1 ) = s ( { 0 } ) = { 0 } ∪ { { 0 } } = { 0 , { 0 } } = { 0 , 1 } 3 = . . . = { 0 , 1 , 2 } {\displaystyle {\begin{aligned}0&=\emptyset \\1&=s(0)=s(\emptyset )=\emptyset \cup \{\emptyset \}=\{\emptyset \}=\{0\}\\2&=s(1)=s(\{0\})=\{0\}\cup \{\{0\}\}=\{0,\{0\}\}=\{0,1\}\\3&=...=\{0,1,2\}\end{aligned}}} e assim em diante. O conjunto N, junto com 0 e a função sucessor s : N → N satisfaz os axiomas de Peano.
Interpretação em teoria das categorias
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 u 0 = 0 X , u ( S x ) = S X ( u x ) . {\displaystyle {\begin{aligned}u0&=0_{X},\\u(Sx)&=S_{X}(ux).\end{aligned}}} Esta é, precisamente, a definição recursiva de 0X e SX.
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.
