Linear extension
Encyclopedia
In order theory
, a branch of mathematics, a linear extension of a partial order is a linear order (or total order
) that is compatible with the partial order.
Alternatively, a linear extension may be viewed as an order-preserving bijection
from a partially ordered set P to a chain C on the same ground set.
in 1930. Marczewski writes that the theorem had previously been proven by Stefan Banach
, Kazimierz Kuratowski
, and Alfred Tarski
, again using the axiom of choice, but that the proofs had not been published.
In modern axiomatic set theory the order-extension theory is itself taken as an axiom, of comparable ontological status to the axiom of choice. The order-extension principle is implied by the Boolean prime ideal theorem
or the equivalent compactness theorem
, but the reverse implication is not provable.
Applying the order-extension principle to a partial order in which every two elements are incomparable shows that (under this principle) every set can be linearly ordered. This assertion that every set can be linearly ordered is known as the ordering principle, OP, and is a weakening of the well-ordering theorem
. However, there are models of set theory
in which the ordering principle holds while the order-extension principle does not.
with the set's elements as its vertices
, is known as topological sorting
; several algorithms solve it in linear time. Despite the ease of finding a single linear extension, the problem of counting all linear extensions of a finite partial order is #P-complete; however, it may be estimated by a fully polynomial-time randomized approximation scheme. Among all partial orders with a fixed number of elements and a fixed number of comparable pairs, the partial orders that have the largest number of linear extensions are semiorder
s.
The order dimension
of a partial order is the minimum cardinality of a set of linear extensions whose intersection is the given partial order; equivalently, it is the minimum number of linear extensions needed to ensure that each critical pair
of the partial order is reversed in at least one of the extensions.
Antimatroid
s may be viewed as generalizing partial orders; in this view, the structures corresponding to the linear extensions of a partial order are the basic words of the antimatroid.
This area also includes one of order theory's most famous open problems, the 1/3–2/3 conjecture
, which states that in any finite partially ordered set P that is not totally ordered
there exists a pair (x,y) of elements of P for which the linear extensions of P in which number between 1/3 and 2/3 of the total number of linear extensions of P. An equivalent way of stating the conjecture is that, if one chooses a linear extension of P uniformly at random, there is a pair (x,y) which has probability between 1/3 and 2/3 of being ordered as . However, for certain infinite partially ordered sets, with a canonical probability defined on its linear extensions as a limit of the probabilities for finite partial orders that cover the infinite partial order, the 1/3–2/3 conjecture does not hold.
Order theory
Order theory is a branch of mathematics which investigates our intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and gives some basic definitions...
, a branch of mathematics, a linear extension of a partial order is a linear order (or total order
Total order
In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
) that is compatible with the partial order.
Definitions
Given any partial orders ≤ and ≤* on a set X, ≤* is a linear extension of ≤ exactly when (1) ≤* is a linear order and (2) for every x and y in X, if , then . It is that second property that leads mathematicians to describe ≤* as extending ≤.Alternatively, a linear extension may be viewed as an order-preserving bijection
Bijection
A bijection is a function giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements...
from a partially ordered set P to a chain C on the same ground set.
Order-extension principle
The statement that every partial order can be extended to a total order is known as the order-extension principle. A proof using the axiom of choice was first published by Edward MarczewskiEdward Marczewski
Edward Marczewski was a Polish mathematician. His surname until 1940 was Szpilrajn.Marczewski was a member of the Warsaw School of Mathematics...
in 1930. Marczewski writes that the theorem had previously been proven by Stefan Banach
Stefan Banach
Stefan Banach was a Polish mathematician who worked in interwar Poland and in Soviet Ukraine. He is generally considered to have been one of the 20th century's most important and influential mathematicians....
, Kazimierz Kuratowski
Kazimierz Kuratowski
Kazimierz Kuratowski was a Polish mathematician and logician. He was one of the leading representatives of the Warsaw School of Mathematics.-Biography and studies:...
, and Alfred Tarski
Alfred Tarski
Alfred Tarski was a Polish logician and mathematician. Educated at the University of Warsaw and a member of the Lwow-Warsaw School of Logic and the Warsaw School of Mathematics and philosophy, he emigrated to the USA in 1939, and taught and carried out research in mathematics at the University of...
, again using the axiom of choice, but that the proofs had not been published.
In modern axiomatic set theory the order-extension theory is itself taken as an axiom, of comparable ontological status to the axiom of choice. The order-extension principle is implied by the Boolean prime ideal theorem
Boolean prime ideal theorem
In mathematics, a prime ideal theorem guarantees the existence of certain types of subsets in a given abstract algebra. A common example is the Boolean prime ideal theorem, which states that ideals in a Boolean algebra can be extended to prime ideals. A variation of this statement for filters on...
or the equivalent compactness theorem
Compactness theorem
In mathematical logic, the compactness theorem states that a set of first-order sentences has a model if and only if every finite subset of it has a model...
, but the reverse implication is not provable.
Applying the order-extension principle to a partial order in which every two elements are incomparable shows that (under this principle) every set can be linearly ordered. This assertion that every set can be linearly ordered is known as the ordering principle, OP, and is a weakening of the well-ordering theorem
Well-ordering theorem
In mathematics, the well-ordering theorem states that every set can be well-ordered. A set X is well-ordered by a strict total order if every non-empty subset of X has a least element under the ordering. This is also known as Zermelo's theorem and is equivalent to the Axiom of Choice...
. However, there are models of set theory
Model theory
In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....
in which the ordering principle holds while the order-extension principle does not.
Related results
The algorithmic problem of constructing a linear extension of a partial order on a finite set, represented by a directed acyclic graphDirected acyclic graph
In mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...
with the set's elements as its vertices
Vertex (graph theory)
In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...
, is known as topological sorting
Topological sorting
In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that, for every edge uv, u comes before v in the ordering...
; several algorithms solve it in linear time. Despite the ease of finding a single linear extension, the problem of counting all linear extensions of a finite partial order is #P-complete; however, it may be estimated by a fully polynomial-time randomized approximation scheme. Among all partial orders with a fixed number of elements and a fixed number of comparable pairs, the partial orders that have the largest number of linear extensions are semiorder
Semiorder
In order theory, a branch of mathematics, a semiorder is a type of ordering that may be determined for a set of items with numerical scores by declaring two items to be incomparable when their scores are within some threshold of each other and otherwise using the numerical comparison of their scores...
s.
The order dimension
Order dimension
In mathematics, the dimension of a partially ordered set is the smallest number of total orders the intersection of which gives rise to the partial order....
of a partial order is the minimum cardinality of a set of linear extensions whose intersection is the given partial order; equivalently, it is the minimum number of linear extensions needed to ensure that each critical pair
Critical pair (order theory)
In order theory, a discipline within mathematics, a critical pair is a pair of elements in a partially ordered set that are incomparable but that could be made comparable without changing the order relationships of any other pairs of elements....
of the partial order is reversed in at least one of the extensions.
Antimatroid
Antimatroid
In mathematics, an antimatroid is a formal system that describes processes in which a set is built up by including elements one at a time, and in which an element, once available for inclusion, remains available until it is included...
s may be viewed as generalizing partial orders; in this view, the structures corresponding to the linear extensions of a partial order are the basic words of the antimatroid.
This area also includes one of order theory's most famous open problems, the 1/3–2/3 conjecture
1/3–2/3 conjecture
In order theory, a branch of mathematics, the 1/3–2/3 conjecture states that, if one is comparison sorting a set of items then, no matter what comparisons may have already been performed, it is always possible to choose the next comparison in such a way that it will reduce the number of possible...
, which states that in any finite partially ordered set P that is not totally ordered
Total order
In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
there exists a pair (x,y) of elements of P for which the linear extensions of P in which number between 1/3 and 2/3 of the total number of linear extensions of P. An equivalent way of stating the conjecture is that, if one chooses a linear extension of P uniformly at random, there is a pair (x,y) which has probability between 1/3 and 2/3 of being ordered as . However, for certain infinite partially ordered sets, with a canonical probability defined on its linear extensions as a limit of the probabilities for finite partial orders that cover the infinite partial order, the 1/3–2/3 conjecture does not hold.