Критическая пара (теория порядка)

Диаграмма Хассе частичного порядка с критической парой ⟨ b , c ⟩. Добавление серая линия сделает b < c без каких-либо других изменений. И наоборот, ⟨ c , b ⟩ не является критической парой, поскольку d < c , но не d < b .

В теории порядка , математической дисциплине, критическая пара — это пара элементов частично упорядоченного множества , которые несравнимы , но которые можно сделать сопоставимыми, не требуя каких-либо других изменений в частичном порядке.

Формально, пусть P = ( S , ≤) — частично упорядоченное множество. Тогда критическая пара — это упорядоченная пара ( x , y ) элементов S со следующими тремя свойствами:

• x и y несравнимы в P ,
• для каждого z в S , если z < x, то z < y , и
• для каждого z в S , если y < z, то x < z .

Если ( x , y ) — критическая пара, то бинарное отношение, полученное из P добавлением одиночного отношения x ≤ y, также является частичным порядком. Свойства, необходимые для критических пар, гарантируют, что при добавлении отношения x ≤ y добавление не вызывает каких-либо нарушений транзитивного свойства .

обращает критическую пару ( x набор R линейных расширений P Говорят, что , y ) в P , если существует линейное расширение в R , для которого y встречается раньше, чем x . Это свойство можно использовать для характеристики реализаторов конечных частичных порядков: непустое множество R линейных расширений является реализатором тогда и только тогда, когда оно обращает каждую критическую пару.

Ссылки

• Троттер, В.Т. (1992), Комбинаторика и частично упорядоченные множества: теория размерности , Серия Джонса Хопкинса по математическим наукам, Балтимор: Университет Джонса Хопкинса. Нажимать .