This page intentionally left blank ENCYCLOPEDIA OF MATHEMATICS AND ITS APPLICATIONS FOUNDING EDITOR G. ROTA Editorial Board R. Lutwak Volume 93 Continuous Lattices and Domains ENCYCLOPEDIA OF MATHEMATICS AND ITS APPLICATIONS http://publishing.org/stm/mathematics/com 4 W. Symmetry and separation of variables 6 H.
Thron Continued fractions 12 N. England Mathematical theory of entropy 18 H. Fattorini The Cauchy problem 19 G. Riemenschneider Birkhoff interpolation 21 W.
Tutte Graph theory 22 J. Bastida Field extensions and Galois theory 23 J. Cannon The one dimensional heat equation 25 A. Salomaa Computation and automata 26 N.) Theory of matroids 27 N.
Teugels Regular variation 28 P. Popov Rational approximation of real functions 29 N. Zassenhaus Algorithmic algebraic number theory 31 J. Dhombres Functional equations containing several variables 32 M.
Ger Iterative functional equations 33 R. Ambartzumian Factorization calculus and geometric probability 34 G. Staffans Volterra integral and functional equations 35 G. Rahman Basic hypergeometric series 36 E.
Torgersen Comparison of statistical experiments 37 A Neumaier Intervals methods for systems of equations 38 N. Korneichuk Exact constants in approximation theory 39 R. Ryser Combinatorial matrix theory 40 N. Sakai Operator algebras in dynamical systems 42 W.
Hodges Model theory 43 H. Totik General orthogonal polynomials 44 R. Schneider Convex bodies 45 G. Da Prato and J.
Zabczyk Stochastic equations in infinite dimensions 46 A Bjorner, M. Ziegler Oriented matroids 47 E. Sucheston Stopping times and directed processes 48 C. Sims Computation with finitely presented groups 49 T.
Palmer Banach algebras and the general theory of *-algebras 50 F. Borceux Handbook of categorical algebra I 51 F. Borceux Handbook of categorical algebra II 52 F. Borceux Handbook of categorical algebra III 54 A.
Hassleblatt Introduction to the modern theory of dynamical systems 55 V. Sachkov Combinatorial methods in discrete mathematics 56 V. Sachkov Probabilistic methods in discrete mathematics 57 P. Cohn Skew Fields 58 Richard J.
Gardner Geometric tomography 59 George A. and Peter Graves-Morris Padé approximants 60 Jan Krajicek Bounded arithmetic, propositional logic, and complex theory 61 H. Gromer Geometric applications of Fourier series and spherical harmonics 62 H. Fattorini Infinite dimensional optimization and control theory 63 A.
Thompson Minkowski geometry 64 R. Raghavan Nonnegative matrices and applications 65 K. Engel Sperner theory 66 D. Simic Eigenspaces of graphs 67 F.
Leroux Combinatorial species and tree-like structures 68 R. Wallach Representations of the classical groups 69 T. Lenz Design Theory volume I 2 ed. Wenzel Orthonormal systems and Banach space geometry 71 George E.
Andrews, Richard Askey and Ranjan Roy Special Functions 72 R. Ticciati Quantum field theory for mathematicians 76 A. Ivanov Geometry of sporadic groups I 78 T. Lenz Design Theory volume II 2 ed.
Stormark Lie’s Structural Approach to PDE Systems 81 C. Xu Orthogonal polynomials of several variables 82 J. Mayberry The foundations of mathematics in the theory of sets 83 C. Martins da Silva Rosa Navier-Stokes equations and turbulence 84 B.
Steinke Geometries on Surfaces 85 D. Paris Asymptotics and Mellin–Barnes integrals 86 Robert J. McEliece The theory of information and coding, 2 ed. Magurn An algebraic introduction to K-theory Continuous Lattices and Domains G.
SCOTT Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, São Paulo Cambridge University Press The Edinburgh Building, Cambridge , United Kingdom Published in the United States of America by Cambridge University Press, New York www.org Information on this title: www.org/9780521803380 © Cambridge University Press 2003 This book is in copyright. Subject to statutory exception and to the provision of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press. First published in print format 2003 - isbn-13 978-0-511-06356-5 eBook (NetLibrary) - isbn-10 0-511-06356-3 eBook (NetLibrary) - isbn-13 978-0-521-80338-0 hardback - isbn-10 0-521-80338-1 hardback Cambridge University Press has no responsibility for the persistence or accuracy of s for external or third-party internet websites referred to in this book, and does not guarantee that any content on such websites is, or will remain, accurate or appropriate. Contents Preface page xi Acknowledgments xxi Foreword to A Compendium of Continuous Lattices xxiii Introduction to A Compendium of Continuous Lattices xxvii O A Primer on Ordered Sets and Lattices 1 O-1 Generalities and Notation 1 Exercises 7 Old notes 8 O-2 Completeness Conditions for Lattices and Posets 8 Exercises 17 Old notes 21 New notes 22 O-3 Galois Connections 22 Exercises 31 Old notes 35 O-4 Meet Continuous Lattices and Semilattices 36 Exercises 39 Old notes 41 O-5 T0 Spaces and Order 41 Exercises 45 New notes 47 I Order Theory of Domains 48 I-1 The “Way-below” Relation 49 The way-below relation and continuous posets 49 Auxiliary relations 57 Important examples 62 v vi Contents Exercises 71 Old notes 75 New notes 78 I-2 Products, Substructures and Quotients 79 Products, projection, kernel and closure operators on domains 79 Equational theory of continuous lattices 83 Exercises 90 Old notes 93 New notes 94 I-3 Irreducible elements 95 Open filters and irreducible elements 95 Distributivity and prime elements 98 Pseudoprime elements 106 Exercises 108 Old notes 114 I-4 Algebraic Domains and Lattices 115 Compact elements, algebraic and arithmetic domains 115 Products, kernel and closure operators 119 Completely irreducible elements 125 Exercises 127 Old notes 129 New notes 129 II The Scott Topology 131 II-1 The Scott Topology 132 Scott convergence 132 The Scott topology of domains 138 The Hofmann–Mislove Theorem 144 Exercises 151 Old notes 155 New notes 156 II-2 Scott-Continuous Functions 157 Scott-continuous functions 157 Function spaces and cartesian closed categories of dcpos 161 FS-domains and bifinite domains 165 Exercises 171 Old notes 176 New notes 176 Contents vii II-3 Injective Spaces 176 Injective and densely injective spaces 177 Monotone convergence spaces 182 Exercises 185 Old notes 187 New notes 187 II-4 Function Spaces 187 The Isbell topology 187 Spaces with a continuous topology 190 On dcpos with a continuous Scott topology 197 Exercises 204 Old notes 206 New notes 207 III The Lawson Topology 208 III-1 The Lawson Topology 209 Exercises 216 Old notes 218 III-2 Meet Continuity Revisited 219 Exercises 224 Old notes 225 New notes 226 III-3 Quasicontinuity and Liminf Convergence 226 Quasicontinuous domains 226 The Lawson topology and Liminf convergence 231 Exercises 236 Old notes 240 New notes 240 III-4 Bases and Weights 240 Exercises 249 Old notes 252 New notes 252 III-5 Compact Domains 253 Exercises 261 New notes 263 IV Morphisms and Functors 264 IV-1 Duality Theory 266 Exercises 279 Old notes 279 viii Contents IV-2 Duality of Domains 280 Exercises 289 New notes 290 IV-3 Morphisms into Chains 290 Exercises 301 Old notes 304 IV-4 Projective Limits 305 Exercises 317 Old notes 317 IV-5 Pro-continuous and Locally Continuous Functors 318 Exercises 329 Old notes 330 New notes 330 IV-6 Fixed-Point Constructions for Functors 330 Exercises 340 New notes 342 IV-7 Domain Equations and Recursive Data Types 343 Domain equations for covariant functors 344 Domain equations for mixed variance functors 351 Examples of domain equations 355 Exercises 357 New notes 358 IV-8 Powerdomains 359 The Hoare powerdomain 361 The Smyth powerdomain 363 The Plotkin powerdomain 364 Exercises 372 New notes 374 IV-9 The Extended Probabilistic Powerdomain 374 Exercises 391 New notes 392 V Spectral Theory of Continuous Lattices 394 V-1 The Lemma 395 Exercises 399 Old notes 399 V-2 Order Generation and Topological Generation 400 Exercises 402 Old notes 403 Contents ix V-3 Weak Irreducibles and Weakly Prime Elements 403 Exercises 406 Old notes 407 V-4 Sober Spaces and Complete Lattices 408 Exercises 414 Old notes 415 V-5 Duality for Distributive Continuous Lattices 415 Exercises 423 Old notes 429 V-6 Domain Environments 431 Exercises 437 New notes 437 VI Compact Posets and Semilattices 439 VI-1 Pospaces and Topological Semilattices 440 Exercises 444 Old notes 445 VI-2 Compact Topological Semilattices 445 Exercises 449 Old notes 450 VI-3 The Fundamental Theorem of Compact Semilattices 450 Exercises 457 Old notes 462 VI-4 Some Important Examples 462 Old notes 467 VI-5 Chains in Compact Pospaces and Semilattices 468 Exercises 472 Old notes 473 VI-6 Stably Compact Spaces 474 Exercises 484 New notes 486 VI-7 Spectral Theory for Stably Compact Spaces 486 Exercises 489 Old notes 491 VII Topological Algebra and Lattice Theory: Applications 492 VII-1 One-Sided Topological Semilattices 493 Exercises 498 Old notes 499 x Contents VII-2 Topological Lattices 499 Exercises 504 Old notes 507 New notes 508 VII-3 Hypercontinuity and Quasicontinuity 508 Exercises 515 New notes 515 VII-4 Lattices with Continuous Scott Topology 515 Exercises 521 Old notes 522 Bibliography 523 Books, Monographs, and Collections 523 Conference Proceedings 526 Articles 528 Dissertations and Master’s Theses 559 Memos Circulated in the Seminar on Continuity in Semilattices (SCS) 564 List of Symbols 568 List of Categories 572 Index 575 Preface BACKGROUND.
In 1980 we published A Compendium of Continuous Lattices. A continuous lattice is a partially ordered set characterized by two conditions: firstly, completeness, which says that every subset has a least upper bound; secondly, continuity, which says that every element can be approximated from below by other elements which in a suitable sense are much smaller, as for example finite subsets are small in a set theoretical universe. A certain degree of technicality cannot be avoided if one wants to make more precise what this “suitable sense” is: we shall do this soon enough. When that book appeared, research on continuous lattices had reached a plateau.
The set of axioms proved itself to be very reasonable from many viewpoints; at all of these aspects we looked carefully. The theory of continuous lattices and its consequences were extremely satisfying for order theory, algebra, topol- ogy, topological algebra, and analysis. In all of these fields, applications of continuous lattices were highly successful. Continuous lattices provided truly interdisciplinary tools.
Major areas of application were the theory of computing and computability, as well as the semantics of programming languages. Indeed, the order theoretical foundations of computer science had been, some ten years earlier, the main motivation for the creation of the unifying theory of continuous lattices. Already the Compendium of Continuous Lattices itself contained signals pointing future research toward more general structures than continuous lattices. While the condition of continuity was a robust basis on which to build, the condition of completeness was soon seen to be too stringent for many applications in computer science – and indeed also in pure mathematics; an example is the study of the set of nonempty compact subsets of a topological space partially ordered by ⊇: this set is a very natural object in general topology but fails to be a complete lattice in a noncompact Hausdorff space, while a filter basis of compact sets does have a nonempty intersection.
Some form of completeness xi xii Preface therefore should be retained; the form that is satisfied in most applications is that of “directed completeness”, saying that every subset in which any two element set has an upper bound has a least upper bound; the existence of either a minimal or a maximal element is not implied. In computer science it has become customary to speak of a poset with this weak completeness property as a deeceepea-oh, written dcpo (for directed complete partially ordered set). A continuous dcpo is what we call a domain. Since this word appears in the title of this book, our terminology must be stated clearly at the beginning.
In that branch of order theory with which this book deals there is no terminology clouded in more disagreement and lack of precision than that of a “domain”, because it has become accepted as a sort of nontechnical terminology. Domains in our sense had moved into the focus of researchers’ attention at the time when the Compendium of Continuous Lattices was written, al- though then they were consistently called continuous posets, notably in the Compendium itself where they appear in many exercises. When their signifi- cance was discovered, it was too late to incorporate an emerging theory in the main architecture of the book, and it was too early for presenting a theory in statu nascendi.