Scott-stetige Funktionen: eine alternative Definition

16

Ich kämpfe wirklich mit dieser Eigenschaft:

Lassen seine Kohärenz Räume und f : C L ( X ) C L ( Y ) eine monotone Funktion sein. f ist kontinuierlich , wenn und nur wenn f ( x D x ) = x D f ( x ) , für alle D C l ( X ) , so daß D ein gerichteter Menge ist.X,Yf:Cl(X)Cl(Y)ff(xDx)=xDf(x)DCl(X)D

Die gerichtete Menge ist wie folgt definiert: POSETDist eine gerichtete Menge, wenn z D, wie x z und x 'z . C l ( X ) steht für Cliquen von X: { x | X | a , b x a kohärent b } .x,xD zDxzxz
Cl(X){x|X|a,bxab}

Viele Bücher geben das als Definition von Scott-stetigen Funktionen an , aber leider nicht mein Lehrer. Er gab uns diese Definition von stetig:

kontinuierlich iff es monotone undx C l ( X ) , b F ( x ) , x 0 f i n x , b F ( x 0 ) , wobeimonotondefiniert ist als: f ist monoton wennf a f:Cl(X)Cl(Y)xCl(X),bf(x),x0finx,bf(x0)
fabf(a)f(b)

Dies ist der vorgeschlagene Beweis, den ich habe, aber ich kann die letzte Gleichung nicht verstehen.

Der Beweis von stetig impliziert f ( D ) = f ( D )ff(D)=f(D) :
Sei . Durch die Definition der Kontinuität, x 0 F i n x | b f ( x 0 ) . Man beachte, dass x 0 die Vereinigung von { x ix iD } ist .bf(D)x0finxbf(x0)x0{xixiD}
Wenn direkt ist, gilt :: z D x iz dann x 0z . Durch die Definition der Monotonie, f ( x 0 ) f ( z ) so b f ( z ) (???) f ( D ) . Und selbst das ist wahr, wir sollten zeigen, dass f ( D ) = f ( DDzDxizx0zf(x0)f(z)bf(z) f(D) , nicht nur .f(D)=f(D)

Der Beweis der anderen Implikation ist noch schlimmer, so dass ich ihn hier nicht schreiben kann ... Können Sie mir erklären, wie der Beweis funktionieren kann?

Ofey
quelle
5
@Raphael: Das ist ganz klar Informatik. Diese Konzepte werden verwendet, um Programmiersprachen Semantik zu verleihen. Kohärente Räume liefern Semantik für lineare Logik. Das Originalpapier wird in TCS angezeigt.
Dave Clarke
4
@Raphael: Das halte ich nicht für unbedingt notwendig. Auf der Seite zur Scott-Kontinuität heißt es: "Scott-kontinuierliche Funktionen tauchen in der Untersuchung der Denotationssemantik von Computerprogrammen auf."
Dave Clarke
1
@Raphael: Diese allgemeine Regel mag durchaus der Fall sein, aber das gilt nicht für diese Frage, von der ich gesagt habe, dass sie zum Thema gehört.
Dave Clarke
4
@Raphael Ich versichere Ihnen, dass dies eine Frage der Denotationssemantik ist . Scott Continuity ist aus einem bestimmten Grund nach einem Informatiker benannt.
Gilles 'SO - hör auf böse zu sein'
2
Was ist Cl (•)? Ich halte es für den Abschluss, aber das ist verwirrend, da der Sinn dieses Setups darin zu liegen scheint, dass gerichtete Mengen geschlossen sind.
Louis

Antworten:

11

Die Definition der Kontinuität, die Ihr Lehrer verwendet, ist die schönere. Es sagt Ihnen ziemlich konkret, was Kontinuität bedeutet.

Angenommen, . Dies bedeutet, dass die Funktion unter Berücksichtigung aller Informationen von x , möglicherweise einer unendlichen Menge von Token (Atomen), ein Element erzeugt, das die atomare Information b enthält . (Es könnte auch andere Informationen haben, aber wir sind nicht mit , dass zur Zeit besorgt.) Ihr Lehrers Definition sagt , dass es nicht notwendig ist , um jeden der unendlichen Informationen zu suchen x , um die Ausgangsinformation zu erzeugen b . Eine endliche Teilmenge von x reicht aus, um es zu erzeugen.bf(x)xbxbx

(Melvin Fitings Buch "Computability Theory, Semantics and Logic Programming", Oxford, 1987, nennt diese Eigenschaft Kompaktheit und definiert eine kontinuierliche Funktion als monoton und kompakt.)

Dies ist das Wesen der Kontinuität. Um eine begrenzte Menge an Informationen über die Ausgabe einer Funktion zu erhalten, benötigen Sie nur eine begrenzte Menge an Informationen über die Eingabe. Die Ausgabe, die von der Funktion für eine unendliche Eingabe erzeugt wird, wird erhalten, indem die Informationen, die sie erzeugt, für alle endlichen Approximationen der unendlichen Eingabe zusammengesetzt werden. Mit anderen Worten, Sie bekommen keinen magischen Sprung von den endlichen Annäherungen zu ihrer unendlichen Vereinigung. Was auch immer du im Unendlichen bekommst, du solltest schon in einem endlichen Stadium sein.

Die Standardgleichung ist schön anzusehen, sagt aber nicht alles über die Intuition aus, die ich oben erklärt habe. Mathematisch entspricht dies jedoch der Definition Ihres Lehrers.f(xDx)=xDf(x)

Um zu zeigen, dass ist, genügt es zu zeigen, dass f ( x ) in f ( x D x ) für jedes x D enthalten ist . Das folgt aber direkt aus der Monotonie von f, weil x x D x . Das ist also die "einfache" Richtung.xDf(x)f(xDx)f(x)f(xDx)xDfxxDx

Die andere Richtung, die Ihr Lehrer bewiesen hat, ist die interessante: . Verwenden Sie dazu die oben erwähnte Intuition. Jeder Atominformationsteil B in der linken Seite kommt von einer endlichen Approximation der Eingabe: x 0 f i nx D x . Das heißt, b f ( x 0 ) . Seit x 0f(xDx)xDf(x)bx0finxDxbf(x0)x0endlich ist und in der Vereinigung der gerichteten Menge enthalten ist, muss es etwas in der gerichteten Menge geben, das größer als , vielleicht x 0 selbst. Nennen Sie dieses Element z . Durch Monotonie ist f ( x 0 ) f ( z ) . Also ist b f ( z ) . Da z D , f ( z ) x D f ( x ) . Also, jetzt bx0x0zf(x0)f(z)bf(z)zDf(z)xDf(x)bwird auch in der rechten Seite gesehen. QED.

Wie Sie bemerkt haben, ist es einfach zu zeigen, dass die Kontinuität Ihres Lehrers die hübsche Gleichung impliziert. Das Schwierigere ist zu zeigen, dass die hübsche Gleichung, obwohl sie nicht sehr aussagt, wirklich alles in der Definition Ihres Lehrers aussagt.

Uday Reddy
quelle
1
Die andere Definition mag weniger konkret sein, funktioniert aber allgemeiner, während die vom Lehrer verwendete algebraische Domänen erfordert.
Andrej Bauer
4

Nachdem ich die letzte Antwort geschrieben hatte, fiel mir verspätet ein, dass die Definition des Lehrers von Kontinuität, die ich in meiner Antwort erklärte, der topologische Begriff von Kontinuität ist. Die algebraische Formulierung der Kontinuität, die normalerweise in Lehrbüchern der Informatik erwähnt wird, verbirgt alle topologischen Intuitionen. (In der Tat hat Dana Scott oft geschrieben, dass er topologische Formulierungen absichtlich vermieden hat, weil Informatiker damit nicht vertraut sind.)

Die Verknüpfung zwischen algebraischen und topologischen Formulierungen wird als Stone-Dualität bezeichnet , und es wird zunehmend klar, dass diese Verknüpfung selbst für die Informatik von außerordentlicher Bedeutung ist.

Eine konzeptionelle Darstellung dieser Zusammenhänge (und vieles mehr) finden Sie in Abramskys Informationen, Prozessen und Spielen .

Uday Reddy
quelle
Warum bearbeitest du das nicht in deine ältere Antwort?
Raphael
@Raphael, im Allgemeinen denke ich, dass es in Ordnung ist, mehrere Antworten zu posten, wenn es sich um unterschiedliche Antworten auf die Frage handelt. (Dieser scheint ein wenig an der Grenze zu sein.)
Kaveh
Ich poste eine separate "Antwort", wenn ich denke, dass Leute, die die alte Antwort bereits gelesen haben, vielleicht von der neuen profitieren könnten. Ich denke, Stein-Dualität ist eine große Sache, und wir scheinen es die ganze Zeit zu tun, ohne bewusst darüber nachzudenken.
Uday Reddy