I am a bit stubborn. In my first post on ideal domains, I thought I would be able to extend Keye Martin’s result from metric to quasi-metric spaces. I have said I had failed, but now I think I have succeeded. This leads to a notion that I will call a quasi-ideal domain.
Our purpose today is to show that, if X is a continuous Yoneda-complete quasi-metric space, then it embeds into an algebraic dcpo, and in fact, in a very specific way: as the subspace of limit elements of a quasi-ideal domain.
The elements of that quasi-ideal domain will again be certain formal balls, and will look very much like Keye Martin’s BD(X, d). If you refer to the first post, the main difference will be that our ordering ⊑ will be such that (x, 0) ⊑ (y, 0) whenever x ≤ y — that was not the case before.
Embedding continuous Yoneda-complete spaces into algebraic domains
Let us therefore define (x, r) ⊏ (y, s) iff:
- either (x, r) ≪ (y, s) and r ≥ 2s
- or r=s=0 and x ≤ y (i.e.,d(x, y)=0, or equivalently, (x, 0) ≤ (y, 0)).
Note that I wrote ⊏, not ⊑: ⊏ is a kind of strict part of ⊑. Now define (x, r) ⊑ (y, s) iff (x, r) ⊏ (y, s) or (x, r) = (y, s). With that correction, ⊑ is reflexive, and a painful case analysis shows that it is transitive. Also, ⊑ implies ≤, so the relation is antisymmetric, hence an ordering. Fine.
Let me reuse our former name, and call BD(X) the set of formal balls with the ordering ⊑.
Lemma. For every Yoneda-complete quasi-metric space X, BD(X) is a dcpo, and in fact one in which directed suprema are computed exactly as in B(X).
Proof. There is a similar lemma in Ideal Models I, namely the very first one, although it only applied to complete metric spaces. I had mentioned that the only place where we needed X to be metric was the last line, and this misfortune is now repaired by our new definition of ⊑.
We take a family (xi, ri)i ∈ I in BD(X) that is directed with respect to ⊑, and we let (x, r) = (d-lim xi, inf ri) be its supremum in B(X). (We are using the Kostanek-Waszkiewicz Theorem here.) We must show that (x, r) is also its supremum with respect to ⊑. If the supremum is reached, that is clear. Otherwise, we still have a few cases to distinguish. If ri=0 for i large enough, then we can consider the subfamily of formal balls (xi, ri) with ri=0, and since ⊑ and ≤ coincide on them, we are done.
The final case is where ri>0 for every i. In that case, using the same trick as Ideal Models I, every (xi, ri) is ⊏ some (xj, rj). This implies that r=0, and also that (x, r)=(x, 0) is an upper bound of the family (with respect to ⊑): for every i, (xi, ri) ⊏ (xj, rj) ≤ (x, r) = (x, 0), so (xi, ri) ≪ (x, 0), namely (xi, ri) ⊏ (x, r) by the first clause of the definition of ⊏.
If (y, s) is another upper bound of (xi, ri)i ∈ I (with respect to ⊑), then it is also an upper bound with respect to ≤, so (x, r) ≤ (y, s). In particular, s=0. Since also r=0, using the second clause of the definition of ⊏, (x, r) ⊑ (y, s). ☐
Lemma. For every continuous Yoneda-complete quasi-metric space X, d, the finite elements of BD(X) are those of the form (x, r), r≠0.
Recall that a quasi-metric space is continuous Yoneda-complete if and only if its (ordinary) poset of formal balls is a continuous dcpo.
The proof is the same as for the second and third lemmas of Ideal Models I. For later reference, we recall how we show that no element (x, 0) is finite in BD(X). Since X is continuous Yoneda-complete, (x, 0) is the supremum of a directed family D = (xi, ri)i ∈ I in B(X) with (xi, ri) ≪ (x, 0) for each i. (We shall need to remember that this implies ri>0.) The way-below relation ≪ is the one from B(X). The family D is directed in B(X) (with respect to ≤) but not necessarily with respect to ⊑. We build another family with the same supremum, which is directed with respect to ⊑. This is a family of formal balls (xI, rI), where I ranges over the finite subsets of D. Each is an element of D, and is above every element of I in the ⊑ ordering. It is also above (xJ, rJ) in the ⊑ ordering, for every proper subset J of I, and that ensures that the family of formal balls (xI, rI) is directed with respect to ⊑. Once this is done, if (x, 0) were finite in BD(X), we would have (x, 0) ⊑ (xI, rI) for some I, and that is impossible since rI>0.
Theorem. Let X, d be a continuous Yoneda-complete quasi-metric space. Then X, with the d-Scott topology, is homeomorphic to the subspace of non-finite elements of the algebraic dcpo BD(X).
Proof. The previous lemma shows that the non-finite elements of BD(X) are the formal balls (x, 0), which are in bijection with the points x of X. By the paragraph right before the statement of the theorem, (x, 0) is the supremum of a family of formal balls, with non-zero radii, and which is directed in BD(X), namely with respect to ⊑. That shows that BD(X) is algebraic.
The rest of the proof is exactly the same as in the corresponding theorem in Ideal Models I. Let us call, temporarily, the D-Scott topology the topology induced by the inclusion of X into BD(X).
An open subset U of X in the d-Scott topology is the intersection of X with a Scott-open subset V of B(X). Since ⊑ implies ≤, and since directed suprema are computed in BD(X) as in B(X), V is Scott-open in BD(X), hence U is D-Scott open.
Conversely, let U be a D-Scott open subset of X. For every x ∈ U, there is a formal ball (y, r) ⊑ (x, 0) with r≠0 such that every formal ball (z, 0) such that (y, r) ⊑ (z, 0) is in U. Since r≠0, (y, r) ≪ (x, 0). For every element z such that (y, r) ≪ (z, 0), we plainly observe that (y, r) ⊑ (z, 0), so (z, 0) is in U. It follows that the intersection of X with ↟(y, r) contains (x, 0) and is included in U, showing that U is d-Scott-open. ☐
Quasi-ideal domains
As we shall see, BD(X) has extra properties that make it look even more like Keye Martin’s ideal domains.
Let me make a parenthesis, which might otherwise act as a motivation for the whole construction.
Daniele Varacca once asked me whether the following notion had a name: algebraic domains where every element below a finite element is itself finite. That seems like it should be a natural notion, but I don’t think I’ve seen that anywhere in the literature. The closest is the notion of a dI-domain, where we require a lot more: in a dI-domain, every finite point must have only finitely many points below it—in particular those points will all be finite; a dI-domain is also required to be bounded-complete algebraic, with the property that binary suprema of bounded pairs distribute over binary meets, and we will certainly not make any of those assumptions.
Let me call quasi-ideal domain any algebraic dcpo in which every element below a finite element is finite. Clearly, every ideal domain satisfies that property. In a quasi-ideal domain, the non-finite elements may fail to be maximal, as the following example shows.
Fact. For every set A, the powerset P(A) is quasi-ideal domain. If A is infinite, then P(A) is not an ideal domain.
(The finite elements are the finite subsets of A, and certainly any subset of A that is included in a finite subset is itself finite.)
Anyway, a quasi-ideal domain has just two layers: a lower layer of finite elements, and an upper layer of non-finite elements which can all be obtained as directed suprema of elements from the lower layer.
I will call the non-finite elements the limit elements of the quasi-ideal domain.
As you can see, BD(X) is one example of such a quasi-ideal domain: if (x, r) ⊑ (y, s) where (y, s) is finite (i.e., s≠0), then (x, r) ≤ (y, s), whence r ≥ s > 0, and therefore (x, r) is finite as well.
We can then rephrase the previous theorem under the following much stronger form.
Theorem. Let X, d be a continuous Yoneda-complete quasi-metric space. Then X, with the d-Scott topology, is homeomorphic to the subspace of limit elements of the quasi-ideal domain BD(X).
ω-continuous Yoneda-complete quasi-metric spaces
Can we refine all that when X is second-countable in its d-Scott topology? I do not know yet, but we can if we assume a stronger property, which (by analogy with our notion of continuity for Yoneda-complete quasi-metric spaces) I will call ω-continuity.
Call a Yoneda-complete quasi-metric space X, d ω-continuous if and only if its dcpo of formal balls is… ω-continuous.
Recall that a dcpo is called ω-continuous if and only if it has a countable basis. By Norberg’s Lemma 7.7.13, this is equivalent to its Scott topology being second-countable. In particular, every ω-continuous Yoneda-complete quasi-metric space is both continuous Yoneda-complete and second-countable in its d-Scott topology. (I have not been able to show that, conversely, every second-countable continuous Yoneda-complete quasi-metric space is ω-continuous, and I would be surprised if that were true.)
Now we can refine everything we have done earlier. Fix a basis B of B(X, d), which typically will be countable for an ω-continuous Yoneda-complete quasi-metric space X, d. Define B‘D(X, d) as the following variant of BD(X, d):
- The elements of B‘D(X, d) are the formal balls in the basis B, plus the formal balls of the form (x, 0), x ∈ X.
- The ordering ⊑ is defined as before: (x, r) ⊑ (y, s) iff (x, r) ⊏ (y, s) or (x, r) = (y, s), where (x, r) ⊏ (y, s) iff either (x, r) ≪ (y, s) and r ≥ 2s, or r=s=0 and x ≤ y.
Lemma. For every ω-continuous Yoneda-complete quasi-metric space X, B‘D(X) is a dcpo, and in fact one in which directed suprema are computed exactly as in B(X).
This is proved exactly as our first lemma on BD(X). The important new thing to check is that, given a family (xi, ri)i ∈ I in B‘D(X) that is directed with respect to ⊑, then its sup in B(X) will always be in B‘D(X), that is, it will either be in the basis B or have radius 0. This follows from the case analysis we have already done in our previous similar lemma.
Lemma. For every ω-continuous Yoneda-complete quasi-metric space X, d, the finite elements of B‘D(X) are those of the form (x, r), r≠0, namely those of the basis B.
That is again proved as before.
As a corollary, we obtain the following variant of our first Theorem: Let X, d be a continuous Yoneda-complete quasi-metric space, and fix a basis B of its dcpo of formal balls. Then X, with the d-Scott topology, is homeomorphic to the subspace of non-finite elements of the algebraic dcpo B‘D(X), and the finite elements of the latter are exactly the formal balls in B with non-zero radius. That is, again, proved as before.
When B is countable, that implies that B‘D(X) has countably many finite elements:
Theorem. Let X, d be an ω-continuous Yoneda-complete quasi-metric space. Then X, with the d-Scott topology, is homeomorphic to the subspace of non-finite elements of the ω-algebraic dcpo BD(X).
Let us rephrase that in the language of ideal completion remainders (see Ideal Models II): Every ω-continuous Yoneda-complete quasi-metric space is the ideal completion remainder of a countable poset.
We have seen that the ideal completion remainders of countable posets are the quasi-Polish spaces (a theorem due to Matthew de Brecht). We therefore obtain:
Theorem. The topological spaces underlying the ω-continuous Yoneda-complete quasi-metric spaces (with the d-Scott topology) are exactly the same as those underlying the separable Smyth-complete quasi-metric spaces (with the open ball topology — which in fact coincides with the d-Scott topology in that case), namely the quasi-Polish spaces.
That finally answers one of the questions I had about the definition of quasi-Polish spaces: why should we consider Smyth-complete spaces instead of, say, Yoneda-complete spaces to define them?
The answer is, provided we take ω-continuous Yoneda-complete spaces, and take care of using the d-Scott topology (the right topology, in all situations that I know of):
this does not matter.
— Jean Goubault-Larrecq (March 10th, 2016)