Exercício 2.25. Explique por que o Princípio da Indução aparece como axioma na aritmética de Peano, mas como teorema no contexto de ZFC.
Passo 1
O enunciado pede que eu explique por que o Princípio da Indução aparece como axioma na aritmética de Peano, mas como teorema no contexto de ZFC.\n
Informações relevantes dadas (ou que vou usar sem perguntar mais nada):
Informações relevantes dadas (ou que vou usar sem perguntar mais nada):
- A aritmética de Peano (PA) é uma teoria formal que descreve os números naturais com símbolos primitivos como
e a função sucessor . - Em PA (na sua forma primeira-ordem) o Princípio da Indução aparece como um esquema de axiomas (uma instância por cada fórmula da linguagem).
- ZFC é a teoria de conjuntos usual, com entre outros os axiomas do Infinito e do Esquema de Compreensão (Separação/Replacement) que permitem construir conjuntos.
- Em ZFC é comum construir
como o conjunto dos ordinais finitos (ex.: von Neumann: , , , …) ou, equivalentemente, como a interseção de todos os conjuntos indutivos garantidos pelo axioma do Infinito. - O objetivo concreto: mostrar por que, na prática, isto faz com que a indução seja assumida em PA, mas seja dedutível em ZFC.
Passo 2
O que significa “ser axioma” e “ser teorema” em termos simples\n
- Axioma: uma afirmação que a teoria assume sem prova; é um ponto de partida. Em PA, a indução é assumida (como esquema) porque a linguagem e os demais axiomas não a implicam.
- Teorema: uma afirmação que pode ser deduzida a partir dos axiomas da teoria por regras de inferência. Em ZFC, queremos ver que a mesma forma do princípio de indução pode ser deduzida a partir dos axiomas de ZFC depois que
é definido dentro de ZFC.
Passo 3
Breve apresentação concreta dos axiomas relevantes de PA (sem provar nada) — o lugar da indução ali\n
- A versão informal dos axiomas de Peano inclui (entre outros):
- Existe um
. -
é injetor (se então ). -
não é sucessor de nenhum número (não existe com ). - Esquema/axioma da indução: para toda fórmula
da linguagem, se e então .
- Existe um
- Observação importante: em primeira-ordem a indução aparece como um esquema infinito — uma instância para cada fórmula
. Em segunda-ordem pode-se expressar a propriedade de forma única, mas aí a linguagem é mais rica (permite quantificar sobre propriedades/subconjuntos).
Passo 4
Por que PA precisa assumir a indução (intuição clara e não técnica demais)\n
- PA trabalha numa linguagem cuja semântica refere-se apenas a elementos do domínio “número natural” e não dispõe, como primitivo, de um objeto que seja automaticamente “o menor conjunto indutivo”.
- Os outros axiomas de PA controlam o comportamento de
e do sucessor, mas nada nos obliga a que não exista algum modelo estranho (modelo não padrão) onde a propriedade “fechar-se por sucessor a partir de ” falhe para algumas propriedades expressíveis; por isso é necessário incluir a indução para garantir que todas as propriedades definíveis que se propagam por sucessor realmente valham para todos os elementos “naturais” do modelo. - Em termos meta: sem a indução como axioma não se consegue deduzir certas afirmações sobre todos os naturais — portanto a teoria a assume.
Passo 5
Como ZFC constrói os naturais: a ideia prática e as definições usadas\n
- Axioma do Infinito (forma comum): existe um conjunto
tal que e . Isto garante a existência de um conjunto indutivo (fechado por sucessor). - Definição padrão de
em ZFC (via von Neumann): usa-se a interseção de todos os subconjuntos indutivos de . Em palavras: Assim é o menor conjunto indutivo contido em . - Alternativamente, uma construção equivalente é considerar todos os ordinais finitos e tomar
como o conjunto dos ordinais finitos; essa construção também satisfaz que é o menor conjunto indutivo.
Passo 6
Mostrar, passo a passo, como se prova o princípio da indução em ZFC (prova formal-esquemática)\n
Vou provar em ZFC a seguinte forma do princípio de indução: para toda fórmula (da linguagem de ZFC) com parâmetros fixos,
Vou provar em ZFC a seguinte forma do princípio de indução: para toda fórmula
Prova:
- Defina o conjunto
(Em ZFC isto é permitido usando o Esquema de Separação: separar dentro de os elementos que satisfazem .) - Mostre que
é indutivo: - Como
por hipótese, tem-se . - Suponha
. Então é verdadeira; pela hipótese segue . Como (fechamento da pelo sucessor), então . - Logo
é um subconjunto de que contém e fecha-se por sucessor, isto é, é um conjunto indutivo contido em .
- Como
- Pela definição de
como o menor conjunto indutivo, todo conjunto indutivo contido em tem de ser igual a (ou pelo menos conter todos os seus elementos); em particular, . - Portanto
. QED.
Comentário didático: a chave foi construir dentro de ZFC o conjunto
com a propriedade de minimalidade entre conjuntos indutivos. Uma vez que isso existe e pode ser manipulada por compreensão, a prova da indução é uma linha curta: o conjunto dos
que satisfazem
é indutivo, logo deve conter todos os elementos de
.
Passo 7
Comparação direta — por que a diferença técnica aparece\n
- Em PA:
- A linguagem trata diretamente de termos “números” e da função sucessor, mas não tem à disposição um objeto “o menor conjunto indutivo” nem operações para quantificar sobre subconjuntos de
como objetos da teoria (a menos que se trabalhe em segunda-ordem). - Por isso a propriedade que garante validade universal de certos predicados precisa ser assumida como axioma (esquema), caso contrário a teoria não garante que todos os predicados que se propagam pelo sucessor sejam verdadeiros para todos os naturais.
- A linguagem trata diretamente de termos “números” e da função sucessor, mas não tem à disposição um objeto “o menor conjunto indutivo” nem operações para quantificar sobre subconjuntos de
- Em ZFC:
- Os números naturais são conjuntos construídos a partir dos axiomas (Infinito, Separação, etc.). A existência do menor conjunto indutivo é uma consequência da forma como se define
. - Assim a propriedade da indução é dedutível: para qualquer propriedade definível
pode-se formar o conjunto dos naturais que satisfazem e aplicar a minimalidade de .
- Os números naturais são conjuntos construídos a partir dos axiomas (Infinito, Separação, etc.). A existência do menor conjunto indutivo é uma consequência da forma como se define
- Resumindo em linguagem curta: PA precisa da indução como axioma porque não internaliza a noção de “conjunto de números” em sua linguagem de forma a derivar a propriedade de minimalidade; ZFC constrói
como o menor conjunto indutivo e por isso a indução é consequência lógica dos axiomas de ZFC.
Passo 8
Observações adicionais importantes (para evitar confusões comuns)\n
- Em segunda-ordem os axiomas de Peano podem ter a indução como um único axioma universal (quantificando sobre todos os subconjuntos), e nesse sentido a diferença entre “axioma” e “teorema” também tem a ver com a linguagem (primeira- versus segunda-ordem).
- O facto de ZFC provar a indução não torna ZFC “mais fraca” nem “mais forte” por esse ponto isolado; trata-se apenas de que ZFC é capaz de representar conjuntos e, portanto, demonstrar propriedades que PA tem de assumir.
- Do ponto de vista metamatemático: a prova da indução em ZFC usa os axiomas do Infinito e Esquema de Compreensão/Separação — sem eles não se consegue fazer a construção de
e o argumento cai por terra.
Resposta
Porque em PA (primeira-ordem) os naturais e o operador sucessor são noções primitivas da linguagem e nada nos assegura internamente que toda propriedade que começa em
e é fechada por sucessor vale para todos os elementos, logo o Princípio da Indução precisa ser assumido como (esquema de) axioma; em ZFC os naturais são construídos como o menor conjunto indutivo (graças ao axioma do Infinito e à compreensão/Separação), de modo que, para qualquer propriedade
, o conjunto
é indutivo e portanto igual a
, e assim a indução é dedutível (teorema) a partir dos axiomas de ZFC.