67

Partially Ordered Sets

Consider a relation R on a set S satisfying the following properties:

1. R is reflexive, i.e., xRx for every x ∈ S.
2. R is antisymmetric, i.e., if xRy and yRx, then x = y.
3. R is transitive, i.e., xRy and yRz, then xRz.

Then R is called a partial order relation, and the set S together with partial order is called a partially order set or POSET and is denoted by (S, ≤).

Example:

1. The set N of natural numbers form a poset under the relation ‘≤’ because firstly x ≤ x, secondly, if x ≤ y and y ≤ x, then we have x = y and lastly if x ≤ y and y ≤ z, it implies x ≤ z for all x, y, z ∈ N.
2. The set N of natural numbers under divisibility i.e., ‘x divides y’ forms a poset because x/x for every x ∈ N. Also if x/y and y/x, we have x = y. Again if x/y, y/z we have x/z, for every x, y, z ∈ N.
3. Consider a set S = {1, 2} and power set of S is P(S). The relation of set inclusion ⊆ is a partial order. Since, for any sets A, B, C in P (S), firstly we have A ⊆ A, secondly, if A ⊆B and B⊆A, then we have A = B. Lastly, if A ⊆B and B ⊆C,then A⊆C. Hence, (P(S), ⊆) is a poset.

Elements of POSET:

1. Maximal Element: An element a ∈ A is called a maximal element of A if there is no element in c in A such that a ≤ c.
2. Minimal Element: An element b ∈ A is called a minimal element of A if there is no element in c in A such that c ≤ b.

Note: There can be more than one maximal or more than one minimal element.

Example: Determine all the maximal and minimal elements of the poset whose Hasse diagram is shown in fig:

Solution: The maximal elements are b and f.

The minimal elements are d and e.

Comparable Elements:

Consider an ordered set A. Two elements a and b of set A are called comparable if

          a ≤ b           or           b ≤ a
             R                               R

Non-Comparable Elements:

Consider an ordered set A. Two elements a and b of set A are called non-comparable if neither a ≤ b nor b ≤ a.

Example: Consider A = {1, 2, 3, 5, 6, 10, 15, 30} is ordered by divisibility. Determine all the comparable and non-comparable pairs of elements of A.

Solution: The comparable pairs of elements of A are:
              {1, 2}, {1, 3}, {1, 5}, {1, 6}, {1, 10}, {1, 15}, {1, 30}
              {2, 6}, {2, 10}, {2, 30}
              {3, 6}, {3, 15}, {3, 30}
              {5, 10}, {5, 15}, {5, 30}
              {6, 30}, {10, 30}, {15, 30}

The non-comparable pair of elements of A are:
              {2, 3}, {2, 5}, {2, 15}
              {3, 5}, {3, 10}, {5, 6}, {6, 10}, {6, 15}, {10, 15}

Linearly Ordered Set:

Consider an ordered set A. The set A is called linearly ordered set or totally ordered set, if every pair of elements in A is comparable.

Example: The set of positive integers I₊ with the usual order ≤ is a linearly ordered set.

---