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 :
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 be a set of boxes. In introduce the partial order accepting if a box contains a box 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.
Case 1. Assume now that 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 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 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.
Example 4. On introduce a partial order if and . Consider the subset of defined by the inequalities and . Then observe that is the smallest element in , but has no largest element. There is an infinite family of maximal elements in 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 is said to be linearly ordered if any two elements are comparable under , in other words, one of the following conditions holds: either or .
For example, the set of reals is linearly ordered under the partial order on .
Example 5. Are the sets considered in Example 1 linearly ordered?
i) No. Any two distinct elements are not comparable.
ii) No. Consider with subsets and .
iii) No. It suffices to take elements and in .
iv) Yes. Any two elements of are comparable under the partial order .
v) No. Take functions and defined on the interval .
vi) No. It suffices to take elements and in .
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 is said to be well ordered if every nonempty subset of has the least element.
Example 7. is well ordered under the usual order introduced in (this fact we will prove in the future).