Content deleted Content added
m Added {{Order theory}} |
templatize ref; cite journal version |
||
| (11 intermediate revisions by 5 users not shown) | |||
Line 1:
{{Short description|Mathematical ordering of a partial order}}
{{CS1 config|mode=cs2}}
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]].
== Definitions ==
=== Linear extension of a partial order ===
A [[partial order]] is a [[Reflexive relation|reflexive]], [[Transitive relation|transitive]] and [[Antisymmetric relation|antisymmetric]] relation. Given any partial orders <math>\,\leq\,</math> and <math>\,\leq^*\,</math> on a set <math>X,</math> <math>\,\leq^*\,</math> is a linear extension of <math>\,\leq\,</math> exactly when
# <math>\,\leq^*\,</math> is a [[total order]], and
# For every <math>x, y \in X,</math> if <math>x \leq y,</math> then <math>x \leq^* y.</math>
It is that second property that leads mathematicians to describe <math>\,\leq^*\,</math> as '''extending''' <math>\,\leq.</math>
Alternatively, a linear extension may be viewed as an [[order-preserving]] [[bijection]] from a partially ordered set <math>P</math> to a [[Total order#Chains|chain]] <math>C</math> on the same ground set.
=== Linear extension of a preorder ===
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 <math>x\precsim y</math> and <math>y\precsim x</math> hold, while a partial-order allows this only when <math>x=y</math>. A relation '''<math>\precsim^*</math>''' is called a linear extension of a preorder <math>\precsim</math> if:
# '''<math>\precsim^*</math>''' is a [[total preorder]], and
# For every <math>x, y \in X,</math> if <math>x\precsim y</math> then <math>x\precsim^* y</math> , and
# For every <math>x, y \in X,</math> if <math>x\prec y</math> then <math>x\prec^* y</math> . Here, <math>x\prec y</math> means "<math>x \precsim y</math> and not <math>y \precsim x</math>".
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 <math>x \precsim y</math> and not <math>y \precsim x</math>. By condition 2, <math>x\precsim^* y</math>. By reflexivity, "not <math>y \precsim x</math>" implies that <math>y\neq x</math>. Since '''<math>\precsim^*</math> '''is a partial order, <math>x\precsim^* y</math> and <math>y\neq x</math> imply "not <math>y\precsim^* x</math>". Therefore, <math>x\prec^* y</math>.
However, for general preorders, condition 3 is needed to rule out trivial extensions. Without this condition, the preorder by which all elements are equivalent (<math>y \precsim x</math> and <math>x \precsim y</math> hold for all pairs ''x'',''y'') would be an extension of every preorder.
== Order-extension principle ==
{{further|Szpilrajn extension theorem}}
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|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.<ref>{{citation
| last = Marczewski | first = Edward | authorlink = Edward Marczewski
| journal = Fundamenta Mathematicae
Line 22 ⟶ 38:
| year = 1930| doi = 10.4064/fm-16-1-386-389 | doi-access = free
}}.</ref>
There is an analogous statement for preorders: every preorder can be extended to a total preorder. This statement was proved by Hansson.<ref>{{citation |last=Hansson |first=Bengt |date=1968 |title=Choice Structures and Preference Relations |url=https://www.jstor.org/stable/20114617 |journal=Synthese |volume=18 |issue=4 |pages=443–458 |doi=10.1007/BF00484979 |jstor=20114617 |issn=0039-7857}}</ref>{{Rp|___location=Lemma 3}}
In modern [[axiomatic set theory]] the order-extension principle 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]],<ref>{{citation
Line 131 ⟶ 149:
| title = Balanced pairs in partial orders
| volume = 201
| year = 1999| doi-access =
}}.</ref> An equivalent way of stating the conjecture is that, if one chooses a linear extension of <math>P</math> uniformly at random, there is a pair <math>(x, y)</math> which has probability between 1/3 and 2/3 of being ordered as <math>x < y.</math> 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.<ref>{{citation
| last1 = Brightwell | first1 = G. R.
Line 151 ⟶ 169:
Counting the number of linear extensions of a finite poset is a common problem in [[algebraic combinatorics]]. This number is given by the leading coefficient of the [[order polynomial]] multiplied by <math>|P|!.</math>
[[Young
| last1 = Chan | first1 = Swee Hong
| last2 = Pak | first2 = Igor | author2-link = Igor Pak
| arxiv = 2311.02743
| date = March 2025
| doi = 10.4171/EMSS/97
| journal = EMS Surveys in Mathematical Sciences
| title = Linear extensions of finite posets}}</ref>
==References==
| |||