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

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

Определения

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

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

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

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

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

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

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

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

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

Примеры

• Каждое конечное частично упорядоченное множество направленно полное.
• Все полные решетки также направленно полные.
• Для любого частичного набора набор всех непустых фильтров , упорядоченных по включению подмножества , представляет собой 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.
• Давайте использовать термин « дедуктивная система » как набор предложений , замкнутых относительно следствий (для определения понятия следствия воспользуемся, например, Альфреда Тарского ). алгебраическим подходом ). Существуют интересные теоремы, касающиеся множества дедуктивных систем, представляющих собой направленно-полный частичный порядок. Кроме того, набор дедуктивных систем может быть выбран естественным образом так, чтобы он имел наименьший элемент (так что он также может быть точечным dcpo), поскольку набор всех следствий пустого набора (т. е. «множество логически доказуемых /логически действительные предложения») является (1) дедуктивной системой, (2) содержащейся во всех дедуктивных системах.

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

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

Альтернативно, упорядоченный набор $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.Таким образом, полные частичные порядки с непрерывными по Скотту отображениями образуют декартову замкнутую категорию .

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

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

См. также

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

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

Ссылки

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