Explique, com suas palavras, a diferença entre um conjunto parcialmente ordenado e um conjunto totalmente ordenado. Dê um exemplo de um conjunto (e a ordem!) que é parcialmente ordenado mas não é totalmente ordenado.
Passo 1
O que o enunciado pede: explicar a diferença entre um conjunto parcialmente ordenado e um conjunto totalmente ordenado; e dar um exemplo concreto de um conjunto (e a ordem) que é parcialmente ordenado mas não é totalmente ordenado.
Informações dadas: nenhuma específica além do pedido; vou escolher um exemplo simples e intuitivo para mostrar a diferença.
Informações dadas: nenhuma específica além do pedido; vou escolher um exemplo simples e intuitivo para mostrar a diferença.
Passo 2
Definição de conjunto parcialmente ordenado (com explicação): um conjunto com uma relação de ordem parcial é um par
onde
é um conjunto e
é uma relação binária em
que satisfaz três propriedades. Vou escrever cada propriedade e explicar o que significa.
Reflexividade: para todo
vale
.
Explicação: cada elemento está relacionado consigo mesmo; isso evita esquisitices tipo “ninguém está ordenado com ele mesmo”.
Explicação: cada elemento está relacionado consigo mesmo; isso evita esquisitices tipo “ninguém está ordenado com ele mesmo”.
Antissimetria: para todos
, se
e
então
.
Explicação: se dois elementos estão mutuamente relacionados, eles têm que ser o mesmo elemento. Isso impede que elementos distintos fiquem “empatados” como se fossem iguais.
Explicação: se dois elementos estão mutuamente relacionados, eles têm que ser o mesmo elemento. Isso impede que elementos distintos fiquem “empatados” como se fossem iguais.
Transitividade: para todos
, se
e
então
.
Explicação: a ordem deve “passar adiante”: se vem antes de
e
vem antes de
, então
vem antes de
.
Explicação: a ordem deve “passar adiante”: se
Quando uma relação
tem essas três propriedades, dizemos que
é um conjunto parcialmente ordenado (ou poset, de “partially ordered set”).
Passo 3
Definição de conjunto totalmente ordenado (com explicação): um conjunto totalmente ordenado (ou ordenação linear) é um poset
que, além das três propriedades anteriores, satisfaz a propriedade de comparabilidade (ou totalidade):
Comparabilidade (totalidade): para todo
vale
ou
(ou ambos, no caso
).
Explicação: quaisquer dois elementos são comparáveis — não existem pares de elementos “incomensuráveis” ou “incomparáveis”. Em uma ordem total, você sempre consegue dizer qual dos dois é menor ou maior (ou que são iguais).
Explicação: quaisquer dois elementos são comparáveis — não existem pares de elementos “incomensuráveis” ou “incomparáveis”. Em uma ordem total, você sempre consegue dizer qual dos dois é menor ou maior (ou que são iguais).
Resumo intuitivo: toda ordem total é uma ordem parcial com o extra de que não há elementos incomparáveis; uma ordem parcial permite que existam elementos que não se relacionam nem numa direção nem na outra.
Passo 4
Escolhi um exemplo simples e visual: o conjunto das partes de
, ou seja a família
, com a relação de inclusão
. Vou listar os elementos (peguei estes dados do exemplo escolhido):
A ordem que considero é a inclusão de conjuntos, ou seja o par
.
Passo 5
Vou verificar passo a passo que
é uma ordem parcial em
.
Reflexividade: para todo
temos
porque todo conjunto é subconjunto de si mesmo. Ex.:
. Portanto reflexividade ok.
Antissimetria: se
e
então
. Explicação: isso é uma propriedade geral de conjuntos (se cada elemento de
está em
e vice-versa, os conjuntos têm exatamente os mesmos elementos). Ex.: se
e
então teríamos igualdade — mas aqui o segundo não é verdadeiro; quando os dois são verdadeiros isso força igualdade. Portanto antissimetria ok.
Transitividade: se
e
então
. Isso também é uma propriedade padrão de inclusão de conjuntos. Portanto transitividade ok.
Concluímos que
é um poset (uma ordem parcial).
Passo 6
Agora mostro que essa ordem NÃO é total. Preciso encontrar dois elementos
tais que nem
nem
.
Escolho
e
(ambos estão na lista de
). Verifico:
? Não — porque
.
? Não — porque
.
Como há pelo menos um par de elementos incomparáveis, a propriedade de comparabilidade falha. Logo
não é uma ordem total.
Passo 7
Interpretação final e dica de prova para a prova (um conselho prático): para mostrar que algo é ordem parcial, prove as três propriedades (reflexiva, antissimétrica, transitiva) uma por uma, dando argumentos simples como fiz aqui. Para mostrar que NÃO é ordem total, basta encontrar um exemplo concreto de dois elementos incomparáveis (como
e
acima). Esse contraexemplo é a forma mais direta e rápida em prova.
Resposta
A diferença: um poset
satisfaz reflexividade, antissimetria e transitividade; um conjunto totalmente ordenado é um poset que, além disso, satisfaz comparabilidade: para todo
vale
ou
.
Exemplo: é parcialmente ordenado, mas não é totalmente ordenado, pois
e
são incomparáveis (nem
nem
).
Exemplo: