Funkcje ciągłe Scotta: alternatywna definicja

16

Naprawdę walczę z tą właściwością:

Niech będą spacjami koherencyjnymi, a będzie funkcją monotoniczną. jest ciągłe wtedy i tylko wtedy, gdy , dla wszystkich takich, że jest zbiorem ukierunkowanym.f : C l ( X ) C l ( Y ) f f ( x D x ) = x D f ( x ) D C l ( X ) DX,Yf:Cl(X)Cl(Y)ff(xDx)=xDf(x)DCl(X)D

Zestaw kierunkowy jest zdefiniowany w następujący sposób: POSET to zestaw ukierunkowany iff x , x D z D taki i . oznacza kliki X: coherent .Dx,xD zDx z C l ( X ) { x | X | a , b x a b }xzxz
Cl(X){x|X|a,bxab}

Wiele książek podaje to jako ciągłe funkcje Scotta , ale niestety nie mój nauczyciel. Podał nam definicję ciągłości:

f:Cl(X)Cl(Y) jest ciągły iff jest monotoniczny i , gdzie monotoniczny jest zdefiniowany jako: jest monotoniczny iffxCl(X),bf(x),x0finx,bf(x0)
a b f ( a ) f ( b )fabf(a)f(b)

To proponowany dowód, który mam, ale nie rozumiem ostatniego równania.

Dowód ciągłości oznaczaf ( D ) = f ( D )ff(D)=f(D) :
Niech . Zgodnie z definicją ciągłości . Zauważ, że jest związkiem . Jeśli jest bezpośredni, to: a następnie . Z definicji monotonii so (???) . I nawet to prawda powinniśmy pokazać, że , nie tylkox 0 f i n x b f ( x 0 ) x 0 { x ix iD } D z D x iz x 0z f ( x 0 ) f ( z ) b fbf(D)x0finxbf(x0)x0{xixiD}
DzDxizx0zf(x0)f(z)bf(z) f(D)f(D)=f(D) .

Dowód innej implikacji jest jeszcze gorszy, więc nie mogę go tutaj napisać ... Czy możesz mi wyjaśnić, w jaki sposób dowód może działać?

Ofey
źródło
5
@Raphael: To wyraźnie informatyka. Te pojęcia są używane do nadania semantyki językom programowania. Spójne przestrzenie zapewniają semantykę dla logiki liniowej. Oryginalny papier pojawia się w TCS.
Dave Clarke
4
@Raphael: Nie sądzę, że jest to absolutnie konieczne. Strona o ciągłości Scotta stwierdza: „Funkcje ciągłe Scotta ukazują się w badaniu denotacyjnej semantyki programów komputerowych”.
Dave Clarke,
1
@Raphael: Ta ogólna zasada może mieć miejsce, ale to nie dotyczy tego pytania, które, jak powiedziałem, jest tematyczne.
Dave Clarke,
4
@ Rafael Zapewniam cię, że to pytanie o semantykę denotacyjną . Ciągłość Scotta została nazwana na cześć informatyka z jakiegoś powodu (Scott przeciął granicę między matematyką a CS, ale to jest jego praca CS).
Gilles 'SO - przestań być zły'
2
Co to jest Cl (•)? Uważam to za zamknięcie, ale jest to mylące, ponieważ wydaje się, że celem tego ustawienia jest to, że ukierunkowane zestawy są zamknięte.
Louis,

Odpowiedzi:

11

Definicja ciągłości stosowana przez twojego nauczyciela jest lepsza. Mówi ci konkretnie, co oznacza ciągłość.

Załóżmy, że . Oznacza to, że biorąc pod uwagę wszystkie informacje o x , być może nieskończony zestaw tokenów (atomów), funkcja wytwarza pewien element zawierający atomową informację b . (Może mieć również inne informacje, ale w tej chwili nie jesteśmy tym zainteresowani.) Definicja twojego nauczyciela mówi, że nie trzeba patrzeć na wszystkie nieskończone informacje x , aby uzyskać informacje wyjściowe b . Wystarczy skończony podzbiór x , aby go wytworzyć.bf(x)xbxbx

(Książka Melvina Fittinga „Teoria obliczalności, semantyka i programowanie logiczne”, Oxford, 1987, nazywa tę zwięzłość właściwości i definiuje funkcję ciągłą jako monotoniczną i zwartą.)

To jest istota ciągłości. Aby uzyskać skończoną ilość informacji na temat wyniku funkcji, potrzebujesz tylko skończonej ilości informacji na temat danych wejściowych. Dane wyjściowe wytworzone przez funkcję dla nieskończonego wejścia są uzyskiwane przez złożenie razem informacji, które produkuje dla wszystkich skończonych przybliżeń nieskończonego wejścia. Innymi słowy, nie dostajesz żadnego magicznego skoku, przechodząc od skończonych przybliżeń do ich nieskończonej jedności. Cokolwiek otrzymujesz w nieskończoności, powinieneś już być na pewnym skończonym etapie.

Standardowe równanie jest ładne, ale nie mówi o całej intuicji, którą wyjaśniłem powyżej. Jednak matematycznie jest to odpowiednik definicji nauczyciela.f(xDx)=xDf(x)

Aby pokazać, że , wystarczy, aby pokazać, że f ( x ) jest zawarte w F ( x D x ) , dla każdego x D . Ale wynika to bezpośrednio z monotoniczności f, ponieważ x x D x . Jest to więc kierunek „łatwy”.xDf(x)f(xDx)f(x)f(xDx)xDfxxDx

Drugi kierunek, udowodniony przez twojego nauczyciela, jest interesujący: . Aby to zobaczyć, skorzystaj z intuicji, o której wspomniałem powyżej. Każda informacja atomowa b po lewej stronie pochodzi z pewnego skończonego przybliżenia wejścia: x 0 f i nx D x . To znaczy, b f ( x 0 ) . Ponieważ x 0f(xDx)xDf(x)bx0finxDxbf(x0)x0jest skończony i jest zawarty w unii zbioru kierowanego, musi być coś w zestawie kierowanym, który jest większy niż , być może sam x 0 . Nazwij ten element z . Przez monotoniczność, f ( x 0 ) f ( z ) . Więc b f ( z ) . Ponieważ z D , f ( z ) x D f ( x ) . Więc teraz bx0x0zf(x0)f(z)bf(z)zDf(z)xDf(x)bwidać również po prawej stronie. CO BYŁO DO OKAZANIA.

Jak zauważyłeś, wykazanie, że ciągłość nauczyciela implikuje ładne równanie, jest łatwe. Trudniej jest pokazać, że ładne równanie, choć wygląda na to, że nie mówi zbyt wiele, naprawdę mówi wszystko w definicji twojego nauczyciela.

Uday Reddy
źródło
1
Druga definicja może być mniej konkretna, ale działa bardziej ogólnie, podczas gdy ta używana przez nauczyciela wymaga domen algebraicznych.
Andrej Bauer,
4

Z opóźnieniem przyszło mi do głowy, po tym jak napisałem ostatnią odpowiedź, że definicja ciągłości nauczyciela, którą wyjaśniłam w mojej odpowiedzi, jest topologicznym pojęciem ciągłości. Algebraiczne sformułowanie ciągłości, która jest zwykle wspomniane informatyki podręcznikach ukrywa wszelkie topologicznych intuicje. (W rzeczywistości Dana Scott często pisała, że ​​celowo unikał sformułowań topologicznych, ponieważ informatyków nie jest z tym zaznajomiona.)

Związek między sformułowaniami algebraicznymi i topologicznymi nazywa się dualnością kamienną , a teraz staje się coraz bardziej jasne, że samo to połączenie jest niezwykle ważne dla informatyki.

Aby zapoznać się z koncepcyjnym przedstawieniem tych połączeń (i wiele innych), zobacz Informacje, procesy i gry Abramsky'ego .

Uday Reddy
źródło
Dlaczego nie edytujesz tego w swojej starszej odpowiedzi?
Raphael
@ Rafael, generalnie myślę, że dobrze jest opublikować wiele odpowiedzi, gdy są to różne odpowiedzi na pytanie. (Ten wydaje się trochę na granicy.)
Kaveh
Publikuję osobną „odpowiedź”, gdy myślę, że ludzie, którzy już przeczytali starą odpowiedź, mogliby skorzystać z nowej. Myślę, że dualność Kamienia to wielka sprawa i wydaje się, że robimy to cały czas, nie myśląc o tym świadomie.
Uday Reddy,