extension of a poset
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 , 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. By Zorn’s lemma, and the construction above, every poset has a linear extension: take to be the poset of all extension of (ordered by inclusion), given a chain of elements in , the union is an element of , so that has a maximal element, which can easily be seen to be linear. Thus we have just proved what is known as the order extension principle:
Proposition 1 (order extension principle)
Every partial ordering on a set can be extended to a linear ordering.
And since every set is trivially a poset, where iff , we record the following corollary, known as the ordering principle:
Corollary 1 (ordering principle)
Every set can be linearly ordered.
In fact, every poset is the intersection of all of its linear extensions
for if 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.
Remark. Instead of the stronger axiom of choice, the order extension principle can be proved using the weaker Boolean prime ideal theorem. Furthermore, the ordering principle implies the axiom of choice for finite sets.
References
- 1 W. T. Trotter, Combinatorics and Partially Ordered Sets, Johns-Hopkins University Press, Baltimore (1992).
- 2 T. J. Jech, The Axiom of Choice, North-Holland Pub. Co., Amsterdam, (1973).
Title | extension of a poset |
Canonical name | ExtensionOfAPoset |
Date of creation | 2013-03-22 16:31:57 |
Last modified on | 2013-03-22 16:31:57 |
Owner | CWoo (3771) |
Last modified by | CWoo (3771) |
Numerical id | 15 |
Author | CWoo (3771) |
Entry type | Definition |
Classification | msc 06A06 |
Synonym | linear extension |
Defines | maximal poset |
Defines | linear extension of a poset |
Defines | realizer |
Defines | ordering principle |
Defines | order extension principle |