Linear extension

In mathematics, a partial order ≤^* on a set X is an extension of a partial order ≤ on X provided that for any elements x₁ and x₂ of X with x₁ ≤ x₂, it is also the case that x₁ ≤^* x₂. A linear extension of ≤ is an extension that is a linear order, or total order.

1 Order-extension principle
2 An alternative definition
3 See also
4 References

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]}

An alternative definition

Given a poset $P$ and a chain $C$ , then $f:P \to C$ 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 $x, y \in P$ for which the linear extensions of $P$ in which $x < y$ number between ⅓ and ⅔ of the total number of linear extensions of $P$ .

References

^ Edward Marczewski (1930). "Sur l'extension de l'ordre partiel". Fundamenta Mathematicae 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.

Open source encyclopedia content modification information:

This page was last modified on 15 September 2009 at 12:11.

Authorship and Review

Open source encyclopedia content provided here is not reviewed directly by MedLibrary.org. Content is sourced directly from Wikipedia and is authored by an open community of volunteers. It is not produced by or in any way affiliated with MedLibrary.org.

Usage Guidelines

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article on "Linear extension", which is available in its original form here:

http://en.wikipedia.org/w/index.php?title=Linear_extension

All material adapted used from Wikipedia is available under the terms of the GNU Free Documentation License. Wikipedia® itself is a registered trademark of the Wikimedia Foundation, Inc.

Linear extension -- Please Click to Return to Front Page