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).