Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Linear extension
Summary
In order theory, a branch of mathematics, a linear extension of a partial order is a total order (or linear order) that is compatible with the partial order. As a classic example, the lexicographic order of totally ordered sets is a linear extension of their product order.
A partial order is a reflexive, transitive and antisymmetric relation. Given any partial orders and on a set is a linear extension of exactly when
is a total order, and
For every 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 from a partially ordered set to a chain on the same ground set.
A preorder is a reflexive and transitive relation. The difference between a preorder and a partial-order is that a preorder allows two different items to be considered "equivalent", that is, both and hold, while a partial-order allows this only when . A relation is called a linear extension of a preorder if:
is a total preorder, and
For every if then , and
For every if then . Here, means " and not ".
The difference between these definitions is only in condition 3. When the extension is a partial order, condition 3 need not be stated explicitly, since it follows from condition 2. Proof: suppose that and not . By condition 2, . By reflexivity, "not " implies that . Since is a partial order, and imply "not ". Therefore, .
However, for general preorders, condition 3 is needed to rule out trivial extensions. Without this condition, the preorder by which all elements are equivalent ( and hold for all pairs x,y) would be an extension of every preorder.
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 Marczewski (Szpilrajin) 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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Ontological neighbourhood
Related publications (10)
Related people (4)
Related concepts (11)
Product order
In mathematics, given a partial order and on a set and , respectively, the product order (also called the coordinatewise order or componentwise order) is a partial ordering on the Cartesian product Given two pairs and in declare that if and Another possible ordering on is the lexicographical order, which is a total ordering. However the product order of two total orders is not in general total; for example, the pairs and are incomparable in the product order of the ordering with itself.
Series-parallel partial order
In order-theoretic mathematics, a series-parallel partial order is a partially ordered set built up from smaller series-parallel partial orders by two simple composition operations. The series-parallel partial orders may be characterized as the N-free finite partial orders; they have order dimension at most two. They include weak orders and the reachability relationship in directed trees and directed series–parallel graphs. The comparability graphs of series-parallel partial orders are cographs.
Order dimension
In mathematics, the dimension of a partially ordered set (poset) is the smallest number of total orders the intersection of which gives rise to the partial order. This concept is also sometimes called the order dimension or the Dushnik–Miller dimension of the partial order. first studied order dimension; for a more detailed treatment of this subject than provided here, see . The dimension of a poset P is the least integer t for which there exists a family of linear extensions of P so that, for every x and y in P, x precedes y in P if and only if it precedes y in all of the linear extensions.