Todo subconjunto não-vazio   possui um elemento mínimo, ou seja, se  .

Prova
  • Devemos mostrar o complementar de   em relação ao   assim  
    • Tomemos um subconjunto   :   formado pelos elementos que não estão em  , ou seja,  .
  • a quem pertence o elemento  
    • Se   o teorema está demonstrado, pois   é o menor elemento do  .
    • Se   logo  
  • O conjunto  
    • Agora tomemos um subconjunto de  , chamado   onde n é o maior natural tal que aconteça isso, assim  
  • mostrar que  
    • Pela construção do conjunto  , temos que  . Se  , teríamos   e logo  . Como não faz sentido, logo  , portanto  
  • Devemos mostrar que   é o menor elemento de  
    • Como todos os antecessores de   são os elementos de  , temos que   é o menor elemento de  , pois os elementos menores que   estão em  

Teorema (Boa Ordem = Indução)

editar

Vale o Princípio da Boa Ordem se, e somente se, vale o Princípio da Indução.

Demonstração
  • Suponha válido o Princípio da Boa Ordem. Seja   satisfazendo as propriedades do princípio da indução.
    • Suponhamos, por absurdo, que  . Isto significa que existe algum elemento de   que não pertence a A e, portanto, o conjunto   é não vazio.
    • Pelo Princípio da Boa Ordem, B possui um elemento mínimo  . Com certeza m > 1, pois como  . Assim,   é um natural menor que m.
    • Pela minimalidade de m, temos que   e portanto  . Pelo 2ª propriedade do princípio da indução, concluímos que  , o que é um absurdo.
  • Suponha válido o Princípio da Indução. Seja   não vazio.
    • Suponhamos por absurdo que B não possua elemento mínimo. Em particular,   (senão 1 seria elemento mínimo de B). Seja  .
    • Observamos inicialmente que  . De fato, se  , então existiria  , ou seja, n < n.
      • Tendo   temos também n < m qualquer que seja  , em particular, tomando   obtemos n < n o que é absurdo. Concluímos que  .
    • Mostraremos a seguir que  . Vejamos agora que isto é suficiente para concluir a demonstração. Neste caso temos   contradizendo a hipótese  .
    • Mostremos, por indução, que  . Já sabemos que   e portanto   qualquer que seja  , ou seja,  . Tomemos  . Por definição de A temos   qualquer que seja  , logo   para todo  . Se   então   é um elemento mínimo de B. Como, por hipótese, B não possui elemento mínimo, segue que   e portanto   para qualquer  . Concluímos que  . Pelo Princípio da Indução  .
Nota: Na Teoria axiomática dos Conjuntos de Zermelo-Fraenkel [sistema denotado como "ZF sem adição de axiomas extras"], a generalização deste princípio acima é equivalente para o Axioma da Escolha, criado em 1904 pelo matemático alemão Ernst Zermelo. Este é considerado um dos axiomas mais importantes da história da Matemática, apesar de suas consequências não-construtivas e controversas (vide o Paradoxo de Banach-Tarski, entre outros).

Exemplo 1

editar
Mostre que, dados  .
  • Dados  , pela lei da tricotomia, temos três possibilidades  .
    • Caso  , tome  , assim  
    • Caso  , tome  , assim  
    • Caso  . Tome  . A não é vazio, pois  .
      • Pelo Princípio da Boa Ordem (P.B.O.),  .

Exemplo 2

editar

Se  

  • Considere  . Pelo PBO,