Направленные множества в математике.

Введение

Математическое упорядочение с верхними границами
В математике направленное множество (или направленный предзаказ, или фильтрованное множество) — это непустое множество вместе с рефлексивным и транзитивным бинарным отношением (то есть предзаказом), с дополнительным свойством, что для каждой пары элементов существует верхняя граница. Иными словами, для любых элементов x и y из множества S должен существовать элемент z в S такой, что x ≤ z и y ≤ z. Предзаказ направленного множества называется направлением. Понятие, определенное выше, иногда называют множеством, направленным вверх. Множество, направленное вниз, определяется аналогично, что означает, что каждая пара элементов ограничена снизу. Некоторые авторы (и эта статья) подразумевают, что направленное множество направлено вверх, если не указано иное. Другие авторы называют множество направленным только в том случае, если оно направлено как вверх, так и вниз. Направленные множества являются обобщением непустых полностью упорядоченных множеств. То есть, все полностью упорядоченные множества являются направленными множествами (в отличие от частично упорядоченных множеств, которые не обязаны быть направленными). Полурешетки присоединения (которые являются частично упорядоченными множествами) также являются направленными множествами, но не наоборот. Аналогично, решетки направлены как вверх, так и вниз. В топологии направленные множества используются для определения сетей, которые обобщают последовательности и объединяют различные понятия предела, используемые в анализе. Направленные множества также порождают прямые пределы в абстрактной алгебре и (в более общем смысле) в теории категорий.

Эквивалентное определение

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

Примеры

Множество натуральных чисел с обычным порядком является одним из наиболее важных примеров ориентированного множества. Любое вполне упорядоченное множество является ориентированным множеством, включая и .

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

Продукт направленных множеств

Пусть и будут направленными множествами. Тогда декартово произведение можно сделать направленным множеством, определив ⇔ и . По аналогии с порядком произведения, это направление произведения на декартовом произведении. Например, множество пар натуральных чисел можно сделать направленным множеством, определив ⇔ и .

Направленный в сторону точки

Если α – действительное число, то множество ℝ можно превратить в направленное множество, определив ≤, если x – y ≥ 0 (то есть, "большие" элементы ближе к α). Мы говорим, что действительные числа направлены к α. Это пример направленного множества, которое не является ни частично упорядоченным, ни полностью упорядоченным. Это происходит потому, что антисимметричность нарушается для каждой пары x и y, равноудалённых от α, где x и y находятся по разные стороны от α. В частности, это происходит, когда x < α < y для некоторого действительного α, в этом случае x ≤ y и y ≤ x, хотя x ≠ y. Если бы этот предзаказ был определён на [0, ∞) вместо ℝ, то он всё равно образовал бы направленное множество, но теперь он имел бы (единственный) наибольший элемент, а именно 0; однако, он всё равно не был бы частично упорядоченным. Этот пример можно обобщить на метрическое пространство X, определив на X предзаказ x ≤ y, если и только если d(x, α) ≤ d(y, α).

Логика

Пусть – формальная теория, то есть множество предложений, обладающих определенными свойствами (подробности можно найти в статье по данной теме). Например, может быть теорией первого порядка (такой как теория множеств Цермело — Френкеля) или более простой теорией нулевого порядка. Предварительно упорядоченное множество является направленным множеством, поскольку если и если обозначает предложение, образованное логической конъюнкцией, то и где
Если – алгебра Линденбаума — Тарского, связанная с , то является частично упорядоченным множеством, которое также является направленным множеством.

Контраст с полуотростками

Направленное множество является более общим понятием, чем полурешетка соединения: любая полурешетка соединения является направленным множеством, поскольку соединение или наименьшая верхняя грань двух элементов является требуемой. Однако обратное неверно, примером служит направленное множество {1000, 0001, 1101, 1011, 1111}, упорядоченное побитово (например, выполняется, но не выполняется, поскольку в последнем бите 1 > 0), где у множества {1000, 0001} есть три верхние грани, но нет наименьшей верхней грани, см. рисунок. (Также обратите внимание, что без 1111 множество не является направленным.)

Направленные подмножества

Отношение порядка в направленном множестве не обязательно должно быть антисимметричным, и поэтому направленные множества не всегда являются частичными порядками. Однако термин «направленное множество» также часто используется в контексте частично упорядоченных множеств (позитов). В этом контексте подмножество частично упорядоченного множества называется направленным подмножеством, если оно является направленным множеством относительно того же частичного порядка: иными словами, это не пустое множество, и для любой пары его элементов существует верхняя граница. Здесь отношение порядка на элементах подмножества наследуется от исходного частично упорядоченного множества, поэтому явно требовать рефлексивности и транзитивности не нужно. Направленное подмножество позита не обязательно должно быть замкнутым вниз; подмножество позита является направленным тогда и только тогда, когда его замыкание вниз является идеалом. Хотя определение направленного множества относится к множеству, направленному «вверх» (для любой пары элементов существует верхняя граница), можно также определить множество, направленное «вниз», в котором для любой пары элементов существует общая нижняя граница. Подмножество позита направлено вниз тогда и только тогда, когда его замыкание вверх является фильтром. Направленные подмножества используются в теории доменов, которая изучает направленные полные частично упорядоченные множества. Это позиты, в которых для каждого направленного вверх множества требуется существование наименьшей верхней границы. В этом контексте направленные подмножества снова предоставляют обобщение сходящихся последовательностей.