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):
  • A aritmética de Peano (PA) é uma teoria formal que descreve os números naturais com símbolos primitivos como 0 e a função sucessor S.
  • 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 \mathbb{N} como o conjunto dos ordinais finitos (ex.: von Neumann: 0=\varnothing, 1=\{\varnothing\}, 2=\{\varnothing,\{\varnothing\}\}, …) 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 \mathbb{N} é 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):
    1. Existe um 0.
    2. S é injetor (se S(a)=S(b) então a=b).
    3. 0 não é sucessor de nenhum número (não existe x com S(x)=0).
    4. Esquema/axioma da indução: para toda fórmula \varphi(x) da linguagem, se \varphi(0) e \forall x(\varphi(x)\to\varphi(S(x))) então \forall x\,\varphi(x).
  • Observação importante: em primeira-ordem a indução aparece como um esquema infinito — uma instância para cada fórmula \varphi. 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 0 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 0” 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 I tal que \varnothing\in I e \forall x\in I\; (x\cup\{x\}\in I). Isto garante a existência de um conjunto indutivo (fechado por sucessor).
  • Definição padrão de \mathbb{N} em ZFC (via von Neumann): usa-se a interseção de todos os subconjuntos indutivos de I. Em palavras: \mathbb{N} \;=\; \bigcap \{X\subseteq I \mid \varnothing\in X \text{ e } \forall x\in X\,(x\cup\{x\}\in X)\}.Assim \mathbb{N} é o menor conjunto indutivo contido em I.
  • Alternativamente, uma construção equivalente é considerar todos os ordinais finitos e tomar \mathbb{N} como o conjunto dos ordinais finitos; essa construção também satisfaz que \mathbb{N} é 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 P(x) (da linguagem de ZFC) com parâmetros fixos,
\text{se }P(\varnothing)\text{ e }\forall n\in\mathbb{N}\,(P(n)\to P(n\cup\{n\}))\text{ então }\forall n\in\mathbb{N}\,P(n).ã
Prova:
  1. Defina o conjunto A := \{n\in\mathbb{N} \mid P(n)\}.(Em ZFC isto é permitido usando o Esquema de Separação: separar dentro de \mathbb{N} os elementos que satisfazem P.)
  2. Mostre que A é indutivo:
    • Como P(\varnothing) por hipótese, tem-se \varnothing\in A.
    • Suponha x\in A. Então P(x) é verdadeira; pela hipótese \forall n\in\mathbb{N}\,(P(n)\to P(n\cup\{n\})) segue P(x\cup\{x\}). Como x\cup\{x\}\in\mathbb{N} (fechamento da \mathbb{N} pelo sucessor), então x\cup\{x\}\in A.
    • Logo A é um subconjunto de \mathbb{N} que contém \varnothing e fecha-se por sucessor, isto é, é um conjunto indutivo contido em \mathbb{N}.
  3. Pela definição de \mathbb{N} como o menor conjunto indutivo, todo conjunto indutivo contido em \mathbb{N} tem de ser igual a \mathbb{N} (ou pelo menos conter todos os seus elementos); em particular, A=\mathbb{N}.
  4. Portanto \forall n\in\mathbb{N}\,P(n). QED.
Comentário didático: a chave foi construir dentro de ZFC o conjunto \mathbb{N} 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 n que satisfazem P é indutivo, logo deve conter todos os elementos de \mathbb{N}.

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 \mathbb{N} 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.
  • 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 \mathbb{N}.
    • Assim a propriedade da indução é dedutível: para qualquer propriedade definível P pode-se formar o conjunto dos naturais que satisfazem P e aplicar a minimalidade de \mathbb{N}.
  • 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 \mathbb{N} 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 \mathbb{N} 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 0 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 P, o conjunto \{n\in\mathbb{N}\mid P(n)\} é indutivo e portanto igual a \mathbb{N}, e assim a indução é dedutível (teorema) a partir dos axiomas de ZFC.

Exercícios relacionados