Mostre que a relação
é uma relação de ordem em
.
Passo 1
O que o problema pede: mostrar que a relação
em
é uma relação de ordem.
Informações que temos (convenções e definição que vou usar):
Informações que temos (convenções e definição que vou usar):
- Vou trabalhar com a ordem usual em
(aquela que herdamos dos inteiros). - Para evitar ambiguidade sobre se
, vou usar a descrição equivalente e muito prática: dizer que significa que existe um número inteiro não negativo tal que . Escrevo isso assim:
- O que é preciso provar para que
seja uma relação de ordem (definição): mostrar que é reflexiva, antissimétrica e transitiva. (Depois eu mostro também que, além de ordem parcial, é de fato uma ordem total/linear em .)
Passo 2
Provar reflexividade. Primeiro explico o conceito: uma relação
em um conjunto
é reflexiva se, para todo
, valem
ou, em notação de desigualdade,
. No nosso caso isso significa verificar que, para todo
, vale
.
Prova concreta: tome qualquer
. Escolha
. Observa-se que
e
logo, pela definição que usamos, existe
(especificamente
) tal que
. Portanto
. Conclusão:
é reflexiva em
.
Comentário prático: o número
é o “testemunho” que garante a reflexividade — sempre podemos somar zero e obter o mesmo número.
Passo 3
Provar antissimetria. Conceito: uma relação
é antissimétrica se, sempre que
e
, então
. Para
precisamos mostrar: se
e
então
.
Prova concreta: suponha
com
e
. Pelas definições, existem
tais que
Substituindo a primeira na segunda:
Reagrupando:
Agora, em
a soma de dois números não negativos só pode ser zero se ambos forem zero. Logo
e
. Com
da primeira equação obtemos
. Portanto
é antissimétrica.
Explicação didática: a ideia é que, se você pode ir de
a
somando algo não negativo e também voltar de
a
somando algo não negativo, essas “somas extras” têm de ser nulas — logo os dois são o mesmo número.
Passo 4
Provar transitividade. Conceito:
é transitiva se, sempre que
e
, então
. Para
precisamos: se
e
então
.
Prova concreta: suponha
com
e
. Então existem
tais que
Substituindo a primeira na segunda obtemos
Como
, pela definição isso mostra que
. Portanto
é transitiva.
Pequena dica prática: ao compor duas desigualdades do tipo
e
basta somar os “excedentes”
e
para obter o excedente total de
até
.
Passo 5
Conclusão parcial: como já demonstramos reflexividade, antissimetria e transitividade, segue que
é uma relação de ordem (isto é, uma ordem parcial) em
.
Passo 6
Mostrar que a ordem é, na verdade, total (linear). Definição: uma ordem é total se, para quaisquer
, vale
ou
. Vou provar isso rapidamente porque é uma propriedade útil para provas na prática.
Prova prática: tome
. Considere a diferença
vista como número inteiro. Há duas possibilidades: ou
ou
. Se
então
e
, logo
. Se
então
, isto é,
e então
, logo
. Portanto para quaisquer
um dos dois relacionamentos vale — a ordem é total.
Comentário: essa argumentação usa que os inteiros são totalmente ordenados; restringindo essa ordem aos naturais obtemos uma ordem total em
.
Passo 7
Exemplos rápidos para fixar a intuição:
-
porque (aqui ). -
porque não existe com . - Se
e então pelo que vimos (teste da antissimetria com ).
Resposta
A relação
em
é reflexiva, antissimétrica e transitiva, portanto é uma relação de ordem; além disso, é uma ordem total (linear) em
.