# 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 non-trivial 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 non-trivial partial order extending $\leq_{P}$, non-trivial 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.

## 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