Wat is Ordeningsrelatie?

Voorbeeld 1.34

$(\R, \leq)$ is totaal geordend. $(\mathcal{P}(E), \subseteq)$ is partieel geordend zodra $E$ twee elementen heeft: $\{a\}$ en $\{b\}$ zijn onvergelijkbaar. De deelverzameling $A = \{\{a\}, \{b\}\}$ van $\mathcal{P}(\{a,b\})$ heeft geen grootste element, maar wel een bovengrens $\{a, b\}$: het onderscheid tussen grootste elementen en bovengrenzen keert voor $\R$ terug in Hoofdstuk 10.

Voorbeeld 1.35 (Twee ordes op het rooster $\N^2$)

Vergelijk paren natuurlijke getallen componentsgewijs: $(a, b) \preceq (a', b')$ wanneer $a \leq a'$ en $b \leq b'$ (de productorde). Dit is een orde — elk axioma wordt coördinaat voor coördinaat overgeërfd — maar een partiële: $(1, 3)$ en $(2, 0)$ zijn onvergelijkbaar. Vergelijk nu als in een woordenboek: $(a, b) \preceq_{\mathrm{lex}} (a', b')$ wanneer $a < a'$, of $a = a'$ en $b \leq b'$ (de lexicografische orde). Transitiviteit vraagt een gevalsonderscheid, maar geldt, en nu zijn elke twee paren vergelijkbaar: de orde is totaal. Beide ordes rangschikken dezelfde verzameling verschillend — $(0, 100) \preceq_{\mathrm{lex}} (1, 0)$ terwijl de productorde er niets over zegt — een herinnering dat een orde een structuur is die je kiest en geen eigenschap van de verzameling. Lexicografisch vergelijken is bovendien de standaardtruc om verscheidene sorteercriteria tot één criterium samen te smeden.

Voorbeeld 1.7 (Volgorde van de kwantoren)

De volgorde van verschillende kwantoren doet ertoe:

In de eerste uitspraak mag $y$ van $x$ afhangen; in de tweede moet één enkele $y$ het voor alle $x$ doen. Twee gelijke kwantoren mogen daarentegen altijd van plaats wisselen.