Полный частичный заказ

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

Определения

Термин « полный частичный порядок» , сокращенно cpo , имеет несколько возможных значений в зависимости от контекста.

Частично упорядоченное множество является направленно-полным частичным порядком ( dcpo ), если каждое из его направленных подмножеств имеет супремум . (Подмножество частичного порядка является направленным, если оно непусто и каждая пара элементов имеет верхнюю границу в подмножестве.) В литературе dcpos иногда также фигурирует под названием up-complete poset .

Указанный направленно-полный частичный порядок ( указанный dcpo , иногда сокращенно cppo ) — это dcpo с наименьшим элементом (обычно обозначаемым ). Сформулировав это иначе, указанный dcpo имеет супремум для каждого направленного или пустого подмножества. Термин цепочно-полный частичный порядок также используется из-за характеристики указанных dcpos как частично упорядоченных множеств, в которых каждая цепь имеет супремум. ${\displaystyle \bot }$

Связанное понятие — понятие ω-полного частичного порядка ( ω-cpo ). Это частично упорядоченные множества, в которых каждая ω-цепь ( ) имеет супремум, принадлежащий частично упорядоченному множеству. То же самое понятие можно распространить на другие мощности цепей. ^[1] ${\displaystyle x_{1}\leq x_{2}\leq x_{3}\leq ...}$

Каждый dcpo является ω-cpo, поскольку каждая ω-цепь является направленным множеством, но обратное неверно . Однако каждый ω-cpo с базисом также является dcpo (с тем же базисом). ^[2] ω-cpo (dcpo) с базисом также называется непрерывным ω-cpo (или непрерывным dcpo).

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

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

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

По аналогии с дополнением Дедекинда–Макнейла частично упорядоченного множества, каждое частично упорядоченное множество может быть расширено единственным образом до минимального dcpo. ^[1]

Примеры

• Каждый конечный посет является направленно полным.
• Все полные решетки также направлены полно.
• Для любого poset множество всех непустых фильтров , упорядоченное включением подмножества , является dcpo. Вместе с пустым фильтром оно также является направленным. Если порядок имеет двоичные соответствия , то эта конструкция (включая пустой фильтр) фактически дает полную решетку .
• Каждое множество S можно превратить в точечный dcpo, добавив наименьший элемент ⊥ и введя плоский порядок с ⊥ ≤  s и s ≤  s для каждого s в S и без каких-либо других отношений порядка.
• Множество всех частичных функций на некотором заданном множестве S можно упорядочить, определив f  ≤  g тогда и только тогда, когда g расширяет f , т. е. если область определения f является подмножеством области определения g и значения f и g совпадают на всех входных данных, для которых они оба определены. (Эквивалентно, f  ≤  g тогда и только тогда, когда f  ⊆  g , где f и g отождествляются со своими соответствующими графиками .) Этот порядок является точечным dcpo, где наименьшим элементом является нигде не определенная частичная функция (с пустой областью определения). Фактически, ≤ также ограниченно полно . Этот пример также демонстрирует, почему не всегда естественно иметь наибольший элемент.
• Множество всех линейно независимых подмножеств векторного пространства V , упорядоченное по включению .
• Множество всех функций частичного выбора на наборе непустых множеств, упорядоченных по ограничению.
• Множество всех простых идеалов кольца , упорядоченное по включению.
• Специализация любого трезвого пространства — это dcpo.
• Давайте будем использовать термин « дедуктивная система » как множество предложений , замкнутое относительно следствия (для определения понятия следствия давайте воспользуемся, например, алгебраическим подходом Альфреда Тарского ^{[3] [4]} ). Существуют интересные теоремы, которые касаются множества дедуктивных систем, являющихся направленно-полным частичным порядком. ^[5] Кроме того, множество дедуктивных систем может быть выбрано так, чтобы иметь наименьший элемент естественным образом (так что оно может быть также направленным dcpo), потому что множество всех следствий пустого множества (т. е. «множество логически доказуемых/логически допустимых предложений») является (1) дедуктивной системой (2), содержащейся во всех дедуктивных системах.

Характеристика

Упорядоченный набор является dcpo тогда и только тогда, когда каждая непустая цепь имеет супремум. Как следствие, упорядоченный набор является точечным dcpo тогда и только тогда, когда каждая (возможно пустая) цепь имеет супремум, т. е. тогда и только тогда, когда он является цепочно-полным . ^{[1] [6] [7] [8]} Доказательства основаны на аксиоме выбора .

В качестве альтернативы, упорядоченное множество является точечным dcpo тогда и только тогда, когда каждое сохраняющее порядок самоотображение имеет наименьшую неподвижную точку . ${\displaystyle P}$ ${\displaystyle P}$

Непрерывные функции и неподвижные точки

Функция f между двумя dcpos P и Q называется (по Скотту) непрерывной , если она отображает направленные множества в направленные множества, сохраняя при этом их супремумы:

• ${\displaystyle f(D)\subseteq Q}$направлено для каждого направленного . ${\displaystyle D\subseteq P}$
• ${\displaystyle f(\sup D)=\sup f(D)}$за каждый направленный . ${\displaystyle D\subseteq P}$

Обратите внимание, что каждая непрерывная функция между dcpos является монотонной функцией . Это понятие непрерывности эквивалентно топологической непрерывности, индуцированной топологией Скотта .

Множество всех непрерывных функций между двумя dcpo P и Q обозначается [ P  →  Q ]. Оснащенное точечным порядком , это снова dcpo, и указывается всякий раз, когда указывается Q. Таким образом, полные частичные порядки с непрерывными по Скотту отображениями образуют декартову замкнутую категорию . ^[9]

Каждое сохраняющее порядок отображение f точечного dcpo ( P , ⊥) имеет наименьшую неподвижную точку. ^[10] Если f непрерывна, то эта неподвижная точка равна супремуму итераций ( ⊥, f  (⊥), f  ( f  (⊥)), … f ⁿ (⊥), …) ⊥ (см. также теорему Клини о неподвижной точке ).

Другая теорема о неподвижной точке — теорема Бурбаки-Витта , утверждающая, что если — функция из dcpo в себя со свойством, что для всех , то имеет неподвижную точку. Эта теорема, в свою очередь, может быть использована для доказательства того, что лемма Цорна является следствием аксиомы выбора. ^{[11] [12]} ${\displaystyle f}$ ${\displaystyle f(x)\geq x}$ ${\displaystyle x}$ ${\displaystyle f}$

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

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

Направленная полнота различными способами связана с другими понятиями полноты, такими как цепочечная полнота .

Примечания

1. Марковский, Джордж (1976), «Цепочно-полные посеты и направленные множества с приложениями», Algebra Universalis , 6 (1): 53–68, doi :10.1007/bf02485815, MR  0398913, S2CID  16718857
2. Абрамски С. , Габбей Д.М. , Майбаум Т.С. (1994). Справочник по логике в информатике, том 3. Оксфорд: Clarendon Press. Предложение 2.2.14, стр. 20. ISBN 9780198537625.
3. Тарский, Альфред: Bizonyítás é igazság / Válogatott tanulmanyok. Гондолат, Будапешт, 1990 г. (Название означает: Доказательство и истина / Избранные статьи.)
4. Стэнли Н. Беррис и Х. П. Санкаппанавар: Курс универсальной алгебры
5. См. онлайн на стр. 24 упражнения 5–6 §5 в [1]. Или на бумаге см. Tar:BizIg.
6. Губо-Ларрек, Жан (23 февраля 2015 г.). «Лемма Ивамуры, теорема Марковского и ординалы» . Проверено 6 января 2024 г.
7. Кон, Пол Мориц. Универсальная алгебра . Harper and Row. стр. 33.
8. Goubault-Larrecq, Jean (28 января 2018 г.). «Markowsky or Cohn?» . Получено 6 января 2024 г.
9. Барендрегт, Хенк , Лямбда-исчисление, его синтаксис и семантика Архивировано 23 августа 2004 г. в Wayback Machine , Северная Голландия (1984)
10. Это усиление теоремы Кнастера–Тарского , иногда называемой «теоремой Патарая». Например, см. раздел 4.1 книги «Realizability at Work: Separating Two Constructive Notions of Finiteness» (2016) Безема и др. См. также главу 4 книги « The foundations of program verification » (1987), 2-е издание, Жак Лёккс и Курт Зибер, John Wiley & Sons, ISBN 0-471-91282-4 , где теорема Кнастера–Тарского, сформулированная над указанными dcpo, доказывается в упражнении 4.3-5 на стр. 90. 
11. Бурбаки, Николя (1949), «Sur le theorème de Zorn», Archiv der Mathematik , 2 (6): 434–437 (1951), doi : 10.1007/bf02036949, MR  0047739, S2CID  117826806.
12. Витт, Эрнст (1951), "Beweisstudien zum Satz von M. Zorn", Mathematische Nachrichten , 4 : 434–438, doi : 10.1002/mana.3210040138, MR  0039776.

Ссылки

• Davey, BA; Priestley, HA (2002). Введение в решетки и порядок (второе издание). Cambridge University Press. ISBN 0-521-78451-4.