Funções Scott-contínuas: uma definição alternativa

16

Estou realmente lutando com esta propriedade:

Deixe que X,Y ser espaços coerentes e ser uma função monótona. é contínuo se e somente se , para todos os modo que seja um conjunto direcionado.f f ( x D x ) = x D f ( x )f:Cl(X)Cl(Y)ff(xDx)=xDf(x)DDCl(X)D

Dirigido conjunto é definido assim: poset é um conjunto dirigido sse tal e . significa cliques de X: coerente .Dz D x z x 'z C l ( X ) { x | X | a , b x a b }x,xD zDxzxz
Cl(X){x|X|a,bxab}

Muitos livros dão isso como uma definição de funções contínuas de Scott , mas infelizmente não são meu professor. Ele nos deu essa definição de contínuo:

f:Cl(X)Cl(Y) é contínuo se for monótono e , em que monótono é definido como: é monótono sexCl(X),bf(x),x0finx,bf(x0 0)
fumabf(uma)f(b)

Esta é a prova proposta que tenho, mas não consigo entender a última equação.

A prova de contínua implicaf ( D ) = f ( D )ff(D)=f(D) :
Seja bf(D) . Pela definição de continuidade, x0finxbf(x0) . Observe que x0 é a união de {xixiD} .
Se D for direto, então: zDxiz seguida, x0z . Pela definição de monotonia, f(x0)f(z) então bf(z) (???) f(D) . E mesmo isso é verdade, devemos mostrar que f(D)=f(D) , não apenas .

A prova da outra implicação é ainda pior, então não posso escrevê-la aqui ... Você pode me explicar como a prova pode funcionar?

Ofey
fonte
5
@Raphael: Isso é claramente ciência da computação. Esses conceitos são usados ​​para dar semântica às linguagens de programação. Espaços coerentes fornecem semântica para lógica linear. O papel original aparece no TCS.
21412 Dave Clarke
4
@ Rafael: Eu não acho que isso é absolutamente necessário. A página sobre continuidade de Scott declara "funções contínuas de Scott aparecem no estudo da semântica denotacional de programas de computador".
Dave Clarke
1
@ Rafael: Essa regra geral pode muito bem ser o caso, mas isso não se aplica a esta pergunta, que eu disse que está no tópico.
Dave Clarke
4
@ Rafael, garanto que essa é uma pergunta sobre semântica denotacional . A continuidade de Scott recebeu o nome de um cientista da computação por um motivo (bem, Scott atravessou a fronteira entre matemática e CS, mas este é o seu trabalho em CS).
Gilles 'SO- stop being evil'
2
O que é Cl (•)? Considero que é o fechamento, mas isso é confuso, pois o ponto dessa configuração parece ser que os conjuntos direcionados estão fechados.
Louis

Respostas:

11

A definição de continuidade usada pelo seu professor é a melhor. Ele diz muito concretamente o que significa continuidade.

Suponha que . Isso significa que, dada toda a informação de x , possivelmente um conjunto infinito de tokens (átomos), a função produz algum elemento que possui a informação atômica b . (Pode haver outras informações também, mas não estamos preocupadas com isso no momento.) A definição de seu professor diz que não é necessário examinar todas as informações infinitas de x para produzir as informações de saída b . Algum subconjunto finito de x é suficiente para produzi-lo.bf(x)xbxbx

(O livro de Melvin Fitting "Teoria da computabilidade, semântica e programação lógica", Oxford, 1987, chama essa propriedade de compacidade e define uma função contínua como monótona e compacta.)

Essa é a essência da continuidade. Para obter uma quantidade finita de informações sobre a saída de uma função, você só precisa de uma quantidade finita de informações sobre a entrada. A saída produzida pela função para uma entrada infinita é obtida reunindo as informações que produz para todas as aproximações finitas da entrada infinita. Em outras palavras, você não recebe nenhum salto mágico ao passar das aproximações finitas para a união infinita. Tudo o que você obtém no infinito, já deve estar em algum estágio finito.

A equação padrão é bonita de se olhar, mas não diz a você toda a intuição que expliquei acima. No entanto, matematicamente, é equivalente à definição do seu professor.f(xDx)=xDf(x)

Para mostrar que , que é suficiente para mostrar que f ( x ) está incluído na f ( x D x ) , para cada x D . Mas isso se segue diretamente da monotonicidade de f, porque x x D x . Então, essa é a direção "fácil".xDf(x)f(xDx)f(x)f(xDx)xDfxxDx

A outra direção, comprovada pelo seu professor, é a interessante: . Para ver isso, use a intuição que mencionei acima. Qualquer informação atômica b no lado esquerdo vem de alguma aproximação finita da entrada: x 0 f i nx D x . Ou seja, b f ( x 0 ) . Desde x 0f(xDx)xDf(x)bx0finxDxbf(x0)x0é finito e está incluído na união do conjunto direcionado, deve haver algo no conjunto direcionado que seja maior que , talvez x 0 em si. Chame esse elemento z . Por monotonicidade, f ( x 0 ) f ( z ) . Então, b f ( z ) . Desde z D , F ( z ) x D f ( x ) . Então agora bx0x0zf(x0)f(z)bf(z)zDf(z)xDf(x)bé visto também no lado direito. QED.

Como você observou, mostrar que a continuidade do professor implica que a bonita equação é fácil. O mais difícil é mostrar que a equação bonita, apesar de parecer que não está dizendo muito, realmente diz tudo na definição do professor.

Uday Reddy
fonte
1
A outra definição pode ser menos concreta, mas funciona de maneira mais geral, enquanto a usada pelo professor exige domínios algébricos.
21313 Andrej Bauer
4

Ocorreu-me tardiamente, depois que escrevi a última resposta, que a definição de continuidade do professor que eu estava explicando em minha resposta é a noção topológica de continuidade. A formulação algébrica de continuidade que geralmente é mencionada nos livros de ciência da computação esconde todas as intuições topológicas. (De fato, Dana Scott costuma escrever que evita deliberadamente formulações topológicas porque os cientistas da computação não estão familiarizados com isso.)

A ligação entre as formulações algébricas e topológicas é chamada dualidade de Stone , e agora está se tornando cada vez mais claro que essa ligação em si é extremamente importante para a Ciência da Computação.

Para uma exposição conceitual dessas conexões (e muito mais), consulte as informações, processos e jogos de Abramsky .

Uday Reddy
fonte
Por que você não edita isso em sua resposta mais antiga?
Raphael
@ Rafael, geralmente eu acho que é bom postar várias respostas quando são respostas diferentes para a pergunta. (Este parece um pouco na fronteira embora.)
Kaveh
Eu posto uma "resposta" separada quando penso que as pessoas que talvez já tenham lido a resposta antiga talvez possam se beneficiar da nova. Acho que a dualidade de Stone é um grande negócio, e parece que fazemos isso o tempo todo sem pensar conscientemente.
precisa saber é o seguinte