Teoria kategorii dla informatyków/Wykład 12: Teoria dziedzin I
Dziedziny jako częściowe porządki
Ten wykład jest wprowadzeniem w teorię dziedzin, którą zapoczątkowały badania Dany Scotta i Christophera Stracheya nad semantyką funkcyjnych języków programowania pod koniec lat 60. Dziedziny są to pewne częściowe porządki, które posiadają suprema zbiorów skierowanych i dodatkową relację binarną nazywaną relacją aproksymacji. Przeróżne kategorie dziedzin zostały wykorzystane jako matematyczne modele języków programowania, w sensie, który wyjaśnimy w Wykładzie 13. Kategorie dziedzin są znakomitym uniwersum, w którym za pomocą ścisłych matematycznych metod można opisywać rekursywne definicje procedur, struktur danych i innych mechanizmów języków programowania.
Ten wykład wprowadza wszystkie wstępne pojęcia teorii dziedzin w języku częściowych porządków i jest niezależny od wcześniejszych wykładów.
Dziedziny jako częściowe porządki
Porządek (inaczej: częściowy porządek, zbiór częściowo uporządkowany, poset) to zbiór wyposażony w relację
, która jest zwrotna, przechodnia i antysymetryczna.Niech
będzie częściowym porządkiem. Element jest ograniczeniem górnym zbioru , jeśli dla każdego (co zapisujemy również ). Podobnie, element jest ograniczeniem dolnym zbioru , jeśli dla każdego (czyli ). Jeśli dwa dowolne elementy posiadają w ograniczenie górne, to oznaczamy to jako . W przeciwnym wypadku piszemy . Najmniejsze ograniczenie górne zbioru (jeśli istnieje) nazywamy supremum i oznaczamy . Największe ograniczenie dolne zbioru (jeśli istnieje) nazywamy infimum i oznaczamy . Jeśli jest dwuelementowy, np. , i posiada supremum (infimum), to piszemy ( ) i mówimy o supremum (infimum) binarnym.Poset jest kratą, jeśli ma wszystkie suprema i infima binarne. Poset jest kratą zupełną, jeśli dowolny jego podzbiór posiada zarówno supremum, jak i infimum.
Podzbiór
porządku nazywamy skierowanym, co oznaczamy , jeśli jest niepusty i każde dwa elementy z posiadają ograniczenie górne w (tzn. i dla pewnego ). Łańcuchem nazywamy każdy zbiór skierowany, który jest liniowy. Supremum zbioru skierowanego oznaczamy , kiedykolwiek istnieje. Podzbiór porządku nazywamy filtrowanym, jeśli jest niepusty i każde dwa elementy z posiadają ograniczenie dolne w (tzn. i dla pewnego ). Infimum zbioru filtrowanego (jeśli istnieje) oznaczamy .Poset
nazywamy -zupełnym, jeśli posiada element najmniejszy oraz każde dwa elementy takie, że , posiadają supremum .Oznaczamy:
jest zbiorem dolnym, jeśli . jest zbiorem górnym, jeśli . jest ideałem, jeśli jest skierowany i dolny. jest filtrem, jeśli jest filtrowany i górny. Ideałem głównym nazywamy każdy ideał postaci dla . Filtrem głównym jest każdy filtr postaci dla pewnego .
Poset
nazywamy dcpo) (od angielskiego określenia: directed-complete partial order), jeśli każdy zbiór skierowany posiada supremum w .W każdym zbiorze częściowo uporządkowanym
możemy zdefiniować relację aproksymacji (ang. way-below relation) w następujący sposób: dla mamy (czytamy: aproksymuje lub jest skończony względem ) wtedy i tylko wtedy, gdy dla każdego zbioru skierowanego takiego, że mamy dla pewnego . W jednym zdaniu:Element
nazywamy zwartym lub skończonym, gdy . Zbiór wszystkich elementów zwartych posetu oznaczamy zwykle . Dla relacji przyjmujemy podobne oznaczenia, jak dla porządku:
Relacja aproksymacji w dowolnym posecie posiada następujące własności:
- ,
- ,
- .
Bazą posetu nazywamy każdy podzbiór taki, że dla każdego zbiór jest skierowany i posiada supremum .
Definicja 12.1
Twierdzenie 12.2
Dowód
będzie ciągły i będzie bazą dla . Niech będzie dowolnym elementem . Pokażemy, że jest zbiorem skierowanym i jego supremum to . Niech . Skoro z założenia zbiór jest skierowany z supremum , to z definicji relacji aproksymacji istnieją dwa elementy takie, że oraz . Ale ze skierowania zbioru wynika istnienie elementu takiego, że oraz . A zatem z własności (w2) mamy , czyli wykazaliśmy, że zbiór jest skierowany. Zauważmy, że jest ograniczeniem górnym zbioru . Jeśli jest dowolnym innym ograniczeniem górnym, to skoro , to . A zatem . Z drugiej strony, jeśli jest dowolnym posetem takim, że , to jest bazą, a więc jest ciągły.Zauważmy, że drobna modyfikacja pierwszej części powyższego dowodu pozwala nam wywnioskować, że jeśli
jest bazą dla , to dowolny nadzbiór jest również bazą dla .Twierdzenie 12.3 [interpolatywność aproksymacji]
- .
Definicja 12.4 [dziedzina]
Dziedziną algebraiczną nazywamy każdy dcpo algebraiczny
. Poset jest dziedziną -ciągłą, jeśli posiada przeliczalną bazę. Dziedzina algebraiczna z przeliczalną bazą jest nazywana dziedziną -algebraiczną lub dziedziną Scotta. (Zauważmy, że na to, by dziedzina algebraiczna była -algebraiczna potrzeba i wystarcza, by baza była przeliczalna. Dowód tego stwierdzenia jest bardzo prosty i wynika z dwóch faktów: z tego, że dla każdej bazy dziedziny oraz z tego, że w dowolnym posecie każdy nadzbiór bazy jest również bazą).Rozważmy następujące sztandarowe przykłady zbiorów częściowo uporządkowanych:
Przykład 12.5 [poset skończony]
Przykład 12.6 [liczby naturalne]
z porządkiem naturalnym każdy element jest zwarty, tak więc jest posetem algebraicznym. Poset nie jest jednak dcpo, ponieważ łańcuch nie ma supremum.
Przykład 12.7 [odcinek]
z naturalnym porządkiem jest ciągły, co łatwo wynika z faktu, że wtedy i tylko wtedy, gdy lub . Jest to również krata zupełna, a więc w szczególności dziedzina ciągła i poset -zupełny.
Przykład 12.8 [zbiór potęgowy]

Pokażemy, że dla
mamy wtedy i tylko wtedy, gdy jest skończonym podzbiorem . Rzeczywiście, załóżmy, że . Ponieważi tenże zbiór jest skierowany, istnieje
Załóżmy, że taki, że . Zbiór jest więc skończony, jako podzbiór zbioru skończonego . . Przypuśćmy, że dla pewnego zbioru skierowanego w . Mamy więc , co oznacza, że dla każdego istnieje taki, że . Ponieważ jest skierowany, istnieje , który zawiera wszystkie zbiory . To oznacza, że , co należało pokazać.
Przykład 12.9 [dziedzina podprzedziałów odcinka]
dla
. Poset jest dcpo, -zupełny, -ciągły i nie jest algebraiczny. Elementem najmniejszym jest , a element największy nie istnieje. Elementami maksymalnymi są wszystkie przedziały postaci dla , które utożsamiamy w sposób naturalny z liczbami rzeczywistymi z odcinka . Relacja aproksymacji jest dana jako:Bazą przeliczalną w
jest rodzina wszystkich podprzedziałów odcinka o końcach wymiernych.
Przykład 12.10 [dziedzina przedziałów]
Przykład 12.11 [dziedzina kul]
Można pokazać, że relacja
jest częściowym porządkiem. Posetjest ciągły, a relacja aproksymacji może być opisana jako:
Poset
jest dziedziną (tj. jest dcpo) wtedy i tylko wtedy, gdy jest przestrzenią metryczną zupełną. Poset jest -ciągły wtedy i tylko wtedy, gdy przestrzeń metryczna jest ośrodkowa.
Przykład 12.12 [model zbioru Cantora]
Funkcje monotoniczne
Funkcję
między posetami nazywamy monotoniczną, jeśli zachowuje porządek, tj. jeśli w , to w . Funkcja jest ciągła, jeśli zachowuje suprema zbiorów skierowanych, to znaczy: jeśli jest skierowany i posiada supremum , to posiada supremum . Zauważmy, że każda funkcja ciągła jest monotoniczna. Rzeczywiście, jeśli w , to zbiór jest skierowany i ma supremum . Tak więc . Z kolei, monotoniczność implikuje, że dla skierowanego, zbiór jest również skierowany. Wnioskujemy więc, że funkcja jest ciągła wtedy i tylko wtedy, gdy dla dowolnego zbioru skierowanego posiadającego supremum, zbiór jest skierowany oraz zachodzi .
Dziedziny jako topologie
Topologią na zbiorze
nazywamy dowolną rodzinę podzbiorów zbioru zamkniętą zewzględu na skończone przecięcia i dowolne sumy, a parę nazywamy przestrzenią topologiczną.Definicję powyższą możemy wypowiedzieć na wiele równoważnych sposobów, na przykład: topologią nazywamy każdy podzbiór porządku zamknięty ze względu na dowolne suprema i skończone infima. O elementach mówimy, że są to zbiory otwarte. Z definicji mamy więc, że skończone przecięcie zbiorów otwartych jest zbiorem otwartym i dowolna suma zbiorów otwartych jest zbiorem otwartym. Tak więc rodzina jest kratą, w której istnieją wszystkie suprema. To znaczy, że jest w rzeczywistości kratą zupełną, ponieważ infimum dowolnego podzbioru zbioru jest równe supremum zbioru wszystkich ograniczeń dolnych . W szczególności, każda topologia na zbiorze zawiera zbiór pusty (który jest równy dla ) i całą przestrzeń ( ).Jeśli
, to nazywamy topologią dyskretną; jeśli , to nazywamy topologią trywialną}.Niech
będzie przestrzenią topologiczną. Otoczeniempunktu nazywamy dowolny zbiór taki, że dla pewnego . Można łatwo pokazać, że dowolny podzbiór zbioru jest otwarty (to znaczy ) wtedy i tylko wtedy, gdy jest otoczeniem każdego swojego elementu. Zbiór otoczeń oznaczymy . Jak łatwo zauważyć, zbiór jest filtrem w kracie i dlatego nazywamy go często filtrem otoczeń punktu . Zauważmy też, że dla dowolnego , filtr otoczeń jest wyznaczony jednoznacznie, a więc w rzeczywistości odwzorowanie dane przezjest dobrze określoną funkcją.
Niech
będzie przestrzenią topologiczną i niech . Wnętrzem zbioru nazywamy największy zbiór otwarty zawarty w , który będziemy oznaczać dalej jako lub po prostu , jeśli jest jasne o jakiej topologii jest właśnie mowa. Zauważmy, że odwzorowanie dane przezjest dobrze określoną funkcją. Ponadto, zbiór
jest otwarty wtedy i tylko wtedy, gdy , to znaczy, gdy jest punktem stałym odwzorowania . Co więcej, .Dopełnienia zbiorów otwartych w przestrzeni topologicznej nazywamy zbiorami domkniętymi. Rodzina zbiorów domkniętych posiada własności dualne do własności zbiorów otwartych, a więc jest zamknięta ze względu na dowolne przecięcia i skończone sumy i tworzy kratę zupełną, zarówno względem inkluzji, jak i względem odwrotnej inkluzji. Kratę zbiorów domkniętych oznaczamy dalej jako
. Ponieważ jest podzbiorem zamkniętym ze względu na dowolne infima, więc dla dowolnego istnieje najmniejszy zbiór domknięty zawierający , który jest niczym innym, jak tylko infimum zbioru ograniczeń górnych w (czyli przecięciem wszystkich domkniętych nadzbiorów ). Zbiór ten oznaczamy albo po prostu , jeśli jest ustalona. Podobnie, jak w przypadku operacji wnętrza, odwzorowanie jest dobrze określoną funkcją, a zbiór jest domknięty wtedy i tylko wtedy, gdy jest punktem stałym odwzorowania , to jest, gdy .
Bazy w przestrzeniach topologicznych
Niech
będzie przestrzenią topologiczną. Bazątopologii nazywamy każdą podrodzinę taką, że dla każdego otoczenia punktu istnieje taki, że . W szczególności, cała rodzina jest bazą topologii .Przypomnijmy, że jeśli
jest częściowym porządkiem, to jego podzbiory są współkońcowe, jeśli . Ponadto, jeśli oraz , to mówimy, że jest współkońcowy w . Rozważmy więc kratę dla przestrzeni topologicznej . W tej kracie rodzina dla dowolnego jest zbiorem skierowanym. Zauważmy, że podrodzina topologii na jest bazą wtedy i tylko wtedy, gdy dla każdego , zbiór jest współkońcowy w , gdzie .Zbiory zwarte
Podzbiór
przestrzeni topologicznej nazywamy zwartym, jeśli dowolne pokrycie zbiorami otwartymi zawiera podpokrycie skończone, to jest: jeśli dla dowolnej rodziny , to istnieje podrodzina taka, że . W praktyce będziemy mieli bardzo często do czynienia z rodzinami indeksowanymi, więc definicja zwartości upraszcza się do następującej: jest zwarty wtedy i tylko wtedy, gdy dla implikuje dla , gdzie .
Porządek specjalizacji i aksjomaty oddzielania
W dowolnej przestrzeni topologicznej
możemy zdefiniować relację przechodnią i zwrotną między elementami w następujący sposób:()
którą nazywamy preporządkiem specjalizacji. Mówimy, że przestrzeń topologiczna
spełnia aksjomat oddzielania (lub: jest przestrzenią ) jeśli jest częściowym porządkiem, to znaczy wtedy i tylko wtedy, gdy jest relacją antysymetryczną. Dalej, mówimy, że przestrzeń topologiczna spełnia aksjomat oddzielania (jest przestrzenią ) wtedy i tylko wtedy, gdy redukuje się do równości. Oczywiście definicje powyższe implikują, że każda przestrzeń jest , ale nie jest odwrotnie, jak pokazuje przykład topologii na zbiorze dwuelementowym .Nazwy aksjomaty oddzielania pochodzą stąd, że w przestrzeniach topologicznych o własnościach
czy zbiory otwarte oddzielają punkty w odpowiedni sposób. W dalszej części wykładu będziemy mówić głównie o przestrzeniach , które nie są przestrzeniami (konkretnie, tak zwana topologia Scotta na nietrywialnych dziedzinach posiada te własności, co wykażemy poniżej). Z drugiej strony, niemal wszystkie przestrzenie topologiczne rozważane w analizie, geometrii itd., itp. spełniają aksjomaty silniejsze niż . Nasz wykład będzie więc różnił się znacznie od standardowego wykładu topologii ogólnej.
Funkcje ciągłe na dziedzinach
Można śmiało powiedzieć, że struktura topologiczna na zbiorach jest wprowadzana po to, aby w sposób ścisły móc mówić o ciągłości funkcji. Przedmiot Topologia jest więc przede wszystkim nauką o funkcjach ciągłych między przestrzeniami topologicznymi.
Definicja 12.13
Dowodzi się w prosty sposób, że funkcja jest ciągła wtedy i tylko wtedy, gdy przeciwobraz dowolnego zbioru domkniętego jest domknięty.
Topologia Scotta na porządkach
W tej części wykładu pokażemy, że każdy zbiór częściowo uporządkowany może być traktowany jako przestrzeń topologiczna. Topologia, którą w naturalny sposób można zdefiniować na każdym posecie nazywa się topologią Scotta i pochodzi od nazwiska słynnego logika Dany S. Scotta (prof. Scott wykłada i bierze udział w konferencjach matematycznych i informatycznych do dziś).
Definicja 12.14
- ( jest zbiorem górnym),
- Jeśli dla zbioru skierowanego mamy , to istnieje element taki, że .
Twierdzenie 12.15
Dowód
. Pokażemy, że . Jest oczywiste, że jest zbiorem górnym, więc pokażemy tylko własność (S2). Niech będzie dowolnym zbiorem skierowanym w , który posiada supremum . Jeśli , to i , a więc istnieją elementy i . Ale jest skierowany, więc istnieje taki, że . Ponieważ i są zbiorami górnymi, , co należało pokazać. Niech będzie dowolną rodziną zbiorów otwartych. Jest jasne, że jest zbiorem górnym. Następnie, jeśli dla , to dla pewnego . A zatem istnieje taki, że . Element należy więc do , a więc , czego należało dowieść.Można pokazać, że zbiór
jest domknięty w sensie Scotta, jeśli jest zbiorem dolnym i zawiera wszystkie suprema swoich podzbiorów skierowanych (o tej drugiej własności mówimy, że zbiór domknięty w sensie Scotta jest zamknięty ze względu na suprema zbiorów skierowanych). Najprostszymi przykładami zbiorów domkniętych są ideały główne dla .Okazuje się, że porządek specjalizacji dla topologii Scotta na
jest zawsze porządkiem częściowym, który pokrywa się z tym na .
Twierdzenie 12.16
- ,
- ,
- .
Co więcej, topologia Scotta jest
.
Dowód
Topologia Scotta na dziedzinach
Niech
będzie porządkiem ciągłym. Łatwo pokazać, że w topologii Scotta na mamy dla każdego . Lecz o tej sytuacji możemy powiedzieć nawet więcej:
Twierdzenie 12.17
Dowód
są zbiorami otwartymi w sensie Scotta. Niech dla dowolnego i . Skoro jest skierowany z supremum , to z otwartości wynika, że istnieje . A zatem dla pewnego , co należało pokazać.Funkcje ciągłe w sensie Scotta
Na zakończenie pokażemy, że funkcje ciągłe między posetami są dokładnie funkcjami ciągłymi w sensie Scotta. Jest to jedna z przyczyn, dla których topologia Scotta odgrywa podstawową rolę w teorii dziedzin.
Twierdzenie 12.18
- jest ciągła,
- jest funkcją ciągłą między topologiami i .
Dowód
będzie ciągła i . Ponieważ funkcje ciągłe są monotoniczne, jest zbiorem górnym. Jeśli dla pewnego zbioru skierowanego , to , to istnieje taki, że . To oznacza, że , co należało pokazać. Z drugiej strony, załóżmy, że jest ciągła w sensie Scotta. Niech w . Wtedy jest zbiorem domkniętym w sensie Scotta zawierającym , a więc zbiór ten musi zawierać również . To daje . Funkcja jest więc monotoniczna. Niech będzie skierowany. Rozważmy przeciwobraz zbioru domkniętego . Jest on domknięty w i zawiera , a więc musi też zawierać . Pokazaliśmy, że , czyli . Ale monotoniczność implikuje, że , co należało pokazać.