Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

  • Частично упорядоченный набор является направленным полным частичным порядком ( dcpo ), если каждое из его направленных подмножеств имеет супремум . Подмножество частичного порядка является направленным, если оно не пусто и каждая пара элементов имеет верхнюю границу в подмножестве. В литературе dcpos иногда встречается под ярлыком up-complete poset .
  • Частично упорядоченный набор - это направленный-полный частичный порядок с точками, если это DCPO с наименьшим элементом. Иногда их называют сокращенно cppo s.
  • Частично упорядоченное множество - это ω-полный частичный порядок ( ω-cpo ), если это ч.у., в котором каждая ω-цепь ( x 1 ≤ x 2 ≤ x 3 ≤ x 4 ≤ ...) имеет супремум, принадлежащий базовый набор позета. Каждый dcpo является ω-cpo, поскольку каждая ω-цепь является направленным множеством, но обратное неверно. Однако каждое ω-cpo с базисом также является dcpo (с тем же базисом). [1] ω-cpo (dcpo) с базисом также называется непрерывным ω-cpo (непрерывным dcpo).

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

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

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

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

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

Свойства [ править ]

Упорядоченное множество P является заостренным DCPO тогда и только тогда , когда каждая цепь имеет верхнюю грань в P , т.е. P является цепью полной . [5] В качестве альтернативы, упорядоченное множество P является указанным dcpo тогда и только тогда, когда каждое сохраняющее порядок собственное отображение P имеет наименьшую фиксированную точку . Каждое множество S можно превратить в заостренный dcpo, добавив наименьший элемент ⊥ и введя плоский порядок с ⊥ ≤  s и s ≤  s для каждого s  ∈  S и никаких других отношений порядка.

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

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

  • направлен по каждому направлению .
  • для каждого направленного .

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

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

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

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

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

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

  1. ^ Abramsky S , Gabbay DM , Maibaum TS (1994). Справочник по логике в компьютерных науках, том 3 . Оксфорд: Clarendon Press. Предложение 2.2.14, стр. 20. ISBN 9780198537625.
  2. ^ Тарский, Альфред: Bizonyítás és igazság / Válogatott tanulmányok. Gondolat, Budapest, 1990. (Название означает: Доказательство и истина / Избранные статьи.)
  3. ^ Стэнли Н. Беррис и HP Sankappanavar: курс универсальной алгебры
  4. ^ См. Онлайн на стр. 24 упражнения 5–6 из §5 в BurSan: UnivAlg . Или, на бумаге, см. Tar: BizIg .
  5. ^ Марковский, Джордж (1976), "Сеть-полной Posets и направленные наборы с приложениями", Алгебра Universalis , 6 (1): 53-68, DOI : 10.1007 / bf02485815 , МР 0398913 , S2CID 16718857  .
  6. ^ Барендрегт, Хенк , Лямбда-исчисление, его синтаксис и семантика. Архивировано 23августа2004 г. в Wayback Machine , Северная Голландия (1984).
  7. ^ См. Теорему Кнастера – Тарского ; Основы проверки программ, 2-е издание, Жак Лоэккс и Курт Сибер, John Wiley & Sons, ISBN 0-471-91282-4 , глава 4; Теорема Кнастера – Тарского, сформулированная над cpo, дается для доказательства в качестве упражнения 4.3–5 на стр. 90. 

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

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