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
).

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

Picture 2
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.

Picture 3
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).
Leave a Reply
You must be logged in to post a comment.