Namespaces
Variants
Actions

Difference between revisions of "Continuous lattice"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (MR/ZBL numbers added)
Line 11: Line 11:
 
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]]].
 
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]]].
  
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]].
+
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]].
  
 
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.
 
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.
Line 21: Line 21:
 
A detailed account of continuous lattice theory is given in [[#References|[a9]]], and a more concise one in [[#References|[a10]]], Chapt. 7. Reference [[#References|[a11]]] discusses some more recent developments in the subject and contains an extensive bibliography on continuous lattices up to 1985.
 
A detailed account of continuous lattice theory is given in [[#References|[a9]]], and a more concise one in [[#References|[a10]]], Chapt. 7. Reference [[#References|[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 [[#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|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</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</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</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</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</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</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</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)</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top"> P.T. Johnstone,   "Stone spaces" , Cambridge Univ. Press (1982)</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)</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)</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) {{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>

Revision as of 21:51, 30 March 2012

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 : One says that an element is way below an element (and writes ) if, whenever is a directed subset of with , there exists an with . The elements way below a given element form an ideal (in fact the intersection of all those ideals with ); one says that is continuous if for every . 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 in a complete lattice is compact, or finite, if and only if ; 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

(where is the set of choice functions ) for which the set is (upwards) directed for each . In particular, a completely distributive lattice is continuous; conversely, one can show that if is a (finitely) distributive complete lattice such that both and are continuous, then is completely distributive.

If and are continuous lattices, then the set of all functions from to 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 has for its open sets those which are upper sets (i.e. and implies ) and inaccessible by directed sups (i.e. directed and implies ). 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 are precisely those whose characteristic functions are Scott-continuous mappings . Equipped with their Scott topologies, continuous lattices are precisely the injective objects (with respect to subspace inclusions, cf. Injective object) in the category of topological spaces [a1]; equivalently, they are precisely the retracts of powers of the Sierpiński space (the latter being the two-element lattice 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 , ). It is Hausdorff (unlike the Scott topology) and compact, and the binary meet operation 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 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 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 holds if there is a compact set with ; 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 and using an inverse limit construction, Scott imbedded any continuous lattice in a continuous lattice which is naturally isomorphic to . Every element in such a continuous lattice 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 is well-defined. Therefore, the continuous lattices are models of the -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 have suprema by the weaker assumption that all non-empty upwards directed sets have suprema and that all sets are upwards directed.

Continuous posets allow a theory of the type of Pontryagin duality. The lattice of open subsets of a Hausdorff space is a continuous lattice if and only if 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) 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=17410