Linear extension: Difference between revisions

Revision as of 13:06, 28 February 2023

Latest revision as of 22:11, 28 August 2025

(9 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]].

Line 6:

=== 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

Line 21:

# 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 isneed not requiredbe 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 36 ⟶ 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 145 ⟶ 149:

| title = Balanced pairs in partial orders

| volume = 201

| year = 1999| doi-access = free

}}.</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 165 ⟶ 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 tableaudiagram]]s can be considered as linear extensions of a finite [[Ideal (order theory)|order-ideal]] in the infinite poset <math>\N \times \N,</math>. and theySimilarly, [[Young tableau|standard Young tableaux]] can be considered as linear extensions of a poset corresponding to the Young diagram. For the (usual) Young diagrams, linear extensions are counted by the [[hook length formula]]. For the skew Young diagrams, linear extensions are counted by a determinantal formula.<ref>{{citation

| 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==