Applied General Topology c© Universidad Politécnica de Valencia Volume 3, No. 1, 2002 pp. 91–112 Duality and quasi-normability for complexity spaces Salvador Romaguera ∗ and Michel Schellekens Abstract. The complexity (quasi-metric) space was introduced in [23] to study complexity analysis of programs. Recently, it was intro- duced in [22] the dual complexity (quasi-metric) space, as a subspace of the function space [0, +∞)ω. Several quasi-metric properties of the complexity space were obtained via the analysis of its dual. We here show that the structure of a quasi-normed semilinear space provides a suitable setting to carry out an analysis of the dual com- plexity space. We show that if (E,‖.‖) is a biBanach space (i.e., a quasi-normed space whose induced quasi-metric is bicomplete), then the function space (B∗E,‖.‖B∗) is biBanach, where B ∗ E = {f : ω → E |∑∞ n=0 2−n(‖f(n)‖∨‖−f(n)‖) < +∞}, and ‖f‖B∗ = ∑∞ n=0 2−n‖f(n)‖. We deduce that the dual complexity space admits a structure of quasi- normed semlinear space such that the induced quasi-metric space is order-convex, upper weightable and Smyth complete, not only in the case that this dual is a subspace of [0,+∞)ω but also in the general case that it is a subspace of Fω where F is any biBanach norm- weightable space. We also prove that for a large class of dual complexity (sub)spaces, lower boundedness implies total boundedness. Finally, we investigate completeness of the quasi-metric of uniform convergence and of the Hausdorff quasi-pseudo-metric for the dual complexity space, in the context of function spaces and hyperspaces, respectively. 2000 AMS Classification: 54E50, 54E15, 54C35, 46E15. Keywords: complexity space, quasi-norm, quasi-metric, biBanach space, Smyth complete. 1. Introduction and preliminaries Throughout this paper the letters R, R+, ω and N will denote the set of all real numbers, of all nonnegative real numbers, of all nonnegative integer ∗The first-listed author acknowledges the support of the Spanish Ministry of Science and Technology, grant BFM2000-1111 92 S. Romaguera and M. Schellekens numbers and of all positive integer numbers, respectively. Our basic references for quasi-metric spaces are [7] and [12]. Let us recall that a quasi-pseudometric on a (nonempty) set X is a non- negative real-valued function d on X × X such that for all x,y,z ∈ X: (i) d(x,x) = 0 and (ii) d(x,y) ≤ d(x,z) + d(z,y). In our context a quasi-metric on X is a quasi-pseudometric d on X which satisfies: (iii) d(x,y) = d(y,x) = 0 ⇔ x = y. If d is a quasi-(pseudo)metric on X, then the function ds defined on X ×X by ds(x,y) = max{d(x,y),d(y,x)} is a (pseudo)metric on X. A quasi-(pseudo)metric space is a pair (X,d) such that X is a (nonempty) set and d is a quasi-(pseudo)metric on X. The function u defined on R×R by u(x,y) = (y−x)∨0 for all x,y ∈ R, is an interesting example of a quasi-metric, where, as usual, ∨ denotes the maximum of y −x and 0. Note that us is exactly the Euclidean metric on R. The function u−1 defined on (0, +∞] × (0, +∞] by u−1(x,y) = ( 1y − 1 x ) ∨ 0 for all x,y ∈ (0, +∞] also provides an interesting example of a quasi-metric, in our context, where we adopt the convention that 1∞ = 0. Each quasi-pseudometric d on X generates a topology T(d) on X which has as a base the family of open balls {Sd(x,r) | x ∈ X, r > 0}, where Sd(x,r) = {y ∈ X | d(x,y) < r} for all x ∈ X and r > 0. It is clear, that d is a quasi-metric if and only if T(d) is a T0 topology. A quasi-(pseudo)metric d on X is called bicomplete [7] if ds is a complete (pseudo)metric on X. In this case, (X,d) is said to be a bicomplete quasi- (pseudo)metric space. In [27] and [28], Smyth presented a topological framework for denotational semantics based on the theory of complete (and totally bounded) quasi-uniform and quasi-metric spaces. Sünderhauf continued this work in the setting of topo- logical quasi-uniform spaces [29]. Künzi characterized in [12] both Smyth com- pletable and Smyth complete quasi-uniform spaces in terms of left K-Cauchy filters as discussed in [19]. We shall formulate these characterizations in the special case of quasi-(pseudo)metric spaces: A quasi-(pseudo)metric space (X,d) is Smyth completable if and only if every left K-Cauchy filter on (X,d) is a Cauchy filter on the (pseudo)metric space (X,ds) [12], where a filter F on (X,d) is left K-Cauchy provided that for each ε > 0 there is an Fε ∈ F such that Sd(x,ε) ∈ F for all x ∈ Fε [18]. A quasi-metric space (X,d) is Smyth complete if and only if every left K-Cauchy filter on (X,d) is convergent with respect to the metric topology T(ds) [12]. Therefore, every bicomplete Smyth completable quasi-metric space is Smyth complete. Smyth completable quasi-pseudometric spaces also can be studied in terms of left K-Cauchy sequences. In fact, it is proved in [25] that a quasi-pseudometric space (X,d) is Smyth completable if and only if every left K-Cauchy sequence in (X,d) is a Cauchy sequence in the pseudometric space (X,ds), where a sequence (xn)n∈N in (X,d) is left K-Cauchy if for each ε > 0 there is an nε ∈ N such that d(xn,xm) < ε whenever m ≥ n ≥ nε [17] (equivalently, (xn)n∈N is Duality and quasi-normability for complexity spaces 93 left K-Cauchy if and only the filter that generates is left K-Cauchy [18, Lemma 2]). The weightable quasi-metric spaces, or the equivalent partial metric spaces, were introduced by Matthews [16], as a part of the study of denotational se- mantics of dataflow networks. Excellent topological results on this class of spaces may be found in [12] and in [15]. Let us recall that a quasi-metric space (X,d) is called weightable if there is a function w: X → R+, such that w(x) + d(x,y) = w(y) + d(y,x) for all x,y ∈ X. The function w is said to be a weighting function for (X,d). It was proved in [12] that every weightable quasi-metric space is Smyth completable. Hence, every weightable bicomplete quasi-metric space is Smyth complete. The upper weightable quasi-metric spaces were introduced in [24], in the context of the development of a topological foundation for complexity analy- sis. A quasi-metric space (X,d) is called upper weightable if it is functionally bounded by a weighting function w, where (X,d) is functionally bounded pro- vided that there is a function f : X → R+, such that d(x,y) ≤ f(y) for all x,y ∈ X. As usual, the associated preorder ≤d of a quasi-pseudometric space (X,d) is defined by x ≤d y ⇔ d(x,y) = 0. A quasi-pseudometric space has a maximum if the associated preorder has a maximum. A join semilattice is a partially ordered set (X,≤) such that every two elements x,y ∈ X have a supremum xty. According to [24] a quasi-pseudometric join semilattice is a quasi-pseudometric space which is a join semilattice for its associated preorder. An optimal quasi- pseudometric join semilattice is a quasi-pseudometric join semilattice (X,d) such that d(x t y,y) = d(x,y) for all x,y ∈ X. A quasi-pseudometric space (X,d) is called order-convex if d(x,z) = d(x,y)+d(y,z) whenever z ≤d≤ y ≤d x (see [24]). The theory of complexity (quasi-metric) spaces, introduced in [23], pro- vides a topological foundation for the complexity analysis of algorithms. This theory constitutes a part of the research in Theoretical Computer Science and Topology and is developed in the setting of the Smyth completion of quasi-metric spaces. Applications of this theory to the complexity analysis of Divide & Conquer algorithms have been discussed in [23]. Let us recall that the complexity space (with values in (0, +∞]) is the pair (C,dC), where C = {f : ω → (0, +∞] | ∑∞ n=0 2 −n 1 f(n) < +∞}, and dC is the quasi-metric defined on C by dC(f,g) = ∑∞ n=0 2 −n[( 1 g(n) − 1 f(n) )∨0], whenever f,g ∈ C. dC is called in [23] “the complexity distance”, and intuitively it measures relative improvements in the complexity of programs. The dual complexity space (with values in (R+)ω) is introduced in [22] as a pair (C∗,dC∗), where C∗ = {f : ω → R+ | ∑∞ n=0 2 −nf(n) < +∞}, and dC∗ is the quasi-metric defined on C∗ by dC∗(f,g) = ∑∞ n=0 2 −n[(g(n) −f(n)) ∨ 0], whenever f,g ∈ C∗. (C,dC) is isometric to (C∗,dC∗) by the isometry Ψ : C∗ → C, defined by Ψ(f) = 1/f (see [22]). Thus, via the analysis of its dual, several quasi-metric 94 S. Romaguera and M. Schellekens properties of (C,dC), in particular Smtyh completeness and total boundedness, are studied in [22]. A motivation for the use of the dual instead of the original complexity space is the fact that the dual is mathematically somewhat more appealing, since dC∗ is ”derived” from the restriction to R+ of the quasi-metric u defined above. Consequently, the presentation of the proofs becomes some- what more elegant. Furthermore, it is possible to carry out the complexity analysis of algorithms based on the dual complexity space. In fact, the dual complexity space has the advantage that it respects the interpretation usually given to the minimum ⊥ in semantic domains (see [22, Section 4]). The complexity of a given program is frequently obtained by a summation of complexity functions or by a product of a complexity function by a constant, where these operations intuitively correspond to operations carried out by the program on data structures. In order to obtain an appropriate structure both for realizing these operations and for developing a consistent theory for the analysis of the dual complexity space we introduce, in Section 2, the notion of a biBanach space and study a kind of biBanach function space for which the dual complexity space is a quasi-normed semilinear subspace whose induced quasi-metric is upper weightable, order-convex and Smyth complete, even in the general case that the dual is a subspace of Fω, where F is any biBanach norm-weightable space (see Section 3). We also show, among other things, that a dual complexity space having a lower bound is totally bounded whenever the induced quasi-metric on the range space is linear. Finally, in Section 4, we study completeness of the quasi-metric of uniform convergence and of the Hausdorff quasi-pseudometric for the dual complexity space, in the context of function spaces and hyperspaces, respectively. 2. BiBanach function spaces We start this section giving the definitions of a quasi-norm and of a quasi- normed space in the sense of [5], [6] and [21] (see [4] for the related notion of a nonsymmetric norm). Let (E, +, ·) be a linear space on R. A quasi-norm on E is a nonnegative real-valued function ‖.‖ on E such that for all x,y ∈ E and a ∈ R+: (i ) ‖x‖ = ‖−x‖ = 0 ⇔ x = e (where e denotes the neutral element of (E, +)); (ii ) ‖ax‖ = a‖x‖; (iii ) ‖x + y‖≤‖x‖ + ‖y‖. The pair (E,‖.‖) is then called a quasi-normed space. (Note that the function ‖.‖s defined on E by ‖x‖s = max{‖x‖ ,‖−x‖}, for all x ∈ E, is a norm on E.) The quasi-norm ‖.‖ induces, in a natural way, a quasi-metric d‖.‖ on E, defined by d‖.‖(x,y) = ‖y −x‖ for all x,y ∈ E. If the quasi-metric d‖.‖ is bicomplete, we say that (E,‖.‖) is a biBanach space. Duality and quasi-normability for complexity spaces 95 Example 2.1. Let (R, +, ·) be the (usual) Euclidean linear space. For each x ∈ R define ‖x‖ = max{x, 0}. Then ‖.‖ is a quasi-norm on R such that ‖.‖s is the Euclidean norm. Therefore, (R,‖.‖) is a biBanach space. Example 2.2. Let (E,‖.‖) be a quasi-normed space. Define B∗E = {f : ω → E | ∞∑ n=0 2−n‖f(n)‖s < +∞}. If for each f,g ∈B∗E and each a ∈ R we define f + g and a ·f in the natural way, then it easily follows that (B∗E, +, ·) is a linear space (on R) because, clearly, − f ∈ B∗E whenever f ∈ B ∗ E. We then deduce that (B ∗ E,‖.‖B∗) is a quasi-normed space, where ‖f‖B∗ = ∞∑ n=0 2−n‖f(n)‖ for all f ∈B∗E. Remark 2.3. The definition of the space B∗E may seem somewhat surprising at first because it could be considered more natural to define this space as {f : ω → E | ∑∞ n=0 2 −n‖f(n)‖ < +∞}. However, the following simple example justifies our selection: Consider the biBanach space (R,‖.‖) of Example 2.1. Define f : ω → R by f(n) = −2n for all n ∈ ω. Then, ∑∞ n=0 2 −n‖f(n)‖ = 0, but ∑∞ n=0 2 −n‖−f(n)‖ = +∞, so for the possible alternative definition mentioned above, B∗E would not be a group. In the rest of this section we focus our attention on the quasi-normed space (B∗E,‖.‖B∗), because the dual complexity space will be a closed semilinear sub- space of it (see Section 3 for the definition of a semilinear space). Theorem 2.4. Let (E,‖.‖) be a biBanach space. Then (B∗E,‖.‖B∗) is a bi- Banach space. Proof. Let (fk)k∈ω be a Cauchy sequence in the normed space (B∗E, (‖.‖B∗) s). Define a quasi-metric p on B∗E by p(f,g) = ∞∑ n=0 2−n min{‖g(n) −f(n)‖ , 1} for all f,g ∈B∗E. Then p induces the topology of pointwise convergence on B ∗ E. Since p ≤ d‖.‖B∗ , (fk)k∈ω is a Cauchy sequence in the metric space (B ∗ E,p s). Then, for each n ∈ ω, the sequence (fk(n))k∈ω is a Cauchy sequence in the Banach space (E,‖.‖s), so it is convergent to a point xn ∈ E with respect to the topology induced by the norm ‖.‖s on E. Define a function g : ω → E, by g(n) = xn for all n ∈ ω. We first prove that g ∈B∗E : 96 S. Romaguera and M. Schellekens Indeed, assume the contrary. Then, for each j ∈ ω there is an mj ∈ ω such that (2.1) j < mj∑ n=0 2−n‖g(n)‖s . On the other hand, since (fk)k∈ω is a Cauchy sequence in (B∗E, (‖.‖B∗) s), there exists a k1 ∈ ω such that for each k ≥ k1, (2.2) ∞∑ n=0 2−n‖fk(n) −fk1 (n)‖ s < 1. Thus, (2.2′) mj∑ n=0 2−n‖fk(n) −fk1 (n)‖ s < 1 whenever k ≥ k1. Let j ∈ ω. Then there exists a k0 ≥ k1 such that ‖g(n) − fk0 (n)‖s < 2−j, for n = 0, 1, . . . ,mj. Hence, (2.3) mj∑ n=0 2−n‖g(n) −fk0 (n)‖ s < 2−j mj∑ n=0 2−n < 2−(j−1). By (2.1), (2.3) and (2.2′), we obtain, (2.4) j < 2−(j−1) + mj∑ n=0 2−n‖fk0 (n)‖ s < 2 + mj∑ n=0 2−n‖fk1 (n)‖ s , which implies that ∞∑ n=0 2−n‖fk1 (n)‖ s = +∞, a contradiction. We conclude that g ∈B∗E. Finally, we prove that (‖g −fk‖B∗)s → 0 as k → +∞. (Compare [22, proof of Theorem 3]): Let j ∈ ω. Then there exists a k(j) ∈ ω such that for every k,m ≥ k(j), (2.5) ∞∑ n=0 2−n‖fk(n) −fm(n)‖ s < 2−3j. Since both fk(j) and g are in B∗E, there exists n0 ∈ ω (depending on j) such that n0 > 1 and 2−(n0−1)n0 < 2 −3j,(2.6) ∞∑ n=n0 2−n ∥∥fk(j)(n)∥∥s < 2−3j, and ∞∑ n=n0 2−n‖g(n)‖s < 2−3j. Duality and quasi-normability for complexity spaces 97 Moreover, there exists a kj ≥ k(j) such that for every k,m ≥ kj, (2.7) ∞∑ n=0 2−n‖fk(n) −fm(n)‖ s < 2−n0. Choose any k ≥ kj. Then for each n ∈ ω with 0 ≤ n ≤ n0 − 1, there exists an mn ≥ k such that ‖g(n) − fmn(n)‖s < 2−n0 . By (2.7) and the triangle inequality, ‖g(n) −fk(n)‖ s < 2−n0 (1 + 2n) whenever 0 ≤ n ≤ n0−1. Therefore n0−1∑ n=0 2−n‖g(n) −fk(n)‖ s < 2−n0 · 2n0 < 2−3j. Moreover, it follows from (2.5) and (2.6), that ∞∑ n=n0 2−n‖g(n) −fk(n)‖ s ≤ ∞∑ n=n0 2−n‖g(n)‖s + ∞∑ n=n0 2−n‖fk(n)‖ s < 2−3j + ∞∑ n=n0 2−n ∥∥fk(j)(n)∥∥s + 2−3j < 3 · 2−3j for every k ≥ kj. Thus we have shown that for each j ∈ ω there is a kj ∈ ω such that ∞∑ n=0 2−n‖g(n) −fk(n)‖ s < 4 · 2−3j ≤ 2−j whenever k ≥ kj. We conclude that (B∗E,‖.‖B∗) is a biBanach space. � Remark 2.5. Note that if (E,‖.‖) is a quasi-normed space, then (‖.‖B∗) s and (‖.‖s)B∗ are equivalent norms on B∗E. We finish this section with a result on the preservation of order-convexity which will be used later on. A quasi-normed space (E,‖.‖) is called order-convex if the quasi-metric space (E,d‖.‖) is order-convex. Proposition 2.6. Let (E,‖.‖) be an order-convex quasi-normed space. Then (B∗E,‖.‖B∗) is order-convex. Proof. Let f,g,h ∈B∗E be such that f ≤d‖.‖B∗ g ≤d‖.‖B∗ h, where d‖.‖B∗ denotes the quasi-metric induced on B∗E by ‖.‖B∗. Then f(n) ≤d‖.‖ g(n) ≤d‖.‖ h(n) for all n ∈ ω. Since (E,‖.‖) is order convex, ‖f(n) −h(n)‖ = ‖f(n) −g(n)‖ + ‖g(n) −h(n)‖ for all n ∈ ω. But ∞∑ n=0 2−n‖f(n) −g(n)‖ < +∞ and ∞∑ n=0 2−n‖g(n) −h(n)‖ < +∞. 98 S. Romaguera and M. Schellekens Hence, ∞∑ n=0 2−n‖f(n) −g(n)‖ + ∞∑ n=0 2−n‖g(n) −h(n)‖ = ∞∑ n=0 2−n[‖f(n) −g(n)‖ + ‖g(n) −h(n)‖] = ∞∑ n=0 2−n‖f(n) −h(n)‖ . So, ‖f −h‖B∗ = ‖f −g‖B∗ +‖g −h‖B∗. We conclude that (B ∗ E,‖.‖B∗) is order- convex. � 3. The dual complexity space In our context a semilinear space on R+ is an ordered triple (E, +, ·), such that (E, +) is an Abelian semigroup with neutral element e, and · is a function from R+ ×E to E such that for all x,y ∈ E and a,b ∈ R+: a ·(b ·x) = (ab) ·x, (a + b) ·x = (a ·x) + (b ·x), a · (x + y) = (a ·x) + (a ·y), and 1 ·x = x. Let us recall that every semilinear space is a cone in the sense of Keimel and Roth [10]. Definition 3.1. A quasi-normed semilinear space is a pair (F,‖.‖F ) such that F is a nonempty subset of a quasi-normed space (E,‖.‖), ‖.‖F denotes the restriction of the quasi-norm ‖.‖ to F, and (F, + |F , · |F ) is a semilinear space on R+. If (F,‖.‖F ) is a quasi-normed semilinear space, then the restriction to F of the quasi-metric d‖.‖, induced on E by the quasi-norm ‖.‖, will be denoted by d‖.‖F . Definition 3.2. A biBanach semilinear space is a pair (F,‖.‖F ) such that F is a nonempty subset of a biBanach space (E,‖.‖), F is closed in the Banach space (E,‖.‖s), and (F,‖.‖F ) is a quasi-normed semilinear space. If in addition, the following condition is satisfied: (i) (F,d‖.‖ F ) is an order-convex optimal quasi-metric join semilattice hav- ing a maximum, then, (F,‖.‖F ) is called a biBanach norm-weightable space. The terminology “norm-weightable” is justified by Corollary 3.8 below. Remark 3.3. Note that if (F,‖.‖F ) is a biBanach semilinear space, then d‖.‖F is a bicomplete quasi-metric on F. Lemma 3.4. Let (F,‖.‖F ) be a biBanach semilinear space such that (F,d‖.‖F ) has a maximum. Then the neutral element e is the (unique) maximum of (F,d‖.‖F ). Duality and quasi-normability for complexity spaces 99 Proof. Let x0 be the maximum for (F,d‖.‖F ). Then e ≤d‖.‖F x0, so ‖x0‖F = d‖.‖F (e,x0) = 0. Moreover, 2 ·x0 ≤d‖.‖F x0, so, ‖−x0‖ = d‖.‖F (2 ·x0,x0) = 0. We conclude that x0 = e. � Corollary 3.5. Let (F,‖.‖F ) be a biBanach semilinear space such that (F,d‖.‖F ) has a maximum. Then, ‖x−y‖≤‖x‖F , for all x,y ∈ F . Proof. Let x,y ∈ F. Then ‖x−y‖ = d‖.‖ F (y,x) ≤ d‖.‖ F (y,e) + d‖.‖ F (e,x). By Lemma 3.4, d‖.‖F (y,e) = 0. Hence, ‖x−y‖≤ d‖.‖F (e,x) = ‖x‖F . � Example 3.6. Consider the biBanach space (R,‖.‖) of Example 2.1. It is straightforward to show that (R+,‖.‖ R + ) is a biBanach norm-weightable space. Of course, (R+, + |R+ ) is not a group. Next we give an auxiliary lemma on quasi-metric join semilattices, which, joint with its corollaries, will be useful later on. It can be derived from [24, Theorem 15] which states that an optimal quasi-metric join semilattice (X,d) is weigthable if and only if it is it is functionally bounded and order-convex. However, in order to help the reader we shall give a direct proof. Lemma 3.7. Let (X,d) be an order-convex optimal quasi-metric join semilat- tice having a maximum element x0. Then, (X,d) is upper weightable by the weighting function w: X → R+ defined by w(x) = d(x0,x) for all x ∈ X. Proof. Choose any pair of points x,y ∈ X. Since (X,d) is a join semilattice and x0 is its maximum, we obtain x ≤d x t y ≤d x0, and y ≤d x t y ≤d x0. Therefore, w(x) = d(x0,x) = d(x0,xty) + d(xty,x) = d(x0,xty) + d(y,x) and w(y) = d(x0,y) = d(x0,xty) + d(xty,y) = d(x0,xty) + d(x,y). Hence, w(x) + d(x,y) = d(x0,xty) + d(y,x) + d(x,y) = w(y) + d(y,x). Finally, d(x,y) ≤ d(x,x0) + d(x0,y) = w(y), since d(x,x0) = 0. We conclude that (X,d) is upper weightable with weighting function w(x) = d(x0,x) for all x ∈ X. � From Lemmas 3.4 and 3.7, we deduce the following result. Corollary 3.8. Let (F,‖.‖F ) be a biBanach norm-weightable space. Then the quasi-metric space (F,d‖.‖ F ) is upper weightable by the weighting function w: F → R+ defined by w(x) = ‖x‖F for all x ∈ F . Since every (upper) weightable bicomplete quasi-metric space is Smyth com- plete [12], we deduce from Lemma 3.7 and Remark 3.3 the following Corollary 3.9. Let (F,‖.‖F ) be a biBanach norm-weightable space. Then the quasi-metric space (F,d‖.‖F ) is Smyth complete. 100 S. Romaguera and M. Schellekens Let (F,‖.‖F ) be a biBanach semilinear space. Then, by Definition 3.2, there exists a biBanach space (E,‖.‖) such that F is a (nonempty) closed subset of the Banach space (E,‖.‖s), ‖.‖F denotes the restriction of ‖.‖ to F and (F,‖.‖F ) is a quasi-normed semilinear space. Now define C∗F = {f : ω → F | ∞∑ n=0 2−n‖f(n)‖s < +∞}, and, for each f ∈C∗F , ‖f‖C∗ = ∞∑ n=0 2−n‖f(n)‖F . Obviously, C∗F ⊆B ∗ E. The following proposition should be compared with Remark 2.3. Proposition 3.10. Let (F,‖.‖F ) be a biBanach norm-weightable space. Then C∗F = {f : ω → F | ∞∑ n=0 2−n‖f(n)‖F < +∞}. Proof. Let f : ω → F be such that ∑∞ n=0 2 −n‖f(n)‖F < +∞. Since e ∈ F, it follows from Corollary 3.5 that ‖−f(n)‖ = ‖e‖ = 0 for all n ∈ ω. Hence∑∞ n=0 2 −n‖f(n)‖s = ∑∞ n=0 2 −n‖f(n)‖F < +∞. We conclude that f ∈C ∗ F . � Proposition 3.11. Let (F,‖.‖F ) be a biBanach semilinear space. Then (C∗F ,‖.‖C∗) is a biBanach semilinear space. Proof. Let (E,‖.‖) be the biBanach space for which (F,‖.‖F ) is a biBanach semilinear space. From the semilinearity of (F, + |F , · |F ) it immediately fol- lows that (C∗F , +, .) is a semilinear space on R + for the natural addition and multiplication. On the other hand, (B∗E,‖.‖B∗) is a biBanach space by The- orem 2.4. We shall prove that C∗F is a closed subset of the Banach space (B∗E, (‖.‖B∗) s). Indeed: Let f ∈ B∗E be such that (‖f −fk‖B∗) s → 0, where (fk)k∈ω is a sequence of elements of C∗F . Then ‖f(n) −fk(n)‖ s → 0 whenever n ∈ ω. Since F is closed in (E,‖.‖s), we deduce that f(n) ∈ F for all n ∈ ω. Thus, f ∈C∗F . We conclude that (C∗F ,‖.‖C∗) is a biBanach semilinear space. � It follows from the preceding result that the quasi-metric d‖.‖C∗ defined on C∗F by d‖.‖C∗ (f,g) = ‖g −f‖B∗ is bicomplete. Definition 3.12. Let (F,‖.‖F ) be a biBanach norm-weightable space. Then, the quasi-metric space (C∗F , d‖.‖C∗ ) is called the dual complexity space (of (F,‖.‖F )). Any subspace of (C∗F ,d‖.‖C∗ ) is also called a dual complexity space. Lemma 3.13 ([26]). A quasi-pseudometric join semilattice (X,d) is optimal if and only if for all x,y,z ∈ X, d(xtz,y tz) ≤ d(x,y). Duality and quasi-normability for complexity spaces 101 It is interesting to note that the equivalent condition to optimality, in the preceding lemma, is exactly the more familiar notion of t-invariance as dis- cussed in [8]. Proposition 3.14. The dual complexity space (C∗F ,d‖.‖C∗ ) is an order-convex optimal quasi-metric join semilattice and it has a maximum. Proof. We first show that (C∗F ,d‖.‖C∗ ) is a quasi-metric join semilattice. Let f,g ∈ C∗F . Since (F,d‖.‖F ) is a quasi-metric join semilattice, for each n ∈ ω there is a supremum f(n) t g(n) ∈ F of f(n) and g(n). Define a function f tg : ω → F by (f tg)(n) = f(n) tg(n) for all n ∈ ω. By Lemma 3.13 and the fact that e is the maximum of (F,d‖.‖ F ), we have: ‖f(n) tg(n)‖F = d‖.‖F (e,f(n) tg(n)) = d‖.‖F (etg(n),f(n) tg(n)) ≤ d‖.‖ F (e,f(n)) = ‖f(n)‖F , for all n ∈ ω. Therefore, ∑∞ n=0 2 −n‖(f tg)(n)‖F ≤ ∑∞ n=0 2 −n‖f(n)‖F < +∞, so f tg ∈C∗F by Proposition 3.10. On the other hand, since f(n) ≤d‖.‖F f(n) t g(n) and g(n) ≤d‖.‖F f(n) t g(n) for all n ∈ ω, we deduce that ‖(f tg)(n) −f(n)‖ = ‖(f tg)(n) −g(n)‖ = 0 for all n ∈ ω, so d‖.‖C∗ (f,f t g) = d‖.‖C∗ (g,f t g) = 0, and, hence, f ≤d‖.‖C∗ f t g and g ≤d‖.‖C∗ f t g. Furthermore, if h ∈C∗F satisfies f ≤d‖.‖C∗ h and g ≤d‖.‖C∗ h, we deduce, by the definition of supremum, that (f t g)(n) ≤d‖.‖F h(n) for all n ∈ ω. Therefore, f tg ≤d‖.‖C∗ h. Thus, we have shown that the function f tg, is the (unique) supremum of f and g in (C∗,d‖.‖C∗ ). Hence, (C ∗,d‖.‖C∗ ) is a quasi-metric join semilattice. Next we show that the quasi-metric join semilattice (C∗,d‖.‖C∗ ) is optimal. Let f,g ∈C∗F . Then, by the optimality of (F,d‖.‖F ), we have d‖.‖C∗ (f tg,g) = ∞∑ n=0 2−nd‖.‖ F (f(n) tg(n),g(n)) = ∞∑ n=0 2−nd‖.‖ F (f(n),g(n)) = ‖g −f‖B∗ = d‖.‖C∗ (f,g). Hence, (C∗,d‖.‖C∗ ) is optimal. On the other hand, the argument used in the proof of Proposition 2.6 shows that (C∗,d‖.‖C∗ ) is also order-convex. Finally, the function fe : ω → F defined by fe(n) = e for all n ∈ ω, is the (unique) maximum of (C∗,d‖.‖C∗ ) because d‖.‖C∗ (f,fe) = 0 for all f ∈C ∗ F . This completes the proof. � 102 S. Romaguera and M. Schellekens From Propositions 3.11 and 3.14, we immediately deduce the following Theorem 3.15. Let (F,‖.‖F ) be a biBanach norm-weightable space. Then, (C∗F ,‖.‖C∗) is a biBanach norm-weightable space. Corollary 3.16. The dual complexity space (C∗F ,d‖.‖C∗ ) is an upper weightable Smyth complete quasi-metric space. Proof. By Theorem 3.15 and Corollary 3.8, (C∗F ,d‖.‖C∗ ) is upper weightable with weighting function w: C∗F → R + given by w(f) = ‖f‖C∗ for all f ∈ C ∗ F . Finally, by Theorem 3.15 and Corollary 3.9, (C∗F ,d‖.‖C∗ ) is a Smyth complete quasi-metric space. � Remark 3.17. In Proposition 3.14, we have shown that for any dual complex- ity space (C∗F ,d‖.‖C∗ ), d‖.‖C∗ (f,fe) = 0 whenever f ∈ C ∗ F , where fe(n) = e for all n ∈ ω. From this fact, it easily follows that the dual complexity space also is a Baire space. Example 3.18. Let (E,‖.‖) be a biBanach space. By Theorem 2.4, the func- tion space (B∗E,‖.‖B∗) is also a biBanach space. Now let F be a nonempty subset of E such that (F,‖.‖F ) is a biBanach norm-weightable space. Thus, (C∗F ,‖.‖C∗) is a biBanach norm-weightable space by Theorem 3.15. Define B∗B∗ E = {f : ω →B∗E | ∞∑ n=0 2−n(‖f(n)‖B∗) s < +∞} and C∗C∗ F = {f : ω →C∗F | ∞∑ n=0 2−n‖f(n)‖C∗ < +∞}. By Theorem 2.4, (B∗B∗ E ,‖.‖B∗B∗ ) is a biBanach space and, by Proposition 3.10 and Theorem 3.15, (C∗C∗ F ,‖.‖C∗C∗ ) is a biBanach norm-weightable space. Let (C∗F ,d‖.‖C∗ ) be the dual complexity space (of the biBanach norm-weight- able space (F,‖.‖F )) and let F ⊆C ∗ F . Then, the restriction of d‖.‖C∗ to F will be also denoted by d‖.‖C∗ . Definition 3.19. A dual complexity space (F,d‖.‖C∗ ), where F ⊆C ∗ F , has an upper bound U ∈ C∗F if for each f ∈ F, f ≤d‖.‖C∗ U. Similarly, (F,d‖.‖C∗ ) has a lower bound L ∈C∗F if for each f ∈F, L ≤d‖.‖C∗ f. For each U ∈C∗F , we define (C ∗ F ) U = {f ∈C∗F | U is an upper bound for f}. The following easy example shows that the structure of a semilinear space of C∗F is not preserved by (C ∗ F ) U , in general. Example 3.20. Let (R+,‖.‖ R + ) be the biBanach norm-weightable space of Example 3.6. Let U ∈ C∗ R + defined by U(n) = 1 for all n ∈ ω. Then the function f defined on ω by f(n) = 1 2 U(n) for all n ∈ ω is in C∗F \ (C ∗ F ) U . Duality and quasi-normability for complexity spaces 103 However, the complexity (sub)space ((C∗F ) U,d‖.‖C∗ ) inherits the quasi-metric properties of (C∗F ,d‖.‖C∗ ), obtained in Proposition 3.14 and Corollary 3.16, as follows. Theorem 3.21. For each U ∈ C∗F , ((C ∗ F ) U,d‖.‖C∗ ) is an upper weightable Smyth complete order-convex optimal quasi-metric join semilattice and it has a maximum. Proof. Let U ∈ C∗F . Let f,g ∈ (C ∗ F ) U . By Proposition 3.14, there is f t g ∈ C∗F . By the definition of supremum, f t g ≤d‖.‖C∗ U, so f t g ∈ (C ∗ F ) U . Hence, ((C∗F ) U,d‖.‖C∗ ) is a quasi-metric join semilattice. Moreover, it is upper weightable, order-convex and optimal, because these properties are hereditary, and, obviously, U is its maximum. Finally, in order to show that ((C∗F ) U,d‖.‖C∗ ) is Smyth complete, it suffices to show that (C∗F ) U is a closed subset of the met- ric space (C∗F , (d‖.‖C∗ ) s), and, then, apply Corollary 3.16. Assume the contrary. Then there is f ∈C∗F \ (C ∗ F ) U such that (d‖.‖C∗ ) s(f,fk) → 0 for some sequence (fk)k∈ω in (C∗F ) U . Furthermore, there is n0 ∈ ω such that d‖.‖F (f(n0),U(n0)) = δ > 0. Therefore, δ ≤ d‖.‖ F (f(n0),fk(n0))+d‖.‖ F (fk(n0),U(n0)) = d‖.‖ F (f(n0), fk(n0)) for all k ∈ ω. But, d‖.‖F (f(n0),fk(n0)) → 0 as k → +∞. So, we have reached a contradiction. The proof is complete. � Let us recall [24] that a linear quasi-metric space is a quasi-metric space (X,d) such that is associated order ≤d is linear. It is known [24] that every linear quasi-metric space is an optimal quasi-metric join semilattice. Note that (R+,d‖.‖ R+ ) is a linear quasi-metric space. A quasi-metric space (X,d) is called precompact if for each ε > 0 there is a finite subset A of X such that X = ⋃ a∈A Sd(a,ε). (X,d) is called totally bounded if (X,ds) is a totally bounded metric space (see, for instance, [7]). It is well known that every totally bounded quasi-metric space is precompact but the converse implication is not true in general. It follows from a result of Künzi [12, Proposition 12] that every hereditarly precompact weightable quasi-metric space is totally bounded. By using this result we shall prove the following Theorem 3.22. Let (F,‖.‖F ) be a biBanach norm-weightable space such that ≤d‖.‖F is linear and let F ⊆C ∗ F . If (F, d‖.‖C∗ ) has a lower bound, then it is totally bounded. Proof. Since (C∗F ,d‖.‖C∗ ) is (upper) weightable and weightability is a heredi- tary property it suffices to show that (F,d‖.‖C∗ ) is hereditarily precompact by Künzi’s proposition cited above. Actually, it is enough to prove that any sub- space (G, d‖.‖C∗ ) of (C ∗ F ,d‖.‖C∗ ) which has a lower bound is precompact, since all subspaces of (F,d‖.‖C∗ ) are of this kind. Hence, let (G,d‖.‖C∗ ) be a subspace of (C ∗ F ,d‖.‖C∗ ) which has a lower bound, say L ∈C∗F and let ε > 0. 104 S. Romaguera and M. Schellekens Since (F,‖.‖F ) is a biBanach norm-weightable space, it follows from Lemma 3.4 and Corollary 3.8, that d‖.‖F (x,e) = 0 for all x ∈ F, and that the quasi- metric space (F,d‖.‖ F ) is (upper) weightable by the function w defined on F by w(x) = ‖x‖F for all x ∈ F. (Let us also recall that F is a subset of a biBanach space (E,‖.‖) such that ‖.‖F denotes the restriction of ‖.‖ to F.) Since L ∈C∗F , ∑∞ n=0 2 −n(‖L(n)‖F ) s < +∞. Hence, there is k ∈ ω such that∑∞ n=k+1 2 −n‖L(n)‖F < ε/2. Moreover, for each f ∈ G and each n ∈ ω, we have d‖.‖F (e,f(n)) ≤ d‖.‖F (e,L(n)) +d‖.‖F (L(n),f(n)) = d‖.‖F (e,L(n)). Thus, ‖f(n)‖F ≤‖L(n)‖F . Therefore, for each f ∈G, ∞∑ n=k+1 2−n‖f(n)‖F < ε/2, and ‖f(n)‖F ≤ B for all n ≤ k, where B = max{‖L(n)‖F | n ≤ k}. Now consider the set of functions Gk obtained from G by restricting each function of G to the domain {0, . . . ,k}. Fix an m ∈ ω such that m ≥ 1 and B m+1 < ε 4 . Define a partition of the real interval [0,B] consisting of the intervals Bm0 , . . . ,B m m, where Bm0 = [0, B m+1 ], and for all j ∈{1, . . . ,m}, Bmj = (j B m+1 , (j + 1) B m+1 ]. Take the quotient of the set Gk, given by the equivalence relation ∼, defined on G by: f ∼ g ⇔ for each n ≤ k there is j ≤ m such that both ‖f(n)‖F ,‖g(n)‖F ∈ B m j . The set Gk/∼, is clearly finite. Let its cardinality be h, and choose h ele- ments f1, . . . ,fh of G, such that f1 | {0, . . . ,k}, . . . ,fh | {0, . . . ,k}, is a list of representatives, one for each class of the quotient Gk/∼. Given f ∈G, let i ∈{1, . . . ,h} be such that fi is the representative for which fi | {0, . . . ,k}∼ f | {0, . . . ,k}. Then d‖.‖C∗ (fi,f) = ∞∑ n=0 2−nd‖.‖F (fi(n),f(n)) = k∑ n=0 2−nd‖.‖F (fi(n),f(n)) + ∞∑ n=k+1 2−nd‖.‖F (fi(n),f(n)). Let n ∈ ω. If fi(n) ≤d‖.‖F f(n), we obtain d‖.‖F (fi(n),f(n)) = 0. Other- wise, since ≤d‖.‖F is linear and w is a weighting function on F, we deduce that d‖.‖ F (fi(n),f(n)) = ‖f(n)‖F −‖fi(n)‖F Therefore, d‖.‖C∗ (fi,f) ≤ k∑ n=0 2−n B m + 1 + ∞∑ n=k+1 2−n‖f(n)‖F < 2B m + 1 + ε 2 < ε. Duality and quasi-normability for complexity spaces 105 We conclude that (G,d‖.‖C∗ ) is precompact. Hence, (F,d‖.‖C∗ ) is hereditarily precompact and, thus, totally bounded. � Remark 3.23. It is shown in [22] that the dual complexity space (C∗F ,d‖.‖C∗ ) is not precompact and, thus, not totally bounded, in general. Hence, the condition of the existence of a lower bound cannot be omitted in the statement of the preceding theorem. For each L ∈ C∗F and each F ⊆C ∗ F , we define FL = {f ∈ F | L is a lower bound for f}. In particular, (C∗F )L = {f ∈C ∗ F | L is a lower bound for f}. Let us recall that a subset Y of a topological space X is said to be relatively compact if Y (in X) is compact. Theorem 3.24. Let (F,‖.‖F ) be a biBanach norm-weightable space such that ≤d‖.‖F is linear. Then, for each L ∈ C ∗ F and each F ⊆C ∗ F , FL is relatively compact in the (complete) metric space (C∗F , (d‖.‖C∗ ) s). Proof. Given L ∈ C∗F and F ⊆C ∗ F , we first prove that L is a lower bound for FL, where FL denotes the closure of FL in (C∗F , (d‖.‖F ) s). Assume the contrary. Then there is f ∈FL such that d‖.‖F (L(n0),f(n0)) = δ > 0 for some n0 ∈ ω. On the other hand, there is a sequence (fk)k∈ω in FL such that (d‖.‖C∗ ) s(f,fk) → 0. Thus, δ ≤ d‖.‖F (L(n0),fk(n0)) + d‖.‖F (fk(n0), f(n0)) = d‖.‖ F (fk(n0),f(n0)). Since d‖.‖ F (fk(n0),f(n0)) → 0 as k → +∞, we obtain a contradiction. Hence, (FL,d‖.‖C∗ ) is a totally bounded quasi-metric space by Theorem 3.22. It then follows from the Smyth completeness of (C∗F ,d‖.‖F ) that FL is compact in (C∗F , (d‖.‖C∗ ) s). � Corollary 3.25. Let (F,‖.‖F ) be a biBanach norm-weightable space such that ≤d‖.‖F is linear. Then, for each L ∈C ∗ F , ((C ∗ F )L, (d‖.‖C∗ ) s) is a compact metric space. Proof. A similar argument to the given in the proof of Theorem3.21, shows that (C∗F )L is closed in (C ∗ F , (d‖.‖C∗ ) s). By Theorem 3.24, ((C∗F )L, (d‖.‖C∗ ) s) is compact. � The following example shows that the condition that the order ≤d‖.‖F is linear on F cannot be omitted in Theorems 3.22 and 3.24 and Corollary 3.25. Example 3.26. Consider the biBanach norm-weightable space (R+,‖.‖ R + ) and the biBanach norm-weightable space (C∗ R +,‖.‖C∗ R+ ) (see Theorem 3.15). Define L: ω → C∗ R + by (L(n))(m) = 22n if m = n, and (L(n))(m) = 0 other- wise. Now consider the sequence (fk)k∈ω such that for each k ∈ ω, fk : ω →C∗R+ is defined by (fk(n))(m) = 22n if m = n = k, and (fk(n))(m) = 0 otherwise. Clearly, d‖.‖C∗ (L(n),fk(n)) = 0 for all n,k ∈ ω, because (fk(n))(m) is only different from zero when m = n = k and in such a case one has (fn(n))(n) = 106 S. Romaguera and M. Schellekens 22n = (L(n))(n). Therefore, L is a lower bound for F = {fk | k ∈ ω}. However, d‖.‖C∗ C∗ (fk,fk+1) = 1 for all k ∈ ω, because d‖.‖C∗C∗ (fk,fk+1) = ∞∑ n=0 2−nd‖.‖C∗ (fk(n),fk+1(n)) = ∞∑ n=0 2−n   ∞∑ j=0 2−j[((fk+1(n))(j) − (fk(n))(j)) ∨ 0]   and (fk+1(n)(j)) = 0 except when j = n = k + 1. In this case, one has (fk+1(n))(j) − (fk(n))(j) = 22j, so d‖.‖C∗C∗ (fk,fk+1) = 2−j2−j22j = 1. We conclude that (F,d‖.‖C∗C∗ ) is not totally bounded. We remark that it is possible still to endow the complexity space with a satisfactory structure in this context. To this end we first introduce the notion of a unitary quasi-normed space. Definition 3.27. A unitary quasi-normed space is a triple (E,‖.‖ ,?) such that (E,‖.‖) is a quasi-normed space (on R) and ? is an internal commutative (multiplication) law for which there is a unique element 1E ∈ E such that for each x ∈ E\{e} there exists a unique 1 x ∈ E\{e} satisfying x ? 1 x = 1E. If (E,‖.‖ ,?) is a unitary quasi-normed space, we may define a quasi-metric d−1 on E \{e} as follows: d−1(x,y) = ∥∥∥∥1y − 1x ∥∥∥∥ for all x,y ∈ E\{e}. Now let F be a (nonempty) subset of E which is closed for the law ? and such that (F,‖.‖F ) is a biBanach norm-weightable space satisfying that for each x ∈ F\{e}, 1 x ∈ F (note that, in fact, 1E ∈ F). Then, we construct a set F∞ = (F\{e}) ∪{∞}, where ∞ /∈ E is defined by the conditions: (i) for every x ∈ F, ∞+ x = x +∞ = ∞, (ii) for every x ∈ F, ∞?x = x?∞ = ∞ and (iii) 1 ∞ = e. Note that, by (iii), the quasi-metric d−1 |F\{e} can be extended to F∞. This extension will be also denoted by d−1. (Moreover, if one defines ∞·r = r ·∞ = ∞ for all r > 0, then (F∞, +, ·) is a cone in the sense of [10].) Under the above conditions we define CF∞ = { f : ω → F∞ | ∑∞ n=0 2 −n ∥∥∥ 1f(n)∥∥∥s < +∞} and dC(f,g) = ∞∑ n=0 2−nd−1(f(n),g(n)) for all f,g ∈CF∞. Then, it is straightforward to check that dC is a quasi-metric on CF∞. Duality and quasi-normability for complexity spaces 107 Definition 3.28. The quasi-metric space (CF∞,dC) is called the complexity space (of (F∞,d−1)). Remark 3.29. Note that (R,‖.‖ ,?) is a unitary quasi-normed space, where (R,‖.‖) is the biBanach space of Example 2.1 and ? denotes the usual multipli- cation on R. Moreover the induced quasi-metric d−1 is exactly the quasi-metric u−1 defined in Section 1. Taking F = R+, we have that F∞ = (0, +∞] and CF∞ = {f : ω → (0, +∞] |∑∞ n=0 2 −n 1 f(n) < +∞}. Thus, we obtain the complexity space (with values in (0, +∞]), as discussed in [23]. Given a biBanach norm-weightable space (F,‖.‖F ), consider the complexity space (CF∞,dC) and the dual complexity space (C∗F ,dC∗). Then, as in [22], we may define an isometry Ψ : CF∞ → C∗F by Ψ(f) = 1/f for all f ∈ CF∞. Combining this fact with the propositions and theorems proved in this section, we obtain, among other, the following results: A) The complexity space (CF∞,dC) is an optimal join semilattice order- convex quasi-metric space and the point f∞ is its maximum, where f∞(n) = ∞ for all n ∈ ω. B) The complexity space (CF∞,dC) is an upper weightable Smyth complete quasi-metric space. C) Let (F,‖.‖F ) be a biBanach norm-weightable space such that ≤d‖.‖F is linear and let F ⊆CF∞. If (F,dC) has a lower bound, then it is totally bounded. D) Let (F,‖.‖F ) be a biBanach norm-weightable space such that ≤d‖.‖F is linear. Then, for each L ∈ CF∞, ((CF∞)L, (dC)s) is a compact metric space. Comment. Our assumption regarding complexity lower bounds both for the dual complexity space and the complexity space (see Theorem 4 and state- ment C) above), may seems restrictive at first from a computational point of view. Indeed, by the Blum speed up theorem ([3] or [9]), there exist problems for which any algorithm computing such a problem can be replaced by a new algo- rithm which computes the given problem significantly faster. More specifically, an asymptotic gain can be obtained at each time which is logarithmic in the complexity of the program one starts out with. However, such problems may be seen as artificially constructed to prove the theorem according to [9] which continues to state that ”for an important class of problems that can occur in practice an optimal algorithm does exists”, by Levin’s theorem, and hence one does obtain a lower bound, in general. As such our assumption is justifiable not only by the concrete examples of complexity lower bounds which one can find in the literature (e.g. [11]), but also finds formal justification by the above cited result. 108 S. Romaguera and M. Schellekens 4. Function spaces and hyperspaces for complexity spaces In this section we investigate completeness of the quasi-metric of uniform convergence and of the Hausdorff quasi-pseudometric for dual complexity spaces, in the context of function spaces and hyperspaces, respectively. We will need to consider extended quasi-(pseudo)metrics. They satisfy the usual axioms for a quasi-(pseudo)metric, except that we allow d(x,y) = +∞. Let X be a nonempty set and let (Y,d) be a quasi-(pseudo)metric space. Denote by D the extended quasi-(pseudo)metric defined on the set Y X of all functions from X to Y by D(f,g) = sup{d(f(x),g(x)) | x ∈ X} for all f,g ∈ Y X. D is called the extended quasi-(pseudo)metric of uniform convergence (of (Y,d)) (compare [20, p. 88-89]). Similarly to [13, Proposition 5] we obtain that if X is a nonempty set and (Y,d) is a bicomplete quasi-(pseudo)metric space, then D is a bicomplete ex- tended quasi-(pseudo)metric on Y X. From this result and Theorem 2.4 we deduce the following Proposition 4.1. Let (E,‖.‖) be a biBanach space. Then, for each nonempty set X the extended quasi-metric of uniform convergence of (B∗E,d‖.‖B∗ ) is bi- complete on (B∗E) X. Now suppose that (F,‖.‖F ) is a biBanach norm-weightable space. It then follows from Propositions 3.11 and 4.1, that for each nonempty set X, the extended quasi-metric of uniform convergence of the dual complexity space (C∗F ,d‖.‖C∗ ) is bicomplete on (C ∗ F ) X. In the light of Corollary 3.16, it seems natural to ask if this extended quasi-metric is actually Smyth complete. The following example shows that this is not the case. Example 4.2. Let (R+,‖.‖ R + ) be the biBanach norm-weightable space of Example 3.6. Denote by D the extended quasi-metric of uniform convergence of (C∗ R +,d‖.‖C∗ ). Define a sequence (Gk)k∈N of functions from ω to C ∗ R + by Gk(m) := { 2mχm if m ≥ k 0 otherwise for all m ∈ ω (here, χm denotes the characteristic function of {m}). Note that for each k ∈ N and each m,n ∈ ω, we have (Gk+1(m))(n) ≤ (Gk(m))(n), so D(Gk,Gk+1) = sup{d‖.‖C∗ (Gk(m),Gk+1(m)) | m ∈ ω} = 0 for all k ∈ N. Hence, (Gk)k∈N is a left K-Cauchy sequence with respect to D. Since, for each k ∈ N, (Gk(k))(k) = 2k and (Gk+1(k))(k) = 0, we deduce that (Gk)k∈N is not a Cauchy sequence in the extended metric Ds. We conclude that D is not Smyth completable and, thus, it is not Smyth complete. Duality and quasi-normability for complexity spaces 109 Let (X,d) be a quasi-pseudometric space and denote by P0(X) the collection of all nonempty subsets of X. According to [1], the extended Hausdorff quasi- pseudometric of d on P0(X) is defined by dH(A,B) = max{sup a∈A d(a,B), sup b∈B d(A,b)} whenever A,B ∈P0(X). Our next example shows that the if (C∗F ,d‖.‖C∗ ) is the dual complexity space (of (F,‖.‖F )), the extended Hausdorff quasi-pseudometric of the Smyth com- plete quasi-metric d‖.‖C∗ is not Smyth completable, in general. Example 4.3. Let (R+,‖.‖ R + ) be the biBanach norm-weightable space of Example 3.6. As in Example 4.2 define a sequence (Gk)k∈N of functions from ω to C∗ R + by Gk(m) := { 2mχm if m ≥ k 0 otherwise for all m ∈ ω. Then (Aj)j∈N is a sequence in P0(C∗R+ ), where Aj = {Gk(m) | k ≥ j, m ∈ ω} for all j ∈ N. Fix j ∈ N and let Gk(m) ∈ Aj. Since (Gk+1(m))(n) ≤ (Gk(m))(n) for all n ∈ ω and Gk+1(m) ∈ Aj+1, we deduce that d‖.‖C∗ (Gk(m),Aj+1) = 0. Similarly, for each Gk(m) ∈ Aj+1, d‖.‖C∗ (Aj,Gk(m)) = 0. Hence, ((d‖.‖C∗ )H)(Aj,Aj+1) = 0 for all j ∈ N, and, thus, (Aj)j∈N is a left K-Cauchy sequence with respect to the extended Hausdorff quasi-pseudometric of d‖.‖C∗ . Nevertheless, ((d‖.‖C∗ )H)(Aj+1,Aj) = 1 for all j ∈ N, because d‖.‖C∗ (Aj+1,Gj(j)) = 1. So the extended Hausdorff quasi-peudometric of d‖.‖C∗ is not Smyth completable on P0(C ∗ R + ). However, several interesting kinds of dual complexity (sub)spaces have Smyth completable extended Hausdorff quasi-pseudometrics (actually totally bounded) as we shall show. Indeed, it follows from results of Künzi and Ryser [14, Corollaries 2 and 9], that the extended Hausdorff quasi-pseudometric on P0(X) of a totally bounded (resp. totally bounded and bicomplete) quasi-pseudometric d on a set X, is to- tally bounded (resp. totally bounded and bicomplete). Combining these results with Theorems 3.22 and 3.24, respectively, we obtain: Proposition 4.4. Let (F,‖.‖F ) be a biBanach norm-weightable space such that ≤d‖.‖F is linear and let F ⊆C ∗ F . If (F,d‖.‖C∗ ) has a lower bound, then the extended Hausdorff quasi-pseudometric of d‖.‖C∗ is totally bounded on P0(F). 110 S. Romaguera and M. Schellekens Proposition 4.5. Let (F,‖.‖F ) be a biBanach norm-weightable space such that ≤d‖.‖F is linear, let L ∈ C ∗ F and F a closed subset of (C ∗ F , (d‖.‖C∗ ) s). Then the extended Hausdorff quasi-pseudometric of d‖.‖C∗ is totally bounded and bicomplete on P0(FL). Hence, the (hyper)space (P0(FL), ((d‖.‖C∗ )H) s) is compact. Let us recall that the Vietoris topology of a topological space (X,T) is defined as the topology on P0(X) which as a subbase the collection of sets of the form V + = {A ∈P0(X) | A ⊆ V} and W− = {A ∈P0(X) | A∩W 6= ∅}, whenever V and W are open sets in (X,T). Let (X,T) be a quasi-pseudometrizable space and let d be any quasi-pseudo- metric on X compatible with T . It is well known (see [1]) that the topology generated by the extended Hausdorff quasi-pseudometric of d is finer than the Vietoris topology on the collection of all nonempty compact subsets of (X,T(d)). In [2] it is given an example of a compact quasi-metric space (X,d) for which the topology of the extended Hausdorff quasi-pseudometric of d is strictly finer than the Vietoris topology of (X,T(d)) on the collection of all nonempty compact subsets of (X,T(d)). However, we can prove that the two topologies coincide when one works on the collection Ks0(X) of all nonempty compact subsets of the pseudometric space (X,ds). It is easy to see that the restriction of the extended Hausdorff quasi-pseudometric to Ks0(X) is actually a quasi-pseudometric. Proposition 4.6. Let (X,d) be a quasi-pseudometric space. Then the Vietoris topology of (X,T(d)) coincides with the topology generated by the Hausdorff quasi-pseudometric of d on Ks0(X). Proof. Let A ∈ Ks0(X) and choose an arbitrary ε > 0. Then, there is a finite subset Aε of A such that A ⊆∪a∈Aε(Sd)s(a,ε/4). Then, the sets V + |Ks0(X)= {B ∈K s 0(X) | B ⊆ ⋃ a∈Aε Sd(a,ε/4)} and W− |Ks0(X)= {B ∈K s 0(X) | B ∩Sd(a,ε/4) 6= ∅ for all a ∈ Aε} are open neighborhoods of A with respect to the Vietoris topology of (X,T(d)) on Ks0(X). Denote their intersection by G. We shall show that G ⊆ SdH (A,ε). Indeed: Let B ∈ G. Choose any a ∈ A. Then, ds(a,aε) < ε/4 for some aε ∈ Aε. Moreover, there is a b ∈ B such that d(aε,b) < ε/4. Therefore, d(a,b) < ε/2. So, supa∈A d(a,B) ≤ ε/2. Now, choose any b ∈ B. Then, there is an a ∈ Aε such that d(a,b) < ε/4. Hence, supb∈B d(A,b) ≤ ε/4. Consequently, SdH (A,B) ≤ ε/2. We conclude that the Vietoris topology of (X,T(d)) coincides with the topology of dH on Ks0(X). � As a consequence of the preceding proposition and Corollary 3.25, we obtain the following Corollary 4.7. Let (F,‖.‖F ) be a biBanach norm-weightable space such that ≤d‖.‖F is linear. Then, the Vietoris topology of the dual complexity space Duality and quasi-normability for complexity spaces 111 (C∗F ,d‖.‖C∗ ) coincides with the topology generated by the Hausdorff quasi-pseudo- metric of d‖.‖C∗ on the collection of subsets of P0(C ∗ F ) defined by {(C ∗ F ) L | L ∈ C∗F}. References [1] G. Berthiaume, On quasi-uniform hyperspaces, Proc. Amer. Math. Soc. 66 (1977), 335– 343. [2] J. Cao, H.P.A. Künzi, I.L. Reilly and S. Romaguera, Quasi-uniform hyperspaces of compact subsets, Topology Appl. 87 (1998), 117–126. [3] M. Davis, R. Sigal and E.J. Weyuker, Computability, Complexity and Languages, Aca- demic Press, 1994. [4] E. P. Dolzhenko and E. A. Sevast’yanov, Sign-sensitive approximations, the space of sign-sensitive weight. The rigidity and the freedom of a system, Russian Acad. Sci. Dokl. Math. 48 (1994), 397–401. [5] J. Ferrer, V. Gregori and C. Alegre, Quasi-uniform structures in linear lattices, Rocky Mountain J. Math. 23 (1993), 877–884. [6] R. C. Flagg and R. D. Kopperman, The asymmetric topology of Computer Science, in: Proc. MFPS 9, S. Brooks et al. editors, Lectures Notes in Computer Science, 802, Springer-Verlag, 1993, 544–553. [7] P. Fletcher and W. F. Lindgren, Quasi-Uniform Spaces, Marcel Dekker, New York, 1982. [8] G. Gierz, K. H. Hofmann, K. Keimel, J. D. Lawson, M. Misolave and D. S. Scott, A Compendium of Continuous Lattices, Springer-Verlag, Berlin, Heidelberg, 1980. [9] N. Jones, Computability and Complexity from a Programming Perspective, Foundations of Computing series, MIT press, 1997. [10] K. Keimel and W. Roth, Ordered Cones and Approximation, Springer-Verlag, Berlin, Heidelberg, 1992. [11] D. Knuth, The Art of Computer Programming, Vol 3, Addison-Wesley, 1973. [12] H. P. A. Künzi, Nonsymmetric topology, in: Proc. Colloquium on topology, 1993, Szekszárd, Hungary, Colloq. Math. Soc. János Bolyai Math. Studies, 4 (1995), 303– 338. [13] H. P. A. Künzi and S. Romaguera, Spaces of continuous functions and quasi-uniform convergence, Acta Math. Hungar. 75 (1997), 287–298. [14] H. P. A. Künzi and C Ryser, The Bourbaki quasi-uniformity, Topology Proc. 20 (1995), 161–183. [15] H. P. A. Künzi and V. Vajner, Weighted quasi-metric spaces, in: Proc. 8th Summer Conference on General Topology and Appl., Ann. New York Acad. Sci. 728 (1994), 64–77. [16] S. G. Matthews, Partial metric topology, in: Proc. 8th Summer Conference on General Topology and Appl., Ann. New York Acad. Sci. 728 (1994), 183–197. [17] I. L. Reilly, P. V. Subhramanyam and M. K. Vamanamurthy, Cauchy sequences in quasi-pseudo-metric spaces, Monatsh. Math. 93 (1982), 127–140. [18] S. Romaguera, Left K-completeness in quasi-metric spaces, Math. Nachr. 157 (1992), 15–23. [19] S. Romaguera, On hereditary precompactness and completeness in quasi-uniform spaces, Acta Math. Hungar. 73 (1996), 159–178. [20] S. Romaguera and M. Ruiz-Gómez, Bitopologies and quasi-uniformities on spaces of continuous functions, Publ. Math. Debrecen 47 (1995), 81–93. [21] S. Romaguera and M. Sanchis, Semi-Lipschitz functions and best approximation in quasi-metric spaces, J. Approx. Theory 103 (2000), 292-301. [22] S. Romaguera and M. Schellekens, Quasi-metric properties of complexity spaces, Topol- ogy Appl. 98 (1999), 311–322. 112 S. Romaguera and M. Schellekens [23] M. Schellekens, The Smyth completion: a common foundation for denotational seman- tics and complexity analysis, in: Proc. MFPS 11, Electronic Notes in Theoretical Com- puter Science 1 (1995), 211-232. [24] M. Schellekens, On upper weightable spaces, in: Proc. 11th Summer Conference on General Topology and Appl., Ann. New York Acad. Sci. 806 (1996), 348–363. [25] M. Schellekens, Complexity spaces revisited. Extended abstract, in: Proc. 8th Prague Topological Symposium, Topology Atlas, 1996, 337–348. [26] M. Schellekens, The correspondence between partial metrics and semivaluations, Theo- retical Computer Sci., to appear. [27] M. B. Smyth, Quasi-uniformities: Reconciling domains with metric spaces, in: Proc. MFPS 3, LNCS 298, M. Main et al. editors, Springer, Berlin 1988, 236–253. [28] M. B. Smyth, Totally bounded spaces and compact ordered spaces as domains of com- putation, in: Topology and Category Theory in Computer Science, G.M. Reed, A.W. Roscoe and R.F. Wachter editors, Clarendon Press, Oxford 1991, 207–229. [29] Ph. Sünderhauf, The Smyth-completion of a quasi-uniform space, in: M. Droste and Y. Gurevich editors, Semantics of Programming Languages and Model Theory, Algebra, Logic and Appl., 5, Gordon and Breach Sci. Publ., 1993, 189–212. Received April 2001 Revised August 2001 S. Romaguera Departamento de Matemática Aplicada Universidad Politécnica de Valencia Apartado 22012 46022 Valencia Spain E-mail address : sromague@mat.upv.es M. Schellekens Department of Computation National University of Ireland Cork, Ireland E-mail address : m.schellekens@cs.ucc.ie