Linear extension

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.

Given any partial orders ≤ and ≤^* on a set X, ≤^* is a linear extension of ≤ exactly when (1) ≤^* is a total order and (2) for every x and y in X, if x ≤ y, then x ≤^*y. 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 P to a chain C on the same ground set.

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

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, but the reverse implication doesn't hold.

...
Wikipedia