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.
(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
. 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
): Se uma propriedade satisfaz então. -
Segunda forma do PIM (indução forte, que chamarei de PIM
): Se uma propriedade satisfaz então. -
Princípio da Boa Ordenação (PBO): Toda subconjunto não-vazio
tem um menor elemento; isto é, se então existe tal que .
A resolução começa no Passo 2.
Passo 2
Prova da implicação
.
Estratégia: provar por contradição que qualquer subconjunto não-vazio
tem mínimo, assumindo que
é válida.
Construção e raciocínio passo a passo:
-
Suponha, para obter contradição, que exista um conjunto
não vazio que não possui menor elemento. Quero deduzir uma contradição usando . -
Defina a propriedade
da seguinte maneira (esta é crucial e simples de entender): ou formalmentesignifica . Intuição: senão tem mínimo, então, para cada , nenhum dos inteiros até pode estar em — caso contrário teríamos um mínimo. -
Verifique a base
. Se então seria o menor elemento de (contradiz a suposição de que não tem mínimo). Logo , portanto é verdadeira. -
Mostre o passo indutivo
. Suponha verdadeira, isto é, nenhum elemento pertence a . Se , então seria o menor elemento de (porque não há elementos em ), contradizendo a hipótese inicial. Logo e é verdadeira. -
Agora aplicamos
: de e segue . Em particular, para todo temos . -
Conclusão: se nenhum
pertence a , então . Isso contradiz a hipótese de que é não vazio. Portanto a suposição inicial (existência de sem mínimo) é falsa. -
Resultado: toda subconjunto não-vazio de
tem menor elemento. Ou seja, .
Passo 3
Prova da implicação
.
Estratégia: assumir
e provar
usando o argumento do “menor contraexemplo”.
Passo a passo:
-
Suponha que
é uma propriedade que satisfaz e . Queremos mostrar . -
Argumento por contradição: suponha que exista algum
tal que é falsa. Defina o conjunto dos contraexemplos Por hipótese de contradição,. -
Pelo PBO,
possui um menor elemento; chame-o de . Assim e para todo temos , isto é, é verdadeira para todo . -
Observe que
, porque é verdadeira; logo e é definido em . -
Como
é o menor contraexemplo, para vale (pois e elementos menores não estão em ). Pela hipótese indutiva , segue é verdadeira. -
Isso contradiz
(que afirma falsa). Assim a suposição de que é falsa. -
Conclusão:
, logo é verdadeira para todo . Assim .
Passo 4
Conclusão de (a): juntando os Passos 2 e 3 temos a equivalência
Expliquei ambas as implicações: da indução fraca deduzi a boa ordenação por meio da propriedade "nenhum elemento de
é
", e da boa ordenação deduzi a indução fraca pelo menor contraexemplo.
Passo 5
Provar agora a equivalência entre
e
(item (b)(i)).
Duas implicações devem ser mostradas:
e
.
-
Prova de
. -
Suponha que
é válida e que uma propriedade satisfaz as hipóteses da indução forte, isto é, -
Defina a nova propriedadeIsto significa que
afirma que são todas verdadeiras. -
Verifique a base:
é exatamente , que é verdadeira. -
Verifique o passo indutivo: suponha
verdadeira; isto é, é verdadeira para todo . Pela hipótese da indução forte aplicada a obtemos . Logo (que exige ) é verdadeira. -
Aplicando
a obtemos . Em particular, para cada vale . Assim a indução forte segue da fraca: .
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éé verdadeiro”. -
-
Prova de
. - Esta implicação é imediata: a hipótese da
(isto é, ) é um caso particular da hipótese da (porque se então, em particular, e daí ). 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 obtemos o resultado para .
- Esta implicação é imediata: a hipótese da
-
Conclusão do item (b)(i):
e são equivalentes.
Passo 6
Conclusão do item (b)(ii): equivalência entre
e PBO.
-
Já provamos em (a) que
(Passo 4). -
Em (Passo 5) provamos que
. -
Pela transitividade da equivalência, segueisto é, a segunda forma do PIM é equivalente ao PBO.
Resposta
(a)
\n
(b)(i) \n
(b)(ii)
(b)(i)
(b)(ii)