O que é Relação de ordem?

Exemplo 1.34

$(\R, \leq)$ é totalmente ordenado. $(\mathcal{P}(E), \subseteq)$ é parcialmente ordenado assim que $E$ tem dois elementos: $\{a\}$ e $\{b\}$ não são comparáveis. O subconjunto $A = \{\{a\}, \{b\}\}$ de $\mathcal{P}(\{a,b\})$ não tem maior elemento, mas tem uma cota superior $\{a, b\}$: a distinção entre maior elemento e cota superior reaparece, para $\R$, no Capítulo 10.

Exemplo 1.35 (Duas ordens na grade $\N^2$)

Sobre pares de naturais, compare coordenada a coordenada: $(a, b) \preceq (a', b')$ quando $a \leq a'$ e $b \leq b'$ (a ordem produto). Isso é uma ordem — cada axioma é herdado coordenada a coordenada — mas parcial: $(1, 3)$ e $(2, 0)$ são incomparáveis. Agora compare como num dicionário: $(a, b) \preceq_{\mathrm{lex}} (a', b')$ quando $a < a'$, ou $a = a'$ e $b \leq b'$ (a ordem lexicográfica). A transitividade exige uma verificação em dois casos, mas vale, e quaisquer dois pares são agora comparáveis: a ordem é total. As duas ordens hierarquizam o mesmo conjunto de modos diferentes — $(0, 100) \preceq_{\mathrm{lex}} (1, 0)$, ainda que a ordem produto nada diga — lembrete de que uma ordem é uma estrutura que se escolhe, e não uma propriedade do conjunto. A comparação lexicográfica é também o truque padrão para reduzir vários critérios de ordenação a um só.

Exemplo 1.7 (Ordem dos quantificadores)

A ordem de quantificadores distintos importa:

Na primeira proposição $y$ pode depender de $x$; na segunda, um único $y$ deve servir para todo $x$. Já dois quantificadores iguais, esses sempre comutam.