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, transitive and antisymmetric relation. Given any partial orders ≤ {\displaystyle \,\leq \,} and ≤ ∗ {\displaystyle \,\leq ^{*}\,} on a set X , {\displaystyle X,} ≤ ∗ {\displaystyle \,\leq ^{*}\,} is a linear extension of ≤ {\displaystyle \,\leq \,} exactly when
≤ ∗ {\displaystyle \,\leq ^{*}\,} is a total order, and For every x , y ∈ X , {\displaystyle x,y\in X,} if x ≤ y , {\displaystyle x\leq y,} then x ≤ ∗ y . {\displaystyle x\leq ^{*}y.}
It is that second property that leads mathematicians to describe ≤ ∗ {\displaystyle \,\leq ^{*}\,} as extending ≤ . {\displaystyle \,\leq .}
Alternatively, a linear extension may be viewed as an order-preserving bijection from a partially ordered set P {\displaystyle P} to a chain C {\displaystyle C} 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 x ≾ y {\displaystyle x\precsim y} and y ≾ x {\displaystyle y\precsim x} hold, while a partial-order allows this only when x = y {\displaystyle x=y} . A relation ≾ ∗ {\displaystyle \precsim ^{*}} is called a linear extension of a preorder ≾ {\displaystyle \precsim } if:
≾ ∗ {\displaystyle \precsim ^{*}} is a total preorder, and For every x , y ∈ X , {\displaystyle x,y\in X,} if x ≾ y {\displaystyle x\precsim y} then x ≾ ∗ y {\displaystyle x\precsim ^{*}y} , and For every x , y ∈ X , {\displaystyle x,y\in X,} if x ≺ y {\displaystyle x\prec y} then x ≺ ∗ y {\displaystyle x\prec ^{*}y} . Here, x ≺ y {\displaystyle x\prec y} means " x ≾ y {\displaystyle x\precsim y} and not y ≾ x {\displaystyle 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 ≾ y {\displaystyle x\precsim y} and not y ≾ x {\displaystyle y\precsim x} . By condition 2, x ≾ ∗ y {\displaystyle x\precsim ^{*}y} . By reflexivity, "not y ≾ x {\displaystyle y\precsim x} " implies that y ≠ x {\displaystyle y\neq x} . Since ≾ ∗ {\displaystyle \precsim ^{*}} is a partial order, x ≾ ∗ y {\displaystyle x\precsim ^{*}y} and y ≠ x {\displaystyle y\neq x} imply "not y ≾ ∗ x {\displaystyle y\precsim ^{*}x} ". Therefore, x ≺ ∗ y {\displaystyle 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 ≾ x {\displaystyle y\precsim x} and x ≾ y {\displaystyle x\precsim y} hold for all pairs x,y) would be an extension of every preorder.
Order-extension principle
… excerpt ends here. Continue reading the full article.
