Next: Maximal and minimal elements. Up: Binary relations Previous: Equivalence relations   Contents

# Posets

Definition 4.4.1   Let be a set and let be a binary relation on . The relation is an ordering on if it is reflexive, anti-symmetric and transitive.

Let us see the two most classical examples:

Example 4.4.2   The relation is an ordering on :
1. The relation is reflexive: for any real number , we have .
2. The relation is anti-symmetric: for any two real numbers and we have:

3. The relation is transitive: for any three real numbers , and , we have:

Example 4.4.3   In the set , we define the following relation, denoted by :

 such that

The relation is an ordering on :
1. The relation is reflexive: for any , thus .
2. The relation is anti-symmetric: for any two numbers in , we have:

It follows that , thus . As and are positive integers, the only possibility is , i.e. .
3. The relation is transitive: for any three numbers in , we have:

It follows that . As and are positive integers, the product is a positive integer and .

Definition 4.4.4   Let be an ordered set, with ordering denoted by . The relation is called a total ordering if for any pair of elements of , either or is true. An ordering which is not a total ordering is called a partial ordering. A set together with a partial ordering is called a partially orderd set or, more briefly a poset.

Let be a positive integer and consider the set of divisors of , denoted by . The set is partially ordered by division. As seen at the beginning of this chapter, we can represent this poset by an arrow diagram. As an example, take ; Figure 6 displays the corresponding arrow diagram.

This diagram is rather intricated. As the relation is reflexive, we can skip the loops on the vertices of the diagrams (the green loops); we get the diagram in Figure 7.

This diagram is still complicated; actually, the display contains superfluous arrows, namely those arrows which are a result of transitivity (the red arrows). If we leave only the minimal arrows'', i.e. those arrows which cannot be decomposed into shorter ones, we get the so-called Hasse diagram for (see Figure 8).

Let us summarize the steps for drawing the Hasse diagram of a (finite) poset:
(i)
Draw the total diagram of the ordering (the lower the element is displayed as a vertex, the smaller this element is with respect to the ordering);
(ii)
Erase the loops on the vertices;
(iii)
Erase the composite arrows, i.e. the arrows which can be obtained by transitivity from more than one arrow.

Subsections

Next: Maximal and minimal elements. Up: Binary relations Previous: Equivalence relations   Contents
root 2002-06-10