Questão 4. Sejam
e
números naturais. Prove as seguintes propriedades básicas de ordem:
(A adição preserva a ordem)
se, e somente se,
.
(A adição preserva a ordem)
Passo 1
O enunciado dá que
são números naturais e pede para provar a equivalência
Informações relevantes e definições que vamos usar (todas valem para números naturais):
- A definição de ordem:
significa que existe tal que . - Propriedades elementares da adição: associatividade e comutatividade, e
. - Propriedade do sucessor
: se então (injeção do sucessor). - Vamos precisar da lei de cancelamento da adição: se
então . Vou provar essa lei por indução sobre antes de usá-la.
Passo 2
Provar a lei de cancelamento por indução em
:
Base (
). Se
então, usando
para todo
, obtemos
. Logo a propriedade vale para
.
Passo indutivo. Suponha que para um certo
valha: se
então
. Mostraremos que vale para
(o sucessor de
).
Suponha
. Pela definição recorrente da adição em naturais, sabe-se que
e
. Assim
Pela injetividade do sucessor
, segue
. Pela hipótese indutiva, disso segue
. Portanto a propriedade vale para
.
Concluímos por indução que, para todo
, se
então
. Esta é a lei de cancelamento da adição.
Passo 3
Provar a implicação direta:
.
Suponha
. Pela definição de ordem existe
tal que
Somando
aos dois lados da igualdade (isto é, aplicando a operação
em ambos os membros) obtemos, usando associatividade da adição,
Como
é um número natural, isto mostra que
é da forma
com
; em particular existe
(escolher
) tal que
o que, pela definição de ordem, significa
. Assim a adição preserva a ordem no sentido direto.
Passo 4
Provar a implicação recíproca:
.
Suponha
. Pela definição de ordem existe
tal que
Pela associatividade da adição podemos reescrever o lado direito como
ou seja
Agora aplicamos a lei de cancelamento (provada no Passo 2) com
,
e o mesmo
: de
segue
. Pela definição de ordem isso implica
. Assim a adição preserva a ordem no sentido inverso.
Passo 5
Juntando os dois sentidos mostrados nos Passos 3 e 4, obtemos a equivalência desejada: para quaisquer
,