Defina e dê um exemplo:
de uma relação de ordem parcial (que não é total) e total.
de uma relação de ordem parcial (que não é total) e total.
Passo 1
O enunciado pede para definirmos dois tipos de relações de ordem em um conjunto:
- uma ordem parcial que não seja total, e
- uma ordem total (também chamada de ordem linear).
O conteúdo é teoria de relações parciais e ordens, e precisamos usar as definições de reflexividade, antissimetria, transitividade e, no caso da ordem total, a propriedade de comparabilidade.
Passo 2
Definimos relação de ordem parcial em um conjunto
como uma relação
que satisfaz, para todo
:
- Reflexividade:
. - Antissimetria:
. - Transitividade:
.
Se existir pelo menos um parcom tal que nem nem valem, dizemos que a ordem não é total.
Exemplo: seja
e defina
.
Então é reflexiva, antissimétrica e transitiva, mas
e
são incomparáveis (
e
), logo não é total.
Então
Passo 3
Definimos relação de ordem total (ou linear) como uma relação de ordem parcial que, além de satisfazer reflexividade, antissimetria e transitividade, também satisfaz a comparabilidade:
Isto é, quaisquer dois elementos são comparáveis.
Exemplo clássico: no conjunto dos inteiros , tomar a relação “
” define uma ordem total, pois para quaisquer
sempre vale
ou
.
Exemplo clássico: no conjunto dos inteiros
Resposta
Relação de ordem parcial (não total):
Definição: relação que é reflexiva, antissimétrica e transitiva, mas existe pelo menos um par
com
não comparável.
Exemplo: .
Definição: relação
Exemplo:
Relação de ordem total:
Definição: relação de ordem parcial que também satisfaz comparabilidade ( ,
ou
).
Exemplo: .
Definição: relação de ordem parcial que também satisfaz comparabilidade (
Exemplo: