Questão 4. Sejam
e
números naturais. Prove as seguintes propriedades básicas de ordem:
se, e somente se,
.
Passo 1
O enunciado dá que
são números naturais e pede para provar a equivalência
onde
denota o sucessor de
(ou seja,
na notação habitual).
Informações e definições que vamos usar (tudo retirado da teoria de números naturais):
- A definição de ordem não estrita (
): significa que existe tal que
- A definição de ordem estrita (
): significa que existe com e
(Equivalente a
e
.)
- Definição recursiva da adição:
- Propriedade básica usada: todo natural diferente de
é sucessor de algum natural; ou seja, se então existe tal que .
A partir dessas definições vamos provar as duas implicações da equivalência. Não resolvo nada neste passo; apenas assinalei o que foi dado e as ferramentas que vamos usar.
Passo 2
Lema técnico que usaremos (e que provarei rapidamente): para quaisquer naturais
e
vale
Prova do lema por indução em
:
- Caso base
: pela definição de adição,
logo
.
- Passo indutivo: suponha
para um . Então, usando a definição de adição,
Pela hipótese indutiva
, então
Mas, novamente pela regra de adição na segunda coordenada,
Assim
, completando o passo indutivo.
Portanto o lema
é válido para todo
. Esse lema é uma aplicação direta da recursão da adição; é uma identidade que facilita reescrever soma com um sucessor.
Passo 3
Prova da implicação
: suponha
. Pela definição de
existe
com
e
Como
, pela propriedade citada existe
tal que
. Substituindo em
obtemos
Pela definição da adição isso é equivalente a
Agora aplicamos o lema do Passo 2 com o mesmo
:
Comparando com
, temos
Isto mostra que existe
tal que
, ou seja, por definição de
,
Portanto
implica
.
Passo 4
Prova da implicação
: suponha
. Pela definição de
existe
tal que
Pelo lema do Passo 2 temos
. Assim
Usando a identidade
(que é apenas a mesma regra de adição escrita de outra forma), obtemos
Note que
. Logo existe um natural não nulo (especificamente
) tal que
. Pela definição de
isso significa exatamente
.
Portanto
implica
.
Passo 5
Conclusão: juntando os Passos 3 e 4 provamos as duas direções. A equivalência está demonstrada:
se, e somente se,
.
Um exemplo rápido para fixar a intuição: com
e
, temos
porque
com
. A sucessão dá
e
porque
. Os dois lados batem.