Kontinuitet enligt Scott

Kontinuitet enligt Scott är en egenskap hos funktioner över partiellt ordnade mängder , vilket uttrycks i bevarandet av den exakta övre gränsen med avseende på den partiella ordningsrelationen .

Scotts topologi är en struktur över ett komplett gitter eller, mer allmänt, över en komplett partiellt ordnad uppsättning , där övre uppsättningar anses öppna som är otillgängliga för direkta anslutningar, eller motsvarande, en topologi inom vilken fungerar över partiellt ordnade uppsättningar som bevarar exakt övre gräns , är kontinuerliga [1] .

Koncepten utvecklades på 1970-talet av Dana Scott , tack vare dem byggdes den första konsekventa modellen av den otypade λ-kalkylen och denotationssemantik . I synnerhet är applikations- och curryfunktionerna kontinuerliga i Scotts bemärkelse [2] .

Definitioner

Om och är delvis ordnade uppsättningar, är funktionen mellan dem Scott-kontinuerlig om det för någon riktad delmängd finns en minsta övre gräns för dess bild och följande villkor är uppfyllt: . $P$ $F$ $f\colon P\to Q$ $D\subseteq P$ $\sup f(D)$ $\sup f(D)=f(\sup D)$

Scott-topologin på en komplett poset introduceras genom att definiera en öppen uppsättning som har följande egenskaper: $\langle D,\sqsubseteq \rangle$ $O$

från vad som följer ; $x\in O$ $x\sqsubseteq y$ $y\in O$
om , var och riktad , då [3] . $\bigqcup X\in O$ $X\subseteq D$ $X$ $X\cap O\neq \varnothing$

Scotts topologi introducerades först för kompletta gitter [4] , generaliserades därefter till fullständiga partiellt ordnade uppsättningar [3] .

Kategorin vars objekt är kompletta delvis ordnade uppsättningar och vars morfismer är mappningar kontinuerliga i betydelsen Scott betecknas med . ${\mathsf {CPO}}$

Egenskaper

Scott-kontinuerliga funktioner är alltid monotona med avseende på den partiella ordningsrelationen .

En delmängd av en delvis ordnad mängd stängs i Scott-topologin om och endast om den är en lägre mängd och inkluderar de minsta övre gränserna av alla dess delmängder [5] .

En fullständig partiellt ordnad uppsättning utrustad med Scott-topologin är alltid ett T 0 -mellanrum och ett Hausdorff ett om och endast om ordningsrelationen är trivial [5] .

För varje Scott-kontinuerlig funktion som kartlägger en komplett poset på sig själv, gäller Kleenes sats , enligt vilken varje sådan avbildning har en unik minsta fixpunkt . Dessutom är mappningen som definieras på uppsättningen Scott-kontinuerliga funktioner och som returnerar för varje funktion värdet av dess fixpunkt ( ), i sig Scott-kontinuerlig [6] . $\mathbf {Fix}$ $f\colon D\to D$ $\mathbf {Fix} (f)=x\Leftrightarrow f(x)=x$

Kategorin är kartesisk sluten [7] . ${\mathsf {CPO}}$

Analoger

En konstruktion nära Scotts topologi är den kategori av -rum som utvecklades av Yuri Ershov 1975 [8] - den kan också användas för att konstruera en konsekvent modell av λ-kalkylen. Som dess fördel noteras [9] att kategorin -rum är kartesisk stängd, varje objekt i den är ett topologiskt utrymme, topologin på produkten är produkten av topologierna av faktorer, och topologin i rummet av funktioner visar sig vara topologin för punktvis konvergens . Scott-topologin har inte sådana bekväma egenskaper; i synnerhet är produkten av Scott-topologier på kompletta, delvis ordnade uppsättningar inte, i det allmänna fallet, en Scott-topologi på en produkt av uppsättningar. $f_0$ $f_0$

Anteckningar

↑ Barendregt, 1985 , Theorem 1.2.6, sid. 23.
↑ Barendregt, 1985 , Theorems 1.2.13, 1.2.14, sid. 25.
↑ 1 2 Barendregt, 1985 , sid. 24.
↑ Scott, 1972 .
↑ 1 2 Abramsky, 1995 .
↑ Barendregt, 1985 , Theorem 1.2.17, sid. 25-26.
↑ Barendregt, 1985 , Theorem 1.2.16, sid. 25.
↑ Ershov, Yuri . Numreringsteori. — M .: Nauka , 1977. — 416 sid.
↑ Barendregt, 1985 , sid. 22.

Litteratur

Abramsky, Samson och Jung, Achim. Domänteori // Semantiska strukturer. — Handbok i logik i datavetenskap. - Oxford : Oxford University Press , 1995. - V. 3. - 512 sid. — ISBN 978-0198537625 .
Barendregt, Henk . Lambdakalkyl. Dess syntax och semantik = The Lambda Calculus. Dess syntax och semantik. — M .: Mir , 1985. — 606 sid. - 4800 exemplar. (ryska)
Scott, Dana . Continous Lattices (engelska) // Lecture Notes in Mathematics . - 1972. - Vol. 274 . — S. 97–136 . - doi : 10.1007/BFb0073967 .
Vickers, Steven. Topologi via logik. - Cambridge : Cambridge University Press , 1989. - 206 sid. - ISBN 0-521-36062-5 .