Posets

Definition 4.4.1   Let $E$ be a set and let $\mathcal{R}$ be a binary relation on $E$. The relation $\mathcal{R}$ is an ordering on $E$ if it is reflexive, anti-symmetric and transitive.

Let us see the two most classical examples:

Example 4.4.2   The relation $\leq$ is an ordering on $\mathbb{R}$:

1. The relation is reflexive: for any real number $x$, we have $x \leq x$.
2. The relation is anti-symmetric: for any two real numbers $x$ and $y$ we have:

   $$\begin{cases}x \leq y \\ y \leq x \end{cases} \Longrightarrow x=y.$$

   
   

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

   $$\begin{cases}x \leq y \\ y \leq z \end{cases} \Longrightarrow x \leq z.$$

   
   

Example 4.4.3   In the set $\mathcal{N}=\mathbb{N}- \{ 0 \}$, we define the following relation, denoted by $\vert$:

$$\forall x \in \mathcal{N}, \; \forall y \in \mathcal{N}, \; x \; \vert \; y \Longleftrightarrow \; \exists k \in \mathcal{N} y=kx.$$

The relation $\vert$ is an ordering on $\mathcal{N}$:

1. The relation is reflexive: for any $x \in \mathcal{N}, \; x= 1 \cdot x$, thus $x \; \vert \; x$.
2. The relation is anti-symmetric: for any two numbers $x,y$ in $\mathcal{N}$, we have:

   $$\begin{cases}x \; \vert \; y \\ y \; \vert \; x \end{cases} ... ...xists q \in \mathcal{N} \text{ such that } x=qy \end{cases} .$$

   
   
   It follows that $x=qy=q(px)=(qp)x$, thus $qp=1$. As $p$ and $q$ are positive integers, the only possibility is $p=q=1$, i.e. $x=y$.
3. The relation is transitive: for any three numbers $x,y,z$ in $\mathcal{N}$, we have:

   $$\begin{cases}x \; \vert \; y \\ y \; \vert \; z \end{cases} ... ...xists q \in \mathcal{N} \text{ such that } z=qy \end{cases} .$$

   
   
   It follows that $z=qy=q(px)=(qp)x$. As $p$ and $q$ are positive integers, the product $pq$ is a positive integer and $x \; \vert \; z$.

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

Let $n$ be a positive integer and consider the set of divisors of $n$, denoted by $\mathcal{D}_n$. The set $\mathcal{D}_n$ 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 $n=24$; Figure 6 displays the corresponding arrow diagram.

Figure: The arrow diagram of $\mathcal{D}_{24}$.

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.

Figure: An intermediate arrow diagram of $\mathcal{D}_{24}$.

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 $\mathcal{D}_{24}$ (see Figure 8).

Figure: Hasse diagram of $\mathcal{D}_{24}$.

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.