Questão 19 Mostre que, em
, vale a propriedade da Tricotomia:
Para quaisquer
, uma e apenas uma, das relações ocorre:
Passo 1
O enunciado pede que se mostre a propriedade da tricotomia em
: para quaisquer
, acontece uma e apenas uma das três relações
As informações que temos são apenas que
e
são números naturais e que queremos provar existência (pelo menos uma das três ocorre) e unicidade (não podem ocorrer duas ou mais simultaneamente).
Passo 2
Primeiro vamos fixar a definição de ordem que vamos usar (essa é a forma padrão quando os naturais vêm das axiomas de Peano e da adição):
- Definição: dizemos que
se existe tal que . - Definição: dizemos que
se existe com e . (Isto é, significa e .) - Dizemos que
quando .
Explicando devagar: a ideia é que
quando somando algo a
obtém-se
. Se esse “algo” for
então
; se for um natural positivo então
. Essa é uma forma concreta de transformar a noção intuitiva de “menor” em termos da adição em
.
Passo 3
Antes de provar a tricotomia, comprovamos duas propriedades simples que serão usadas várias vezes.
Lema 1. Se
então
e
.
Prova do lema 1 (rápida):
é o elemento neutro da adição e não tem antecessor (pela construção de
via Peano). Se algum dos somandos fosse não nulo (isto é, sucessor de algo), então a soma seria sucessor de alguma coisa e não poderia ser
. Logo ambos têm de ser
.
Lema 2 (cancelamento à direita). Se
então
.
Prova do lema 2 (esboço elementar por indução em
):
- Base
: dá porque . - Passo indutivo: suponha verdade para
. Se (onde é o sucessor de ), então . Como sucessor é injetor (sucessores distintos são distintos), obtém-se e pela hipótese indutiva .
Assim o cancelamento é válido.
Esses lemas são naturais usando axiomas de Peano e propriedades básicas da adição; eles nos permitem evitar contradições do tipo "algo positivo soma para
".
Passo 4
Agora mostramos que duas das relações não podem ocorrer simultaneamente (unicidade). Mostramos as três impossibilidades em pares:
(i) Não podem ocorrer simultaneamente
e
.
Porque implica, pela definição,
. Logo
é impossível junto com
.
Porque
(ii) Não podem ocorrer simultaneamente
e
.
Suponha, para contradizer, que e
. Então existem
com
,
, tais que
Suponha, para contradizer, que
Substituindo a segunda na primeira:
ou melhor somando
aos dois lados da primeira igualdade seguida da segunda, obtemos
Então
. Mas
e
implicam
, em contradição com o Lema 1. Portanto não é possível ter ao mesmo tempo
e
.
(iii) Não podem ocorrer simultaneamente
e
.
Idêntico a (i): implica
, logo não pode ser que
.
Idêntico a (i):
Com (i)–(iii) concluímos que, se duas das relações ocorressem juntas, haveria contradição; portanto, no máximo uma das três pode ocorrer.
Passo 5
Agora provamos que sempre ocorre pelo menos uma das relações (existência). Faremos isso por indução no segundo parâmetro
. A ideia é: para cada
fixo, mostrar que para todo
uma das três se verifica; isso é natural por indução em
.
Base da indução:
. Seja
.
- Se
então . - Se
então é sucessor de algum , ou seja existe com e . Isso implica (pela definição), ou seja .
Não existe a possibilidade, porque significaria existir com , o que é impossível pelo Lema 1. Assim para sempre ocorre uma das três relações.
Passo 6
Passo indutivo. Suponha que para um dado
a propriedade seja verdadeira: para todo
vale uma e apenas uma de
,
,
. Vamos provar que a propriedade vale para
.
Tome um
arbitrário. Pelo passo indutivo, aplicado a
, uma e apenas uma das seguintes alternativas ocorre:
Analisemos cada caso e traduzamos para relação com
.
- Caso (A): se
então existe com . Então
e como
segue que
.
- Caso (B): se
então
com
, logo existe um natural não nulo (escolhemos
) tal que
. Pela definição, isso significa
.
- Caso (C): se
então existe com . Se então e estamos no caso de igualdade com . Se , escrevendo vemos que
com
, logo
, isto é
.
Assim, em cada um dos três cenários para comparação com
obtemos uma e apenas uma das relações em relação a
: ou
, ou
, ou
. Além disso, pela unicidade já provada no Passo 4, essas três são mutuamente exclusivas. Portanto, para todo
vale uma e apenas uma das relações em relação a
.
Isso completa o passo indutivo.
Passo 7
Concluindo por indução em
: a propriedade vale para
e se vale para
vale para
; portanto vale para todo
e para todo
. Juntando os resultados de existência (sempre ocorre alguma das três) e unicidade (não podem ocorrer duas), obtemos exatamente a tricotomia:
Para quaisquer
, ocorre uma e apenas uma das relações
,
ou
.
Resposta
Para quaisquer
, uma e apenas uma das relações ocorre: