Examples of Partially Ordered Sets

Consider firstly the set $A = \{1,2,3,4\}$, then the relation $\Re$ on A defined by $a \Re b$ if $a \leq b$ is a partial order. The cartesian product $A \times A$ contains 16 members and the above relation is specified by the subset

{(1,1), (1,2), (1,3), (1,4), (2,2), (2,3), (2,4), (3,3), (3,4), (4,4)}

We can show that the relation $\Re$ is a partial ordering by proving that the properties (1), (2) and (3) above all hold.

For (1), we observe that for any $a \in A$, then $a \leq a$. For (2), we note that if $a \leq b$ and $b \leq c$, where $a,b,c \in A$, it follows that $a \leq c$. For (3), if $a \leq b$ and $b \leq a$, then these two inequalities can only be satisfied if a = b. The three properties are satisfied so that the relation $\Re$does indeed constitute a partial ordering on the set A. In fact, the above relation $\Re$ will constitute a partial ordering on the entire set of integers $\Int$.

As a second example, let A denote the set of courses offered by a college for a computer science degree . If we define the relation $\Re$ on A by $a \enskip \Re \enskip b$ if a and bare the same courses or if course a is a pre-requisite for course b (that is, course a must have been studied before course b is started), then the relation $\Re$ makes A into a partially ordered set.

Another example of a partial ordering which arises in the real world is the building of a new house in which there are certain tasks such as digging the foundations, laying the floor, which must be completed before other phases of the construction such as erecting walls and building the roof can be undertaken. If the set of tasks that must be undertaken in building a house is denoted by A, we can define a relation $\Re$ on A by $a \enskip \Re \enskip b$ where a, b $\in$ A if a, bdenote the same task or if task a must be completed before the start of task b. In this manner, we impose an order on the elements of A and so make it into a poset. Those with a knowledge of operational research will recognise this poset as a PERT network (the acronym PERT stands for ``Project Evaluation and Review Technique'').

In general, if A is a set and the relation $\Re$ on A is a partial order (partial ordering relation), then the pair or tuple $(A, \enskip \Re)$ is called a partially ordered set or poset.