linear extension of a partial order




(linear extension)

Given a set XX equipped with a partial ordering \leq, then a linear extension is a linear order lin\leq_{lin} on the same set SS, such that the identity function id Sid_S is order-preserving

(S,)id S(S, lin). (S,\leq) \overset{ id_S }{\longrightarrow} \left(S,\leq_{lin}\right) \,.



(existence of linear extensions)

For finite sets linear extensions (Def. ) always exist. For non-finite sets this is still the case using the axiom of choice.

A proof under AC was first published in (Marczewski 30). The proposition actually follows from the weaker choice principle called the ultrafilter principle, by appeal to the compactness theorem, as follows.


It is a very simple matter to show linear extensions exist in the finite case: one may proceed by induction. Any finite nn-element poset has a minimal element xx (meaning yxy \leq x implies y=xy = x). By induction the restricted partial order on X{x}X \setminus \{x\} admits a linear extension, and then one may simply prepend xx to that linear order to complete the inductive step.

The rest is a routine application of compactness for propositional theories. Let (X,)(X, \leq) be a partially ordered set, and introduce a signature consisting of constants c xc_x, one for each xXx \in X, and a binary relation LL. Introduce axioms ¬(c x=c y)\neg(c_x = c_y) whenever xyx \neq y in XX, and L(c x,c y)L(c_x, c_y) whenever xyx \leq y in the poset XX, and axioms stating that LL is a linear order. By the previous paragraph, the resulting theory is finitely satisfiable upon interpreting each c xc_x as xx. Hence the theory is satisfiable. Taking any model MM, and interpreting the constants in MM, and restricting LL to them, we obtain a linear extension on XX.


See also