Linear extension
From Wikipedia, the free encyclopedia
In mathematics, a partial order ≤* on a set X is an extension of a partial order ≤ on X provided that for any elements x1 and x2 of X with x1 ≤ x2, it is also the case that x1 ≤* x2. A linear extension of ≤ is an extension that is a linear order, or total order.
Contents |
[edit] Order-extension principle
Every partial order can be extended to a total order (order-extension principle, OE). This was first proved by Edward Marczewski in 1930.[1] The order-extension principle is implied by the Boolean prime ideal theorem or the equivalent compactness theorem,[2] but the reverse implication is not provable.[3] The order-extension principle implies that every set can be linearly ordered (ordering principle, OP), but there are models of set theory in which the ordering principle holds while the order-extension principle does not.[citation needed]
[edit] An alternative definition
Given a poset P and a chain C, then 
is a linear extension if f is an order preserving bijection.
The algorithmic problem of constructing a linear extension of a partial order on a finite set, represented by a directed acyclic graph with the set's elements as its vertices, is known as topological sorting.
This area also includes one of order theory's most famous open problems, the ⅓–⅔ conjecture, which states that in any partially ordered set P that is not totally ordered there exists a pair 
for which the linear extensions of P in which x < y number between ⅓ and ⅔ of the total number of linear extensions of P.
[edit] See also
[edit] References
- ^ Edward Marczewski (1930). "Sur l'extension de l'ordre partiel". Fundamenta Mathematucae 16: pp. 386–389.
- ^ Jech, Thomas (2008) [originally published in 1973]. The Axiom of Choice. Dover Publications. ISBN 0-486-46624-8.
- ^ U. Felgner and J. K. Truss (March 1999). "The Independence of the Prime Ideal Theorem from the Order-Extension Principle". The Journal of Symbolic Logic (Association for Symbolic Logic) 64 (1): pp. 199–215.
