A equivalência dos Princípios de Indução e da Boa Ordenação.
(a) Prove que a primeira forma do PIM é equivalente ao PBO.
(b) Conclua que:
i. as duas formas do PIM são equivalentes.
ii. a segunda forma do PIM é equivalente ao PBO.

Passo 1

O enunciado pede provar equivalências entre duas formas do Princípio de Indução Matemática (PIM) e o Princípio da Boa Ordenação (PBO). Vou trabalhar com a convenção usual \mathbb{N}=\{0,1,2,\dots\}. As informações e objetivos são:
  • Objetivo (a): provar que a primeira forma do PIM é equivalente ao PBO.
  • Objetivo (b):
    i. concluir que as duas formas do PIM são equivalentes;
    ii. concluir que a segunda forma do PIM é equivalente ao PBO.
Definições que vamos usar (estão sendo dadas pelo enunciado e eu as explico para não deixar dúvida):
  • Primeira forma do PIM (forma fraca, que chamarei de PIM _1): Se uma propriedade P(n) satisfaz
    P(0)\quad\text{e}\quad \forall n\in\mathbb{N},\; \big(P(n)\Rightarrow P(n+1)\big),
    então \forall n\in\mathbb{N},\; P(n).
  • Segunda forma do PIM (indução forte, que chamarei de PIM _2): Se uma propriedade P(n) satisfaz
    P(0)\quad\text{e}\quad \forall n\in\mathbb{N},\; \Big(\big(\forall k\le n,\;P(k)\big)\Rightarrow P(n+1)\Big),
    então \forall n\in\mathbb{N},\; P(n).
  • Princípio da Boa Ordenação (PBO): Toda subconjunto não-vazio S\subseteq\mathbb{N} tem um menor elemento; isto é, se S\neq\varnothing então existe m\in S tal que \forall x\in S,\; m\le x.
A resolução começa no Passo 2.

Passo 2

Prova da implicação \text{PIM}_1 \Rightarrow \text{PBO}.
Estratégia: provar por contradição que qualquer subconjunto não-vazio S\subseteq\mathbb{N} tem mínimo, assumindo que \text{PIM}_1 é válida.
Construção e raciocínio passo a passo:
  1. Suponha, para obter contradição, que exista um conjunto S\subseteq\mathbb{N} não vazio que não possui menor elemento. Quero deduzir uma contradição usando \text{PIM}_1.
  2. Defina a propriedade Q(n) da seguinte maneira (esta é crucial e simples de entender):
    Q(n):\\ \text{``nenhum elemento de }S\text{ é }\le n\text{''},é
    ou formalmente Q(n) significa \forall k\le n,\; k\notin S.
    Intuição: se S não tem mínimo, então, para cada n, nenhum dos inteiros até n pode estar em S — caso contrário teríamos um mínimo.
  3. Verifique a base Q(0). Se 0\in S então 0 seria o menor elemento de S (contradiz a suposição de que S não tem mínimo). Logo 0\notin S, portanto Q(0) é verdadeira.
  4. Mostre o passo indutivo Q(n)\Rightarrow Q(n+1). Suponha Q(n) verdadeira, isto é, nenhum elemento \le n pertence a S. Se n+1\in S, então n+1 seria o menor elemento de S (porque não há elementos \le n em S), contradizendo a hipótese inicial. Logo n+1\notin S e Q(n+1) é verdadeira.
  5. Agora aplicamos \text{PIM}_1: de Q(0) e \forall n,\;Q(n)\Rightarrow Q(n+1) segue \forall n,\;Q(n). Em particular, para todo n temos n\notin S.
  6. Conclusão: se nenhum n pertence a S, então S=\varnothing. Isso contradiz a hipótese de que S é não vazio. Portanto a suposição inicial (existência de S\neq\varnothing sem mínimo) é falsa.
  7. Resultado: toda subconjunto não-vazio de \mathbb{N} tem menor elemento. Ou seja, \text{PIM}_1\Rightarrow\text{PBO}.

Passo 3

Prova da implicação \text{PBO} \Rightarrow \text{PIM}_1.
Estratégia: assumir \text{PBO} e provar \text{PIM}_1 usando o argumento do “menor contraexemplo”.
Passo a passo:
  1. Suponha que P(n) é uma propriedade que satisfaz P(0) e \forall n,\; P(n)\Rightarrow P(n+1). Queremos mostrar \forall n,\; P(n).
  2. Argumento por contradição: suponha que exista algum n tal que P(n) é falsa. Defina o conjunto dos contraexemplos
    T=\{n\in\mathbb{N}\mid P(n)\\ \text{é falsa}\}.é
    Por hipótese de contradição, T\neq\varnothing.
  3. Pelo PBO, T possui um menor elemento; chame-o de m. Assim m\in T e para todo k<m temos k\notin T, isto é, P(k) é verdadeira para todo k<m.
  4. Observe que m\neq 0, porque P(0) é verdadeira; logo m\ge 1 e m-1 é definido em \mathbb{N}.
  5. Como m é o menor contraexemplo, para k=m-1 vale P(m-1) (pois m-1<m e elementos menores não estão em T). Pela hipótese indutiva P(m-1)\Rightarrow P(m), segue P(m) é verdadeira.
  6. Isso contradiz m\in T (que afirma P(m) falsa). Assim a suposição de que T\neq\varnothing é falsa.
  7. Conclusão: T=\varnothing, logo P(n) é verdadeira para todo n\in\mathbb{N}. Assim \text{PBO}\Rightarrow\text{PIM}_1.

Passo 4

Conclusão de (a): juntando os Passos 2 e 3 temos a equivalência
\text{PIM}_1 \iff \text{PBO}.
Expliquei ambas as implicações: da indução fraca deduzi a boa ordenação por meio da propriedade "nenhum elemento de S é \le n", e da boa ordenação deduzi a indução fraca pelo menor contraexemplo.

Passo 5

Provar agora a equivalência entre \text{PIM}_1 e \text{PIM}_2 (item (b)(i)).
Duas implicações devem ser mostradas: \text{PIM}_1\Rightarrow\text{PIM}_2 e \text{PIM}_2\Rightarrow\text{PIM}_1.
  1. Prova de \text{PIM}_1\Rightarrow\text{PIM}_2.
    • Suponha que \text{PIM}_1 é válida e que uma propriedade P(n) satisfaz as hipóteses da indução forte, isto é,
      P(0)\quad\text{e}\quad \forall n,\;\Big(\big(\forall k\le n,\;P(k)\big)\Rightarrow P(n+1)\Big).
    • Defina a nova propriedade
      Q(n):\\ \forall k\le n,\; P(k).
      Isto significa que Q(n) afirma que P(0),P(1),\dots,P(n) são todas verdadeiras.
    • Verifique a base: Q(0) é exatamente P(0), que é verdadeira.
    • Verifique o passo indutivo: suponha Q(n) verdadeira; isto é, P(k) é verdadeira para todo k\le n. Pela hipótese da indução forte aplicada a n obtemos P(n+1). Logo Q(n+1) (que exige P(0),\dots,P(n+1)) é verdadeira.
    • Aplicando \text{PIM}_1 a Q obtemos \forall n,\;Q(n). Em particular, para cada n vale P(n). Assim a indução forte segue da fraca: \text{PIM}_1\Rightarrow\text{PIM}_2.
    Observação intuitiva: a indução forte apenas permite assumir mais hipóteses no passo indutivo, mas essas hipóteses podem ser obtidas acumulando verdades pelos passos da indução fraca aplicados à propriedade “tudo até n é verdadeiro”.
  2. Prova de \text{PIM}_2\Rightarrow\text{PIM}_1.
    • Esta implicação é imediata: a hipótese da \text{PIM}_1 (isto é, P(n)\Rightarrow P(n+1)) é um caso particular da hipótese da \text{PIM}_2 (porque se \forall k\le n,\;P(k) então, em particular, P(n) e daí P(n+1)). Logo qualquer propriedade que satisfaça as hipóteses da indução fraca também satisfaz as hipóteses da indução forte, e aplicando \text{PIM}_2 obtemos o resultado para \text{PIM}_1.
  3. Conclusão do item (b)(i): \text{PIM}_1 e \text{PIM}_2 são equivalentes.

Passo 6

Conclusão do item (b)(ii): equivalência entre \text{PIM}_2 e PBO.
  1. Já provamos em (a) que \text{PIM}_1\iff\text{PBO} (Passo 4).
  2. Em (Passo 5) provamos que \text{PIM}_1\iff\text{PIM}_2.
  3. Pela transitividade da equivalência, segue
    \text{PIM}_2 \iff \text{PIM}_1 \iff \text{PBO},
    isto é, a segunda forma do PIM é equivalente ao PBO.

Resposta

(a) \displaystyle \text{PIM}_1 \iff \text{PBO}\n
(b)(i) \displaystyle \text{PIM}_1 \iff \text{PIM}_2\n
(b)(ii) \displaystyle \text{PIM}_2 \iff \text{PBO}

Exercícios relacionados