Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Critical pair (order theory)
open-in-new
<p>In <a href="/facts/Order_theory/gn6fM3oJ">order theory</a>, a discipline within mathematics, a critical pair is a pair of elements in a <a href="/facts/Partially_ordered_set/qb4a3FAX">partially ordered set</a> that are <a href="/facts/Comparability/PvLeJXol">incomparable</a> but that could be made comparable without requiring any other changes to the partial order. </p><p>Formally, let <i>P</i> = (<i>S</i>, ≤) be a partially ordered set. Then a critical pair is an ordered pair (<i>x</i>, <i>y</i>) of elements of S with the following three properties: </p> <ul><li>x and y are incomparable in P,</li> <li>for every z in S, if <i>z</i> < <i>x</i> then <i>z</i> < <i>y</i>, and</li> <li>for every z in S, if <i>y</i> < <i>z</i> then <i>x</i> < <i>z</i>.</li></ul> <p>If (<i>x</i>, <i>y</i>) is a critical pair, then the binary relation obtained from P by adding the single relationship <i>x</i> ≤ <i>y</i> is also a partial order. The properties required of critical pairs ensure that, when the relationship <i>x</i> ≤ <i>y</i> is added, the addition does not cause any violations of the <a href="/facts/Transitive_property/9r90y50r">transitive property</a>. </p><p>A set R of <a href="/facts/Linear_extension/jKKPR2pn">linear extensions</a> of P is said to <i>reverse</i> a critical pair (<i>x</i>, <i>y</i>) in P if there exists a linear extension in R for which y occurs earlier than x. This property may be used to characterize <a href="/facts/Order_dimension/JaFXu3WE">realizers</a> of finite partial orders: A nonempty set R of linear extensions is a realizer if and only if it reverses every critical pair. </p> <ul><li>Trotter, W. T. (1992), <i>Combinatorics and partially ordered sets: Dimension theory</i>, Johns Hopkins Series in Mathematical Sciences, Baltimore: Johns Hopkins Univ. Press.</li></ul>