Linear extension

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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.

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 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 x\precsim y and y\precsim x hold, while a partial-order allows this only when x=y . A relation \precsim^* is called a linear extension of a preorder \precsim if: \precsim^* is a total preorder, and For every x, y \in X, if x\precsim y then x\precsim^* y , and For every x, y \in X, if x\prec y then x\prec^* y . Here, x\prec y means " x \precsim y and not y \precsim x ". 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 x \precsim y and not y \precsim x . By condition 2, x\precsim^* y . By reflexivity, "not y \precsim x " implies that y\neq x . Since \precsim^* is a partial order, x\precsim^* y and y\neq x imply "not y\precsim^* x ". Therefore, x\prec^* y . However, for general preorders, condition 3 is needed to rule out trivial extensions. Without this condition, the preorder by which all elements are equivalent ( y \precsim x and x \precsim y hold for all pairs x,y) would be an extension of every preorder.

References

Text derived from https://en.wikipedia.org/w/index.php?oldid=1374260774 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001374260774 · captured 1789070527.0 · version history

Cite this page as: encyclopegia.org, “Linear extension”, snapshot enwiki-001374260774. https://encyclopegia.org/a/linear-extension

Sources cited in this revision

Extracted from the cited revision's reference blocks; absent citations are not invented.