Введение

Математическое множество с упорядочением

В математике, особенно в теории порядка, частичный порядок на множестве — это отношение, согласно которому для некоторых пар элементов один элемент предшествует другому. Слово «частичный» используется для указания того, что не каждая пара элементов обязательно должна быть сопоставима; то есть, могут существовать пары, для которых ни один элемент не предшествует другому. Таким образом, частичные порядки обобщают линейные (или полные) порядки, в которых каждая пара элементов сопоставима. Формально, частичный порядок — это однородное бинарное отношение, которое является рефлексивным, антисимметричным и транзитивным. Частично упорядоченное множество (сокращенно – "посет") — это упорядоченная пара, состоящая из множества (называемого базовым множеством) и частичного порядка на этом множестве. Если смысл ясен из контекста и нет неоднозначности относительно частичного порядка, само множество иногда называют "посетом".

Отношения частичного заказа

Термин «частичный порядок» обычно относится к рефлексивным отношениям частичного порядка, которые в данной статье называются нестрогими частичными порядками. Однако некоторые авторы используют этот термин для другого распространенного типа отношений частичного порядка – нерефлексивных отношений частичного порядка, также называемых строгими частичными порядками. Строгие и нестрогие частичные порядки находятся во взаимно однозначном соответствии, то есть для каждого строгого частичного порядка существует единственный соответствующий нестрогий частичный порядок, и наоборот.

Частичные заказы

Рефлексивное, слабое отношение, обычно называемое просто частичным порядком, — это однородное отношение ≤ на множестве, которое является рефлексивным, антисимметричным и транзитивным. То есть, для всех элементов оно должно удовлетворять следующим условиям:
Рефлексивность: , то есть каждый элемент соотносится с самим собой. Антисимметричность: если и , то , то есть никакие два различных элемента не предшествуют друг другу. Транзитивность: если и , то .
Нестрогий частичный порядок также известен как антисимметричный предзаказ.

Строгие частичные заказы

Нерефлексивный, строгий, поэтому определение остаётся тем же, если из него исключить либо нерефлексивность, либо асимметричность (но не оба свойства одновременно). Строгий частичный порядок также известен как асимметричный строгий предзаказ.

Двойные заказы

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

Обозначение

При заданном множестве и отношении частичного порядка, как правило, нестрогого частичного порядка ≤, мы можем однозначно расширить нашу нотацию для определения четырех отношений частичного порядка: ≤, <, ≥ и >. Здесь ≤ – нестрогое отношение частичного порядка на множестве, < – связанное отношение строгого частичного порядка на множестве (нерефлексивное ядро ≤), ≥ – двойственное к ≤, а > – двойственное к <. Строго говоря, термин "частично упорядоченное множество" относится к множеству, для которого все эти отношения определены соответствующим образом. Но на практике достаточно рассматривать одно отношение: ≤, < или, в редких случаях, строгие и нестрогие отношения вместе.

Термин "упорядоченное множество" иногда используется как сокращение для "частично упорядоченного множества", если из контекста ясно, что не подразумевается другой вид порядка. В частности, полностью упорядоченные множества также могут называться "упорядоченными множествами", особенно в областях, где эти структуры встречаются чаще, чем частично упорядоченные множества. Некоторые авторы используют другие обозначения, такие как ⩽ или ⊴, чтобы отличать частичные порядки от полных порядков. Отношение > является обратным к нерефлексивному ядру ≤, которое всегда является подмножеством дополнения к ≤, но > равно дополнению к ≤ тогда и только тогда, когда ≤ является полным порядком.

Альтернативные определения

Другой способ определения частичного порядка, используемый в информатике, основан на понятии сравнения. В частности, учитывая определение, данное ранее, можно заметить, что два элемента x и y могут находиться в одном из четырех взаимоисключающих отношений друг к другу: либо x < y, либо x = y, либо x > y, либо x и y несравнимы. Это можно представить функцией, которая возвращает один из четырех кодов, получая на вход два элемента. Это определение эквивалентно частичному порядку на сетоиде, где равенство рассматривается как заданное отношение эквивалентности, а не как первоначальное понятие равенства множеств. Уоллис определяет более общее понятие отношения частичного порядка как любое однородное отношение, которое является транзитивным и антисимметричным. Это включает в себя как рефлексивные, так и иррефлексивные частичные порядки как подтипы. Конечный частично упорядоченный набор (poset) можно визуализировать с помощью его диаграммы Хассе. В частности, рассматривая строгое отношение частичного порядка, можно построить ориентированный ациклический граф (DAG), приняв каждый элемент за вершину, а каждое отношение из за отношение порядка за ребро. Транзитивное замыкание этого DAG и будет диаграммой Хассе. Аналогично, этот процесс можно обратить, чтобы построить строгие частичные порядки из определенных DAG. В отличие от этого, граф, соответствующий нестрогому частичному порядку, имеет петли в каждой вершине и, следовательно, не является DAG; когда говорят, что нестрогий порядок изображен диаграммой Хассе, на самом деле отображается соответствующий строгий порядок.

Подмножества

Посе́т называется подпосе́том другого посе́та, если он является подмножеством, а отношение порядка на нём является подмножеством отношения порядка исходного посе́та. Последнее условие эквивалентно требованию, что для любых элементов x и y из подпосе́та (и, следовательно, также из исходного посе́та), если x ≤ y, то x ≤ y. Если подпосе́т является подпосе́том, и кроме того, для всех элементов x и y из подпосе́та, всякий раз когда x ≤ y в исходном посе́те, также выполняется x ≤ y в подпосе́те, то мы называем этот подпосе́т подпосе́том, индуцированным множеством, и записываем .

Линейное расширение

Частичный порядок на множестве называется расширением другого частичного порядка, если для всех элементов, когда выполняется условие , также выполняется условие . Линейное расширение — это расширение, которое также является линейным (то есть полным) порядком. Классическим примером является лексикографический порядок полностью упорядоченных множеств, который является линейным расширением их порядка произведения. Любой частичный порядок можно расширить до полного порядка (принцип расширения порядка). В информатике алгоритмы поиска линейных расширений частичных порядков (представленных как порядки достижимости ориентированных ациклических графов) называются топологической сортировкой.

В теории категорий

Каждый частично упорядоченный набор (и каждый предварительно упорядоченный набор) может рассматриваться как категория, где для объектов x и y существует не более одного морфизма из x в y. Более точно, пусть множество морфизмов будет состоять из единственного морфизма, если x ≤ y (и в противном случае – пустое множество), и пусть для каждого объекта x существует тождественный морфизм. Такие категории иногда называют поцетальными. Частично упорядоченные наборы эквивалентны друг другу тогда и только тогда, когда они изоморфны. В частично упорядоченном наборе наименьший элемент, если он существует, является начальным объектом, а наибольший элемент, если он существует, является конечным объектом. Кроме того, каждый предварительно упорядоченный набор эквивалентен частично упорядоченному набору. Наконец, каждая подкатегория частично упорядоченного набора замкнута относительно изоморфизмов.