Teoria kategorii dla informatyków/Wykład 12: Teoria dziedzin I

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

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.

Uwaga dla dociekliwych
Klasycznym przykładem jest tu język nietypowanego -rachunku. Aby stworzyć semantykę tego języka, należy zaproponować pewną kategorię składającą się z obiektów typu w taki sposób, aby termy -rachunku były interpretowane jako elementy , zaś aplikacja funkcji do argumentu była rozumiana jako aplikacja strzałki do argumentu typu . Jeśli teraz rozważymy -term , widzimy, że pierwsze wolne wystąpienie musi być typu , zaś drugie typu . A zatem musimy wymagać, by . W naszej kategorii semantycznej muszą zatem istnieć nietrywialne punkty stałe funktora . Pokażemy, że to możliwe w Wykładzie 14.

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.

Dana S. Scott ur. 1932
Zobacz biografię

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

Poset jest ciągły jeśli posiada bazę. Jeśli jest bazą, to mówimy, że jest algebraiczny.


Twierdzenie 12.2

Poset jest ciągły wtedy i tylko wtedy, gdy dla każdego , zbiór jest skierowany i mamy .

Dowód

Niech 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. End of proof.gif

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]

Jeśli poset jest ciągły, to relacja aproksymacji posiada własność interpolacji:
  • .


Definicja 12.4 [dziedzina]

Poset nazywamy dziedziną lub dziedziną ciągłą, jeśli jest ciągłym dcpo.

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]

Każdy poset skończony jest dcpo, ponieważ każdy jego podzbiór skierowany posiada element największy. Co więcej, każdy element jest zwarty, a więc jest dziedziną Scotta.

Przykład 12.6 [liczby naturalne]

W posecie liczb naturalnych 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.
Tk-12.1.png


Przykład 12.7 [odcinek]

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.
Tk-12.2.png


Przykład 12.8 [zbiór potęgowy]

Niech będzie dowolnym zbiorem. Zbiór potęgowy jest kratą zupełną i dla każdego mamy i . jest więc w szczególności dcpo i -zupełny. Najmniejszym elementem jest , a największym .
Tk-12.3.png

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 taki, że . Zbiór jest więc skończony, jako podzbiór zbioru skończonego .

Załóżmy, że . 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]

Niech oznacza zbiór wszystkich podprzedziałów domkniętych, niepustych przedziału uporządkowany względem odwrotnej inkluzji, to znaczy:

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.

Tk-12.4.png


Przykład 12.10 [dziedzina przedziałów]

Zbiór wszystkich domkniętych, niepustych przedziałów osi liczb rzeczywistych uporządkowany względem odwrotnej inkluzji, z dodanym elementem najmniejszym, oznaczamy . Poset jest izomorficzny z , więc posiada dokładnie te same cechy co .


Przykład 12.11 [dziedzina kul]

Niech będzie przestrzenią metryczną. Rozważmy rodzinę wszystkich par postaci , gdzie i i zdefiniujmy relację w następujący sposób:

Można pokazać, że relacja jest częściowym porządkiem. Poset

jest 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.

Tk-12.5.png


Przykład 12.12 [model zbioru Cantora]

Zbiór wszystkich skończonych i nieskończonych ciągów zerojedynkowych (oczywiście ) w porządku prefiksowym jest dziedziną Scotta. Każdy zbiór skierowany jest łańcuchem. Elementem najmniejszym jest ciąg pusty . Zbiór elementów maksymalnych pokrywa się ze zbiorem wszystkich ciągów nieskończonych, który z kolei, jak wiadomo, posiada strukturę zbioru Cantora. Każdy element z , który nie jest maksymalny, jest zwarty.
Tk-12.6.png

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 .

Uwaga
Jeśli funkcja monotoniczna jest traktowana kategoryjnie, jako funktor między kategoriami i , to pojęcie ciągłości, które tu wprowadziliśmy nie zgadza się z definicją ciągłości funktora. Przyjmijmy jednak, że w tym i dwóch następnych wykładach ciągłość funkcji między posetami będzie oznaczać tylko i wyłącznie zachowywanie supremów skierowanych.


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 przez

jest 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 przez

jest 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 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

Niech będą przestrzeniami topologicznymi. Mówimy, że funkcja jest ciągła wtedy i tylko wtedy, gdy dla każdego zbioru otwartego w , przeciwobraz jest otwarty w (tj. )).


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

Niech będzie częściowym porządkiem. Zbiór nazywamy otwartym w sensie Scotta, jeśli spełnia dwa warunki:
  • ( jest zbiorem górnym),
  • Jeśli dla zbioru skierowanego mamy , to istnieje element taki, że .
O zbiorze mającym własność (S2) mówimy, że jest nieosiągalny przez suprema zbiorów skierowanych. Rodzinę zbiorów otwartych w sensie Scotta oznaczamy lub po prostu .


Twierdzenie 12.15

Niech będzie częściowym porządkiem. Zbiory otwarte w sensie Scotta tworzą topologię.

Dowód

Niech . 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ść. End of proof.gif

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

Niech będzie częściowym porządkiem. Dla dowolnych elementów następujące warunki są równoważne:
  • ,
  • ,
  • .

Co więcej, topologia Scotta jest .


Dowód

(1)(2) wynika z tego, że zbiory otwarte są górne. (2)(3): przypuśćmy, że . Wówczas istnieje domknięty w sensie Scotta, taki, że i . A zatem dla zbioru otwartego mamy i . To znaczy, że Parser nie mógł rozpoznać (nieznana funkcja „\nepod”): {\displaystyle x\nepod_{\sigma} y} , co należało pokazać (3)(1): ponieważ ideał jest domknięty w sensie Scotta i zawiera , więc , a zatem . Własność wynika z równoważności (1) i (2) powyżej. End of proof.gif

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

Niech będzie porządkiem ciągłym, a jego bazą. Wówczas rodzina jest bazą dla topologii Scotta.

Dowód

Wiemy już, że elementy 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ć. End of proof.gif

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

Niech będą posetami. Dla funkcji następujące warunki są równoważne:
  • jest ciągła,
  • jest funkcją ciągłą między topologiami i .

Dowód

Niech 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ć. End of proof.gif