Namespaces
Variants
Actions

Continuous lattice

From Encyclopedia of Mathematics
Jump to: navigation, search

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=55506