Critical pair (order theory)

File:Critical pair (order theory).svg

In order theory, a discipline within mathematics, a critical pair is a pair of elements in a partially ordered set that are incomparable but that could be made comparable without requiring any other changes to the partial order.

Formally, let {{math|1=P = (S, ≤)}} be a partially ordered set. Then a critical pair is an ordered pair {{math|(x, y)}} of elements of {{mvar|S}} with the following three properties:

• {{mvar|x}} and {{mvar|y}} are incomparable in {{mvar|P}},
• for every {{mvar|z}} in {{mvar|S}}, if {{math|z < x}} then {{math|z < y}}, and
• for every {{mvar|z}} in {{mvar|S}}, if {{math|y < z}} then {{math|x < z}}.

If {{math|(x, y)}} is a critical pair, then the binary relation obtained from {{mvar|P}} by adding the single relationship {{math|x ≤ y}} is also a partial order. The properties required of critical pairs ensure that, when the relationship {{math|x ≤ y}} is added, the addition does not cause any violations of the transitive property.

A set {{mvar|R}} of linear extensions of {{mvar|P}} is said to reverse a critical pair {{math|(x, y)}} in {{mvar|P}} if there exists a linear extension in {{mvar|R}} for which {{mvar|y}} occurs earlier than {{mvar|x}}. This property may be used to characterize realizers of finite partial orders: A nonempty set {{mvar|R}} of linear extensions is a realizer if and only if it reverses every critical pair.