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

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

Определения [ править ]

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

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

Заостренный направленно-полный частичный порядок ( заостренный dcpo , иногда сокращенно cppo ) — это dcpo с наименьшим элементом (обычно обозначаемый $\bot$ ). Другими словами, заостренный dcpo имеет верхнюю границу для каждого направленного или пустого подмножества. термин «полный по цепочке частичный порядок» Также используется из-за характеристики заостренных dcpos как частично упорядоченных наборов, в которых каждая цепь имеет супремум.

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

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

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

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

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

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

Примеры [ править ]

Каждое конечное частично упорядоченное множество направленно полное.
Все полные решетки также направленно полные.
Для любого частичного набора набор всех непустых фильтров , упорядоченных по включению подмножества , представляет собой 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] Доказательства опираются на аксиому выбора .

Альтернативно, упорядоченный набор $P$ является точечным dcpo тогда и только тогда, когда каждое сохраняющее порядок самоотображение $P$ имеет наименьшую фиксированную точку .

Непрерывные функции и фиксированные точки [ править ]

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

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

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

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

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

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

См. также [ править ]

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

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

Примечания [ править ]

^ Перейти обратно: ^а ^б ^с Марковски, Джордж (1976), «Цепные полные постулаты и направленные множества с приложениями», Algebra Universalis , 6 (1): 53–68, doi : 10.1007/bf02485815 , MR 0398913 , S2CID 16718857
^ Абрамский С. , Габбай Д.М. , Майбаум Т.С. (1994). Справочник по логике в информатике, том 3 . Оксфорд: Кларендон Пресс. Положение 2.2.14, стр. 20. ISBN 9780198537625 .
^ Тарский, Альфред: Доказательства и истина / Избранные исследования. Гондолат, Будапешт, 1990 г. (Название означает: Доказательство и истина / Избранные статьи.)
^ Стэнли Н. Беррис и HP Санкаппанавар: Курс универсальной алгебры
^ См. онлайн на стр. 24 упражнения 5–6 §5 в [1] . Или на бумаге см. Tar:BizIg .
^ Губо-Ларрек, Жан (23 февраля 2015 г.). «Лемма Ивамуры, теорема Марковского и ординалы» . Проверено 6 января 2024 г.
^ Кон, Пол Мориц. Универсальная алгебра . Харпер и Роу. п. 33.
^ Губо-Ларрек, Жан (28 января 2018 г.). «Марковский или Кон?» . Проверено 6 января 2024 г.
^ Барендрегт, Хенк , Лямбда-исчисление, его синтаксис и семантика. Архивировано 23 августа 2004 г. в Wayback Machine , Северная Голландия (1984).
^ См. теорему Кнастера – Тарского ; Основы верификации программ, 2-е издание, Жак Лёкс и Курт Зибер, John Wiley & Sons, ISBN 0-471-91282-4 , глава 4; Теорема Кнастера-Тарского, сформулированная для cpo, приведена для доказательства в виде упражнения 4.3-5 на стр. 90.
^ Бурбаки, Николя (1949), «О теореме Цорна», Archiv der Mathematik , 2 (6): 434–437 (1951), doi : 10.1007/bf02036949 , MR 0047739 , S2CID 117826806 .
^ Витт, Эрнст (1951), «Доказательства теоремы М. Цорна», Mathematical News , 4 : 434–438, doi : 10.1002/mana.3210040138 , MR 0039776 .

Ссылки [ править ]

Дэйви, бакалавр; Пристли, ХА (2002). Введение в решетки и порядок (второе изд.). Издательство Кембриджского университета. ISBN 0-521-78451-4 .

[markowsky-1976-1] Перейти обратно: ^а ^б ^с Марковски, Джордж (1976), «Цепные полные постулаты и направленные множества с приложениями», Algebra Universalis , 6 (1): 53–68, doi : 10.1007/bf02485815 , MR 0398913 , S2CID 16718857

[2] Абрамский С. , Габбай Д.М. , Майбаум Т.С. (1994). Справочник по логике в информатике, том 3 . Оксфорд: Кларендон Пресс. Положение 2.2.14, стр. 20. ISBN 9780198537625 .

[Tar-BizIg-3] Тарский, Альфред: Доказательства и истина / Избранные исследования. Гондолат, Будапешт, 1990 г. (Название означает: Доказательство и истина / Избранные статьи.)

[BurSan-UnivAlg-4] Стэнли Н. Беррис и HP Санкаппанавар: Курс универсальной алгебры

[seqdcpo-5] См. онлайн на стр. 24 упражнения 5–6 §5 в [1] . Или на бумаге см. Tar:BizIg .

[6] Губо-Ларрек, Жан (23 февраля 2015 г.). «Лемма Ивамуры, теорема Марковского и ординалы» . Проверено 6 января 2024 г.

[7] Кон, Пол Мориц. Универсальная алгебра . Харпер и Роу. п. 33.

[8] Губо-Ларрек, Жан (28 января 2018 г.). «Марковский или Кон?» . Проверено 6 января 2024 г.

[barendregt1984-9] Барендрегт, Хенк , Лямбда-исчисление, его синтаксис и семантика. Архивировано 23 августа 2004 г. в Wayback Machine , Северная Голландия (1984).

[10] См. теорему Кнастера – Тарского ; Основы верификации программ, 2-е издание, Жак Лёкс и Курт Зибер, John Wiley & Sons, ISBN 0-471-91282-4 , глава 4; Теорема Кнастера-Тарского, сформулированная для cpo, приведена для доказательства в виде упражнения 4.3-5 на стр. 90.

[11] Бурбаки, Николя (1949), «О теореме Цорна», Archiv der Mathematik , 2 (6): 434–437 (1951), doi : 10.1007/bf02036949 , MR 0047739 , S2CID 117826806 .

[12] Витт, Эрнст (1951), «Доказательства теоремы М. Цорна», Mathematical News , 4 : 434–438, doi : 10.1002/mana.3210040138 , MR 0039776 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]