## Order Relations

**Nurlan Abiev**

The present post we devote to *order relations*. For preliminaries see our previous post *Equivalence Relations*. Recall that and are the sets of *real *and *natural *numbers respectively.

### 1 Partially ordered sets

**Definition 1**. A **partial order** on a set is a relation satisfying the following conditions for arbitrary :

i) (*reflexivity*);

ii) If and then (*anti-symmetry*);

iii) If and then (*transitivity*).

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

We often denote a partial order by the symbol (do not confuse it with the usual symbol of inequality). Moreover, we denote if and .

**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 assuming if .

ii) Let be any given set. Assuming if , where are subsets of , we obtain a partial order on the *power set* (the set of all subsets of ).

iii) Suppose that means " divides ", where . Then is a partial order on .

iv) For define if ( is smaller than ). Consequently we obtain a partial order on .

v) The following is a partial order on the set of all real valued functions defined on :

if for all .

vi) On we can introduce a partial order putting if and .

vii) The alphabetical order of letters 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 if any prime divisor of also divides . Such a relation is not a partial order, since it is not anti-symmetric.

Indeed we have true expressions and . However they do not imply at all. Reflexivity and transitivity of this relation are obvious.

**Definition 2**. Assume that is a partially ordered set and . We call an element

i) the **largest** (**greatest**) in , if for every ( is greater than any other element of ).

ii) the **smallest** (**least**) in , if for every ( is smaller than any other element of ).

iii) a **maximal** in if and gives (there is no element of greater than ).

iv) a ** minimal** in if and gives (there is no element of smaller than ).

**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

*Case 1*. Assume now that

*Case 2*. As another case consider

*Case 3*. Finally, let

**Example 4**. On

**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 **linearly ordered** if any two elements

For example, the set of reals

**Example 5**. Are the sets considered in Example 1 linearly ordered?

i) No. Any two distinct elements are not comparable.

ii) No. Consider

iii) No. It suffices to take elements

iv) Yes. Any two elements of

v) No. Take functions

vi) No. It suffices to take elements

vii) Yes. The alphabetical order is linear.

viii) Yes. The lexicographical order is linear as well.

**Example 6**. As you can observe from Example 3 the set in case 1 is linearly ordered. But the sets in cases 2 and 3 are not.

**Definition 4**. A partially ordered set **well ordered** if every nonempty subset of

**Example 7**.

You must be logged in to post a comment.