{"id":1102,"date":"2017-01-12T14:07:52","date_gmt":"2017-01-12T13:07:52","guid":{"rendered":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=1102"},"modified":"2022-11-19T15:22:34","modified_gmt":"2022-11-19T14:22:34","slug":"pointwise-directed-families-of-maps","status":"publish","type":"page","link":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=1102","title":{"rendered":"Pointwise directed families of maps"},"content":{"rendered":"

First, a Happy New Year 2017!<\/p>\n

Today I would like to comment on a paper by Jimmie Lawson and Xiaoyong Xi [1], which explores a funny idea, due to X. Xi.\u00a0 What is really funny is that nobody seems to have ever thought of it before.\u00a0 I must admit that if I had had the same idea, I would probably have not known what to do with it, but they do something clever with it.<\/p>\n

Dcpos of functions<\/h2>\n

A central problem of domain theory is to explore the structure of the dcpo [X<\/em> \u2192 Y<\/em>] of all Scott-continuous maps from a topological space X<\/em> to a dcpo Y<\/em>.\u00a0 Notably, to interpret the semantics of higher-order programs, a typical question is to find a category C<\/strong> of dcpos that is Cartesian-closed, and that boils down to requiring that [X<\/em> \u2192 Y<\/em>] is an object of C<\/strong> for all objects X<\/em> and Y<\/em> of C<\/strong>.<\/p>\n

We have plenty of results in that line.\u00a0 The categories of continuous lattices, of bc-domains, of FS<\/strong>-domains, of RB<\/strong>-domains, of L<\/strong>-domains, are Cartesian-closed.\u00a0 To take a more particular example, in the case of bc-domains, [X<\/em> \u2192 Y<\/em>] is a bc-domain provided Y<\/em> is a bc-domain, but we do not need X<\/em> to be a bc-domain for that, and it is enough that X<\/em>\u00a0 be a core-compact space (see [2, Proposition 2], an improvement over Proposition 5.7.13 in the book<\/a>, which requires X<\/em> to be core-coherent as well).<\/p>\n

In most of those kinds of results, we show that [X<\/em> \u2192 Y<\/em>] has a basis of step functions.\u00a0 What Lawson and Xi show is that we can take something that is more sophisticated.<\/p>\n

Let me remind you what a step function is.\u00a0 We assume that Y<\/em> has a least element \u22a5.\u00a0 An elementary step function<\/em> U<\/em> ↘ y<\/em> maps every element of the open set U<\/em> to y<\/em>, and all other elements to \u22a5.\u00a0 This is always a continuous map.\u00a0 A step function<\/em> is any pointwise supremum of elementary step function, provided such a pointwise supremum exists.\u00a0 This is again a continuous map.<\/p>\n

Pointwise directed suprema<\/h2>\n

The starting point of [1] is that [X<\/em> \u2192 Y<\/em>] is not just a dcpo, i.e., it is not just closed under suprema of directed families of maps, it is also closed under pointwise suprema of families of maps that are pointwise<\/em> directed.<\/p>\n

The difference may not be obvious, so let me illustrate.<\/p>\n

A family (fi<\/sub><\/em>)i \u2208 I<\/sub><\/em> is pointwise directed<\/em> if and only if, for every point x \u2208 X<\/em>, the family (fi<\/sub><\/em>(x<\/em>))i \u2208 I<\/sub><\/em> is directed. This means that I<\/em> is not empty and, for every x<\/em>, for all i, j<\/em> in I<\/em>, there is a k<\/em>\u2208I<\/em> such that fi<\/sub><\/em>(x<\/em>),\u00a0fj<\/sub><\/em>(x<\/em>) \u2264 fk<\/sub><\/em>(x<\/em>).<\/p>\n

The important point is that k<\/em> may depend on<\/em> x<\/em>.\u00a0 If (fi<\/sub><\/em>)i \u2208 I<\/sub><\/em> were directed in the usual sense, then k<\/em> should be the same for every x<\/em> in X<\/em>.<\/p>\n

Every directed family of maps is pointwise directed, but the converse is wrong.\u00a0 For example, consider any<\/em> family of continuous maps from X<\/em> to [0, 1], with its usual ordering.\u00a0 This family is pointwise directed, because any<\/em> family of reals is directed, in particular (fi<\/sub><\/em>(x<\/em>))i \u2208 I<\/sub><\/em>.\u00a0 Take, say, X<\/em> to be the trivial dcpo Z<\/strong> of all non-positive integers with equality as ordering (i.e., no two distinct elements are comparable), I<\/em> to be Z<\/strong> itself, and define\u00a0fi<\/sub><\/em>(x<\/em>) as 1 if x<\/em>=i<\/em>, 0 otherwise.\u00a0 As we have noticed, since every family of reals is directed,\u00a0(fi<\/sub><\/em>)i \u2208 I<\/sub><\/em> is pointwise directed.\u00a0 It is certainly not directed in the usual sense, because all the maps\u00a0fi<\/sub><\/em> are incomparable.<\/p>\n

As I have said earlier, [X<\/em> \u2192 Y<\/em>] is more than just a dcpo.\u00a0 It is closed under suprema of pointwise directed families, not just directed families.<\/p>\n

Lemma [1, Lemma 3.2].<\/strong> Let X<\/em> be a topological space, and Y<\/em> be a dcpo.\u00a0\u00a0 For every pointwise directed family of continuous maps (fi<\/sub><\/em>)i \u2208 I<\/sub><\/em> from X<\/em> to Y<\/em>, its pointwise supremum (the function that maps each x<\/em> of X<\/em> to supi \u2208 I<\/sub><\/em> fi<\/sub><\/em>(x<\/em>)) is continuous, hence is the supremum (in the usual, lattice-theoretic sense: the least of the upper bounds) of (fi<\/sub><\/em>)i \u2208 I<\/sub><\/em>.<\/p>\n

Proof.<\/em> Let f<\/em>(x<\/em>)=supi \u2208 I<\/sub><\/em> fi<\/sub><\/em>(x<\/em>), for every x<\/em> in X<\/em>.\u00a0 Let V<\/em> be an arbitrary open subset of Y<\/em>, and x<\/em> \u2208 f<\/em>-1<\/sup>(V<\/em>).\u00a0 Since V<\/em> is Scott-open, and f<\/em>(x<\/em>) is in V<\/em>, fi<\/sub><\/em>(x<\/em>) is in V<\/em> for some i<\/em> in I<\/em>.\u00a0 Then fi<\/sub><\/em>-1<\/sup>(V<\/em>) is an open neighborhood of x<\/em>, and it is easy to see that it is included in f<\/em>-1<\/sup>(V<\/em>).\u00a0 Therefore f<\/em>-1<\/sup>(V<\/em>) is a neighborhood of each of its points, hence is itself open.\u00a0 \u2610<\/p>\n

Step functions<\/h2>\n

Following Proposition 5.7.13 of the book<\/a>, say that a step function \u22c1j<\/sub><\/em> (Uj<\/sub><\/em> ↘ yj<\/sub><\/em>) is far below<\/em> a continuous map f<\/em> if and only if Uj<\/sub><\/em> is way-below f<\/em>-1<\/sup>(\u219fyj<\/sub><\/em>) for every j<\/em>.\u00a0 Step functions far below f<\/em> are automatically way-below f<\/em>, when X<\/em> is core-coherent (Lemma 5.7.12).\u00a0 Lawson and Xi call those (or a very close notion) approximating step functions.<\/p>\n

Proposition 5.7.13 of the book<\/a> states that if X<\/em> is core-compact and core-coherent, and if Y<\/em> is a bc-domain, then [X<\/em> \u2192 Y<\/em>] is a continuous dcpo, and that every continuous map is the supremum of a directed family of step functions far below it.\u00a0 Proposition 5.7.14 further states that [X<\/em> \u2192 Y<\/em>] is then a bc-domain.<\/p>\n

The proof of Proposition 5.7.13 shows that if X<\/em> is core-compact and core-coherent, but Y<\/em> is only a continuous dcpo with bottom \u22a5, then every continuous map is the supremum of a family of step functions far below it.\u00a0 The only reason why we require Y<\/em> to be a bc-domain in Proposition 5.7.13 is to make sure that that family of step functions is directed<\/em>.<\/p>\n

Allowing ourselves to consider pointwise directed<\/em> families of step functions, we can hope to obtain better results, or at least different results.\u00a0 Lawson and Xi achieve that by replacing step functions by pointwise suprema of finite pointwise directed families of elementary step functions.<\/p>\n

The main theorem\u2014to me\u2014 of [1] reads:<\/p>\n

Theorem [1, Corollary 4.3].<\/strong> Let X<\/em> be core-compact and core-coherent, and Y<\/em> be an RB<\/strong>-domain.\u00a0 Assume that Y<\/em> has a bottom.\u00a0 Then [X<\/em> \u2192 Y<\/em>] is a continuous dcpo.<\/p>\n

(The conclusion also holds if instead of requiring Y<\/em> to have a bottom, we require X<\/em> to be compact.)\u00a0 The plan of the proof is by successive reductions:<\/p>\n

    \n
  1. If Y<\/em> is a Scott-continuous retract of a bifinite domain Z<\/em>, then [X<\/em> \u2192 Y<\/em>] is a Scott-continuous retract of [X<\/em> \u2192 Z<\/em>]: let\u00a0r<\/em>:Z\u00a0\u2192 Y<\/em>, be the retraction, with section s<\/em>, then\u00a0r<\/em> o _ :\u00a0[X<\/em> \u2192 Z<\/em>] \u2192<\/em> [X<\/em> \u2192 Y<\/em>] is a retraction, with section s<\/em> o _.\u00a0 Since a retract of a continuous dcpo is a continuous dcpo, it suffices to show the theorem, assuming that Y<\/em> is a bifinite domain (with bottom).<\/li>\n
  2. If Y<\/em> is a bifinite domain, that is, a limit in Top<\/strong> of an ep-system of finite T0<\/sub> spaces Yj<\/sub><\/em> (i.e., of finite posets), then [X<\/em> \u2192 Y<\/em>] is the limit of a corresponding ep-system of spaces [X<\/em> \u2192 Yj<\/sub><\/em>].\u00a0 Since (projective) limits of ep-systems of continuous dcpos are continuous dcpos (with a basis given by the elements of the inductive limit in Top<\/strong>; to prove it, start from Lemma 9.6.7 in the book<\/a>, then imitate subsequent developments), it suffices to show the theorem, assuming that Y<\/em> is a finite poset.<\/li>\n<\/ol>\n

    Lawson and Xi do not literally proceed that way, but this is really what is at work here.\u00a0 At any rate, the crux of the argument is to look at the case where Y<\/em> is finite, with a bottom element.<\/p>\n

    What they do, then, is to show that, assuming X<\/em> core-compact and core-coherent, and Y<\/em> finite with a bottom, then [X<\/em> \u2192 Y<\/em>] is a continuous dcpo.<\/p>\n

    However, the basis they use is not given by step functions \u2014 try even to define them here! \u2014 rather by pointwise directed suprema<\/em> of finite families of elementary step functions.<\/p>\n

    Constructing a basis of finite pointwise directed suprema of elementary step functions<\/h2>\n

    This is the most technical part of their work.\u00a0 In the bc-domain case, we could take finitely many elementary step functions, Uj<\/sub><\/em> ↘ yj<\/sub><\/em>, far below f<\/em>, take their pointwise supremum, and that was again a (step) function far below f<\/em>.\u00a0 In our case, such suprema do not exist in general, since Y<\/em> is an arbitrary poset with bottom, not a semi-lattice.<\/p>\n

    Instead, following Lawson and Xi, we shall complete any finite family F<\/em> of elementary step functions far below f<\/em> to obtain a larger family F’<\/em> of elementary step functions, still far below f<\/em>, in such a way that F’<\/em> is pointwise directed<\/em>.\u00a0 (Moreover, F’<\/em> will be finite, too.)<\/p>\n

    Their pointwise supremum sup F’<\/em> will then exist: this is precisely the reason why we need F’<\/em> to be pointwise directed.\u00a0 sup F’<\/em> will also be continuous, and we observe that it will be way-below f<\/em>:<\/p>\n

    Lemma.<\/strong> For every finite pointwise directed family F’<\/em> of continuous maps way-below f<\/em>, sup F’<\/em> is also way-below f<\/em>.<\/p>\n

    Proof.<\/em> Let (gi<\/sub><\/em>)i \u2208 I<\/sub><\/em> be a directed family of continuous maps with supremum g<\/em> above f<\/em>.\u00a0 For every f’<\/em> in F’<\/em>, since f’<\/em> is way-below f<\/em>, f’<\/em> \u2264\u00a0gi<\/sub><\/em> for some i<\/em> in I<\/em>.\u00a0 Since (gi<\/sub><\/em>)i \u2208 I<\/sub><\/em> is directed, and F’<\/em> is finite, we may take the same i<\/em> for all f’<\/em> in F’<\/em>.\u00a0 Then, for every x<\/em> in X<\/em>, sup\u00a0F’<\/em> (x<\/em>) \u2264\u00a0gi<\/sub><\/em> (x<\/em>).\u00a0 \u2610<\/p>\n

    The case of two elementary step functions.<\/h3>\n

    To build the family F’<\/em> from F<\/em>, we first consider the case of just two elementary step functions far below f<\/em>, U<\/em> ↘ y<\/em> and V<\/em> ↘ z<\/em>.<\/p>\n

    If U<\/em> and V<\/em> have empty intersection, then {U<\/em> ↘ y<\/em>, V<\/em> ↘ z<\/em>} is already pointwise directed, since at each point x<\/em> one of the two functions is equal to \u22a5.\u00a0 If y<\/em> and z<\/em> are comparable (y<\/em>\u2264z<\/em> or z<\/em>\u2264y<\/em>) then \u22a5, y<\/em>, z<\/em> form a chain and again {U<\/em> ↘ y<\/em>, V<\/em> ↘ z<\/em>} is pointwise directed.<\/p>\n

    So the only interesting case is when U<\/em> and V<\/em> intersect and y<\/em> and z<\/em> are incomparable.\u00a0 Say that {U<\/em> ↘ y<\/em>, V<\/em> ↘ z<\/em>} is a critical pair<\/em> in that case.<\/p>\n

    We look at all upper bounds of {y<\/em>, z<\/em>} in Y<\/em>.\u00a0 Since Y<\/em> is finite, some of these upper bounds are minimal, and we naturally call them the minimal upper bounds<\/em> of {y<\/em>, z<\/em>}.\u00a0 There are only finitely many of them, since Y<\/em> is finite.<\/p>\n

    Define a lift<\/em> of {U<\/em> ↘ y<\/em>, V<\/em> ↘ z<\/em>} as any elementary step function W<\/em> ↘ t<\/em> far below f<\/em> such that t<\/em> is a minimal upper bound of {y<\/em>, z<\/em>}, and W<\/em> is non-empty.\u00a0 (Lawson and Xi already require that W<\/em> intersects U<\/em> \u2229 V<\/em>, but that is unnecessary.)\u00a0 A finite family of lifts Wi<\/sub><\/em> ↘ ti<\/sub><\/em> of {U<\/em> ↘ y<\/em>, V<\/em> ↘ z<\/em>} is a covering<\/em> of {U<\/em> ↘ y<\/em>, V<\/em> ↘ z<\/em>} if and only if the union of the open sets Wi<\/sub><\/em> contains U<\/em> \u2229 V<\/em>.<\/p>\n

    Lemma [1, Lemma 3.6].<\/strong> Let X<\/em> be core-compact and core-coherent.\u00a0 Every critical pair of elementary step functions far below f<\/em>, U<\/em> ↘ y<\/em> and V<\/em> ↘ z<\/em>, has a covering Wi<\/sub><\/em> ↘ ti<\/sub><\/em>, 1\u2264i<\/em>\u2264m<\/em>.\u00a0 Moreover the elements\u00a0ti<\/sub><\/em> are exactly the minimal upper bounds of {y<\/em>, z<\/em>}.<\/p>\n

    Proof.<\/em> From the definition of far below, U<\/em>\u00a0\u22d0 f<\/em>-1<\/sup>(\u219fy<\/em>), that is, U<\/em>\u00a0\u22d0 f<\/em>-1<\/sup>(\u2191y<\/em>), since \u226a and \u2264 coincide on a finite poset. Similarly, V<\/em> \u22d0 f<\/em>-1<\/sup>(\u2191z<\/em>).\u00a0 By core-coherence, U<\/em> \u2229 V<\/em> \u22d0 f<\/em>-1<\/sup>(\u2191y<\/em>) \u2229\u00a0f<\/em>-1<\/sup>(\u2191z<\/em>) = f<\/em>-1<\/sup>(\u2191y<\/em> \u2229 \u2191z<\/em>) = \u222at<\/sub><\/em> f-1<\/sup>(\u2191t<\/em>), where t<\/em> enumerates the minimal upper bounds of {y<\/em>, z<\/em>}.\u00a0 Union is trivially a Scott-continuous operation on O<\/strong>(X<\/em>), and O<\/strong>(X<\/em>) is a continuous poset since X<\/em> is core-compact.\u00a0 Proposition 5.1.66 of the book<\/a> says that every Scott-continuous map on a continuous poset reflects the way-below relation.\u00a0 The way-below relation is\u00a0\u22d0 here.\u00a0 That union reflects way-below means that if A<\/em>\u00a0\u22d0 \u222at<\/sub> Bt<\/sub>,<\/em> where A<\/em> and\u00a0Bt<\/sub><\/em> are open, then there are open subsets Wt<\/sub><\/em> \u22d0 Bt<\/sub><\/em> such that A<\/em> \u2286 \u222at<\/sub> Wt<\/sub><\/em>.\u00a0 We apply this to A<\/em>=U<\/em> \u2229 V<\/em> and to Bt<\/sub><\/em>=f-1<\/sup>(\u2191t<\/em>), remove the indices t<\/em> for which\u00a0Wt<\/sub><\/em> is empty, and we are done.\u00a0 \u2610<\/p>\n

    Arbitrary finite families of elementary step functions.<\/h3>\n

    We now consider the case of an arbitrary finite family F<\/em> of elementary step functions far below f<\/em>.<\/p>\n

    Lemma [1, Lemma 3.8].<\/strong> Let F<\/em> be a finite family of elementary step functions far below f<\/em>.\u00a0 There is a finite family of elementary step functions F’<\/em> far below f<\/em> that contains F<\/em> and is pointwise directed.<\/p>\n

    Proof. Call height<\/em> of an element y<\/em> in Y<\/em> the length of a longest increasing path from \u22a5 to y<\/em>.\u00a0 Note that, in the previous lemma,the height of each of the minimal upper bounds\u00a0ti<\/sub><\/em> is strictly larger than the heights of both y<\/em> and z<\/em>.\u00a0 Let us call height<\/em> of an elementary step function U<\/em> ↘ y<\/em>, the height of y<\/em> if U<\/em> is non-empty, 0 otherwise.<\/p>\n

    For every critical pair, pick a covering of it (as guaranteed by the previous lemma), and call it the<\/em> covering of the critical pair.<\/p>\n

    Let F<\/em>0<\/sub>=F<\/em>.\u00a0 Build F<\/em>1<\/sub>, the union of the coverings of critical pairs of F<\/em>.\u00a0 The height of each element of F<\/em>1<\/sub> is strictly larger than the heights of elements of F<\/em>, hence is at least 1.<\/p>\n

    Let now F<\/em>2<\/sub> be the union of the coverings of critical pairs {U<\/em> ↘ y<\/em>, V<\/em> ↘ z<\/em>} where U<\/em> ↘ y<\/em> is in\u00a0F<\/em>0<\/sub> \u222a F<\/em>1<\/sub>, and V<\/em> ↘ z<\/em> is in F<\/em>1<\/sub>.\u00a0 This contains only functions of height at least 2.<\/p>\n

    Iterate: let F<\/em>3<\/sub> be the union of the coverings of critical pairs {U<\/em> ↘ y<\/em>, V<\/em> ↘ z<\/em>} where U<\/em> ↘ y<\/em> is in\u00a0F<\/em>0<\/sub> \u222a F<\/em>1<\/sub> \u222a F<\/em>2<\/sub>, and V<\/em> ↘ z<\/em> is in F<\/em>2<\/sub> (this contains only functions of height at least 3), etc.<\/p>\n

    The process must stop because Y <\/em>has finite height, say at Fk<\/sub><\/em>.\u00a0 That means that all critical pairs at step k<\/em> have an empty covering.\u00a0 However, for a critical pair {U<\/em> ↘ y<\/em>, V<\/em> ↘ z<\/em>}, U<\/em> \u2229 V<\/em> is non-empty, and cannot be contained in an empty union: the covering of a critical pair cannot be empty.\u00a0 It follows that there is simply no critical pair at step k<\/em> of the completion process.<\/p>\n

    Let F’<\/em> be\u00a0F<\/em>0<\/sub> \u222a F<\/em>1<\/sub> \u222a F<\/em>2<\/sub> \u222a … \u222a Fk<\/sub><\/em>.<\/p>\n

    Before we proceed, note that the construction of F’<\/em> ensures that:<\/p>\n

    (*) the covering of every critical pair included in F’<\/em> is included in F’<\/em>.<\/p><\/blockquote>\n

    Indeed, given such a critical pair, one of the elements of the critical pair, call it V<\/em> ↘ z<\/em>, will be in\u00a0Fj<\/sub><\/em>, for some index j<\/em> that we can take minimal, and the other one, call it U<\/em> ↘ y<\/em>, will be in F<\/em>0<\/sub> \u222a F<\/em>1<\/sub> \u222a F<\/em>2<\/sub> \u222a … \u222a Fj<\/sub><\/em>.\u00a0 By construction, the covering of {U<\/em> ↘ y<\/em>, V<\/em> ↘ z<\/em>} is included in Fj<\/sub><\/em>+1<\/sub>, hence in F’<\/em>.<\/p>\n

    It remains to show that F’<\/em> is pointwise directed.\u00a0 We pick an arbitrary point x<\/em> in X<\/em>, and two elementary step functions\u00a0U<\/em> ↘ y<\/em>, V<\/em> ↘ z<\/em> in F’<\/em>.\u00a0 We need to show that there is another elementary step function\u00a0W<\/em> ↘ t<\/em> whose value at x<\/em> is above the values of both U<\/em> ↘ y<\/em> and V<\/em> ↘ z<\/em> at x<\/em>.<\/p>\n