Ordens parciais e diagramas de Hasse

Ordenar não exige comparar todos os pares. Na divisibilidade, 2 está abaixo de 6 porque $2\mid6$, mas nem $2\mid3$ nem $3\mid2$. Uma ordem parcial conserva esses pares incomparáveis. Assumimos transitividade e quantificadores das lições de relações.

Ordens parciais

Uma ordem parcial é uma relação reflexiva, antissimétrica e transitiva. O par $(A,\preceq)$ chama-se conjunto parcialmente ordenado, ou poset.

São exemplos $(\mathbb Z,\le)$, $(\mathbb N^+,\mid)$ e $(\mathcal P(X),\subseteq)$. A restrição aos inteiros positivos no exemplo de divisibilidade importa: em $\mathbb Z$, $2\mid-2$ e $-2\mid2$, mas $2\ne-2$, o que viola antissimetria.

Dois elementos $a,b$ são comparáveis se $a\preceq b$ ou $b\preceq a$. Uma ordem é total se todos os pares são comparáveis. $\le$ nos inteiros é total; inclusão entre subconjuntos não é total em geral, pois $\{x\}$ e $\{y\}$ podem ser incomparáveis.

Não confundas ordem total com relação total. Uma relação total associa cada origem a pelo menos um destino. Uma ordem total compara todos os pares. Uma ordem parcial reflexiva já é uma relação total, mas pode não ser uma ordem total.

Ordens estritas e boa ordenação

Uma ordem estrita é irreflexiva e transitiva. É também antissimétrica: se $a\prec b$ e $b\prec a$, transitividade daria $a\prec a$, contrariando irreflexividade. A definição da cadeira enumera as três propriedades; a antissimetria é redundante nesse caso.

De uma ordem parcial obtemos $a\prec b$ se $a\preceq b$ e $a\ne b$. No sentido inverso, acrescentamos a identidade à ordem estrita. $<$ nos inteiros é uma ordem estrita total.

Uma boa ordem é uma ordem total em que todo o subconjunto não vazio tem mínimo. $(\mathbb N,\le)$ é bem ordenado; $(\mathbb Z,\le)$ não é, pois o próprio $\mathbb Z$ não tem mínimo. Ter um mínimo no conjunto inteiro não chega: $[0,1]$ tem mínimo, mas o subconjunto $(0,1]$ não tem.

Diagramas de Hasse e elementos especiais

Num diagrama de Hasse de uma ordem finita:

1. Retiramos os laços, que a reflexividade já garante.
2. Retiramos as ligações obtidas por transitividade.
3. Colocamos os menores por baixo dos maiores e desenhamos as ligações sem pontas de seta.

Uma ligação de $a$ a $b$ significa que $b$ cobre $a$: $a\prec b$ sem nenhum elemento estritamente entre eles. Para os divisores positivos de 12, ordenados por divisibilidade:

$1\mid12$, apesar de não haver ligação direta entre 1 e 12. Há um percurso sempre a subir. Uma linha que desce e depois sobe não prova comparabilidade.

Um elemento é minimal se não tem nenhum elemento distinto abaixo dele. É mínimo se está abaixo de todos. Um elemento é maximal se não tem nenhum elemento distinto acima; é máximo se está acima de todos.

Nos divisores de 12, 1 é mínimo e 12 é máximo. Se restringirmos a $A=\{2,3,4,6\}$, os minimais são 2 e 3 e os maximais são 4 e 6. Não há mínimo nem máximo. Repara que 2 não está abaixo de 3 e 6 não está acima de 4.

Um mínimo ou máximo, quando existe, é único pela antissimetria. Uma ordem finita não vazia tem pelo menos um minimal e um maximal, mas pode ter vários. Numa ordem total, um minimal é necessariamente mínimo, porque é comparável com todos os outros.

Restrição e novas coberturas

Para restringir a ordem a um subconjunto, conservamos todas as comparações entre os elementos que ficam e recalculamos as coberturas. Apagar vértices e as linhas incidentes do desenho pode perder comparações.

Nos divisores de 12, $2\mid12$ aparece pelos percursos $2,4,12$ e $2,6,12$. Ao restringir a $\{2,3,12\}$, retiramos 4 e 6, mas $2\mid12$ continua a valer. As novas coberturas são $2-12$ e $3-12$. Os minimais são 2 e 3; nenhum é mínimo porque são incomparáveis. A altura de dois vértices no papel, por si só, não decide a comparação.

Minorantes e majorantes

Para $S\subseteq A$, um minorante está abaixo de todos os elementos de $S$; um majorante está acima de todos. Estes elementos têm de pertencer a $A$, mas não necessariamente a $S$.

O ínfimo é o maior minorante. O supremo é o menor majorante. Nos divisores de 12, para $S=\{4,6\}$, os minorantes são 1 e 2 e o ínfimo é 2. O único majorante é 12, que é o supremo.

Se mudarmos o conjunto ordenado para $\{3,4,6,12\}$, o mesmo subconjunto $\{4,6\}$ deixa de ter minorantes. O mdc 2 não pertence ao conjunto, por isso não pode ser o seu ínfimo: o conjunto ambiente faz parte da pergunta.

Ordem lexicográfica e ordem por componentes

Em pares, a ordem lexicográfica compara primeiro a primeira componente. Só compara a segunda quando as primeiras são iguais:

$$(a,b)\preceq_{\mathrm{lex}}(c,d) \Longleftrightarrow a\prec c\lor(a=c\land b\preceq d).$$

Nas ordens habituais dos naturais, $(1,100)\prec_{\mathrm{lex}}(2,0)$. Se os fatores são totalmente ordenados, o produto lexicográfico também é totalmente ordenado.

A ordem por componentes exige ambas as comparações:

$$(a,b)\preceq_{\mathrm{prod}}(c,d) \Longleftrightarrow a\preceq c\land b\preceq d.$$

Nesta ordem, $(1,100)$ e $(2,0)$ são incomparáveis. Não troques as duas definições ao provar propriedades de uma relação em $A\times B$.

Provar uma ordem num produto

Se $\preceq$ é uma ordem parcial em $A$ e $\prec$ uma ordem estrita em $B$, define:

$$(a,b)T(c,d)\Longleftrightarrow a\preceq c\land d\prec b.$$

$T$ é irreflexiva porque $b\not\prec b$. Se $(a,b)T(c,d)$ e $(c,d)T(e,f)$, temos $a\preceq c\preceq e$ e $f\prec d\prec b$. Pelas transitividades, $a\preceq e$ e $f\prec b$, logo $(a,b)T(e,f)$. Portanto, $T$ é uma ordem estrita. A inversão na segunda componente não estraga transitividade; só muda o sentido em que a encadeamos.

Quando uma relação é função

Uma ordem também é uma relação, mas normalmente não é uma função. Em $\{1,2,3\}$ com $\le$, o elemento 1 relaciona-se com 1, 2 e 3. Uma função tem de escolher exatamente um destino por origem.

A identidade é ao mesmo tempo ordem parcial e função bijetiva. Por isso, “nenhuma ordem é função” também é falso. As condições de função e o papel do domínio e do contradomínio estão na página seguinte.