Namespaces
Variants
Actions

Difference between revisions of "Continuous lattice"

From Encyclopedia of Mathematics
Jump to: navigation, search
(cf Compact lattice element)
m (tex done)
 
(4 intermediate revisions by 2 users not shown)
Line 1: Line 1:
A type of [[Complete lattice|complete lattice]], first studied under this name by D.S. Scott [[#References|[a1]]], [[#References|[a12]]], examples of which occur in many areas of algebra, analysis and topology. Continuous lattices are usually defined in terms of an auxiliary relation, the way-below relation, which is definable in any complete lattice <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c0257001.png" />: One says that an element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c0257002.png" /> is way below an element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c0257003.png" /> (and writes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c0257004.png" />) if, whenever <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c0257005.png" /> is a directed subset of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c0257006.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c0257007.png" />, there exists an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c0257008.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c0257009.png" />. The elements way below a given element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570010.png" /> form an [[Ideal|ideal]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570011.png" /> (in fact the intersection of all those ideals <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570012.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570013.png" />); one says that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570014.png" /> is continuous if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570015.png" /> for every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570016.png" />. Thus, a continuous lattice is a [[partially ordered set]] in which every subset has a least upper bound and in which every element is the least upper bound of all elements way below it. An element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570017.png" /> in a complete lattice is compact, or finite (cf. [[Compact lattice element]]), if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570018.png" />; from this it follows that an [[Algebraic lattice|algebraic lattice]] is continuous, and in fact continuous lattices may be characterized as those complete lattices which are retracts of algebraic lattices by mappings preserving directed sups. Continuous lattices may also be characterized equationally: they are precisely those complete lattices which satisfy all those instances of the complete distributive law
 
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570019.png" /></td> </tr></table>
+
A type of [[Complete lattice|complete lattice]], first studied under this name by D.S. Scott [[#References|[a1]]], [[#References|[a12]]], examples of which occur in many areas of algebra, analysis and topology. Continuous lattices are usually defined in terms of an auxiliary relation, the way-below relation, which is definable in any complete lattice $A$: One says that an element $b$ is way below an element $a$ (and writes $b \ll a$) if, whenever $S$ is a directed subset of $A$ with $\sup S \ge a$, there exists an $s \in S$ with $s \ge b$. The elements way below a given element $a$ form an [[Ideal|ideal]] $\downarrow(a)$ (in fact the intersection of all those ideals $I$ with $\sup I \ge a$); one says that $A$ is continuous if $\sup \downarrow(a) = a$ for every $a \in A$. Thus, a continuous lattice is a [[partially ordered set]] in which every subset has a least upper bound and in which every element is the least upper bound of all elements way below it. An element $a$ in a complete lattice is compact, or finite (cf. [[Compact lattice element]]), if and only if $a \ll a$; from this it follows that an [[Algebraic lattice|algebraic lattice]] is continuous, and in fact continuous lattices may be characterized as those complete lattices which are retracts of algebraic lattices by mappings preserving directed sups. Continuous lattices may also be characterized equationally: they are precisely those complete lattices which satisfy all those instances of the complete distributive law
  
(where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570020.png" /> is the set of choice functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570021.png" />) for which the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570022.png" /> is (upwards) directed for each <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570023.png" />. In particular, a [[Completely distributive lattice|completely distributive lattice]] is continuous; conversely, one can show that if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570024.png" /> is a (finitely) distributive complete lattice such that both <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570025.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570026.png" /> are continuous, then <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570027.png" /> is completely distributive.
+
$$
 +
\inf_{i \in I} \sup_{j \in J_i} a_{i,j} = \sup_{f \in F} \inf_{i\in I} a_{i, f(i)}
 +
$$
  
If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570028.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570029.png" /> are continuous lattices, then the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570030.png" /> of all functions from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570031.png" /> to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570032.png" /> preserving suprema of upwards directed sets is a continuous lattice with respect to the pointwise partial order. The category of continuous lattices and such functions is a Cartesian-closed category (cf. [[Closed category|Closed category]]).
+
(where $F$ is the set of choice functions $I \to \cup_{i\in I} J_i$) for which the set $\{a_{i,j} : j \in J_i\}$ is (upwards) directed for each $i \in I$. In particular, a [[Completely distributive lattice|completely distributive lattice]] is continuous; conversely, one can show that if $A$ is a (finitely) distributive complete lattice such that both $A$ and $A^{\text{op}}$ are continuous, then $A$ is completely distributive.
  
There are two intrinsic topologies which are of importance in the study of continuous lattices. The Scott topology on a complete lattice <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570033.png" /> has for its open sets those <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570034.png" /> which are upper sets (i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570035.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570036.png" /> implies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570037.png" />) and inaccessible by directed sups (i.e. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570038.png" /> directed and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570039.png" /> implies <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570040.png" />). A function between complete lattices is continuous for their Scott topologies if and only if it preserves directed sups; thus the Scott-open subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570041.png" /> are precisely those whose characteristic functions are Scott-continuous mappings <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570042.png" />. Equipped with their Scott topologies, continuous lattices are precisely the injective objects (with respect to subspace inclusions, cf. [[Injective object|Injective object]]) in the [[Category|category]] of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570043.png" /> topological spaces [[#References|[a1]]]; equivalently, they are precisely the retracts of powers of the Sierpiński space (the latter being the two-element lattice <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570044.png" /> equipped with its Scott topology). The second intrinsic topology, the Lawson topology, has as a subbase of open sets the Scott-open sets together with the complements of principal filters (i.e. the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570045.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570046.png" />). It is Hausdorff (unlike the Scott topology) and compact, and the binary meet operation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570047.png" /> is continuous for it; moreover, continuous lattices equipped with their Lawson topologies may be characterized as those compact Hausdorff topological meet semi-lattices for which the continuous semi-lattice of homomorphisms into the unit interval <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570048.png" /> separate points (these are sometimes called (compact) Lawson semi-lattices) [[#References|[a2]]], [[#References|[a3]]]. From this, one obtains yet another, purely lattice-theoretic, characterization of continuous lattices: up to isomorphism, they are precisely the subsets of powers of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570049.png" /> which are closed under directed sups and arbitrary infs.
+
If $L_1$ and $L_2$ are continuous lattices, then the set $[L_1, L_2]$ of all functions from $L_1$ to $L_2$ preserving suprema of upwards directed sets is a continuous lattice with respect to the pointwise partial order. The category of continuous lattices and such functions is a Cartesian-closed category (cf. [[Closed category|Closed category]]).
  
In the lattice of all open sets of a [[Topological space|topological space]], it is easy to see that the relation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570050.png" /> holds if there is a compact set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570051.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570052.png" />; from this it follows that the open-set lattice of a [[Locally compact space|locally compact space]] (or of a locally quasi-compact space) is continuous. Conversely, the continuous lattices which are (finitely) distributive are exactly the open-set lattices of locally compact topological spaces [[#References|[a4]]]. The continuity of the open-set lattices of locally compact spaces is closely related to the good behaviour of function spaces when the domain space is locally compact [[#References|[a5]]], [[#References|[a6]]].
+
There are two intrinsic topologies which are of importance in the study of continuous lattices. The Scott topology on a complete lattice $A$ has for its open sets those $U \subseteq A$ which are upper sets (i.e. $a \in U$ and $a \le b$ implies $b \in $) and inaccessible by directed sups (i.e. $S$ directed and $\sup S \in U$ implies $S \cap U \ne \emptyset$). A function between complete lattices is continuous for their Scott topologies if and only if it preserves directed sups; thus the Scott-open subsets of $A$ are precisely those whose characteristic functions are Scott-continuous mappings $A \to \{0,1\}$. Equipped with their Scott topologies, continuous lattices are precisely the injective objects (with respect to subspace inclusions, cf. [[Injective object|Injective object]]) in the [[Category|category]] of $T_0$ topological spaces [[#References|[a1]]]; equivalently, they are precisely the retracts of powers of the [[Sierpiński space]] (the latter being the two-element lattice $\{0,1\}$ equipped with its Scott topology). The second intrinsic topology, the Lawson topology, has as a [[subbase]] of open sets the Scott-open sets together with the complements of principal filters (i.e. the sets $\{b \in A: b \ge a \}$, $a\in A$). It is Hausdorff (unlike the Scott topology) and compact, and the binary meet operation $A \times A \to A$ is continuous for it; moreover, continuous lattices equipped with their Lawson topologies may be characterized as those compact Hausdorff topological meet semi-lattices for which the continuous semi-lattice of homomorphisms into the unit interval $[0,1]$ separate points (these are sometimes called (compact) Lawson semi-lattices) [[#References|[a2]]], [[#References|[a3]]]. From this, one obtains yet another, purely lattice-theoretic, characterization of continuous lattices: up to isomorphism, they are precisely the subsets of powers of $[0,1]$ which are closed under directed sups and arbitrary infs.
  
Iterating a natural morphism <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570053.png" /> and using an inverse limit construction, Scott imbedded any continuous lattice in a continuous lattice <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570054.png" /> which is naturally isomorphic to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570055.png" />. Every element <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570056.png" /> in such a continuous lattice <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570057.png" /> may thus be regarded as a self-map of this domain and vice versa — provided that "self-maps" are morphisms in the category. As a consequence, self-application of the type <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570058.png" /> is well-defined. Therefore, the continuous lattices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570059.png" /> are models of the [[Lambda-calculus|<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570060.png" />-calculus]].
+
In the lattice of all open sets of a [[Topological space|topological space]], it is easy to see that the relation $U \ll V$ holds if there is a compact set $K$ with $U \subseteq K \subseteq V$; from this it follows that the open-set lattice of a [[Locally compact space|locally compact space]] (or of a locally quasi-compact space) is continuous. Conversely, the continuous lattices which are (finitely) distributive are exactly the open-set lattices of locally compact topological spaces [[#References|[a4]]]. The continuity of the open-set lattices of locally compact spaces is closely related to the good behaviour of function spaces when the domain space is locally compact [[#References|[a5]]], [[#References|[a6]]].
  
A generalization of the concept of a continuous lattice is that of a continuous poset [[#References|[a7]]]. A further generalization, to continuous categories, has also been studied, [[#References|[a8]]]. A continuous poset is defined by replacing in the definition of continuous lattice the requirement that all subsets of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570061.png" /> have suprema by the weaker assumption that all non-empty upwards directed sets have suprema and that all sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570062.png" /> are upwards directed.
+
Iterating a natural morphism $[L,L]\to L$ and using an inverse limit construction, Scott imbedded any continuous lattice in a continuous lattice $D_\infty$ which is naturally isomorphic to $[D_\infty, D_\infty]$. Every element $f$ in such a continuous lattice $D_\infty$ may thus be regarded as a self-map of this domain and vice versa — provided that "self-maps" are morphisms in the category. As a consequence, self-application of the type $f(f)$ is well-defined. Therefore, the continuous lattices $D_\infty$ are models of the [[Lambda-calculus|$\lambda$-calculus]].
  
Continuous posets allow a theory of the type of [[Pontryagin duality|Pontryagin duality]]. The lattice <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570063.png" /> of open subsets of a Hausdorff space is a continuous lattice if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/c/c025/c025700/c02570064.png" /> is locally compact. In this case its Pontryagin dual is the set of compact subsets with reversed inclusion as order relation.
+
A generalization of the concept of a continuous lattice is that of a continuous poset [[#References|[a7]]]. A further generalization, to continuous categories, has also been studied, [[#References|[a8]]]. A continuous poset is defined by replacing in the definition of continuous lattice the requirement that all subsets of $L$ have suprema by the weaker assumption that all non-empty upwards directed sets have suprema and that all sets $\{x : x\ll y\}$ are upwards directed.
 +
 
 +
Continuous posets allow a theory of the type of [[Pontryagin duality|Pontryagin duality]]. The lattice $\mathcal{O}(X)$ of open subsets of a Hausdorff space is a continuous lattice if and only if $X$ is locally compact. In this case its Pontryagin dual is the set of compact subsets with reversed inclusion as order relation.
  
 
A domain is a continuous poset in which, first, every element is the supremum of compact elements, secondly, there are countably many compact elements, and, finally, every set which has an upper bound has a supremum. Domains have applications in the semantics of high-level programming languages; introductions into this aspect can be found in [[#References|[a14]]] and [[#References|[a15]]].
 
A domain is a continuous poset in which, first, every element is the supremum of compact elements, secondly, there are countably many compact elements, and, finally, every set which has an upper bound has a supremum. Domains have applications in the semantics of high-level programming languages; introductions into this aspect can be found in [[#References|[a14]]] and [[#References|[a15]]].
Line 23: Line 26:
 
Continuous lattices were introduced by Dana S. Scott [[#References|[a1]]], [[#References|[a12]]] as a basis for an abstract theory of computation by which a "computation" is approximated better and better by "finite approximations" .
 
Continuous lattices were introduced by Dana S. Scott [[#References|[a1]]], [[#References|[a12]]] as a basis for an abstract theory of computation by which a "computation" is approximated better and better by "finite approximations" .
  
Continuous lattices should not be confused with continuous geometries, which are complete lattices of an entirely different type. Cf. [[Orthomodular lattice|Orthomodular lattice]] for the notion of continuous geometry.
+
Continuous lattices should not be confused with continuous geometries, which are complete lattices of an entirely different type. Cf. [[Orthomodular lattice]] for the notion of continuous geometry.
  
 
====References====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> D.S. Scott, "Continuous lattices" F.W. Lawvere (ed.) , ''Toposes, algebraic geometry and logic (Dalhousic Univ., Jan. 1971)'' , ''Lect. notes in math.'' , '''274''' , Springer (1972) pp. 97–136 {{MR|0404073}} {{ZBL|0239.54006}} </TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> J.D. Lawson, "Topological semilattices with small semilattices" ''J. Lond. Math. Soc. (2)'' , '''1''' (1969) pp. 719–724 {{MR|0253301}} {{ZBL|0185.03801}} </TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top"> K.H. Hofmann, A.R. Stralka, "The algebraic theory of Lawson semilattices" ''Diss. Math.'' , '''137''' (1976) pp. 1–54 {{MR|}} {{ZBL|0359.06016}} </TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top"> K.H. Hofmann, J.D. Lawson, "The spectral theory of distributive continuous lattices" ''Trans. Amer. Math. Soc.'' , '''246''' (1978) pp. 285–310 {{MR|0515540}} {{ZBL|0402.54043}} </TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top"> B.J. Day, G.M. Kelly, "On topological quotient maps preserved by pullbacks or products" ''Proc. Cambridge Philos. Soc.'' , '''67''' (1970) pp. 553–558 {{MR|}} {{ZBL|0191.20801}} </TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top"> J.R. Isbell, "General function spaces, products and continuous lattices" ''Math. Proc. Cambridge Philos. Soc.'' , '''100''' (1986) pp. 193–205 {{MR|0848846}} {{ZBL|0609.54010}} </TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top"> G. Markowsky, "A motivation and generalization of Scott's notion of a continuous lattice" , ''Continuous lattices'' , ''Lect. notes in math.'' , '''871''' , Springer (1981) pp. 298–307</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top"> P.T. Johnstone, A. Joyal, "Continuous categories and exponentiable toposes" ''J. Pure Appl. Alg.'' , '''25''' (1982) pp. 255–296 {{MR|0666021}} {{ZBL|0487.18003}} </TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top"> G. Gierz, K.H. Hofmann, K. Keimel, J.D. Lawson, M.V. Mislove, D.S. Scott, "A compendium of continuous lattices" , Springer (1980) {{MR|0614752}} {{ZBL|0452.06001}} </TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top"> P.T. Johnstone, "Stone spaces" , Cambridge Univ. Press (1982) {{MR|0698074}} {{ZBL|0499.54001}} </TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top"> R.-E. Hoffman (ed.) K.H. Hofmann (ed.) , ''Continuous lattices and their applications'' , M. Dekker (1985)</TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top"> D.S. Scott, "Outline of a mathematical theory of computations" , ''Proc. 4-th Annual Princeton Conf. Information Sc. and Systems'' , Princeton Univ. Press (1970) pp. 169–176</TD></TR><TR><TD valign="top">[a13]</TD> <TD valign="top"> B. Banaschewski (ed.) R.-E. Hoffmann (ed.) , ''Continuous lattices'' , ''Lect. notes in math.'' , '''871''' , Springer (1981) {{MR|0646068}} {{ZBL|0469.06007}} {{ZBL|0452.00011}} </TD></TR><TR><TD valign="top">[a14]</TD> <TD valign="top"> D. Schmidt, "Denotational semantics: An introduction" , Allyn &amp; Bacon (1986)</TD></TR><TR><TD valign="top">[a15]</TD> <TD valign="top"> J.E. Stoy, "Denotational semantics: The Scott–Strachey approach to programming language theory" , M.I.T. (1979) {{MR|0629830}} {{MR|0488969}} {{ZBL|0503.68059}} </TD></TR></table>
+
<table><TR><TD valign="top">[a1]</TD> <TD valign="top"> D.S. Scott, "Continuous lattices" F.W. Lawvere (ed.) , ''Toposes, algebraic geometry and logic (Dalhousic Univ., Jan. 1971)'' , ''Lect. notes in math.'' , '''274''' , Springer (1972) pp. 97–136 {{MR|0404073}} {{ZBL|0239.54006}} </TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top"> J.D. Lawson, "Topological semilattices with small semilattices" ''J. Lond. Math. Soc. (2)'' , '''1''' (1969) pp. 719–724 {{MR|0253301}} {{ZBL|0185.03801}} </TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top"> K.H. Hofmann, A.R. Stralka, "The algebraic theory of Lawson semilattices" ''Diss. Math.'' , '''137''' (1976) pp. 1–54 {{MR|}} {{ZBL|0359.06016}} </TD></TR>
 +
<TR><TD valign="top">[a4]</TD> <TD valign="top"> K.H. Hofmann, J.D. Lawson, "The spectral theory of distributive continuous lattices" ''Trans. Amer. Math. Soc.'' , '''246''' (1978) pp. 285–310 {{MR|0515540}} {{ZBL|0402.54043}} </TD></TR>
 +
<TR><TD valign="top">[a5]</TD> <TD valign="top"> B.J. Day, G.M. Kelly, "On topological quotient maps preserved by pullbacks or products" ''Proc. Cambridge Philos. Soc.'' , '''67''' (1970) pp. 553–558 {{MR|}} {{ZBL|0191.20801}} </TD></TR>
 +
<TR><TD valign="top">[a6]</TD> <TD valign="top"> J.R. Isbell, "General function spaces, products and continuous lattices" ''Math. Proc. Cambridge Philos. Soc.'' , '''100''' (1986) pp. 193–205 {{MR|0848846}} {{ZBL|0609.54010}} </TD></TR>
 +
<TR><TD valign="top">[a7]</TD> <TD valign="top"> G. Markowsky, "A motivation and generalization of Scott's notion of a continuous lattice" , ''Continuous lattices'' , ''Lect. notes in math.'' , '''871''' , Springer (1981) pp. 298–307</TD></TR>
 +
<TR><TD valign="top">[a8]</TD> <TD valign="top"> P.T. Johnstone, A. Joyal, "Continuous categories and exponentiable toposes" ''J. Pure Appl. Alg.'' , '''25''' (1982) pp. 255–296 {{MR|0666021}} {{ZBL|0487.18003}} </TD></TR>
 +
<TR><TD valign="top">[a9]</TD> <TD valign="top"> G. Gierz, K.H. Hofmann, K. Keimel, J.D. Lawson, M.V. Mislove, D.S. Scott, "A compendium of continuous lattices" , Springer (1980) {{ISBN|3-540-10111-X}} {{MR|0614752}} {{ZBL|0452.06001}} </TD></TR>
 +
<TR><TD valign="top">[a10]</TD> <TD valign="top"> P.T. Johnstone, "Stone spaces" , Cambridge Univ. Press (1982) {{MR|0698074}} {{ZBL|0499.54001}} </TD></TR><TR><TD valign="top">[a11]</TD> <TD valign="top"> R.-E. Hoffman (ed.) K.H. Hofmann (ed.) , ''Continuous lattices and their applications'' , M. Dekker (1985)</TD></TR><TR><TD valign="top">[a12]</TD> <TD valign="top"> D.S. Scott, "Outline of a mathematical theory of computations" , ''Proc. 4-th Annual Princeton Conf. Information Sc. and Systems'' , Princeton Univ. Press (1970) pp. 169–176</TD></TR>
 +
<TR><TD valign="top">[a13]</TD> <TD valign="top"> B. Banaschewski (ed.) R.-E. Hoffmann (ed.) , ''Continuous lattices'' , ''Lect. notes in math.'' , '''871''' , Springer (1981) {{MR|0646068}} {{ZBL|0469.06007}} {{ZBL|0452.00011}} </TD></TR>
 +
<TR><TD valign="top">[a14]</TD> <TD valign="top"> D. Schmidt, "Denotational semantics: An introduction" , Allyn &amp; Bacon (1986)</TD></TR>
 +
<TR><TD valign="top">[a15]</TD> <TD valign="top"> J.E. Stoy, "Denotational semantics: The Scott–Strachey approach to programming language theory" , M.I.T. (1979) {{MR|0629830}} {{MR|0488969}} {{ZBL|0503.68059}} </TD></TR></table>
 +
 
 +
{{TEX|done}}

Latest revision as of 04:50, 15 February 2024

A type of complete lattice, first studied under this name by D.S. Scott [a1], [a12], examples of which occur in many areas of algebra, analysis and topology. Continuous lattices are usually defined in terms of an auxiliary relation, the way-below relation, which is definable in any complete lattice $A$: One says that an element $b$ is way below an element $a$ (and writes $b \ll a$) if, whenever $S$ is a directed subset of $A$ with $\sup S \ge a$, there exists an $s \in S$ with $s \ge b$. The elements way below a given element $a$ form an ideal $\downarrow(a)$ (in fact the intersection of all those ideals $I$ with $\sup I \ge a$); one says that $A$ is continuous if $\sup \downarrow(a) = a$ for every $a \in A$. Thus, a continuous lattice is a partially ordered set in which every subset has a least upper bound and in which every element is the least upper bound of all elements way below it. An element $a$ in a complete lattice is compact, or finite (cf. Compact lattice element), if and only if $a \ll a$; from this it follows that an algebraic lattice is continuous, and in fact continuous lattices may be characterized as those complete lattices which are retracts of algebraic lattices by mappings preserving directed sups. Continuous lattices may also be characterized equationally: they are precisely those complete lattices which satisfy all those instances of the complete distributive law

$$ \inf_{i \in I} \sup_{j \in J_i} a_{i,j} = \sup_{f \in F} \inf_{i\in I} a_{i, f(i)} $$

(where $F$ is the set of choice functions $I \to \cup_{i\in I} J_i$) for which the set $\{a_{i,j} : j \in J_i\}$ is (upwards) directed for each $i \in I$. In particular, a completely distributive lattice is continuous; conversely, one can show that if $A$ is a (finitely) distributive complete lattice such that both $A$ and $A^{\text{op}}$ are continuous, then $A$ is completely distributive.

If $L_1$ and $L_2$ are continuous lattices, then the set $[L_1, L_2]$ of all functions from $L_1$ to $L_2$ preserving suprema of upwards directed sets is a continuous lattice with respect to the pointwise partial order. The category of continuous lattices and such functions is a Cartesian-closed category (cf. Closed category).

There are two intrinsic topologies which are of importance in the study of continuous lattices. The Scott topology on a complete lattice $A$ has for its open sets those $U \subseteq A$ which are upper sets (i.e. $a \in U$ and $a \le b$ implies $b \in $) and inaccessible by directed sups (i.e. $S$ directed and $\sup S \in U$ implies $S \cap U \ne \emptyset$). A function between complete lattices is continuous for their Scott topologies if and only if it preserves directed sups; thus the Scott-open subsets of $A$ are precisely those whose characteristic functions are Scott-continuous mappings $A \to \{0,1\}$. Equipped with their Scott topologies, continuous lattices are precisely the injective objects (with respect to subspace inclusions, cf. Injective object) in the category of $T_0$ topological spaces [a1]; equivalently, they are precisely the retracts of powers of the Sierpiński space (the latter being the two-element lattice $\{0,1\}$ equipped with its Scott topology). The second intrinsic topology, the Lawson topology, has as a subbase of open sets the Scott-open sets together with the complements of principal filters (i.e. the sets $\{b \in A: b \ge a \}$, $a\in A$). It is Hausdorff (unlike the Scott topology) and compact, and the binary meet operation $A \times A \to A$ is continuous for it; moreover, continuous lattices equipped with their Lawson topologies may be characterized as those compact Hausdorff topological meet semi-lattices for which the continuous semi-lattice of homomorphisms into the unit interval $[0,1]$ separate points (these are sometimes called (compact) Lawson semi-lattices) [a2], [a3]. From this, one obtains yet another, purely lattice-theoretic, characterization of continuous lattices: up to isomorphism, they are precisely the subsets of powers of $[0,1]$ which are closed under directed sups and arbitrary infs.

In the lattice of all open sets of a topological space, it is easy to see that the relation $U \ll V$ holds if there is a compact set $K$ with $U \subseteq K \subseteq V$; from this it follows that the open-set lattice of a locally compact space (or of a locally quasi-compact space) is continuous. Conversely, the continuous lattices which are (finitely) distributive are exactly the open-set lattices of locally compact topological spaces [a4]. The continuity of the open-set lattices of locally compact spaces is closely related to the good behaviour of function spaces when the domain space is locally compact [a5], [a6].

Iterating a natural morphism $[L,L]\to L$ and using an inverse limit construction, Scott imbedded any continuous lattice in a continuous lattice $D_\infty$ which is naturally isomorphic to $[D_\infty, D_\infty]$. Every element $f$ in such a continuous lattice $D_\infty$ may thus be regarded as a self-map of this domain and vice versa — provided that "self-maps" are morphisms in the category. As a consequence, self-application of the type $f(f)$ is well-defined. Therefore, the continuous lattices $D_\infty$ are models of the $\lambda$-calculus.

A generalization of the concept of a continuous lattice is that of a continuous poset [a7]. A further generalization, to continuous categories, has also been studied, [a8]. A continuous poset is defined by replacing in the definition of continuous lattice the requirement that all subsets of $L$ have suprema by the weaker assumption that all non-empty upwards directed sets have suprema and that all sets $\{x : x\ll y\}$ are upwards directed.

Continuous posets allow a theory of the type of Pontryagin duality. The lattice $\mathcal{O}(X)$ of open subsets of a Hausdorff space is a continuous lattice if and only if $X$ is locally compact. In this case its Pontryagin dual is the set of compact subsets with reversed inclusion as order relation.

A domain is a continuous poset in which, first, every element is the supremum of compact elements, secondly, there are countably many compact elements, and, finally, every set which has an upper bound has a supremum. Domains have applications in the semantics of high-level programming languages; introductions into this aspect can be found in [a14] and [a15].

A detailed account of continuous lattice theory is given in [a9], and a more concise one in [a10], Chapt. 7. Reference [a11] discusses some more recent developments in the subject and contains an extensive bibliography on continuous lattices up to 1985.

Continuous lattices were introduced by Dana S. Scott [a1], [a12] as a basis for an abstract theory of computation by which a "computation" is approximated better and better by "finite approximations" .

Continuous lattices should not be confused with continuous geometries, which are complete lattices of an entirely different type. Cf. Orthomodular lattice for the notion of continuous geometry.

References

[a1] D.S. Scott, "Continuous lattices" F.W. Lawvere (ed.) , Toposes, algebraic geometry and logic (Dalhousic Univ., Jan. 1971) , Lect. notes in math. , 274 , Springer (1972) pp. 97–136 MR0404073 Zbl 0239.54006
[a2] J.D. Lawson, "Topological semilattices with small semilattices" J. Lond. Math. Soc. (2) , 1 (1969) pp. 719–724 MR0253301 Zbl 0185.03801
[a3] K.H. Hofmann, A.R. Stralka, "The algebraic theory of Lawson semilattices" Diss. Math. , 137 (1976) pp. 1–54 Zbl 0359.06016
[a4] K.H. Hofmann, J.D. Lawson, "The spectral theory of distributive continuous lattices" Trans. Amer. Math. Soc. , 246 (1978) pp. 285–310 MR0515540 Zbl 0402.54043
[a5] B.J. Day, G.M. Kelly, "On topological quotient maps preserved by pullbacks or products" Proc. Cambridge Philos. Soc. , 67 (1970) pp. 553–558 Zbl 0191.20801
[a6] J.R. Isbell, "General function spaces, products and continuous lattices" Math. Proc. Cambridge Philos. Soc. , 100 (1986) pp. 193–205 MR0848846 Zbl 0609.54010
[a7] G. Markowsky, "A motivation and generalization of Scott's notion of a continuous lattice" , Continuous lattices , Lect. notes in math. , 871 , Springer (1981) pp. 298–307
[a8] P.T. Johnstone, A. Joyal, "Continuous categories and exponentiable toposes" J. Pure Appl. Alg. , 25 (1982) pp. 255–296 MR0666021 Zbl 0487.18003
[a9] G. Gierz, K.H. Hofmann, K. Keimel, J.D. Lawson, M.V. Mislove, D.S. Scott, "A compendium of continuous lattices" , Springer (1980) ISBN 3-540-10111-X MR0614752 Zbl 0452.06001
[a10] P.T. Johnstone, "Stone spaces" , Cambridge Univ. Press (1982) MR0698074 Zbl 0499.54001
[a11] R.-E. Hoffman (ed.) K.H. Hofmann (ed.) , Continuous lattices and their applications , M. Dekker (1985)
[a12] D.S. Scott, "Outline of a mathematical theory of computations" , Proc. 4-th Annual Princeton Conf. Information Sc. and Systems , Princeton Univ. Press (1970) pp. 169–176
[a13] B. Banaschewski (ed.) R.-E. Hoffmann (ed.) , Continuous lattices , Lect. notes in math. , 871 , Springer (1981) MR0646068 Zbl 0469.06007 Zbl 0452.00011
[a14] D. Schmidt, "Denotational semantics: An introduction" , Allyn & Bacon (1986)
[a15] J.E. Stoy, "Denotational semantics: The Scott–Strachey approach to programming language theory" , M.I.T. (1979) MR0629830 MR0488969 Zbl 0503.68059
How to Cite This Entry:
Continuous lattice. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Continuous_lattice&oldid=36186