Critical pair (order theory)
Encyclopedia
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 changing the order relationships of any other pairs of elements.
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 ,
If is a critical pair then the binary relation obtained from by adding the single order relation is also a partially ordered set. The required properties of a critical pair ensure that, when the relation is added, the addition does not cause any violations of the transitive property.
A set of linear extension
s of is said to "reverse every critical pair" if, for every critical pair of , there exists a linear extension in for which occurs earlier than . This property may be used to characterize realizer
s of partial orders: A nonempty set of linear extensions is a realizer if and only if it reverses every critical pair.
Order theory
Order theory is a branch of mathematics which investigates our 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 introduces the field and gives some basic definitions...
, a discipline within mathematics, a critical pair is a pair of elements in a partially ordered set
Partially ordered set
In mathematics, especially order theory, a partially ordered set 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 binary relation that indicates that, for certain pairs of elements in the...
that are incomparable but that could be made comparable without changing the order relationships of any other pairs of elements.
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 order relation is also a partially ordered set. The required properties of a critical pair ensure that, when the relation is added, the addition does not cause any violations of the transitive property.
A set of linear extension
Linear extension
In order theory, a branch of mathematics, a linear extension of a partial order is a linear order that is compatible with the partial order.-Definitions:...
s of is said to "reverse every critical pair" if, for every critical pair of , there exists a linear extension in for which occurs earlier than . This property may be used to characterize realizer
Order dimension
In mathematics, the dimension of a partially ordered set is the smallest number of total orders the intersection of which gives rise to the partial order....
s of partial orders: A nonempty set of linear extensions is a realizer if and only if it reverses every critical pair.