order theory Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article intr ...

, a discipline within mathematics, a critical pair is a pair of elements in a

partially ordered set In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a binar ...

that are incomparable but that could be made comparable without requiring any other changes to the partial order. Formally, let be a partially ordered set. Then a critical pair is an ordered pair of elements of with the following three properties: * and are incomparable in , *for every in , if then , and *for every in , if then . If is a critical pair, then the binary relation obtained from by adding the single relationship is also a partial order. The properties required of critical pairs ensure that, when the relationship is added, the addition does not cause any violations of the

transitive property In mathematics, a relation on a set is transitive if, for all elements , , in , whenever relates to and to , then also relates to . Each partial order as well as each equivalence relation needs to be transitive. Definition A hom ...

. A set of

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

s of is said to ''reverse'' a critical pair in if there exists a linear extension in for which occurs earlier than . This property may be used to characterize realizers of finite partial orders: A nonempty set of linear extensions is a realizer if and only if it reverses every critical pair.

References

*{{citation, first=W. T., last=Trotter, title=Combinatorics and partially ordered sets: Dimension theory, series=Johns Hopkins Series in Mathematical Sciences, publisher=Johns Hopkins Univ. Press, location=Baltimore, year=1992. Order theory