Частично упорядоченное множество: примеры и диаграмма

Частично упорядоченное множество - это множество с отношением, которое позволяет сравнивать элементы, но не требует сравнимости каждой пары. Например, среди делителей 12 число 2 делит 6, а числа 2 и 3 не делят друг друга. Такое устройство встречается в зависимостях задач, включении множеств и отношениях делимости. В интерактиве можно выбрать число и увидеть, какие его делители сравнимы и сколько пар входит в отношение.
Определение: множество и отношение
Пусть - множество, а - отношение на нём. Пара называется частично упорядоченным множеством, если для любых выполняются три свойства:
- Рефлексивность: .
- Антисимметричность: из и следует .
- Транзитивность: из и следует .
Знак обозначает общий порядок, а не обязательно числовое неравенство. Его смысл задаётся отдельно: «делит», «содержится в» или, например, «является необходимым предшественником либо совпадает». Без отношения одно и то же множество нельзя назвать упорядоченным однозначно. Свойства отношений подробнее разобраны в статье о рефлексивности и транзитивности.
Антисимметричность не запрещает равным элементам находиться в отношении в обе стороны: рефлексивность как раз требует . Она запрещает это только для различных элементов. Если хотя бы одно из трёх свойств нарушено, рассматриваемая пара не является частичным порядком.
Сравнимость и отличие от линейного порядка
Элементы и сравнимы, когда или . Если не выполняется ни одно из утверждений, они несравнимы. Это не означает, что о них ничего не известно: известно, что выбранное отношение не связывает их ни в одном направлении.
Частичный порядок становится линейным, или полным, если каждые два элемента сравнимы. Таков обычный порядок на целых числах. Напротив, делимость на положительных целых даёт частичный порядок: 2 и 3 различны, но ни одно из них не делит другое. При этом 2 и 6 сравнимы, поскольку .
Слово «частичный» не означает, что отношение определено лишь для части пар. Для каждой пары можно проверить истинность обоих направлений; просто оба ответа иногда отрицательны. Частичный порядок может оказаться и линейным: например, делители 8 образуют цепочку .
Пример: делители 12
Рассмотрим и положим , если делит . Каждое число делит себя. Если два положительных числа делят друг друга, они равны. Если и , то : произведение соответствующих целых множителей даёт нужный множитель. Все три условия выполнены.
Для подсчёта пар перечислим для каждого первого элемента все подходящие вторые:
| Первый элемент | Какие элементы он делит | Число пар |
|---|---|---|
| 1 | 1, 2, 3, 4, 6, 12 | 6 |
| 2 | 2, 4, 6, 12 | 4 |
| 3 | 3, 6, 12 | 3 |
| 4 | 4, 12 | 2 |
| 6 | 6, 12 | 2 |
| 12 | 12 | 1 |
Всего упорядоченных пар, в том числе шесть пар вида . Несравнимые пары различных элементов - , и . В таблице порядок пары важен: есть в отношении, а нет. Измените 12 в интерактиве: для простого числа останутся только 1 и само число, а порядок станет линейным.
Как читать диаграмму Хассе
Для конечного частичного порядка удобно нарисовать диаграмму Хассе. Расположим меньшие в смысле отношения элементы ниже больших. Соединим и ребром, если и между ними нет элемента с . Такое непосредственное отношение называют покрытием: покрывает .

На рисунке семь рёбер: –, –, –, –, –, – и –. Стрелки не нужны: направление читают снизу вверх. Петли тоже опущены, поскольку каждый элемент связан с собой. Ребро от 1 к 12 не рисуют: между ними есть промежуточные элементы, хотя .
Чтобы определить сравнимость двух разных вершин, ищите путь, который всё время идёт вверх от одной к другой. Например, доказывает . Путь, который сначала поднимается, а затем спускается, такого вывода не даёт: 2 и 3 обе связаны с 6, но несравнимы. Количество рёбер поэтому не равно количеству пар отношения.
Минимальные, максимальные и крайние элементы
Элемент минимален, если под ним нет другого элемента множества. Он максимален, если над ним нет другого элемента. Наименьший элемент должен быть меньше либо равен каждому элементу; наибольший - больше либо равен каждому. Наименьший всегда минимален, а наибольший максимален, но обратное в общем случае неверно.
Возьмём с делимостью. Здесь 2 и 3 минимальны: ни одно другое число из их не делит. Элементы 6 и 10 максимальны: ни один не делит другого элемента из . Наименьшего и наибольшего нет: 2 и 3 несравнимы, как и 6 с 10. Напротив, среди делителей 12 элемент 1 наименьший, а 12 наибольший. Если наименьший или наибольший существует, он единственен: два таких элемента были бы связаны в обе стороны и совпали бы по антисимметричности.
Подмножества, цепи и зависимости
Для множества рассмотрим все его подмножества и отношение включения . Оно рефлексивно, антисимметрично и транзитивно. Если , то , но и несравнимы. Пустое множество - наименьший элемент, а - наибольший. Число вершин этой конструкции для исходных элементов равно ; почему это так, разобрано в статье о числе подмножеств.
Цепь - подмножество, любые два элемента которого сравнимы; антицепь - подмножество, любые два различных элемента которого несравнимы. В делителях 12 пример цепи - , а антицепи - . Оба понятия зависят от выбранного отношения.
В информатике отношения зависимостей удобно представлять ориентированным ациклическим графом. Если добавить достижимость по путям и пары каждой вершины с собой, получится частичный порядок на вершинах. Топологическая сортировка выбирает линейную последовательность, совместимую с зависимостями: несравнимые задачи могут в ней стоять в разных допустимых порядках. Добавленные при таком выборе сравнения принадлежат линейному расширению, а не исходному отношению.
Как проверить отношение в задаче
Сначала точно выпишите множество и правило сравнения. Затем проверьте каждое из трёх свойств на всём множестве. Для опровержения достаточно одного контрпримера: отношение на числах не рефлексивно, так как ложно. Оно задаёт строгий порядок, но не частичный порядок в принятом здесь рефлексивном определении.
Если отношение задано списком пар, проверьте все диагональные пары, обратные пары разных элементов и все продолжения вида . Например, наличие и без нарушает транзитивность. Далее найдите сравнимые пары и, если требуется, удалите из рисунка петли и транзитивные рёбра. Операции над самими множествами можно освежить в статье про объединение и пересечение.
Разбор задачи: порядок на выбранном подмножестве
Пусть условие просит рассмотреть не все делители 12, а только числа 2, 3, 4 и 6 с прежним правилом делимости. Сначала проверим, что ограничение сохраняет свойства: каждый выбранный элемент по-прежнему делит себя; взаимная делимость положительных чисел по-прежнему означает равенство; транзитивность справедлива для любых трёх выбранных элементов. Поэтому снова получаем частичный порядок, хотя набор сравнений стал меньше.
Непосредственные сравнения здесь только три: 2 делит 4, 3 делит 6 и 2 делит 6. Все три являются покрытиями внутри выбранного множества. Других сравнений различных элементов нет. Следовательно, у диаграммы четыре вершины и три ребра, а минимальными будут 2 и 3. Максимальны 4 и 6. Наименьшего и наибольшего элемента нет: два минимальных элемента несравнимы, как и два максимальных.
Этот пример показывает, почему границы множества существенны. Число 1 делит все выбранные числа, но не является их наименьшим элементом: оно отсутствует в рассматриваемом множестве. Аналогично 12 кратно всем четырём числам, но не является наибольшим элементом этого порядка. При поиске крайних элементов нельзя добавлять удобные числа извне без изменения условия.
Что меняется при добавлении сравнения
Предположим, что в плане работ сначала требуется выполнить подготовку, а затем две независимые проверки. Подготовка предшествует каждой проверке, однако проверки между собой не сравнимы. Есть два допустимых линейных расписания: сначала подготовка и первая проверка, затем вторая; либо подготовка и проверки в обратной последовательности.
Если ввести дополнительное требование «первая проверка до второй», останется одно расписание. При этом нужно учесть все следствия требования: если один этап предшествует первой проверке, он будет предшествовать и второй. В отношении порядка такие следствия уже включены благодаря транзитивности. Для конечного набора задач наличие направленного цикла между разными задачами противоречило бы антисимметричности после перехода к достижимости, поэтому обычную модель зависимостей строят без таких циклов.
Частые ошибки
- Считать, что любые два элемента обязаны сравниваться: это условие линейного порядка.
- Путать антисимметричность с отсутствием пар : такие пары обязательны.
- Считать только нарисованные рёбра отношением: пути вверх тоже задают пары.
- Называть каждый максимальный элемент наибольшим, не сравнив его со всеми остальными.
FAQ
Может ли частичный порядок быть линейным?
Да. Линейный порядок - частный случай частичного, в котором сравнима каждая пара элементов.
Может ли быть несколько минимальных элементов?
Да, если они попарно несравнимы. Но наименьший элемент, когда он существует, только один.
Зачем удалять транзитивные рёбра с диаграммы?
Чтобы упростить изображение: их можно восстановить по восходящим путям. Само отношение при этом не меняется.
Коротко
Частичный порядок задаётся рефлексивным, антисимметричным и транзитивным отношением. Несравнимые элементы допустимы; диаграмма Хассе показывает покрытия, а остальные сравнения восстанавливаются по путям вверх. Это позволяет отделять непосредственные зависимости от их транзитивных следствий.
Читайте также

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

Декартово произведение множеств: примеры и формула
Декартово произведение множеств: что такое упорядоченная пара, как перечислить все элементы A x B, найти мощность и применить к координатной плоскости - с разбором типовых задач.

Принцип включения-исключения: формула и примеры
Принцип включения-исключения: формула для двух и трёх множеств, вывод через диаграмму Венна, задачи на делимость и вероятность, частые ошибки студентов.

Булев куб: вершины, рёбра и расстояние Хэмминга
Булев куб простыми словами: как двоичные наборы становятся вершинами, когда они соседствуют, сколько в кубе рёбер и как найти расстояние между вершинами.

Доминирующее множество в графе: определение и примеры
Как проверить доминирующее множество графа и найти число доминирования: разбираем путь из шести вершин, полный перебор, жадный подход и типичные ошибки.

Гиперграф: что это такое и как его построить
Гиперграф простыми словами: вершины, гиперрёбра и матрица инцидентности. Разбираем пример, степени вершин, связь с обычным графом и области применения.