Seja o conjunto
e a relação
. Mostre que
é uma ordem total em
.
Passo 1
O enunciado dá o conjunto
e a relação
A tarefa é: mostrar que
é uma ordem total em
.
Informações relevantes fornecidas:
Informações relevantes fornecidas:
- Os pares que pertencem a
são exatamente os listados acima. - Queremos verificar as propriedades que definem uma ordem total (ver passos seguintes).
Passo 2
Primeiro vamos lembrar, com calma, o que é uma ordem total. Vou explicar cada conceito e o que significam as variáveis nas definições.
Definição de ordem parcial (uma relação de ordem): uma relação
é uma ordem parcial se satisfaz três propriedades, para todo
:
- Reflexiva:
. Isso significa que todo elemento é relacionado com ele mesmo. Aqui a variável representa um elemento arbitrário de . - Antissimétrica: se
e então . Ou seja, a única forma de ter os dois sentidos é quando os elementos são iguais. - Transitiva: se
e então . As variáveis são elementos quaisquer de .
Definição de ordem total (ou linear): uma ordem parcial
é total se, além das propriedades acima, satisfaz a propriedade de totalidade (ou connex): para todo
vale
ou
. Isso quer dizer que quaisquer dois elementos são comparáveis.
Agora vamos verificar cada propriedade, uma por uma, usando os pares que o enunciado forneceu.
Passo 3
Verificação da reflexividade.
Queremos mostrar que para todo
temos
.
Os elementos de
são
. Na lista de
o enunciado já deu explicitamente os pares
,
e
. Logo, para cada
temos
. Portanto,
é reflexiva.
(Comentário amigo: reflexividade é a parte mais simples — o enunciado já entregou os três pares diagonais.)
Passo 4
Verificação da antissimetria.
Lembrando a definição:
é antissimétrica se sempre que
e
acontece que
.
Vamos analisar os pares não diagonais que aparecem em
: são
,
e
. Para que a antissimetria falhasse existiria algum par de elementos distintos
com ambos
e
.
Verificamos os reversos desses pares:
- O reverso de
é . Esse par NÃO está na lista de . - O reverso de
é . Esse par NÃO está em . - O reverso de
é . Esse par NÃO está em .
Além disso, os únicos pares em
com ambos os elementos iguais são os três diagonais
— nesses casos
e a condição da antissimetria é satisfeita trivialmente.
Como não existe nenhum par com elementos distintos em ambas as direções, concluímos que sempre que
e
necessariamente
. Logo,
é antissimétrica.
Passo 5
Verificação da transitividade.
Definição recapitular:
é transitiva se para quaisquer
, sempre que
e
então
.
Vamos checar todas as possibilidades relevantes. Como
tem só três elementos, podemos olhar os pares em
e ver suas composições:
Pares não diagonais em
:
,
,
. Além desses, temos as diagonais
.
Agora as composições possíveis que podem gerar um novo par são:
-
seguido de : temos e , então pela transitividade deveríamos ter . E, de fato, está em (o enunciado deu esse par). - Composições envolvendo pares reflexivos: por exemplo,
composto com ou com . Essas composições não exigem nenhum par novo porque: - Se
e então o consequente necessário é (que já está presente). - Se
e então o consequente necessário é (que já está presente).
Essas situações são satisfeitas porque todas as diagonais estão em.
- Se
- Outras possíveis composições com os pares não diagonais já listados:
-
só pode ser seguido por um par começando com . O único par em que começa com é , então e implicam (já em ). -
só pode ser seguido por , levando de volta a (já em ). -
pode compor com (resultando em , já em ) ou com (caso 1, já verificado).
Nenhuma composição de pares emexige a presença de um par que não esteja já listado em .
-
Portanto, para todos
as hipóteses
e
implicam
. Assim,
é transitiva.
Passo 6
Verificação da totalidade (comparabilidade/connex).
Definição:
é total se para quaisquer
temos
ou
.
Como
tem três elementos, basta checar as três pares de elementos distintos (as diagonais já satisfazem automaticamente com
):
- Para o par
: (o enunciado dá esse par). Assim, entre e existe comparação. - Para o par
: . Assim, entre e existe comparação. - Para o par
: . Assim, entre e existe comparação.
Em nenhum desses casos falta uma das direções: para cada par de elementos distintos, ao menos uma das duas direções pertence a
. Portanto
é total.
(Comentário amigo: isso significa que todos os elementos são comparáveis numa única cadeia — aqui intuitivamente
está antes de
e
antes de
.)
Passo 7
Conclusão final juntando tudo.
Já mostramos que
é reflexiva (Passo 3), antissimétrica (Passo 4) e transitiva (Passo 5). Então
é uma ordem parcial. Além disso mostramos a propriedade de totalidade (Passo 6): quaisquer dois elementos de
são comparáveis por
. Portanto
é uma ordem total (ou ordem linear) em
.
Uma observação interpretativa útil: a relação descreve a cadeia
, pois
estão em
e não existem as direções contrárias entre elementos distintos.