Nosso objetivo aqui é provar que, se não assumirmos que, no contexto da teoria dos números naturais ou a tricotomia da ordem, ou pelo menos que
então é impossível provar que o Princípio da Boa Ordem (PBO)
Princípio da Indução Finita.
Seja uma linguagem de primeira ordem, com um símbolo de constante (0), uma função unária (sucessor), duas funções binárias (soma e produto) e um símbolo de relação binária (menor). Seja
o seguinte conjunto de fórmulas:
Além disso, para toda fórmula ,
contém:
Que é o PBO para conjuntos definíveis.
Considere agora onde
Onde a tabela de soma e multiplicação dos naturais permanece a mesma que a usual e além disso satisfaz
T1)
T2)
T3)
T4)
T5)
Veja que e ainda:
T6) pois
e basta tomar
em P6 para conclusão.
satisfaz PBO: se
for uma sentença e
, se existir algum
tal que
, então o conjunto
obedece o PBO já que é um subconjunto dos números naturais. Assim existe um menor natural
que satisfaz
. Por T6,
é o menor elemento.
Se não existir nenhum tal que
então
é o menor (e único) elemento.
Vamos mostrar que não satisfaz a PIF:
Seja , então claramente
e
, (pela fórmula 2) e
. Assim
não satisfaz a PIF.