Sejam
e
dois conjuntos totalmente ordenados pela relação
. Sejam
e
elementos de
, em que está definida a relação
dada por:
Prove que
é uma relação de ordem total em
.
Passo 1
O enunciado define em
a relação lexicográfica
Queremos mostrar que
é ordem total, ou seja, que é reflexiva, antissimétrica, transitiva e connexa (total).
Passo 2
Prova de reflexividade.
Seja . Como em todo conjunto ordenado vale
e também
, temos
Seja
Logo,
é reflexiva.
Passo 3
Prova de antissimetria.
Suponha e
tais que
e
.
Suponha
- De
segue ou e . - De
segue ou e .
Se, então não pode valer , restando e daí . Análogo se . Logo necessariamente .
Com, das condições originais seguem e , ou seja . Assim , isto é . Portanto é antissimétrica.
Passo 4
Prova de transitividade.
Sejam ,
e
com
e
.
Sejam
- Se
e , então , logo . - Se
e com , então , logo . - Se
com e , então , logo . - Se
e com , então e , logo .
Em todos os casos, provando a transitividade.
Passo 5
Prova de connexidade (totalidade).
Para quaisquer e
, como
é totalmente ordenado temos
ou
.
Para quaisquer
- Se
, então . - Se
, como é totalmente ordenado temos ou , daí ou ou . - Se
, então .
Assim para todo parvale ou .
Resposta
A relação
é reflexiva, antissimétrica, transitiva e total, logo é uma ordem total em
.