|
Let  be a poset. An extension of  is a poset  such that
From the definition, the underlying set of an extension of a poset does not change. We may therefore, when there is no ambiguity, say that  is an extension of a poset  and use  and  to distinguish the partial ordering on  and  respectively.
Every poset has a trivial extension, namely itself. A poset is maximal if the only extension is the trivial one. Given a poset that is not maximal, can we find a non-trivial extension? Suppose  is a poset and
 ( not comparable). Then
 , where
 and  , is a non-trivial partial order extending  , non-trivial since
 . So a maximal poset is just a linearly ordered set, as any pair of elements is comparable.
An extension  of  is said to be linear if  is a linearly ordered set. As we have just seen from the above construction, every poset  has a linear extension (take a maximal chain
 of poset extensions, then the union
 is a maximal poset extending  , and thus linear). In fact, every poset is the intersection of all of its linear extensions
 is a linear extension of   is not in the intersection, a linear extension  of  can be constructed via above containing  , which is a contradiction. A set
 of linear extensions of a poset  is said to be a realizer of  if
 . Every poset has a realizer.
- 1
- W. T. Trotter, Combinatorics and Partially Ordered Sets, Johns-Hopkins University Press, Baltimore (1992).
|
