5.3 Distiguished elements of partially
ordered sets
Let <X, ≤ > be a partially ordered set. We shall distinguish
in it some elements with respect to the considered ordering relation.
Definition 5.3.1
An element x0 is called a maximal element in a set <X, ≤ > iff there is no element y ∈ X such that x0 ≠ y and x0 ≤ y.
An element x0 is called a minimal element in a set <X, ≤ > iff there is no element y ∈ X such that x0 ≠ y and y ≤ x0 .
Given a Hasse diagram of an ordering relation, e.g. Fig. 5.4.1, we can observe
that maximal elements are the highest ones, the minimal elements are the lowest
ones.
Fig. 5.3.1 Hasse diagram of a partial ordering relation in the set {a, b, c, d, e}. Elements a, b are minimal, elements are d, e maximal ones in this order.
Question 5.3.1 Is it possible to indicate minimal and maximal
elements in the set N of natural numbers with the ordering relation ≤
?
Definition 5.3.2
An element x0 is called the greatest element of an ordered set <X, ≤ > if and only if for every element y ∈ X, y ≤ x0.
An element x0 is called the least element of an ordered set <X, ≤ > if and only if for every element y ∈ X, x0 ≤ y.
Remark a subtle difference in the definitions of the least and a minimal element, the same applies to the definitions of the greatest and a maximal element.
It is evident that the least (the greatest) element is a minimal (a maximal) element. The converse is not true as it will be seen from the examples below.
Example 5.3.1
(1) In the set R, ordered by the relation ≤ there is no minimal nor maximal element. The set R is an infinite set and for every real number x there exist a number greater than x and a number less than x. For the same reason the set R has no the least nor the greatest elements.
(2) In the set of subsets of the set X = {R, G, B} ordered by the inclusion relation (c.f. example 5.2.1(1)) there exists a maximal element, i.e.the set {R, G, B}, and a minimal element ∅. These sets are the greatest and the least elements in P(X). Consider now the set P(X) \{ ∅ } of all non-empty subsets of the set X with inclusion as an ordering relation. The elements {R}, {G}, {B} are minimal and there is no smallest element in this set.
(3) In the set N of natural numbers ordered by the divisibility relation | (c.f. Figure 5.2.1) there exists one minimal element which is also the smakkest element, the set has five maximal elements: 5, 6, 7, 8, 9. There is no a greatest element in this set.
Corollary
As a consequence of the presented examples, an ordered set may contain several minimal elements and several maximal elements.
Lemma 5.3.1
There are at most one greatest element and at most one smallest element in a partially ordered set.
Proof. We shall prove that every ordered set contains at most one greatest element, the other parts of the lemma can be proved similarly. Suppose that in an ordered set <X, ≤ > there are two greatest elements a and b, then
for every element x of the set X, x ≤ a
and x ≤ b.
In particular putting x = a, we obtain b á a, and putting x = b we obtain a á b. By the antisymmetry of order relation we conclude that a = b, which ends the proof.
Question 5.3.2 Is it possible to create an example of an ordered set
which has exactly one maximal element and not the greatest element?