Направленный набор

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

В математике направленное множество ( или направленный предпорядок или фильтрованный набор ) — это непустое множество вместе с рефлексивным и транзитивным бинарным отношением (то есть предпорядком ), с дополнительным свойством, что каждая пара элементов имеет верхнюю границу . ^[1] Другими словами, для любого и в должно существовать в с и Предпорядок направленного множества называется направлением . ${\displaystyle A}$ ${\displaystyle \,\leq \,}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle A}$ ${\displaystyle c}$ ${\displaystyle A}$ ${\displaystyle a\leq c}$ ${\displaystyle b\leq c.}$

Определенное выше понятие иногда называютнаправленный вверх набор . AНаправленный вниз набор определяется аналогично,^[2]что означает, что каждая пара элементов ограничена снизу.^[3] Некоторые авторы (и эта статья) предполагают, что направленный набор направлен вверх, если не указано иное. Другие авторы называют набор направленным тогда и только тогда, когда он направлен как вверх, так и вниз.^[4]

Направленные множества являются обобщением непустых полностью упорядоченных множеств . То есть, все полностью упорядоченные множества являются направленными множествами (в отличие от частично упорядоченных множеств , которые не обязательно должны быть направленными). Join-полурешетки (которые являются частично упорядоченными множествами) также являются направленными множествами, но не наоборот. Аналогично, решетки являются направленными множествами как вверх, так и вниз.

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

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

В дополнение к определению выше, существует эквивалентное определение. Направленное множество — это множество с предпорядком, таким, что каждое конечное подмножество имеет верхнюю границу. В этом определении существование верхней границы пустого подмножества подразумевает, что оно непустое. ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle A}$

Примеры

Множество натуральных чисел с обычным порядком является одним из важнейших примеров направленного множества. Каждое полностью упорядоченное множество является направленным множеством, включая и ${\displaystyle \mathbb {N} }$ ${\displaystyle \,\leq \,}$ ${\displaystyle (\mathbb {N} ,\leq ),}$ ${\displaystyle (\mathbb {N} ,\geq ),}$ ${\displaystyle (\mathbb {R} ,\leq ),}$ ${\displaystyle (\mathbb {R} ,\geq ).}$

(Тривиальным) примером частично упорядоченного множества, которое не является направленным, является множество , в котором единственными отношениями порядка являются и Менее тривиальный пример похож на следующий пример «действительных чисел, направленных к », но в котором правило упорядочения применяется только к парам элементов по одну сторону от (то есть, если взять элемент слева от и справа от него, то и не будут сравнимы, и подмножество не имеет верхней границы). ${\displaystyle \{a,b\},}$ ${\displaystyle a\leq a}$ ${\displaystyle b\leq b.}$ ${\displaystyle x_{0}}$ ${\displaystyle x_{0}}$ ${\displaystyle a}$ ${\displaystyle x_{0},}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle \{a,b\}}$

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

Пусть и будут направленными множествами. Тогда декартово произведение может быть преобразовано в направленное множество, определив если и только если и По аналогии с порядком произведения это направление произведения на декартовом произведении. Например, множество пар натуральных чисел может быть преобразовано в направленное множество, определив если и только если и ${\displaystyle \mathbb {D} _{1}}$ ${\displaystyle \mathbb {D} _{2}}$ ${\displaystyle \mathbb {D} _{1}\times \mathbb {D} _{2}}$ ${\displaystyle \left(n_{1},n_{2}\right)\leq \left(m_{1},m_{2}\right)}$ ${\displaystyle n_{1}\leq m_{1}}$ ${\displaystyle n_{2}\leq m_{2}.}$ ${\displaystyle \mathbb {N} \times \mathbb {N} }$ ${\displaystyle \left(n_{0},n_{1}\right)\leq \left(m_{0},m_{1}\right)}$ ${\displaystyle n_{0}\leq m_{0}}$ ${\displaystyle n_{1}\leq m_{1}.}$

Направлено к точке

Если — действительное число , то множество можно превратить в направленное множество, определив if (так что «большие» элементы ближе к ). Затем мы говорим, что действительные числа были направлены к Это пример направленного множества, которое не является ни частично упорядоченным , ни полностью упорядоченным . Это происходит потому, что антисимметрия нарушается для каждой пары и равноудалена от , где и находятся на противоположных сторонах Явно это происходит, когда для некоторого действительного числа в этом случае и даже несмотря на то , что Если бы этот предпорядок был определен на вместо тогда он все равно образовал бы направленное множество, но теперь у него был бы (уникальный) наибольший элемент , в частности ; однако он все равно не был бы частично упорядоченным. Этот пример можно обобщить на метрическое пространство , определив на или предпорядок тогда и только тогда, когда ${\displaystyle x_{0}}$ ${\displaystyle I:=\mathbb {R} \backslash \lbrace x_{0}\rbrace }$ ${\displaystyle a\leq _{I}b}$ ${\displaystyle \left|a-x_{0}\right|\geq \left|b-x_{0}\right|}$ ${\displaystyle x_{0}}$ ${\displaystyle x_{0}.}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle x_{0},}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle x_{0}.}$ ${\displaystyle \{a,b\}=\left\{x_{0}-r,x_{0}+r\right\}}$ ${\displaystyle r\neq 0,}$ ${\displaystyle a\leq _{I}b}$ ${\displaystyle b\leq _{I}a}$ ${\displaystyle a\neq b.}$ ${\displaystyle \mathbb {R} }$ ${\displaystyle \mathbb {R} \backslash \lbrace x_{0}\rbrace }$ ${\displaystyle x_{0}}$ ${\displaystyle (X,d)}$ ${\displaystyle X}$ ${\displaystyle X\setminus \left\{x_{0}\right\}}$ ${\displaystyle a\leq b}$ ${\displaystyle d\left(a,x_{0}\right)\geq d\left(b,x_{0}\right).}$

Максимальные и наибольшие элементы

Элемент предупорядоченного множества является максимальным элементом, если для каждого следует ^[5]. Он является наибольшим элементом , если для каждого ${\displaystyle m}$ ${\displaystyle (I,\leq )}$ ${\displaystyle j\in I,}$ ${\displaystyle m\leq j}$ ${\displaystyle j\leq m.}$ ${\displaystyle j\in I,}$ ${\displaystyle j\leq m.}$

Любое предупорядоченное множество с наибольшим элементом является направленным множеством с тем же предпорядком. Например, в частично упорядоченном множестве каждое нижнее замыкание элемента; то есть каждое подмножество вида , где есть фиксированный элемент из, является направленным. ${\displaystyle P,}$ ${\displaystyle \{a\in P:a\leq x\}}$ ${\displaystyle x}$ ${\displaystyle P,}$

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

Включение подмножества

Отношение включения подмножества вместе с его дуальным определяют частичные порядки на любом заданном семействе множеств . Непустое семейство множеств является направленным множеством относительно частичного порядка (соответственно, ) тогда и только тогда, когда пересечение (соответственно, объединение) любых двух его членов содержит в качестве подмножества (соответственно, содержится в качестве подмножества) некоторый третий член. В символах семейство множеств направлено относительно (соответственно, ) тогда и только тогда, когда ${\displaystyle \,\subseteq ,\,}$ ${\displaystyle \,\supseteq ,\,}$ ${\displaystyle \,\supseteq \,}$ ${\displaystyle \,\subseteq \,}$ ${\displaystyle I}$ ${\displaystyle \,\supseteq \,}$ ${\displaystyle \,\subseteq \,}$

для всех существует такое , что и (соответственно, и ) ${\displaystyle A,B\in I,}$ ${\displaystyle C\in I}$ ${\displaystyle A\supseteq C}$ ${\displaystyle B\supseteq C}$ ${\displaystyle A\subseteq C}$ ${\displaystyle B\subseteq C}$

или эквивалентно,

для всех существует такое , что (соответственно, ). ${\displaystyle A,B\in I,}$ ${\displaystyle C\in I}$ ${\displaystyle A\cap B\supseteq C}$ ${\displaystyle A\cup B\subseteq C}$

Многие важные примеры направленных множеств можно определить с помощью этих частичных порядков. Например, по определению, предфильтр или база фильтра — это непустое семейство множеств , которое является направленным множеством относительно частичного порядка и которое также не содержит пустое множество (это условие предотвращает тривиальность, поскольку в противном случае пустое множество было бы наибольшим элементом относительно ). Каждая π -система , которая является непустым семейством множеств , замкнутым относительно пересечения любых двух своих членов, является направленным множеством относительно Каждая λ-система является направленным множеством относительно Каждый фильтр , топология и σ-алгебра являются направленными множествами относительно обоих и ${\displaystyle \,\supseteq \,}$ ${\displaystyle \,\supseteq \,}$ ${\displaystyle \,\supseteq \,.}$ ${\displaystyle \,\subseteq \,.}$ ${\displaystyle \,\supseteq \,}$ ${\displaystyle \,\subseteq \,.}$

Хвосты сетей

По определению, сеть — это функция из направленного множества, а последовательность — это функция из натуральных чисел. Каждая последовательность канонически становится сетью, если наделить ее ${\displaystyle \mathbb {N} .}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle \,\leq .\,}$

Если — любая сеть из направленного множества , то для любого индекса множество называется хвостом множества, начинающегося с Семейство всех хвостов является направленным множеством относительно , ​​фактически, оно даже является предварительным фильтром. ${\displaystyle x_{\bullet }=\left(x_{i}\right)_{i\in I}}$ ${\displaystyle (I,\leq )}$ ${\displaystyle i\in I,}$ ${\displaystyle x_{\geq i}:=\left\{x_{j}:j\geq i{\text{ with }}j\in I\right\}}$ ${\displaystyle (I,\leq )}$ ${\displaystyle i.}$ ${\displaystyle \operatorname {Tails} \left(x_{\bullet }\right):=\left\{x_{\geq i}:i\in I\right\}}$ ${\displaystyle \,\supseteq ;\,}$

Районы

Если — топологическое пространство и — точка во множестве всех окрестностей , то можно превратить в направленное множество, записав тогда и только тогда, когда содержит Для каждого и  : ${\displaystyle T}$ ${\displaystyle x_{0}}$ ${\displaystyle T,}$ ${\displaystyle x_{0}}$ ${\displaystyle U\leq V}$ ${\displaystyle U}$ ${\displaystyle V.}$ ${\displaystyle U,}$ ${\displaystyle V,}$ ${\displaystyle W}$

• ${\displaystyle U\leq U}$поскольку содержит себя. ${\displaystyle U}$
• если и тогда и что подразумевает Таким образом ${\displaystyle U\leq V}$ ${\displaystyle V\leq W,}$ ${\displaystyle U\supseteq V}$ ${\displaystyle V\supseteq W,}$ ${\displaystyle U\supseteq W.}$ ${\displaystyle U\leq W.}$
• потому что и так как и у нас есть и ${\displaystyle x_{0}\in U\cap V,}$ ${\displaystyle U\supseteq U\cap V}$ ${\displaystyle V\supseteq U\cap V,}$ ${\displaystyle U\leq U\cap V}$ ${\displaystyle V\leq U\cap V.}$

Конечные подмножества

Множество всех конечных подмножеств множества направлено относительно , ​​поскольку для любых двух их объединение является верхней границей и в . Это конкретное направленное множество используется для определения суммы обобщенного ряда -индексированного набора чисел (или, в более общем смысле, суммы элементов в абелевой топологической группе , такой как векторы в топологическом векторном пространстве ) как предела сети частичных сумм, которая равна: ${\displaystyle \operatorname {Finite} (I)}$ ${\displaystyle I}$ ${\displaystyle \,\subseteq \,}$ ${\displaystyle A,B\in \operatorname {Finite} (I),}$ ${\displaystyle A\cup B\in \operatorname {Finite} (I)}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle \operatorname {Finite} (I).}$ ${\displaystyle {\textstyle \sum \limits _{i\in I}}r_{i}}$ ${\displaystyle I}$ ${\displaystyle \left(r_{i}\right)_{i\in I}}$ ${\displaystyle F\in \operatorname {Finite} (I)\mapsto {\textstyle \sum \limits _{i\in F}}r_{i};}$ $${\displaystyle \sum _{i\in I}r_{i}~:=~\lim _{F\in \operatorname {Finite} (I)}\ \sum _{i\in F}r_{i}~=~\lim \left\{\sum _{i\in F}r_{i}\,:F\subseteq I,F{\text{ finite }}\right\}.}$$

Логика

Пусть будет формальной теорией , которая представляет собой набор предложений с определенными свойствами (подробности о которых можно найти в статье по теме ). Например, может быть теорией первого порядка (например, теорией множеств Цермело–Френкеля ) или более простой теорией нулевого порядка . Предупорядоченное множество является направленным множеством, поскольку если и если обозначает предложение, образованное логической конъюнкцией , то и где Если — алгебра Линденбаума–Тарского, связанная с , то — частично упорядоченное множество, которое также является направленным множеством. ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle (S,\Leftarrow )}$ ${\displaystyle A,B\in S}$ ${\displaystyle C:=A\wedge B}$ ${\displaystyle \,\wedge ,\,}$ ${\displaystyle A\Leftarrow C}$ ${\displaystyle B\Leftarrow C}$ ${\displaystyle C\in S.}$ ${\displaystyle S/\sim }$ ${\displaystyle S}$ ${\displaystyle \left(S/\sim ,\Leftarrow \right)}$

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

Пример направленного множества, которое не является полурешеткой соединений

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

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

Отношение порядка в направленном множестве не обязательно должно быть антисимметричным , и поэтому направленные множества не всегда являются частичными порядками . Однако термин направленный набор также часто используется в контексте частично упорядоченных множеств. В этой ситуации подмножество частично упорядоченного множества называется направленным подмножеством, если оно является направленным множеством в соответствии с тем же частичным порядком: другими словами, это не пустое множество , и каждая пара элементов имеет верхнюю границу. Здесь отношение порядка на элементах наследуется от ; по этой причине рефлексивность и транзитивность не обязательно должны явно требоваться. ${\displaystyle A}$ ${\displaystyle (P,\leq )}$ ${\displaystyle A}$ ${\displaystyle P}$

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

Направленные подмножества используются в теории доменов , которая изучает направленно-полные частичные порядки . ^[6] Это частично упорядоченные множества, в которых каждое направленное вверх множество должно иметь наименьшую верхнюю границу . В этом контексте направленные подмножества снова обеспечивают обобщение сходящихся последовательностей. ^{[ необходимо дальнейшее объяснение ]}

Смотрите также

• Центрированное множество  – Теория порядка
• Фильтрованная категория  – непустая категория, такая что для любых двух объектов 𝑥, 𝑦 существует диаграмма 𝑥→𝑧←𝑦 и для любых двух параллельных стрелок 𝑓,𝑔: 𝑥→𝑦 существует ℎ: 𝑦→𝑧 такая, что ℎ∘𝑓=ℎ∘𝑔Pages displaying wikidata descriptions as a fallback
• Фильтры в топологии  – использование фильтров для описания и характеристики всех основных топологических понятий и результатов.
• Связанное множество  – Математическая концепция, касающаяся частично упорядоченных множеств в теории (частичного) порядка.
• Сеть (математика)  – обобщение последовательности точек.

Примечания

1. Келли, стр. 65.
2. Роберт С. Борден (1988). Курс углубленного исчисления . Courier Corporation. стр. 20. ISBN 978-0-486-15038-3.
3. Арлен Браун; Карл Пирси (1995). Введение в анализ . Springer. стр. 13. ISBN 978-1-4612-0787-0.
4. Зигфрид Карл; Сеппо Хейккиля (2010). Теория неподвижных точек в упорядоченных множествах и ее применение: от дифференциальных и интегральных уравнений к теории игр . Springer. стр. 77. ISBN 978-1-4419-7585-0.
5. Это подразумевает, что если — частично упорядоченное множество . ${\displaystyle j=m}$ ${\displaystyle (I,\leq )}$
6. Герц, стр. 2.

Ссылки

• Дж. Л. Келли (1955), Общая топология .
• Гирц, Хофманн, Кеймель и др. (2003), Непрерывные решетки и домены , Cambridge University Press. ISBN 0-521-80338-1 .