What is Order relation?

Example 1.34

$(\R, \leq)$ is totally ordered. $(\mathcal{P}(E), \subseteq)$ is partially ordered as soon as $E$ has two elements: $\{a\}$ and $\{b\}$ are not comparable. The subset $A = \{\{a\}, \{b\}\}$ of $\mathcal{P}(\{a,b\})$ has no greatest element, yet has an upper bound $\{a, b\}$: the distinction between greatest elements and upper bounds returns, for $\R$, in Chapter 10.

Example 1.35 (Two orders on the grid $\N^2$)

On pairs of naturals, compare componentwise: $(a, b) \preceq (a', b')$ when $a \leq a'$ and $b \leq b'$ (the product order). This is an order — each axiom is inherited coordinate by coordinate — but a partial one: $(1, 3)$ and $(2, 0)$ are incomparable. Now compare like a dictionary: $(a, b) \preceq_{\mathrm{lex}} (a', b')$ when $a < a'$, or $a = a'$ and $b \leq b'$ (the lexicographic order). Transitivity requires a two-case check but holds, and any two pairs are now comparable: the order is total. The two orders rank the same set differently — $(0, 100) \preceq_{\mathrm{lex}} (1, 0)$ though the product order says nothing — a reminder that an order is a structure one chooses, not a property of the set. Lexicographic comparison is also the standard trick for turning several sorting criteria into one.

Example 1.7 (Order of quantifiers)

The order of different quantifiers matters:

In the first statement $y$ may depend on $x$; in the second, one single $y$ must work for all $x$. Two identical quantifiers, on the other hand, always commute.