Orders

Definition 1.4.1. A relation $$<$$ on a set $$A$$ is an order on $$A$$ if:

(Irreflexivity) $\forall x\in A \ \neg(x<x),$
(Asymmetry) $\forall x,y \in A\ (x<y\Rightarrow \neg(y<x)),$
(Transitivity) $\forall x,y,z\in A\ ((x<y \land y<z) \Rightarrow x<z).$

The ordered pair $$(A,<)$$ is called an ordered set.

Example 1.4.2. Suppose that $$A$$ and $$B$$ are two sets with orders $$<_A$$ and $$<_B$$ respectively. A relation $<_{\text{lex}}$ on $A\times B$ is the lexicographic order on $A\times B$ if:

\[(a,b)<_{\mathrm{lex}}(a',b') \quad\Longleftrightarrow\quad a<_A a' \lor (a=a' \land b<_B b').\]

Definition 1.4.3. An order $$<$$ on a set $$A$$ is a total order on $$A$$ if it has comparability:

\[\forall x,y\in A\ (x\neq y\Rightarrow ((x<y)\lor (y<x))).\]

Definition 1.4.4. Let $$(A,<)$$ be an ordered set.
$a\in A$ is a least element of $$A$$ if

\[\forall x\in A\ (a\le x).\]

$a\in A$ is a minimal element of $$A$$ if

\[\forall x\in A\ (x\le a \Rightarrow x=a).\]

So ‘least’ means ‘smaller than everything else’, while ‘minimal’ means ‘nothing else is smaller’.

Proposition 1.4.5. Let $$(A,<)$$ be an ordered set.

If there exists a least element of $$A,$$ then it is minimal and it is unique.
If $$<$$ is a total order, then any minimal element is the least element.

Proof.
(1) Let $$a$$ be a least element if $$A.$$ Then, for all $$x,$$ we have $a\le x.$ If $x\le a,$ then $$x=a,$$ since $$<$$ is asymmetric. Hence $$a$$ is minimal.
Suppose that $a'\in A$ is a least element. Then we have $a\le a'$ and $a'\le a,$ so that $$a=a'.$$ Thus $$a$$ is the unique element.
(2) Let $$a$$ be a minimal element. Then we have $$a<x$$ if $x\ne a.$ Also, for all $x\in A,$ if $x\ne a$ then $$x<a$$ or $$a<x,$$ since $$<$$ is comparable. Consequently, for all $x\in A,$ we have $a\le x.$ Therefore $$a$$ is the least element. $\square$

Definition 1.4.6. An element $$a$$ of the ordered set $$(A,<)$$ is greatest if $x\le a$ for all $x\in A;$ and $$a$$ is maximal if $a\le x$ implies $$x=a.$$

Definition 1.4.7. Let $$(A,<)$$ be an ordered set. If $a_1,a_2\in A$ and $$a_1<a_2,$$ an open interval $$(a_1,a_2)$$ is the set defined by

\[(a_1,a_2) = \lbrace x\in A : a_1<x<a_2 \rbrace.\]

If this set is empty, $$a_1$$ is called the immediate predecessor of $$a_2,$$ and $$a_2$$ is called the immediate successor of $$a_1.$$

Definition 1.4.8. Let $$A$$ and $$B$$ are two sets with order relations $$<_A$$ and $$<_B$$ respectively. $$A$$ and $$B$$ have the same order type if there exists a bijective function $f:A\to B$ such that

\[a_1<_Aa_2 \Longrightarrow f(a_1)<_B f(a_2).\]

Definition 1.4.9. Let $$(A,<)$$ be an ordered set, and $A_0\subseteq A.$ If there is an element $a\in A$ such that $x\leq a$ for all $x\in A_0,$ $$A_0$$ is bounded above and $$a$$ is an upper bound for $$A_0.$$ If $a\in A_0,$ then $$a$$ is the greatest element of $$A_0.$$
Similarly, if there is an element $a\in A$ such that $a\leq x$ for all $x\in A_0,$ $$A_0$$ is bounded below and $$a$$ is a lower bound for $$A_0.$$ If $a\in A_0,$ then $$a$$ is the least element of $$A_0.$$

Definition 1.4.10. Let $$(A,<)$$ be an ordered set and $A_0\subseteq A.$
Suppose that $$A_0$$ is bounded above and $$a$$ is an upper bound for $$A_0.$$ If $$a'<a$$ implies that $$a'$$ is not an upper bound for $$A_0,$$ then $$a$$ is the least upper bound or the supremum for $$A_0.$$ In this case we write

\[a = \sup {A_0}.\]

We now suppose that $$A_0$$ is bounded below and $$a$$ is a lower bound for $$A_0.$$ If $$a<a'$$ implies that $$a'$$ is not a lower bound for $$A_0,$$ then $$a$$ is the greatest lower bound or the infimum for $$A_0.$$ In this case we write

\[a = \inf {A_0}.\]

Lemma 1.4.11. Let $$(A,<)$$ be an ordered set and $A_0\subseteq A.$ Suppose that $$A_0$$ is bounded above and $a=\sup A_0.$ Then for all $\varepsilon>0,$

\[\exists x \in A_0\ (a-\varepsilon<x).\]

Proof. If there are no elements in the interval $(a-\varepsilon, a],$ then $a-\varepsilon$ is an upper bound for $$A_0,$$ which is a contradiction of the premise that $$a$$ is the supremum. Therefore, there exists $x\in A_0$ such that $a-\varepsilon<x.$ $\square$

Definition 1.4.12. An ordered set $$(A,<)$$ has the least-upper-bound property if, for every nonempty subset $$A_0$$ that is bounded above, there exists $a\in A$ such that $a = \sup {A_0}.$
Similarly, $$(A,<)$$ has the greatest-lower-bound property if, for every nonempty subset $$A_0$$ that is bounded below, there exists $a\in A$ such that $a = \inf {A_0}.$

Theorem 1.4.13. Suppose that $$(A,<)$$ is an ordered set with the least-upper-bound property, $$A_0$$ is a nonempty subset of $$A,$$ and $$A_0$$ is bounded below. Let $$L$$ be the set of all lower bounds for $$A_0.$$ Then

\[\exists a\in A \ (a = \sup L) \qquad \text{and} \qquad a = \inf A_0 .\]

Proof. Since $$A_0$$ is bounded below, $$L$$ is not empty. Since every $y\in A_0$ is an upper bound for $$L,$$ $$L$$ is bounded above. Given that $$A$$ has the least-upper-bound property, there exists $x\in L$ such that $x=\sup L;$ we let $a = \sup L.$
Since every $y\in A_0$ is an upper bound for $$L$$ and $$a$$ is the least upper bound for $$L,$$ $$a$$ is a lower bound for $$A_0.$$
Let $$x$$ be any lower bound of $$A_0.$$ By the definition of $$L,$$ $x\in L.$ Since $a=\sup L,$ $x\le a.$ Consequently, $$a$$ is the greatest lower bound for $$A_0.$$ $\square$

Exercises

Exercise 1. Prove that the lexicographic order is an order relation.

Proof. Assume that $$<_A$$ is an order relation on $$A,$$ $$<_B$$ is an order relation on $$B,$$ and $<_{\mathrm{lex}}$ is the lexicographic order on $A\times B.$ Firstly, to check whether the lexicographic order is irreflexive, we determine the truth value of the statement $(a,b)<_{\mathrm{lex}}(a,b).$ It is equivalent to

\[a<_A a \lor \bigl(a=a \land b<_B b\bigr).\]

Since $$<_A$$ and $$<_B$$ are irreflexive, both alternatives are false so that $<_{\mathrm{lex}}$ is irreflexive.
We now check the comparability of $<_{\mathrm{lex}}.$ If $(a,b)\neq (a',b')$ then $a\neq a',$ or $$a=a'$$ and $b\neq b'.$ We first suppose that $a\neq a'.$ Since $$<_A$$ is comparable, $$a<_Aa'$$ or $$a'<_Aa.$$ If $$a<_Aa'$$ then $(a,b)<_{\mathrm{lex}}(a',b').$ Similarly, if $$a'<_Aa$$ then $(a',b')<_{\mathrm{lex}}(a,b).$ We now suppose that $$a=a'$$ and $b\neq b'.$ Since $$<_B$$ is comparable, $$b<_Bb'$$ or $$b'<_Bb.$$ If $$b<_Bb'$$ then $(a,b)<_{\mathrm{lex}}(a',b').$ If $$b'<_Bb$$ then $(a',b')<_{\mathrm{lex}}(a,b).$ Therefore $<_{\mathrm{lex}}$ is comparable.
Finally we check the transitivity. We suppose that $(a,b)<_{\mathrm{lex}} (a',b')$ and $(a',b')<_{\mathrm{lex}} (a'',b'').$ It splits into four cases. Firstly, if $$a<_A a'$$ and $$a' <_A a''$$ then $$a<_Aa''.$$ SecondIy, if $$a=a'$$ and $$a' <_A a''$$ then $$a<_Aa''.$$ Thirdly, if $$a' = a''$$ then $$a<_Aa''.$$ Lastly, if $$a=a'$$ and $$b<_B b',$$ and $$a'=a''$$ and $$b'<_B b'',$$ then $$a=a''$$ and $$b<_B b''.$$ Therefore $<_{\mathrm{lex}}$ is transitive.
Since $<_{\mathrm{lex}}$ is irreflexive, comparable, and transitive, $<_{\mathrm{lex}}$ itself is an order relation on $A\times B.$

Exercise 2. Define a relation on $\mathbb R^2$ by setting $\left(x_0, y_0\right)<\left(x_1, y_1\right)$ if either $$y_0-x_0^2<y_1-x_1^2,$$ or $$y_0-x_0^2=y_1-x_1^2$$ and $$x_0<x_1.$$ Show that this is an order relation on $\mathbb R^2,$ and describe it geometrically.

Proof. Define $F:\mathbb R^2\to \mathbb R^2$ by

\[F(x,y)=(y-x^2,x).\]

Then, by the definition of the given relation,

\[(x_0,y_0)<(x_1,y_1) \quad\Longleftrightarrow\quad F(x_0,y_0)<_{\mathrm{lex}}F(x_1,y_1).\]

Thus the relation $$<$$ on $\mathbb R^2$ is the relation obtained by pulling back the lexicographic order through $$F$$ . We first observe that $$F$$ is injective. Suppose $$F(x_0,y_0)=F(x_1,y_1).$$ Then $$(y_0-x_0^2,x_0)=(y_1-x_1^2,x_1).$$ Hence $$x_0=x_1$$ , and therefore $$y_0-x_0^2=y_1-x_1^2$$ implies $$y_0=y_1$$ . Thus $$(x_0,y_0)=(x_1,y_1)$$ , so $$F$$ is injective.
We now prove that $$<$$ is an order relation. First, $$<$$ is irreflexive. For any $(x,y)\in\mathbb R^2$ , $$F(x,y)=F(x,y),$$ so $F(x,y)<_{\mathrm{lex}}F(x,y)$ is false because $<_{\mathrm{lex}}$ is irreflexive. Therefore $$(x,y)<(x,y)$$ is false, and $$<$$ is irreflexive.
Next, $$<$$ is transitive. Suppose $$(x_0,y_0)<(x_1,y_1)$$ and $$(x_1,y_1)<(x_2,y_2).$$ Then $F(x_0,y_0)<_{\mathrm{lex}}F(x_1,y_1)$ and $F(x_1,y_1)<_{\mathrm{lex}}F(x_2,y_2).$ Since $<_{\mathrm{lex}}$ is transitive, $F(x_0,y_0)<_{\mathrm{lex}}F(x_2,y_2).$ Therefore $$(x_0,y_0)<(x_2,y_2).$$ Thus $$<$$ is transitive.
It remains to check comparability. Let $$(x_0,y_0)$$ and $$(x_1,y_1)$$ be distinct points of $\mathbb R^2$ . Since $$F$$ is injective, $F(x_0,y_0)\neq F(x_1,y_1).$ Since $<_{\mathrm{lex}}$ is a strict total order on $\mathbb R^2$ , $F(x_0,y_0)<_{\mathrm{lex}}F(x_1,y_1)$ or $F(x_1,y_1)<_{\mathrm{lex}}F(x_0,y_0).$ Therefore $$(x_0,y_0)<(x_1,y_1)$$ or $$(x_1,y_1)<(x_0,y_0).$$ Hence $$<$$ is a strict total order on $\mathbb R^2$ .
Geometrically, the ordered pairs correspond to the points on a plane with Cartesian coordinates system. The order first compares the value of $$y-x^2$$ . Given that the point $$(x_0,y_0)$$ is on the parabola $$y=x^2+c,$$ where $$c=y_0-x_0^2,$$ the order is understood to have points on lower parabola $$y=x^2+c_0$$ first, and points on higher parabola $$y=x^2+c_1$$ next, when $$c_0<c_1.$$ In the next step, the points that lie on the same parabola are ordered by their $$x$$ -coordinates from left to right.

References

Munkres, J. R. (2000). Topology (2nd ed.). Pearson.
Rudin, W. (1976). Principles of mathematical analysis (3rd ed.). McGraw-Hill Education.
Cameron, P. J. (1998). Sets, logic and categories. Springer. https://doi.org/10.1007/978-1-4471-0589-3

Semantics

1.4. Orders

Exercises

References