Continuité de Scott
En mathématiques pour l'informatique, étant donné deux ensembles partiellement ordonnés P et Q, une fonction f : P → Q entre eux est Scott-continue (du nom du mathématicien Dana Scott) si elle préserve tous les suprema dirigés, c'est-à -dire que pour chaque sous-ensemble orienté D de P avec supremum dans P, son image a un supremum dans Q, et ce supremum est l'image du supremum de D, c'est-à -dire , où est la jointure dirigée.[1] Lorsque est le poset des valeurs de vérité, c'est-à -dire l'espace de Sierpiński, les fonctions Scott-continues sont des fonctions caractéristiques, et donc l'espace de Sierpiński est le topos de classification des ensembles ouverts.
![{\displaystyle \sqcup f[D]=f(\sqcup D)}](https://img.franco.wiki/i/7c715897d8687fbb6c42ee7c69cce594ebed8447.svg)
Un sous-ensemble O d'un ensemble partiellement ordonné P est appelé Scott-ouvert si c'est un ensemble fermé par le haut et s'il est inaccessible par jointures dirigées, c'est-à -dire si tous les ensembles dirigés D avec supremum en O ont une intersection non vide avec O. Les sous-ensembles Scott-ouverts d'un ensemble partiellement ordonné P forment une topologie sur P, la topologie de Scott. Une fonction entre des ensembles partiellement ordonnés est Scott-continue si et seulement si elle est continue par rapport à la topologie de Scott[1].
La topologie de Scott a d'abord été définie par Dana Scott pour des treillis complets et plus tard définie pour des ensembles partiellement ordonnés[2].
Les fonctions continues de Scott apparaissent dans l'étude de modèles pour les calculs lambda[2] et la sémantique dénotationnelle des programmes informatiques.
Propriétés
Une fonction continue de Scott est toujours monotone.
Un sous-ensemble d'un ordre partiel complet dirigé est fermé par rapport à la topologie de Scott induite par l'ordre partiel si et seulement si c'est un ensemble inférieur et fermé sous suprema de sous-ensembles dirigés[3].
Un ordre partiel complet dirigé (dcpo) avec la topologie de Scott est toujours un espace de Kolmogorov (c'est-à -dire qu'il satisfait l'axiome de séparation T 0 )[3]. Cependant, un dcpo avec la topologie de Scott est un espace de Hausdorff si et seulement si l'ordre est trivial[3]. Les ensembles Scott-ouverts forment un treillis complet lorsqu'ils sont ordonnés par inclusion[4].
Pour tout espace de Kolmogorov, la topologie induit une relation d'ordre sur cet espace, l'ordre de spécialisation : x ≤ y si et seulement si tout voisinage ouvert de x est aussi un voisinage ouvert de y. La relation d'ordre d'un dcpo D peut être reconstruite à partir des ensembles ouverts de Scott comme l'ordre de spécialisation induit par la topologie de Scott. Cependant, un dcpo équipé de la topologie de Scott n'a pas besoin d'être sobre : l'ordre de spécialisation induit par la topologie d'un espace sobre fait de cet espace un dcpo, mais la topologie de Scott dérivée de cet ordre est plus fine que la topologie d'origine[3].
Exemples
Les ensembles ouverts dans un espace topologique donné lorsqu'ils sont ordonnés par inclusion forment un treillis sur lequel la topologie de Scott peut être définie. Un sous-ensemble X d'un espace topologique T est compact vis-à -vis de la topologie sur T (au sens où toute couverture ouverte de X contient une sous couverture finie de X ) si et seulement si l'ensemble des voisinages ouverts de X est ouvert vis-à -vis de la topologie de Scott[4].
Pour CPO, la catégorie fermée cartésienne des dcpo, deux exemples particulièrement notables de fonctions Scott-continues sont curry et apply[5].
Nuel Belnap a utilisé la continuité de Scott pour étendre les connecteurs logiques à une logique à quatre valeurs[6].
Voir également
- Topologie d'Alexandrov
- Topologie supérieure
Références
- Steven Vickers, Topology via Logic, Cambridge University Press, (ISBN 978-0-521-36062-3)
- Dana Scott, Toposes, Algebraic Geometry and Logic, vol. 274, Springer-Verlag, coll. « Lecture Notes in Mathematics », , « Continuous lattices »
- S. Abramsky et A. Jung, Handbook of Logic in Computer Science, vol. Vol. III, Oxford University Press, (ISBN 978-0-19-853762-5), « Domain theory »
- Bauer, Andrej et Taylor, Paul, « The Dedekind Reals in Abstract Stone Duality », Mathematical Structures in Computer Science, vol. 19, no 4,‎ , p. 757–838 (DOI 10.1017/S0960129509007695, lire en ligne, consulté le )
- H.P. Barendregt, The Lambda Calculus, North-Holland, (ISBN 978-0-444-87508-2) (See theorems 1.2.13, 1.2.14)
- N. Belnap (1975) "How Computers Should Think", pages 30 to 56 in Contemporary Aspects of Philosophy, Gilbert Ryle editor, Oriel Press (ISBN 0-85362-161-6)