You are here
Homeextension of a poset
Primary tabs
extension of a poset
Let $(P,\leq_{P})$ be a poset. An extension of $(P,\leq_{P})$ is a poset $(Q,\leq_{Q})$ such that

$Q=P$, and

if $a\leq_{P}b$, then $a\leq_{Q}b$.
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 $\leq_{Q}$ and $\leq_{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 nontrivial extension? Suppose $P$ is a poset and $(a,b)\notin\leq_{P}$ ($a,b$ not comparable). Then $\leq_{Q}:=\leq_{P}\cup A$, where $A=\{(r,s)\mid r\leq a\mbox{ and }b\leq s\}$, is a nontrivial partial order extending $\leq_{P}$, nontrivial since $(a,b)\in\leq_{Q}\leq_{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 $\mathcal{P}$ to be the poset of all extension of $P$ (ordered by inclusion), given a chain $\mathcal{C}$ of elements in $\mathcal{P}$, the union $\bigcup\mathcal{C}$ is an element of $\mathcal{P}$, so that $\mathcal{P}$ 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 $a\leq b$ 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 intersection of all of its linear extensions
$P=\bigcap\{L\mid L\mbox{ 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 contradiction. A set $\mathcal{S}$ of linear extensions of a poset $P$ is said to be a realizer of $P$ if $\displaystyle{\bigcap\mathcal{S}=P}$. 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, JohnsHopkins University Press, Baltimore (1992).
 2 T. J. Jech, The Axiom of Choice, NorthHolland Pub. Co., Amsterdam, (1973).
Mathematics Subject Classification
06A06 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections