next up previous contents
Next: Chains and antichains. Up: Posets Previous: Posets   Contents

Maximal and minimal elements.

In this subsection, we consider a poset $ (E, \prec )$.

Definition 4.4.5       
  1. An element $ M$ in $ E$ is called a maximal element in $ E$ if there exist no $ x \in E$ such that $ M \prec x$.
  2. An element $ m$ in $ E$ is called a minimal element in $ E$ if there exist no $ y \in E$ such that $ y \prec m$.

The Hasse diagram of a (finite) poset is a useful tool for finding maximal and minimal elements: they are respectively top and bottom elements of the diagram. For example, in $ \mathcal{D}_{24}$, $ 1$ is a minimal element and $ 24$ is a maximal element. Note, however, that this example is quite special: there is a unique maximal element and a unique minimal element. This situation is not general. Consider the set $ E=\{2,3,5,6,8,10,12,15,24 \}$ ordered by division. Its Hasse diagram is displayed in Figure 9.

Figure 9: Hasse diagram of a poset.
\begin{figure}
\centering
\mbox{\epsfig{file=HasseDiagram-02.eps, height=5.5cm}}
\end{figure}

It appears clearly that $ (E, \; \vert \; )$ has three minimal elements (namely $ 2$, $ 3$ and $ 5$) and three maximal elements (namely $ 10$, $ 15$ and $ 24$).

Definition 4.4.6       
  1. An element $ a$ is the greatest element of $ E$ if, for any element $ x \in E$, we have $ x \prec a$.
  2. An element $ b$ is the least element of $ E$ if, for any element $ y \in E$, we have $ b \prec y$.

Example 4.4.7       
  1. The set $ \mathcal{D}_{24}$ has a least element (namely $ 1$) and a greatest element (namely $ 24$).
  2. The poset $ \{2,3,5,6,8,10,12,15,24 \}$, ordered by division, has neither a least nor a greatest element.
  3. The poset $ \{ 1,2,3,5,6,8,10,12,15,24 \}$, ordered by division, has $ 1$ as its least element and has no greatest element.

Definition 4.4.8   Let $ (E, \prec )$ be a poset. The set $ E$ is well-ordered is every non empty subset of $ E$ has a least element.

For example, the set of all natural numbers, ordered by $ \leq$ is well-ordered.
next up previous contents
Next: Chains and antichains. Up: Posets Previous: Posets   Contents
root 2002-06-10