Pedido parcial versus pedido total

Um pedido é apenas uma maneira de saber quando algo é menor que outro. Temos um monte de coisas como números (1,2,3 ...) e uma maneira de compará-los (≤). Podemos dizer que 1 ≤ 2, 2 ≤ 3, 1 ≤ 3, 1 ≤ 1 e assim por diante. Perfeitamente natural.

Os números têm uma ordem total porque, dados dois números, um é sempre menor ou igual ao outro. Não importa quais são os dois números que escolhemos: são iguais ou um é menor. Portanto, um pedido total é igual a ≤ para números.

Uma ordem parcial é aquela em que esse não é o caso. Às vezes, não podemos comparar dois itens: eles não são iguais, menores ou maiores que um ao outro! Veja os livros, por exemplo. Como sou um pouco exigente, sempre empilho meus livros com os maiores por baixo:

No entanto, os livros têm duas dimensões: uma altura e uma largura. E os editores estão perfeitamente felizes em abusar disso! Às vezes, tenho dois livros de tamanhos diferentes, sendo nenhum deles o maior. Um é mais longo, mas o outro é mais amplo.

O que eu faço? Eu não tenho uma boa resposta. Mas ilustra bem a idéia de uma ordem parcial: alguns livros são menores que outros ou iguais em tamanho, mas alguns são diferentes e, no entanto, nem menores nem maiores.

Isenção de responsabilidade: O abaixo é direcionado para a pessoa média (razoavelmente inteligente) que talvez saiba muito pouco sobre matemática e, portanto, encobre algumas formalidades. Se subestimei a capacidade do solicitante, fico feliz em colocar mais rigor.

Vamos começar explicando um pedido total. Uma ordem total pode ser pensada intuitivamente como uma ordem (no sentido não técnico) do conjunto de coisas que estamos considerando - esta vem primeiro, depois essa e assim por diante. Essa intuição desmorona um pouco quando consideramos coleções infinitas de coisas, mas funciona. Por exemplo, as letras têm uma ordem total nelas: A vem primeiro, depois B e C ... As principais propriedades que essa ordem deve ter são: Transitividade - se x vem antes de ye y vem antes de z, então x vem antes de z. Totalidade - x vem antes de y ou y vem antes de x. Assimetria - se x vem antes de y, então y não vem antes de x. (observe: se 'assimetria' ou 'antisimetria' está correta aqui depende de estarmos trabalhando com ordens estritas ou fracas, mas isso realmente não importa e apenas complicaria as coisas para entrar em detalhes).

A ordem total com a qual você provavelmente está mais familiarizado é 'menor que' nos números naturais: 1 é menor que 2, que é menor que 3 e assim por diante. Se desenharmos uma ordem total, ela se parecerá com uma longa linha de objetos (novamente, pelo menos no caso finito).


Agora, pedidos parciais são semelhantes, mas são um pouco mais relaxados. Eles não querem alinhar as coisas em uma ordem fixa e rígida - eles apenas querem que certas coisas venham antes de outras. Eles podem não se importar com o que vem primeiro de x e y, desde que x venha antes de z. Uma ordem parcial ainda deve ser transitiva e assimétrica, mas não precisamos mais da totalidade. Um exemplo de ordem parcial é "é um ancestral de" no conjunto de todos os humanos que já viveram. Meu avô é um ancestral de meu pai, e meu pai é um ancestral de mim, então meu avô é um ancestral de mim (por transitividade). Além disso, como meu pai é um ancestral de mim, eu não sou um ancestral de meu pai (por assimetria). Pode haver pessoas que não são ancestrais uma da outra - como meu pai e minha mãe.

Uma ordem parcial pode não parecer uma linha longa - pode parecer uma árvore ou uma treliça, com locais onde a ordem é dividida ou combinada novamente. Como outro exemplo, o diagrama abaixo mostra os subconjuntos do conjunto \ {x, y, z \}, que são parcialmente ordenados por "é um subconjunto de". \ {z \} é um subconjunto de \ {x, z \} e também é um subconjunto de \ {y, z \}, mas nenhum desses últimos é um subconjunto um do outro. No entanto, cada um é um subconjunto de \ {x, y, z \}.