Order Relations

Dec 20

Nurlan Abiev

The present post we devote to order relations. For preliminaries see our previous post Equivalence Relations. Recall that $\mathbb{R}$ and $\mathbb{N}$ are the sets of real and natural numbers respectively.

1 Partially ordered sets

Definition 1. A partial order on a set $X$ is a relation $R \subseteq X\times X$ satisfying the following conditions for arbitrary $x,y,z \in X$ :
i) $xRx$ (reflexivity);
ii) If $xRy$ and $yRx$ then $y=x$ (anti-symmetry);
iii) If $xRy$ and $yRz$ then $xRz$ (transitivity).

Respectively, given a set $X$ with a chosen partial order $R$ on it we call a partially ordered set.

We often denote a partial order $R$ by the symbol $\preceq$ (do not confuse it with the usual symbol of inequality). Moreover, we denote $x\prec y$ if $x\preceq y$ and $x\ne y$ .

Remark 1. The corresponding definitions of the concepts partial order and equivalence relation are distinguished each from other only with respect to the symmetricity property (compare Definition 1 here with Definition 4 in Equivalence Relations).

Example 1. Examples of partially ordered sets:

i) We can define a partial order on any set $X$ assuming $a\preceq b$ if $a=b$ .

ii) Let $X$ be any given set. Assuming $A\preceq B$ if $A\subseteq B$ , where $A,B$ are subsets of $X$ , we obtain a partial order on the power set $2^X$ (the set of all subsets of $X$ ).

iii) Suppose that $n\preceq m$ means " $n$ divides $m$ ", where $n,m\in \mathbb{N}$ . Then $\preceq$ is a partial order on $\mathbb{N}$ .

iv) For $x,y\in \mathbb{R}$ define $x\preceq y$ if $x\le y$ ( $x$ is smaller than $y$ ). Consequently we obtain a partial order on $\mathbb{R}$ .

v) The following is a partial order on the set of all real valued functions defined on $\mathbb{R}$ :
$f\preceq g$ if $f(t)\le g(t)$ for all $t \in [a,b]$ .

vi) On $\mathbb{R}^2$ we can introduce a partial order putting $(x_1,x_2)\preceq (x_2,y_2)$ if $x_1\le x_2$ and $y_1\le y_2$ .

vii) The alphabetical order of letters $a\preceq \cdots \preceq z$ is a partial order on the English alphabet.

viii) The lexicographical order on the set of English words is a partial order.

Remark 2. Not every relation may be a partial order.

Example 2. On the set of positive integers assume $n\preceq m$ if any prime divisor of $n$ also divides $m$ . Such a relation is not a partial order, since it is not anti-symmetric.
Indeed we have true expressions $4\preceq 8$ and $8\preceq 4$ . However they do not imply $4=8$ at all. Reflexivity and transitivity of this relation are obvious.

Definition 2. Assume that $X$ is a partially ordered set and $A\subseteq X$ . We call an element

i) $b\in A$ the largest (greatest) in $A$ , if $x \preceq b$ for every $x\in A$ ( $b$ is greater than any other element of $A$ ).

ii) $a\in A$ the smallest (least) in $A$ , if $a \preceq x$ for every $x\in A$ ( $a$ is smaller than any other element of $A$ ).

iii) $b\in A$ a maximal in $A$ if $x\in A$ and $b \preceq x$ gives $x=b$ (there is no element of $A$ greater than $b$ ).

iv) $a\in A$ a minimal in $A$ if $x\in A$ and $x \preceq a$ gives $x=a$ (there is no element of $A$ smaller than $a$ ).

Picture 1

Remark 3. The words "largest" and "maximal" seem to us to be synonyms. Accordingly, we identify the words "smallest" and "minimal". Such an identification, of course, is legal on the set of real numbers, for instance. But in general, there is subtle difference between these concepts. To clarify them let's consider the following interesting example (see also https://bit.ly/36v3ns8).

Example 3. Let $X$ be a set of boxes. In $X$ introduce the partial order accepting $x\preceq y$ if a box $y$ contains a box $x$ or if they are the same box. Then under the largest box we should mean the box which contains all other boxes, but to be maximal means the property of a box when it can not be contained in any other box.

Picture 2

Case 1. Assume now that $X$ consists of 3 elements (boxes) as shown in Picture 1. Obviously, the red box is the largest element and the green box is the smallest element.

Case 2. As another case consider $X$ consisting of 4 elements (boxes) as in Picture 2. Clearly, there is no largest element. Red and purple boxes are maximal elements. There is no smallest element. Green and purple boxes are minimal elements.

Case 3. Finally, let $X$ be consisting of 4 elements (boxes) (Picture 3). There is no largest element. Red and purple boxes are maximal elements. The green box is the smallest element.

Picture 3

Example 4. On $\mathbb{R}^2$ introduce a partial order $(x_1,x_2)\preceq (x_2,y_2)$ if $x_1\le x_2$ and $y_1\le y_2$ . Consider the subset $A$ of $\mathbb{R}^2$ defined by the inequalities $0\le x\le 1$ and $0\le y \le 1-x$ . Then observe that $(0,0)$ is the smallest element in $A$ , but $A$ has no largest element. There is an infinite family of maximal elements $(x,1-x)$ in $A$ but no distinct pair of them is comparable.

Remark 4. As follows from the definitions and examples above it is quite possible to have more than one maximal (respectively minimal) element of a set, even though the largest (respectively the smallest) element doesn't exist. By the property of anti-symmetry the largest and the smallest elements of a set are both unique (if they exist, of course). Moreover, the largest (respectively, the smallest) element is maximal (respectively, minimal). The maximal element is not always the largest. Likewise, the minimal element need not to be the smallest.

2 Linearly ordered sets. Well ordered sets

Finally, recall some useful definitions.

Definition 3. A partially ordered set $X$ is said to be linearly ordered if any two elements $x,y\in X$ are comparable under $\preceq$ , in other words, one of the following conditions holds: either $x\preceq y$ or $y\preceq x$ .