Ordens parciais e diagramas de Hasse

Ordens

Uma ordem parcial é reflexiva, antissimétrica e transitiva. Uma ordem total exige ainda quaisquer $a,b$ comparáveis.

• A divisibilidade em $\mathbb N^+$ e a inclusão em $\mathcal P(X)$ são parciais. Em $\mathbb Z$, a divisibilidade não é antissimétrica, pois $2\mid-2$ e $-2\mid2$.
• Uma ordem estrita é irreflexiva e transitiva; também impede pares opostos.
• Escreve $a\prec b$ para $a\preceq b$ com $a\ne b$. Juntar a identidade recupera a ordem não estrita.
• Uma boa ordem é total e dá um mínimo a todo o subconjunto não vazio. $\mathbb N$ com $\le$ é bem ordenado; $\mathbb Z$ não é.

“Ordem total” compara todos os pares; “relação total” dá um destino a cada origem. A identidade $\operatorname{id}_A$ é uma relação total e uma ordem parcial, mas em $A=\{a,b\}$ deixa $a$ e $b$ incomparáveis, por isso não é uma ordem total. Uma ordem pode nem ser uma função.

Hasse

Num diagrama de Hasse finito omitem-se os laços e as setas transitivas, com os elementos menores por baixo. Há ligação quando há cobertura: $a\prec b$ sem nada entre. Lê o diagrama por percursos sempre a subir.

Elemento	Condição dos outros elementos
Minimal	nenhum elemento distinto abaixo
Mínimo	abaixo de todos os elementos
Maximal	nenhum elemento distinto acima
Máximo	acima de todos os elementos

O mínimo e o máximo, se existem, são únicos. Uma ordem finita não vazia tem minimais e maximais, mas pode não ter mínimo nem máximo. Numa ordem total, um elemento minimal é mínimo.

Ao restringir a ordem, conserva as comparações e recalcula as coberturas. Apagar vértices do desenho perde essas coberturas:

Ínfimo e supremo

Um minorante fica abaixo de todo o conjunto $S$; um majorante fica acima. Ambos pertencem ao conjunto ambiente $A$, podendo estar fora de $S$.

• O ínfimo é o maior minorante; o supremo é o menor majorante.
• Nos divisores de 12, $\inf\{4,6\}=2$ e $\sup\{4,6\}=12$.
• Se o ambiente for $\{3,4,6,12\}$, o conjunto $\{4,6\}$ não tem minorante. O mdc 2 está fora do ambiente.

Produto

A ordem lexicográfica decide pela primeira componente e usa a segunda só em caso de empate. Com fatores totais é uma ordem total:

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

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

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

$(1,100)\prec_{\mathrm{lex}}(2,0)$, mas estes pares são incomparáveis por componentes. No produto, encadeia cada componente no seu sentido.

Provas de ordens e leitura de Hasse.