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.