*55*

# Partially Ordered Sets

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

- R is reflexive, i.e., xRx for every x âˆˆ S.
- R is antisymmetric, i.e., if xRy and yRx, then x = y.
- 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:

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

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