Преемственность Скотта

Определение непрерывности функций между частично упорядоченными множествами

В математике , если даны два частично упорядоченных множества P и Q , функция f : P → Q между ними является непрерывной по Скотту (названной в честь математика Даны Скотт ), если она сохраняет все направленные супремумы . То есть для каждого направленного подмножества D множества P с верхней границей в P его образ имеет верхнюю границу в Q , и эта верхняя граница является образом верхней границы D , т. е . где находится направленное соединение. ^[1] Когда ЧУУ истинностных значений, т.е. пространство Серпинского , тогда непрерывные по Скотту функции являются характеристическими функциями открытых множеств, и, таким образом, пространство Серпинского является классифицирующим пространством для открытых множеств. ^[2] ${\displaystyle \sqcup f[D]=f(\sqcup D)}$ ${\displaystyle \sqcup }$ ${\displaystyle Q}$

Подмножество O частично упорядоченного множества P называется Скотт-открытым, если оно является верхним множеством и если оно недоступно направленными соединениями , т. е. если все направленные множества D с супремумом в O имеют непустое пересечение с O. Открытые по Скотту подмножества частично упорядоченного множества P образуют топологию на P , топологию Скотта . Функция между частично упорядоченными множествами является непрерывной по Скотту тогда и только тогда, когда она непрерывна относительно топологии Скотта. ^[1]

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

Непрерывные по Скотту функции используются при изучении моделей лямбда-исчислений ^[3] и денотационной семантики компьютерных программ.

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

Непрерывная по Скотту функция всегда монотонна , то есть если для , то . ${\displaystyle A\leq _{P}B}$ ${\displaystyle A,B\subset P}$ ${\displaystyle f(A)\leq _{Q}f(B)}$

Подмножество направленного полного частичного порядка замкнуто относительно топологии Скотта, индуцированной частичным порядком, тогда и только тогда, когда оно является нижним множеством и замкнуто относительно супремумов направленных подмножеств. ^[4]

Направленный полный частичный порядок (dcpo) с топологией Скотта всегда является пространством Колмогорова (т. е. он удовлетворяет аксиоме разделения T 0 ). ^[4] Однако dcpo с топологией Скотта является хаусдорфовым пространством тогда и только тогда, когда порядок тривиален. ^[4] Множества, открытые по Скотту, образуют полную решетку , если они упорядочены по включению . ^[5]

Для любого пространства Колмогорова топология индуцирует отношение порядка в этом пространстве, порядок специализации : x ≤ y тогда и только тогда, когда каждая открытая окрестность x также является открытой окрестностью y . Отношение порядка dcpo D может быть восстановлено из открытых по Скотту множеств как порядок специализации, индуцированный топологией Скотта. Однако dcpo, оснащенный топологией Скотта, не обязательно должен быть трезвым : порядок специализации, индуцированный топологией трезвого пространства, превращает это пространство в dcpo, но топология Скотта, полученная на основе этого порядка, тоньше, чем исходная топология. ^[4]

Примеры

Открытые множества в данном топологическом пространстве, упорядоченные по включению , образуют решетку , на которой может быть определена топология Скотта. Подмножество X топологического пространства T компактно относительно топологии на T (в том смысле, что каждое открытое покрытие X содержит конечное подпокрытие X ) тогда и только тогда , когда множество открытых окрестностей X открыто относительно топология Скотта. ^[5]

Для CPO , декартовой закрытой категории dcpo, двумя особенно примечательными примерами непрерывных по Скотту функций являются curry и apply . ^[6]

Нуэль Белнап использовал непрерывность Скотта для расширения логических связок до четырехзначной логики . ^[7]

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

• Топология Александрова
• Верхняя топология

Сноски

1. Викерс, Стивен (1989). Топология через логику . Издательство Кембриджского университета . ISBN 978-0-521-36062-3.
2. Топология Скотта в n Lab
3. Скотт, Дана (1972). «Непрерывные решетки». В Ловере, Билл (ред.). Топосы, алгебраическая геометрия и логика . Конспект лекций по математике. Том. 274. Шпрингер-Верлаг.
4. Абрамский, С.; Юнг, А. (1994). «Теория предметной области» (PDF) . В Абрамский С.; Габбай, DM; Майбаум, TSE (ред.). Справочник по логике в информатике . Том. III. Издательство Оксфордского университета. ISBN 978-0-19-853762-5.
5. Бауэр, Андрей и Тейлор, Пол (2009). «Реалии Дедекинда в абстрактной каменной двойственности». Математические структуры в информатике . 19 (4): 757–838. CiteSeerX 10.1.1.424.6069 . дои : 10.1017/S0960129509007695. S2CID  6774320 . Проверено 8 октября 2010 г. 
6. Барендрегт, HP (1984). Лямбда-исчисление . Северная Голландия. ISBN 978-0-444-87508-2. (См. теоремы 1.2.13, 1.2.14)
7. Н. Белнап (1975) «Как компьютеры должны думать», страницы с 30 по 56 в « Современных аспектах философии» , редактор Гилберта Райла , Oriel Press ISBN 0-85362-161-6 

Рекомендации

• «Топология Скотта». ПланетаМатематика .