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

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

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

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

• Икс и у несравнимы в п,
• для каждого z в S, если z < Икс тогда z < у, и
• для каждого z в S, если у < z тогда Икс < z.

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

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

Рекомендации

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