next up previous contents
Next: Maximal and minimal elements. Up: Binary relations Previous: Equivalence relations   Contents

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{displaymath}\begin{cases}x \leq y \\  y \leq x \end{cases}
 \Longrightarrow x=y.\end{displaymath}    

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

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

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

$\displaystyle \forall x \in \mathcal{N}, \; \forall y \in \mathcal{N}, \;
 x \; \vert \; y \Longleftrightarrow \; \exists k \in \mathcal{N}$    such that $\displaystyle 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{displaymath}\begin{cases}x \; \vert \; y \\  y \; \vert \; x \end{cases}
...
...xists q \in \mathcal{N} \text{ such that } x=qy
 \end{cases}
 .\end{displaymath}    

    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{displaymath}\begin{cases}x \; \vert \; y \\  y \; \vert \; z \end{cases}
...
...xists q \in \mathcal{N} \text{ such that } z=qy
 \end{cases}
 .\end{displaymath}    

    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}$.
\begin{figure}
\centering
\mbox{\epsfig{file=TotalDiagram24.eps, height=5.5cm}}
\end{figure}

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}$.
\begin{figure}
\centering
\mbox{\epsfig{file=IntermediateDiagram24.eps, height=5.5cm}}
\end{figure}

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}$.
\begin{figure}
\centering
\mbox{\epsfig{file=HasseDiagram24.eps, height=5.5cm}}
\end{figure}

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 up previous contents
Next: Maximal and minimal elements. Up: Binary relations Previous: Equivalence relations   Contents
root 2002-06-10