The way-below relation of function spaces over semantic domains

Thomas Erker^{∗}  Martín Hötzel Escardó^{†}  Klaus Keimel^{∗}

To appear in Topology and Its Applications

Version of Tuesday 22 \underline{nd} July 1997

Abstract

For partially ordered sets that are continuous in the sense of D. S. Scott, the waybelow relation is crucial. It expresses the approximation of an ideal element by its finite parts. We present explicit characterizations of the way-below relation on spaces of continuous functions from topological spaces into continuous posets. Although it is well-known in which cases these function spaces are continuous posets, such characterizations were lacking until now.

Keywords: Continuous posets, Scott domains, continuous lattices, function spaces, waybelow relation.

AMS classification: 06B35, 68Q55, 54C35.

The notion of a continuous partially ordered set in the sense of D. S. Scott [7, 2, 1], or continuous domain for short, is rooted in the fundamental idea of approximating ideal objects by their finitary parts.

Technically speaking, one considers directed complete posets; that is, partially ordered sets L in which every directed subset D has a least upper bound, denoted by ^{⋁↑} D. An element c is said to be a finitary approximation of a ∈ L (one also says that c is relatively compact in or simply way-below a), and one writes c ≪ a, if for any directed subset D of L, the condition a ≤ ^{⋁↑} D implies c ≤ d for some d ∈ D. If for every a ∈ L there is a directed set D of finitary approximants c ≪ a such that a = ^{⋁↑} D, then L is called a continuous domain or simply a continuous poset. The basic references for the theory are [2, 1].

The notion of approximation in the previous paragraph is phrased in purely order theoretical terms. It can be viewed as topological convergence with respect to the Scott topology. This is the topology on a directed complete poset for which the closed sets are those lower sets which are closed for the formation of directed joins. In the case of a continuous domain, the sets of the form

↑ ↑c = {a ∈ L : c ≪ a} , c ∈ L ,

∗Fachbereich Mathematik, Technische Hochschule, 64289 Darmstadt, Germany, E-mail:

{erker,keimel}@mathematik.th-darmstadt.de.

†Department of Computing, Imperial College, 180 Queen’s Gate, London SW7 2BZ, United Kingdom, E-mail: M.Escardo@doc.ic.ac.uk.

form a base for the Scott open sets. In this paper, continuous domains are always considered as topological spaces endowed with the Scott topology. With respect to this topology, a continuous domain L is sober and locally compact (in the sense that every point has a base of compact neighbourhoods), but far from being a Hausdorff space [2, II.1.20]. Note that compactness does not include the Hausdorff property in this paper.

As the relation c ≪ a is basic for the whole theory, it is important to characterize it in simple terms in concrete situations. Often this turns out to be more complicated than one might expect. A striking example is the probabilistic power domain over a continuous domain where an explicit characterization of the way-below relation relies on the Ford-Fulkerson Theorem [6, 5]. Another good test case is that of function spaces. It is well known that the space [X → L] of all continuous functions from a locally compact topological space X into a continuous lattice L with the pointwise ordering is a continuous lattice [2, II.4.6].

In the Compendium [2], one finds two characterizations of the way-below relation in these function spaces: Firstly, in I.1.21.1, in the special case where X is a compact Hausdorff space and L the extended real line, secondly for the general case in II.4.20. While in the special case they are correct except for the last one, the characterizations in II.4.20 are correct for X Hausdorff. As a counterexample one may use the function space [L → L] with L the unit interval endowed with the Scott topology induced by its natural order. With respect to this topology, L is indeed locally compact, but strongly non-Hausdorff, because a Scott open set containing the bottom element is necessarily the whole of L. As the example of the function space [L → L] is crucial for the whole theory, it is essential to admit non-Hausdorff spaces for X.

We establish characterizations of the way-below relation on function spaces that might be those that were intended in the Compendium. The conditions in the Compendium are modelled too closely on the Hausdorff case. Nevertheless, for many results we need additional conditions on X that will not be surprising for the experts. We shall ask the space X to be locally compact and coherent. The last condition needs some explanation.

In any topological space X we may consider those sets which are intersections of open sets. Such sets are called saturated. In the Hausdorff setting this notion is superfluous, as all sets are saturated. A space is called coherent if it is sober and the intersection of any two compact saturated subsets is compact.

Before we proceed to the heart of the subject, let us discuss the generality in which we wish to place ourselves. Let X be a topological space, whose lattice of open sets will be denoted by O(X), and L be a directed complete poset (endowed with the Scott topology). The set [X → L] of continuous functions f : X → L is directed complete with respect to the pointwise ordering. Let us assume that L has a smallest element. For [X → L] to be a continuous domain, it is firstly necessary for the lattice O(X) to be continuous. Indeed, as the two-element lattice 2 is a continuous retract of L, the function space [X → 2] is a continuous retract of [X → L], and [X → 2] is canonically isomorphic to O(X). The spaces X for which O(X) is continuous are called core compact. They only slightly generalize locally compact spaces as for sober spaces core compactness is equivalent to local compactness [2, V.5.6]. Thus, the reader may restrict his attention to locally compact spaces X. For [X → L] to be continuous, it is secondly necessary for L to be a continuous domain, as L is a continuous retract of the function space. In order to see this, identify the elements of L with constant functions, choose a fixed element a ∈ X and evaluate all functions at a in order to obtain L as a retract of [X → L]. If we want [X → L] to be continuous for every locally compact space X, then L has to be a continuous L-domain; that is, a continuous domain in which every principal ideal is a lattice [1]. As L-domains are technically more involved, we first restrict our attention to bounded complete continuous domains; that is, continuous domains with least upper bounds of upper bounded subsets.

In summary, we shall consider function spaces [X → L] where X is a core compact space and L a bounded complete continuous domain.

In the first section we approach the way-below relation on these function spaces in terms of interpolating step functions. In the second section co-step functions are used instead. In the third section we present our main characterizations of the way-below relation. In the last section we show how to generalize the results to L-domains.

1 Step functions and the continuity of function spaces

Through the whole paper, X denotes a core compact space, O(X) the lattice of open subsets of X, and L a bounded complete continuous domain.

The set [X → L] of all continuous functions g : X → L is a bounded complete domain with respect to the pointwise order induced by L. For U ∈ O(X) and s ∈ L, the continuous map (U↘s): X → L defined by

(U↘s)(x) = \begin{cases}s & if x ∈ U, \\ ⊥ & otherwise. \end{cases}

is called a single-step function. A finite family (U_{i}↘s_{i}), i = 1, …, n, of single-step functions is bounded iff the set {s_{i} : x ∈ U_{i}} is bounded for each x ∈ X. A step function is a join of a bounded finite collection of single-step functions.

Lemma 1 The following conditions hold for all g ∈ [X → L]:

(a) For every U ∈ O(X) and every s ∈ L such that U ≪ g^{−1}(↑ ↑s), we have that (U↘s) ≪ g.

(b) For every finite family U_{i} ∈ O(X) and s_{i} ∈ L such that U_{i} ≪ g^{−1}(↑ ↑s_{i}) for i = 1, …, n, we have that ⋁_{i=1}^{n}(U_{i}↘s_{i}) ≪ g.

(c) g = ⋁{(U↘s) : U ≪ g^{−1}(↑ ↑s)}.

Proof: (a) Let U ∈ O(X) and s ∈ L with U ≪ g^{−1}(↑ ↑s), and let H be a directed subset of [X → L] with g ≤ ^{⋁↑} H. For every x ∈ g^{−1}(↑ ↑s), we then have that s ≪ g(x) ≤ ^{⋁↑}_{h∈H} h(x). Hence there is some h_{x} ∈ H with s ≪ h_{x}(x). Since x ∈ h_{x}^{−1}(↑ ↑s) and x is arbitrary, we have that g^{−1}(↑ ↑s) ⊆ ^{⋃↑}_{h∈H} h^{−1}(↑ ↑s). Since U ≪ g^{−1}(↑ ↑s), we conclude that U ⊆ h^{−1}(↑ ↑s) for some h ∈ H. If x ∈ U then (U↘s)(x) = s ≤ h(x). Otherwise (U↘s)(x) = ⊥ ≤ h(x). Therefore (U↘s) ≤ h.

(b) As the hypotheses imply that the family (U_{i}↘s_{i}) , i = 1, …, n, is bounded by g, it has a join. Since (U_{i}↘s_{i}) ≪ g for each i, by (a) we conclude that ⋁_{i=1}^{n}(U_{i}↘s_{i}) ≪ g.

(c) Since O(X) is a continuous lattice, s ≪ g(x) iff x ∈ g^{−1}(↑ ↑s) iff x ∈ U ≪ g^{−1}(↑ ↑s) for some U ∈ O(X). Therefore

⋁{(U↘s) : U ≪ g^{−1}(↑ ↑s)}(x) = ⋁{s : ∃U.x ∈ U ≪ g^{−1}(↑ ↑s)} = ⋁{s : s ≪ g(x)} = g(x),

because L is continuous.

Let S(g) be the set of step functions of the type considered in Lemma 1(b). Then f ≪ g for all f ∈ S(g) by Lemma 1(b), S(g) is directed, and g = ^{⋁↑} S(g) by Lemma 1(c). We have thus established

Proposition 2 [X → L] is a bounded complete continuous domain with a basis consisting of step functions.

The preceding proposition yields a first characterization of the way-below relation on function spaces via interpolating step functions:

Corollary 3 Let f, g ∈ [X → L]. Then f ≪ g iff there are finitely many U_{i} ∈ O(X), s_{i} ∈ L with U_{i} ≪ g^{−1}(↑ ↑s_{i}), for i = 1, …, n, such that f ≤ ⋁_{i=1}^{n}(U_{i}↘s_{i}).

The following consequence, unfortunately, is not sufficient to characterize the way-below relation on [X → L]:

Corollary 4 If f ≪ g then f(x) ≪ g(x) for all x ∈ X.

Proof: With the notation of the preceding corollary, we have that

f(x) ≤ ⋁_{i=1}^{n}(U_{i}↘s_{i})(x) = ⋁_{x∈U_{i}} s_{i}.

But x ∈ U_{i} implies s_{i} ≪ g(x). Therefore ⋁_{x∈U_{i}} s_{i} ≪ g(x).

While the preceding results are well-known [2] [1], the following is new. We are going to show that the converse of Lemma 1(a) does not hold in general. More precisely, we shall characterize those situations in which the converse of Lemma 1(a) holds. This is of interest because Corollary 3 reduces the characterization of the way-below relation to step functions. We first need two concepts.

A core-compact space X is called stable if U ≪ V and U ≪ V′ together imply U ≪ V ∩V′ for all U, V, V′ ∈ O(X). Note that, for locally compact sober spaces, stability is equivalent to coherence by [8, Prop. 1].

We call a poset L tree-like if it has a least element and if the principal ideals ↓x = {y ∈ L : y ≤ x}, x ∈ L, are chains. This condition is very strong. But note that all complete linearly ordered sets like the unit interval or the extended real line are tree-like.

Proposition 5 The condition

(U↘s) ≪ g implies U ≪ g^{−1}(↑ ↑s)

holds for all U ∈ O(X), s ∈ L \ {⊥} and g ∈ [X → L] if and only if X is stable or L is tree-like.

Proof: ‘If’: Let (U↘s) ≪ g with s ≠⊥. By Corollary 3, there are U_{i} ∈ O(X) and s_{i} ∈ L with U_{i} ≪ g^{−1}(↑ ↑s_{i}), i = 1, …, n and (U↘s) ≤ ⋁_{i=1}^{n}(U_{i}↘s_{i}) ≪ g. For each x ∈ U, let I_{x} = {i : x ∈ U_{i}} and V_{x} = ⋂_{i∈I_{x}} U_{i}. Then we have that

s = (U↘s)(x) ≤ ⋁_{i=1}^{n}(U_{i}↘s_{i})(x) = ⋁_{i∈I_{x}} s_{i}.

By definition, V_{x} ⊆ U_{i} ≪ g^{−1}(↑ ↑s_{i}) holds for any i ∈ I_{x}. Hence, if X is stable, we conclude that

V_{x} ≪ ⋂_{i∈I_{x}} g^{−1}(↑ ↑s_{i}) = g^{−1}( ⋂_{i∈I_{x}} ↑ ↑s_{i}) = g^{−1}(↑ ↑ ⋁_{i∈I_{x}} s_{i}) ⊆ g^{−1}(↑ ↑s).

If, on the other hand, the lower set ↓ ⋁_{i∈I_{x}} s_{i} is a chain, then there is an index i_{0} ∈ I_{x} such that s_{i_{0}} = ⋁_{i∈I_{x}} s_{i}, and again we conclude that

V_{x} ⊆ U_{i_{0}} ≪ g^{−1}(↑ ↑s_{i_{0}}) = g^{−1}(↑ ↑ ⋁_{i∈I_{x}} s_{i}) ⊆ g^{−1}(↑ ↑s).

Therefore g^{−1}(↑ ↑s) ≫ ⋃_{x∈U} V_{x} ⊇ U, because there are only finitely many distinct V_{x}.

‘Only if’: Assume that X is not stable and that L is not tree-like. Then there are U, V_{1}, V_{2} ∈ O(X) satisfying U ≪ V_{1}, V_{2} and U ≪̸ V_{1}∩V_{2}, and incomparable bounded elements b_{1}, b_{2} ∈ L. As L is bounded complete, the supremum b_{1} ∨ b_{2} exists. By continuity of L, there are c_{1} ≪ b_{1} and c_{2} ≪ b_{2} such that c := c_{1} ∨c_{2} is neither below b_{1} nor below b_{2} (but way-below b_{1} ∨ b_{2}, of course). This situation is illustrated in the following Hasse diagram:

b_{1} ∨ b_{2}
[figure]
b_{1} c_{1} ∨ c_{2} ‖  b_{2}
[figure]
c_{1} ‖  c_{2} ‖

Let g = (V_{1}↘b_{1}) ∨ (V_{2}↘b_{2}). Then

g^{−1}(↑ ↑c) = g^{−1}(↑ ↑(c_{1} ∨ c_{2})) = g^{−1}(↑(b_{1} ∨ b_{2})) = V_{1} ∩ V_{2} ≫̸ U.

We conclude the proof by showing that (U↘c) ≪ g. Let G ⊆ [X → L] be a directed set with g ≤ ^{⋁↑} G. Since suprema are calculated pointwise, for any x ∈ V_{1} there is a g_{x} ∈ G with g_{x}(x) ≫ c_{1}. By continuity of g_{x}, there is an open set U_{x} with g_{x}(U_{x}) ⊆ ↑ ↑c_{1}. Since V_{1} is covered by {U_{x} : x ∈ V_{1}} and U ≪ V_{1}, there is a finite subcover {U_{x_{1}}, …, U_{x_{n}}} of U. Let h_{1} ∈ G be an upper bound of {g_{x_{1}}, …, g_{x_{n}}}. For any y ∈ U ∩ U_{x_{i}} we have that

h_{1}(y) ≥ g_{x_{i}}(y) ∈ g_{x_{i}}(U_{x_{i}}) ⊆ ↑ ↑c_{1}

Hence h_{1}(U) ⊆ ↑ ↑c_{1}. In the same fashion we construct h_{2} ∈ G with h_{2}(U) ⊆ ↑ ↑c_{2}. Therefore any upper bound h ∈ G of h_{1} and h_{2} is above (U↘c), because h(U) ⊆ ↑ ↑c_{1} ∩ ↑ ↑c_{2} = ↑ ↑c.

2 Way-below via co-step functions

In Corollary 3 we established a characterization of the way-below relation via interpolating step functions. These step functions are continuous with respect to the given topology on X and the Scott topology on L. They correspond to lower semicontinuous step functions in classical analysis. Step functions of another type, corresponding to upper semicontinuous step functions in classical analysis, produce an elegant alternative characterization of the way-below relation.

Through this section we restrict ourselves to the case in which X is locally compact and sober. Notice that in the presence of sobriety, local compactness and core-compactness are equivalent conditions.

Let Q(X) denote the collection of compact saturated subsets of X. The co-compact topology of X is the topology generated by all complements of compact saturated sets. If X is coherent, these and the empty set are exactly the co-compact open sets.

In analogy to single-step functions, we define the function ⟨K↘t⟩: X → L by

⟨K↘t⟩(x) = \begin{cases}t & if x ∈ K, \\ ⊥ & otherwise, \end{cases}

for every K ∈ Q(X) and t ∈ L. The join of a bounded finite family of such functions exists if there is a function above them. We call ⋁_{i=1}^{n}⟨K_{i}↘t_{i}⟩ a co-step function. It is continuous with respect to the co-compact topologies on X and L.

Proposition 6 Let f, g ∈ [X → L]. Then f ≪ g if and only if there is a co-step function k such that f(x) ≤ k(x) ≪ g(x) for all x ∈ X.

Proof: ‘If’: Let k = ⋁_{i=1}^{n}⟨K_{i}↘t_{i}⟩ with K_{i} ∈ Q(X). Since k(x) ≪ g(x), we have that K_{i} ⊆ g^{−1}(↑ ↑t_{i}) = ⋃_{h≪g} h^{−1}(↑ ↑t_{i}). So we need only finitely many functions way-below g, say h_{i,1}, …, h_{i,n_{i}}, such that K_{i} ⊆ ⋃_{j=1}^{n_{i}} h_{i,j}^{−1}(↑ ↑t_{i}). Hence, the function ⟨K_{i}↘t_{i}⟩ is below ⋁_{j=1}^{n_{i}} h_{i,j}, and therefore f ≤ k ≤ ⋁_{i,j} h_{i,j} ≪ g, because the index set for the supremum is finite.

‘Only if’: There is a step function ⋁_{i=1}^{n}(U_{i}↘t_{i}) between f and g such that U_{i} ≪ g^{−1}(↑ ↑t_{i}) for each i. So we can choose K_{i} ∈ Q(X) such that U_{i} ⊆ K_{i} ⊆ g^{−1}(↑ ↑t_{i}). This yields (U_{i}↘t_{i})(x) ≤ ⟨K_{i}↘t_{i}⟩(x) ≪ g(x) for all x ∈ X. Hence, ⋁_{i=1}^{n}⟨K_{i}↘t_{i}⟩ is the desired function.

The following gives an application of the above characterization:

Proposition 7 Let X be a locally compact, compact and coherent space, let L and L′ be bounded complete continuous domains, and let f, g ∈ [X → L], and f′, g′ ∈ [L → L′]. If f ≪ g and f′ ≪ g′ then f′ ∘ f ≪ g′ ∘ g.

Proof: By Proposition 6, we obtain a co-step function k = ⋁_{i=1}^{n}⟨K_{i}↘t_{i}⟩ between f and g. By Corollary 4, f′ ≪ g′ implies f′(y) ≪ g′(y). Hence we have that for all x ∈ X,

f′(f(x)) ≤ f′(k(x)) ≪ g′(k(x)) ≤ g′(g(x)).

As we shall verify below, f′ ∘ k is a co-step function. Therefore f′ ∘ f ≪ g′ ∘ g by another application of Proposition 6.

For I ⊆ {1, …, n}, define K_{I} := ⋂_{i∈I} K_{i}, s_{I} := ⋁_{i∈I} t_{i} and I(x) := {i ∈ {1, …, n} : x ∈ K_{i}} for all x ∈ X. We shall show that

f′ ∘ k = ⋁_{y∈X}⟨K_{I(y)}↘f′(t_{I(y)})⟩, (1)

concluding f′ ∘ k is indeed a co-step function. Note that the sets K_{I} are compact, because X is a coherent and compact space (K_{∅} = X), and that the supremum in (1) is taken over a finite set. The functions f′ and I ↦ t_{I} are monotone, and so is I ↦ f′(t_{I}). Hence, we only need the largest I such that x ∈ K_{I} in order to evaluate the right hand side of (1) at the point x. This is I = I(x), therefore the right hand side at x equals f′(t_{I(x)}). By definition of k, this is (f′ ∘ k)(x).

3 Main characterizations of the way-below relation

We now approach the main result of this paper, consisting of three characterizations of the way-below relation on the function space [X → L]. Two of them reduce the way-below relation on the function space to the way-below relation on L, and the other reduces the way-below relation on the function space to the way-below relation on O(X).

The support of f ∈ [X → L] is defined to be the open set

supp f := {x ∈ X : f(x) ≠ ⊥}.

Notice that supp f ≪ X simply means that supp f is contained in a compact subset. The patch topology of X is the join of the original and the co-compact topology; that is, the collection O(X) ∪ {X \ Q : Q ∈ Q(X)} is a subbase for the patch open sets. The sets of the form V \ Q with V ∈ O(X) and Q ∈ Q(X) constitute a base for the patch open sets. More details can be found in [2, V.5.11 and VII.3.6] and [4, Sec. 4].

Theorem 8 Let X be a locally compact space and L be a bounded complete continuous domain. If X is coherent then the following statements are equivalent for all f, g ∈ [X → L]:

1. f ≪ g.

2. (a) supp f ≪ X and

(b) there are finitely many V_{i} ∈ O(X), Q_{i} ∈ Q(X), t_{i} ∈ L, for i = 1, …, n, such that

(i) t_{i} ≪ g(v) for all v ∈ V_{i}, (ii) f(w) ≤ t_{i} for all w ∉ Q_{i}, (iii) X = ⋃_{i=1}^{n} V_{i}\Q_{i}.

3. There are patch open sets W_{i} ⊆ X, t_{i} ∈ L, for i in some index set I, and Q ∈ Q(X) such that

(a) supp f ⊆ Q ⊆ ⋃_{i} W_{i},

(b) f(x) ≤ t_{i} ≪ g(x) for all x ∈ W_{i}.

4. There exist V_{i} ∈ O(X), Q_{i} ∈ Q(X) and t_{i} ∈ L, i = 1, …, n, such that

(a) V_{i} ≪ g^{−1}(↑ ↑t_{i})

(b) f(x) ≤ t_{i} for all x ∉ Q_{i}

(c) supp f ⊆ ⋃_{i=1}^{n} V_{i} \ Q_{i}.

If X is just sober then the implications (4) ⇒ (1) ⇒ (2) ⇒ (3) hold.

Proof: Condition (2) implies (3), because W_{i} := V_{i} \ Q_{i}, i = 1, …, n, is a patch open cover of X. The implications (1)⇒(2), (3)⇒(1), (2)⇒(4) and (4)⇒(1) will be established in Lemmas 9, 12, 13 and 14, respectively.

In the following, f and g are arbitrary members of [X → L]. As a shorthand, we write f ≪_{2} g, f ≪_{3} g, or f ≪_{4} g if statement (2), (3) or (4) of the theorem above is satisfied respectively.

Lemma 9 f ≪ g implies f ≪_{2} g.

Proof: By proposition 6, there is a co-step function k = ⋁_{j=1}^{m}⟨K_{j}↘s_{j}⟩ above f and pointwise way-below g. This yields condition 2(a) of Theorem 8, because supp f ⊆ ⋃_{j=1}^{m} K_{j}. We now construct V_{x} ∈ O(X), Q_{x} ∈ Q(X) and t_{x} ∈ L, for each x ∈ X, in such a way that condition 2(b) holds and the set {(V_{x}, Q_{x}, t_{x}) : x ∈ X} is finite. Let t_{x} = k(x) and V_{x} = g^{−1}(↑ ↑t_{x}). It is clear that V_{x} is a neighbourhood of x such that condition 2(b)(i) holds. Let Q_{x} = ⋃_{x∉K_{j}} K_{i}. Since x ∉ Q_{x}, item 2(b)(iii) also holds. In order to see that 2(b)(ii) holds, notice that if w ∉ Q_{x} then w ∈ K_{j} implies x ∈ K_{j}. Hence w ∉ Q_{x} implies

f(w) ≤ k(w) = ⋁_{w∈K_{j}} s_{j} ≤ ⋁_{x∈K_{j}} s_{j} = k(x) = t_{x} . (2)

Therefore condition 2(b) holds.

Without the assumption of coherence, counterexamples to the converse of Lemma 9 exist even if L is almost trivial:

Remark 10 If X contains an open set which is not compact and which is the intersection of a finite non-empty family of compact saturated sets, and if L has more than one element, then there are functions f, g ∈ [X → L] satisfying f ≪_{2} g but not f ≪ g.

Proof: Let O be open, not compact, and O = ⋂_{i=2}^{n} Q_{i} for Q_{i} ∈ Q(X). Take a, b ∈ L with ⊥< b ≪ a. The functions g := (O↘a) and f := (O↘b) satisfy f ≪_{2} g, because we can take V_{1} = O, Q_{1} = ∅, t_{1} = b and V_{i} = X, t_{i} =⊥, for i = 2, …, n. Since O is not compact, there is a directed family {O_{j}}_{j} of open proper subsets of O covering O. Therefore we have that g = (O↘a) = ⋁_{j}(O_{j}↘a) and (O_{j}↘a) ≱ (O↘b) = f, contradicting f ≪ g.

Example 11 Let X = ℕ ∪ {a_{1}, a_{2}, ⊥} be partially ordered by ⊥< a_{i} < n, for i = 1, 2 and n ∈ ℕ. Then X fulfills the conditions of Remark 10, as one sees by taking Q_{i} = ↑a_{i}, for i = 1, 2, and O = ℕ.

Lemma 12 If X is coherent then f ≪_{3} g implies f ≪ g.

Proof: We may assume that every W_{i} in condition (3) of Theorem 8 is a non-empty basic patch open set W_{i} = V_{i} \ Q_{i} with V_{i} ∈ O(X) and Q_{i} ∈ Q(X). Since t_{i} ≪ g(x) for all x ∈ W_{i}, we have that W_{i} ⊆ V_{i} ∩ g^{−1}(↑ ↑t_{i}). And since for every x ∈ W_{i} we can choose a V_{i,x} ∈ O(X) such that x ∈ V_{i,x} ≪ V_{i} ∩ g^{−1}(↑ ↑t_{i}), we have that W_{i} = ⋃_{x∈W_{i}} V_{i,x} \ Q_{i} and V_{i,x} ≪ g^{−1}(↑ ↑t_{i}). Moreover, since any compact saturated subset of a coherent space is patch compact [8], we need only finitely many of the patch open sets V_{i,x} \ Q_{i}, say V_{i_{k},x_{k}} \ Q_{i_{k}} with k = 1, …, n, to cover Q ⊇ supp f. If x ∈ V_{i_{k},x_{k}} \ Q_{i_{k}} then f(x) ≤ t_{i_{k}}. Therefore we have a step function

f ≤ ⋁_{k=1}^{n}(V_{i_{k},x_{k}}↘t_{i_{k}})

which is way-below g by Lemma 1(b).

Lemma 13 If X is coherent then f ≪_{2} g implies f ≪_{4} g.

Proof: Let W_{i} = V_{i} \ Q_{i} and copy literally step 2 and 3 of the proof of Lemma 12. This does not change the Q_{i}’s, and so the condition f(x) ≤ t_{i} for all x ∉ Q_{i} still holds.

Lemma 14 f ≪_{4} g implies f ≪ g.

Proof: Let V_{i}, Q_{i} and t_{i}, i = 1, …, n as in statement (4) of Theorem 8. By Lemma 1(b), the step function s := ⋁_{i=1}^{n}(V_{i}↘t_{i}) is way-below g. If x ∈ supp f then there is an i_{0} such that x ∈ V_{i_{0}} \ Q_{i_{0}}. This implies that f(x) ≤ t_{i_{0}} ≤ s(x). Therefore f ≤ s ≪ g.

This concludes the proof of Theorem 8.

A continuous function h: Y → X between locally compact spaces is defined to be proper if h^{−1}(Q) is compact for every Q ∈ Q(X) (see [3]). The following generalizes Corollary 4:

Corollary 15 Let Y be locally compact and coherent, and let h ∈ [Y → X] be a proper map. Then f ≪ g implies f ∘ h ≪ g ∘ h.

Proof: Let W_{i}, t_{i} and Q be as in Theorem 8 (3) and let P_{i} = h^{−1}(W_{i}). This yields (f ∘ h)(y) ≤ t_{i} ≪ (g ∘ h)(y) for all y ∈ P_{i}. We have that

supp(f ∘ h) = h^{−1}(supp f) ⊆ h^{−1}(Q) ⊆ h^{−1}(⋃_{i} W_{i}) = ⋃_{i} P_{i}.

Also, the set h^{−1}(Q) is compact saturated because h is proper. Since proper maps are patch continuous, the sets P_{i} are patch open. Therefore statement (3) of Theorem 8 holds.

The following is a complement to Theorem 8:

Proposition 16 The condition

f ≪ g implies f ≪_{4} g

holds for all f, g ∈ [X → L] if and only if X is coherent or L is tree-like.

Proof: ‘If’: By Theorem 8, we only need to consider the case of tree-like L. If f′ ≪ g then there is a step function f satisfying f′ ≤ f ≪ g. In order to establish f′ ≪_{4} g, it is enough to show that f ≪_{4} g. By definition of step function, f(X) is a finite set and O_{t} := f^{−1}(↑t) is open for each t ∈ f(X). Also, we have that

(O_{t}↘t) ≤ ⋁_{s∈f(X)}(O_{s}↘s) = f ≪ g

for each t ∈ f(X). By Proposition 5, O_{t} ≪ g^{−1}(↑ ↑t) follows. Hence, there are K_{t} ∈ Q(X) and U_{t} ∈ O(X) for each t ∈ f(X) with

O_{t} ⊆ K_{t} ⊆ U_{t} ≪ g^{−1}(↑ ↑t).

Let Q_{t} = ⋃{K_{s} : s ≰ t, s ∈ f(X)} for each t ∈ f(X). Then we have that Q_{t} ∈ Q(X), U_{t} ≪ g^{−1}(↑ ↑t), and f(x) ≤ t for each t ∈ f(X) and each x ∉ Q_{t}.

We claim that supp f ⊆ ⋃_{t∈f(X)} U_{t} \ Q_{t}. Since L is tree-like, s ≰ t implies that either s > t or {s, t} is unbounded. The sets g^{−1}(↑ ↑s) and g^{−1}(↑ ↑t) are disjoint in the latter case. Hence U_{t} ∩ K_{s} = ∅. We thus conclude that

U_{t} \ Q_{t} = U_{t} \ ⋃{K_{r} : r > t, r ∈ f(X)}
⊇ U_{t} \ ⋃{U_{r} : r > t, r ∈ f(X)} =: Ũ_{t}

for each t ∈ f(X). If t is maximal in f(X) then Ũ_{t} equals U_{t}. By order induction, ⋃{Ũ_{r} : r ≥ t, r ∈ f(X)} = ⋃{U_{r} : r ≥ t, r ∈ f(X)} for each t ∈ f(X). Therefore supp f is covered by the sets Ũ_{t}, and so it is also covered by the sets U_{t} \ Q_{t}.

‘Only if’: Assume that neither L is tree-like and nor X is coherent. As mentioned just before Proposition 5, the latter implies that X is not stable. By Proposition 5, there are g ∈ [X → L], U ∈ O(X) and s ∈ L satisfying (U↘s) ≪ g and U ≪̸ g^{−1}(↑ ↑s).

Assume that (U↘s) ≪_{4} g, and let U_{i} ∈ O(X), Q_{i} ∈ Q(X), and t_{i} ∈ L, i = 1, …, n, as in the definition of ≪_{4}. Thus, for each x ∈ U there is an index i_{x} such that x ∈ U_{i_{x}} \ Q_{i_{x}}. Hence

s = (U↘s)(x) ≤ t_{i_{x}} and g^{−1}(↑ ↑t_{i_{x}}) ≫ U_{i_{x}}.

This yields g^{−1}(↑ ↑s) ⊇ g^{−1}(↑ ↑t_{i_{x}}) ≫ U_{i_{x}}. Since the set {i_{x} : x ∈ U} is finite, it follows that g^{−1}(↑ ↑s) ≫ ⋃_{x∈U} U_{i_{x}} ⊇ U, a contradiction to the choice of g, U, and s.

4 Generalization to L-domains

The main results established so far remain true if we generalize the bounded complete continuous domain L to a continuous L-domain with a least element. Recall that an L-domain is a directed complete poset in which every principal ideal ↓a is a complete lattice. In this section we sketch the necessary modifications.

The cost of the generalization is at least the burden of bookkeeping where suprema are calculated. If L is an L-domain and a is an upper bound of M ⊆ L, then ^{⋁a} M denotes the supremum of M in the lattice ↓a. In particular, if (U_{i}↘s_{i}), i = 1, …, n, are single-step functions below g ∈ [X → L], then their supremum in ↓g is written ^{⋁g}_{i=1,...,n}(U_{i}↘s_{i}) and it is given by

\begin{matrix}⋁ & g \\ i=1,...,n \end{matrix}(U_{i}↘s_{i})(x) =\begin{matrix}⋁ & g(x) \\ x∈U_{i} \end{matrix} s_{i}.

In the following, L will be a continuous L-domain, X a locally compact sober space, and f and g arbitrary members of [X → L].

Proposition 17 [X → L] is a continuous L-domain with a base consisting of step functions.

Proof: Just add the label ‘g’ or ‘g(x)’ to the supremum signs in the proofs leading to Proposition 2.

Proposition 18 f ≪ g in the function space [X → L] if and only if there is a co-step function k with f(x) ≤ k(x) ≪ g(x) for all x ∈ X.

The only non-trivial modification in the proof of Theorem 8 lies in Lemma 9. In order to illustrate this, let us consider the poset of Example 11. If L is this poset then L is an L-domain whose identity function id: L → L is a compact element in the function space and therefore a supremum of finitely many step functions:

id =\begin{matrix}⋁ & id \\ i=1,2 \end{matrix}(↑a_{i}↘a_{i}).

Note that this is an example of a step function having an infinite image. Fortunately, this space is not coherent, and so it is ruled out by the conditions of the theorem. A second (unavoidable) complication is that inequality (2) in the proof of Lemma 9 is not true for L-domains: the supremum on the left would be calculated in ↓g(w) while the one on the right would be below g(x), and there is no reason why they should be comparable. We thus need a more subtle argumentation.

Lemma 19 Let a and b be upper bounds of a subset M of L. If ^{⋁a} M and ^{⋁b} M have an upper bound then they are equal.

Lemma 20 If X is coherent then f ≪ g implies f ≪_{2} g.

Proof: This is a refinement of the proof of Lemma 9. By Proposition 18, we can find a co-step function k = ^{⋁g}_{i=1,...,n}⟨K_{i}↘s_{i}⟩ such that f(x) ≤ k(x) ≪ g(x) for all x ∈ X. For each y ∈ X, the set g^{−1}(↑ ↑k(y)) is a neighbourhood of y. Since X is locally compact, we can choose B_{y} ∈ O(X) and C_{y} ∈ Q(X) such that y ∈ B_{y} ⊆ C_{y} ⊆ g^{−1}(↑ ↑k(y)). Let I(z) = {i ∈ {1, …, n} : z ∈ K_{i}} and K_{I} = ⋂_{i∈I} K_{i}. We first assume that X is compact. In this case the set K_{I}, for I ⊆ {1, …, n}, is compact because X is coherent. Hence, there are finitely many elements of K_{I}, say y_{1}^{I}, …, y_{m}^{I}, such that ⋃_{j=1}^{m} B_{y_{j}^{I}} covers K_{I}. For each z ∈ X, choose

γ(z) ∈ {y_{1}^{I(z)}, …, y_{m}^{I(z)}}

such that z ∈ B_{γ(z)}. This defines a function γ: X → X satisfying I(γ(z)) ⊇ I(z). Note that {I(z) : z ∈ X} and {γ(z) : z ∈ X} are finite sets. Let t_{x} = k(γ(x)), V_{x} = B_{γ(x)}, and

Q_{x} = ⋃_{i∉I(x)} K_{i} ∪ ⋃{C_{γ(z)} : x ∉ C_{γ(z)}, z ∈ X}.

We claim that f(w) ≤ t_{x} if w ∉ Q_{x}. In order to prove this, we show that k(x) ≤ k(γ(x)) and then that k(w) ≤ k(x). Since I(x) ⊆ I(γ(x)) and x ∈ B_{γ(x)} ⊆ g^{−1}(↑ ↑k(γ(x))),

\begin{matrix}⋁ & g(x) \\ i∈I(x) \end{matrix} s_{i} = k(x) ≤ g(x)

and

\begin{matrix}⋁ & g(γ(x)) \\ i∈I(x) \end{matrix} s_{i} ≤ \begin{matrix}⋁ & g(γ(x)) \\ i∈I(γ(x)) \end{matrix} s_{i} = k(γ(x)) ≤ g(x).

By Lemma 19, the leftmost terms of the inequalities are identical and we thus have that k(x) ≤ k(γ(x)). By definition of Q_{x}, we have that x ∈ C_{γ(w)} and I(w) ⊆ I(x). This implies that

\begin{matrix}⋁ & g(w) \\ i∈I(w) \end{matrix} s_{i} = k(w) ≤ k(γ(w)) ≤ g(x)

and

\begin{matrix}⋁ & g(x) \\ i∈I(w) \end{matrix} s_{i} ≤\begin{matrix}⋁ & g(x) \\ i∈I(x) \end{matrix} s_{i} = k(x) ≤ g(x).

Again, both suprema (of {s_{i} : i ∈ I(w)}) are equal, and therefore k(w) ≤ k(x).

If X is not compact then there is a ŷ such that I(ŷ) = ∅ and k(ŷ) =⊥. Let Bŷ = Cŷ = X and γ(u) = ŷ for each u ∉ ⋃_{i=1}^{n} K_{i}. Since Cŷ is not used to built any Q_{x}, the above argument goes through with the constructions extended in this way.

Theorem 21 Theorem 8 generalizes from bounded complete continuous domains to continuous L-domains.

Acknowledgements

This research was supported by the British Council and the DAAD through a joint ARCgrant.

References

[1] S. Abramsky and A. Jung. Domain theory. In S. Abramsky, D. M. Gabbay, and T. S. E. Maibaum, editors, Handbook of Logic in Computer Science, volume 3, pages 1–168. Clarendon Press, 1994.

[2] G. Gierz, K. H. Hofmann, K. Keimel, J. D. Lawson, M. Mislove, and D. S. Scott. A Compendium of Continuous Lattices. Springer Verlag, Berlin, 1980.

[3] K. H. Hofmann and J. Lawson. The Spectral Theory of Distributive Continuous Lattices. Transitions of the American Mathematical Society, 246:285–310, 1978.

[4] K. H. Hofmann and M. Mislove. Local compactness and continuous lattices. In B. Banaschewski and R.-E. Hoffmann, editors, Continuous Lattices, Proceedings Bremen 1979, volume 871 of Lecture Notes in Mathematics, pages 209–248. Springer Verlag, 1981.

[5] C. Jones. Probabilistic non-determinism. PhD thesis, Department of Computer Science, University of Edinburgh, Edinburgh, 1990. 201pp.

[6] C. Jones and G. Plotkin. A probabilistic powerdomain of evaluations. In Logic in Computer Science, pages 186–195. IEEE Computer Society Press, 1989.

[7] D. S. Scott. Continuous lattices. In E. Lawvere, editor, Toposes, Algebraic Geometry and Logic, volume 274 of Lecture Notes in Mathematics, pages 97–136. Springer Verlag, 1972.

[8] M. B. Smyth. Stable compactification I. Journal of the London Mathematical Society, 45:321–340, 1992.