Jatkuvuus Scottin mukaan

Jatkuvuus Scottin mukaan on funktioiden ominaisuus osittain järjestetyille joukoille , joka ilmaistaan tarkan ylärajan säilymisenä osittaisen järjestyksen suhteen .

Scottin topologia on rakenne , joka ylittää täydellisen hilan tai yleisemmin täydellisen osittain järjestetyn joukon , jossa ylempiä joukkoja pidetään avoimina , joihin suorat yhteydet eivät pääse, tai vastaavasti topologia, jossa toimii osittain järjestettyjen joukkojen yli , jotka säilyttävät tarkka yläraja , ovat jatkuvia [1] .

Käsitteet kehitti 1970-luvulla Dana Scott , joiden ansiosta rakennettiin ensimmäinen johdonmukainen malli tyypittämättömästä λ-laskennasta ja denotaatiosemantiikasta . Erityisesti aplikaatio- ja curryfunktiot ovat jatkuvia Scottin [2] merkityksessä .

Määritelmät

Jos ja ovat osittain järjestettyjä joukkoja, niin niiden välinen funktio on Scottin jatkuva , jos jollakin suunnatulla osajoukolla on sen kuvan pienin yläraja ja seuraava ehto täyttyy: . $P$ $K$ $f\colon P\to Q$ $D\subseteq P$ $\sup f(D)$ $\sup f(D)=f(\sup D)$

Scott-topologia täydellisessä posetissa otetaan käyttöön määrittelemällä avoin joukko , jolla on seuraavat ominaisuudet: $\langle D,\sqsubseteq \rangle$ $O$

seuraavasta ; _ _ $x\in O$ $x\sqsubseteq y$ $y\in O$
jos , missä ja suunnattu , niin [3] . $\bigqcup X\in O$ $X\subseteq D$ $X$ $X\cap O\neq \varnothing$

Scottin topologia otettiin ensin käyttöön täydellisille hiloille [4] , minkä jälkeen se yleistettiin täydellisiksi osittain järjestetyiksi joukoiksi [3] .

Kategoria , jonka objektit ovat täydellisiä osittain järjestettyjä joukkoja ja joiden morfismit ovat jatkuvia kuvauksia Scottin merkityksessä, on merkitty . ${\mathsf {CPO}}$

Ominaisuudet

Scott-jatkuvat funktiot ovat aina monotonisia osittaisen järjestyksen suhteen .

Osittain järjestetyn joukon osajoukko on suljettu Scott-topologiassa silloin ja vain, jos se on alajoukko ja sisältää kaikista sen osajoukoista pienimmän ylärajan [ 5] .

Täydellinen osittain järjestetty joukko, jolla on Scott-topologia, on aina T 0 -avaruus ja Hausdorff -avaruus jos ja vain, jos järjestysrelaatio on triviaali [5] .

Jokaiselle Scott-jatkuvalle funktiolle, joka kuvaa koko posetin itseensä, pätee Kleenen lause , jonka mukaan jokaisella sellaisella kuvauksella on ainutlaatuinen pienin kiinteä piste . Lisäksi Scott-jatkuvien funktioiden joukkoon määritetty kuvaus, joka palauttaa jokaiselle funktiolle sen kiinteän pisteen arvon ( ), on itse Scott-jatkuva [6] . $\mathbf {Korjaa}$ $f\colon D\to D$ $\mathbf {Korjaa} (f)=x\Leftrightarrow f(x)=x$

Luokka on karteesinen suljettu [7] . ${\mathsf {CPO}}$

Analogit

Rakenne, joka on ominaisuuksiltaan lähellä Scottin topologiaa, on Juri Ershovin vuonna 1975 kehittämä -avaruuksien luokka [8] – sitä voidaan käyttää myös λ-laskennan johdonmukaisen mallin rakentamiseen. Sen etuna on [9] , että -avaruuksien luokka on karteesinen suljettu, jokainen objekti siinä on topologinen avaruus, tuotteen topologia on tekijöiden topologioiden tulos ja topologia avaruudessa. funktiot osoittautuvat pisteittäisen konvergenssin topologiaksi . Scott-topologialla ei ole tällaisia sopivia ominaisuuksia; erityisesti Scott-topologioiden tulos täydellisissä osittain järjestetyissä joukoissa ei yleensä ole Scott-topologia joukkojen tulolla. $f_0$ $f_0$

Muistiinpanot

↑ Barendregt, 1985 , Lause 1.2.6, s. 23.
↑ Barendregt, 1985 , Lauseet 1.2.13, 1.2.14, s. 25.
↑ 1 2 Barendregt, 1985 , s. 24.
↑ Scott, 1972 .
↑ 1 2 Abramsky, 1995 .
↑ Barendregt, 1985 , Lause 1.2.17, s. 25-26.
↑ Barendregt, 1985 , Lause 1.2.16, s. 25.
↑ Ershov, Juri . Numerointiteoria. — M .: Nauka , 1977. — 416 s.
↑ Barendregt, 1985 , s. 22.

Kirjallisuus

Abramsky, Simson ja Jung, Achim. Domain Theory // Semanttiset rakenteet. — Tietojenkäsittelytieteen logiikan käsikirja. - Oxford : Oxford University Press , 1995. - V. 3. - 512 s. — ISBN 978-0198537625 .
Barendregt, Henk . Lambda-laskenta. Sen syntaksi ja semantiikka = The Lambda Calculus. Sen syntaksi ja semantiikka. — M .: Mir , 1985. — 606 s. - 4800 kappaletta. (Venäjän kieli)
Scott, Dana . Jatkuvat hilat (englanti) // Matematiikan luentomuistiinpanot . - 1972. - Voi. 274 . — s. 97–136 . - doi : 10.1007/BFb0073967 .
Vickers, Steven. Topologia logiikan kautta. - Cambridge : Cambridge University Press , 1989. - 206 s. - ISBN 0-521-36062-5 .