extension of a poset


Let (P,P) be a poset. An extensionPlanetmathPlanetmath of (P,P) is a poset (Q,Q) such that

  • Q=P, and

  • if aPb, then aQb.

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 Q is an extension of a poset P and use Q and P to distinguish the partial ordering on Q and P 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 P is a poset and (a,b)P (a,b not comparablePlanetmathPlanetmath). Then Q:=PA, where A={(r,s)ra and bs}, is a non-trivial partial order extending P, non-trivial since (a,b)Q-P. So a maximal poset is just a linearly ordered set, as any pair of elements is comparable.

An extension Q of P is said to be linear if Q is a linearly ordered set. By Zorn’s lemma, and the construction above, every poset P has a linear extension: take 𝒫 to be the poset of all extension of P (ordered by inclusion), given a chain 𝒞 of elements in 𝒫, the union 𝒞 is an element of 𝒫, so that 𝒫 has a maximal elementMathworldPlanetmath, 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 ab iff a=b, 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 intersectionMathworldPlanetmath of all of its linear extensions

P={LL is a linear extension of P},

for if (a,b) is not in the intersection, a linear extension M of P can be constructed via above containing (a,b), which is a contradictionMathworldPlanetmathPlanetmath. A set 𝒮 of linear extensions of a poset P is said to be a realizer of P if 𝒮=P. Every poset has a realizer.

Remark. Instead of the stronger axiom of choiceMathworldPlanetmath, 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