Funciones continuas de Scott: una definición alternativa

16

Realmente estoy luchando con esta propiedad:

Deje que sea espacios de coherencia y es una función monótona. es continuo si y solo si , para todos modo que D es un conjunto dirigido.X,Yf f ( x D x ) = x D f ( x ) D C l ( X ) Df:Cl(X)Cl(Y)ff(xDx)=xDf(x)reCl(X)D

El conjunto dirigido se define así: D POSET es un conjunto dirigido iff \ forall x, x '\ in D \ exist z \ in D tales x \ subseteq z y x' \ subseteq z . Cl (X) representa camarillas de X: \ {x \ subseteq | X | \ mid a, b \ in x \ Rightarrow una coherente b \} .z Dx,xD zDxzxz
Cl(X){x|X|a,bxab}

Muchos libros dan eso como una definición de las funciones continuas de Scott , pero desafortunadamente no es mi maestro. Nos dio esta definición de continuo:

f:Cl(X)Cl(Y) es continuo si es monótono y xCl(X),bf(x),x0finx,bf(x0) ,
donde monotone se define como: f es monotone iff abf(a)f(b)

Esta es la prueba propuesta que tengo, pero no puedo entender la última ecuación.

La prueba de f continua implica f(D)=f(D) :
Sea bf(D) . Según la definición de continuidad, x0finxbf(x0) . Tenga en cuenta que x0 es la unión de {xixiD} .
Si D es directo, entonces: zDxiz entonces x0z . Según la definición de monotonía, f(x0)f(z) por lo que bf(z) (???) f(D) . E incluso eso es cierto, debemos mostrar que f(D)=f(D) , no solo .

La prueba de la otra implicación es aún peor, así que no puedo escribirla aquí ... ¿Puede explicarme cómo puede funcionar la prueba?

Ofey
fuente
55
@Raphael: Esto es claramente informática. Estos conceptos se utilizan para dar semántica a los lenguajes de programación. Los espacios coherentes proporcionan semántica para la lógica lineal. El documento original aparece en TCS.
Dave Clarke
44
@Raphael: No creo que sea absolutamente necesario. La página sobre la continuidad de Scott establece que "las funciones continuas de Scott aparecen en el estudio de la semántica denotacional de los programas de computadora".
Dave Clarke
1
@Raphael: Esa regla general puede ser el caso, pero eso no se aplica a esta pregunta, que he dicho es sobre el tema.
Dave Clarke el
44
@Raphael, le aseguro que esta es una pregunta sobre la semántica denotacional . La continuidad de Scott lleva el nombre de un informático por una razón (bueno, Scott se colocó a horcajadas en la frontera entre matemáticas y CS, pero este es su trabajo de CS).
Gilles 'SO- deja de ser malvado'
2
¿Qué es Cl (•)? Supongo que es el cierre, pero esto es confuso, ya que el objetivo de esta configuración parece ser que los conjuntos dirigidos están cerrados.
Louis

Respuestas:

11

La definición de continuidad utilizada por su maestro es la mejor. Te dice muy concretamente qué significa continuidad.

Supongamos que . Eso significa que, dada toda la información de x , posiblemente un conjunto infinito de tokens (átomos), la función produce algún elemento que tiene la información atómica b . (También podría tener otra información, pero no estamos interesados ​​en eso en este momento). La definición de su maestro dice que no es necesario mirar toda la información infinita de x para producir la información de salida b . Algún subconjunto finito de x es suficiente para producirlo.bf(x)xbxbx

(El libro de Melvin Fitting "Teoría de la computabilidad, semántica y programación lógica", Oxford, 1987, llama a esta propiedad compacidad y define una función continua como monótono y compacto).

Esta es la esencia de la continuidad. Para obtener una cantidad finita de información sobre la salida de una función, solo necesita una cantidad finita de información sobre la entrada. La salida producida por la función para una entrada infinita se obtiene juntando la información que produce para todas las aproximaciones finitas de la entrada infinita. En otras palabras, no obtienes ningún salto mágico al pasar de las aproximaciones finitas a su unión infinita. Cualquier cosa que obtengas en el infinito, ya deberías llegar a una etapa finita.

La ecuación estándar es bonita de ver, pero no te dice toda la intuición que he explicado anteriormente. Sin embargo, matemáticamente, es equivalente a la definición de tu maestro.f(xDx)=xDf(x)

Para mostrar que , es suficiente para mostrar que f ( x ) se incluye en f ( x D x ) , para cada x D . Pero eso se deduce directamente de la monotonicidad de f porque x x D x . Entonces, esta es la dirección "fácil".xDf(x)f(xDx)f(x)f(xDx)xDfxxDx

La otra dirección, probada por su profesor, es la interesante: . Para ver esto, use la intuición que he mencionado anteriormente. Cualquier información atómica b en el lado izquierdo proviene de una aproximación finita de la entrada: x 0 f i nx D x . Es decir, b f ( x 0 ) . Desde x 0f(xDx)xDf(x)bx0finxDxbf(x0)x0es finito y está incluido en la unión del conjunto dirigido, debe haber algo en el conjunto dirigido que sea mayor que , tal vez x 0 en sí. Llame a ese elemento z . Por monotonicidad, f ( x 0 ) f ( z ) . Entonces, b f ( z ) . Dado que z D , f ( z ) x D f ( x ) . Entonces, ahora bx0x0zf(x0)f(z)bf(z)zDf(z)xDf(x)btambién se ve en el lado derecho. QED

Como ha notado, demostrar que la continuidad de su maestro implica que la ecuación bonita es la parte fácil. Lo más difícil es mostrar que la ecuación bonita, a pesar de parecer que no dice mucho, realmente dice todo en la definición de tu maestro.

Uday Reddy
fuente
1
La otra definición puede ser menos concreta, pero funciona de manera más general, mientras que la utilizada por el profesor requiere dominios algebraicos.
Andrej Bauer el
4

Se me ocurrió tardíamente, después de escribir la última respuesta, que la definición de continuidad del maestro que estaba explicando en mi respuesta es la noción topológica de continuidad. La formulación algebraica de continuidad que generalmente se menciona en los libros de texto de Ciencias de la Computación oculta todas las intuiciones topológicas. (De hecho, Dana Scott ha escrito a menudo que ha evitado deliberadamente las formulaciones topológicas porque los informáticos no están familiarizados con él).

El vínculo entre las formulaciones algebraicas y topológicas se llama dualidad de Stone , y ahora está cada vez más claro que este vínculo en sí mismo es extremadamente importante para la informática.

Para una exposición conceptual de estas conexiones (y mucho más), vea la información, procesos y juegos de Abramsky .

Uday Reddy
fuente
¿Por qué no editas esto en tu respuesta anterior?
Raphael
@Raphael, en general creo que está bien publicar múltiples respuestas cuando son respuestas diferentes a la pregunta. (Este parece un poco en la frontera sin embargo.)
Kaveh
Publico una "respuesta" por separado cuando creo que las personas que podrían haber leído la respuesta anterior tal vez podrían beneficiarse de la nueva. Creo que la dualidad de Stone es un gran problema, y ​​parece que lo hacemos todo el tiempo sin pensarlo conscientemente.
Uday Reddy