<p>It has been a while, but if I recall correctly, the following paper should be useful in answering the question:</p>
<blockquote>
<p>Andrej Bauer, Gordon Plotkin, Dana S. Scott: <a href="https://doi.org/10.1016/j.tcs.2014.02.042" rel="nofollow noreferrer">Cartesian closed categories of separable Scott domains</a>, Theoretical Computer Science, Volume 546, 2014, Pages 17-29</p>
</blockquote>
<p>(In particular, search for &quot;bilimit&quot;, there are some useful remarks.)</p>
<p>What ought to happen is that starting with <span class="math-container">$D_0$</span> whose coherence number (as defined in the paper) is <span class="math-container">$\alpha$</span>, in many cases the resulting <span class="math-container">$D_\infty$</span> should be universal for the <span class="math-container">$\alpha$</span>-coherent domains. But this is only an informed guess that is probably not 100% correct, perhaps the claim only holds for <span class="math-container">$\alpha &lt; \omega$</span> or some such. Nevertheless, I expect the situation to be analyzable with the tools developed in the paper.</p>
<p>Let's look at two examples. First, if we start with <span class="math-container">$D_0 = \{\bot, \top\}$</span> then <span class="math-container">$D_\infty$</span> will be a countably-based algebraic lattice. If we can show that <span class="math-container">$\mathcal{P}(\omega)$</span> is a retract of <span class="math-container">$D_\infty$</span> (which sounds plausible) then it should easily follow that <span class="math-container">$D_\infty$</span> is universal for countably-based algebraic lattices.</p>
<p>Second, if we start with <span class="math-container">$D_0 = \mathbb{N}_\bot$</span>, then my guess is that <span class="math-container">$D_\infty$</span> will be universal for 2-coherent domains, because the coherence number of <span class="math-container">$\mathbb{N}_\bot$</span> is <span class="math-container">$2$</span>. There are enough lemmas in the paper to get you started on figuring this out.</p>
<p>I hope this is going to be enough help. I am not really inclined to do real thinking, as it looks like it will take a couple of days. Do let us know if you come to any useful conclusions!</p>

CC BY-SA 4.0
2024-07-21T23:55:27.123Z
Thank you so much. for the reference to your paper and discussion how it's applicable to my problem. Needless to say, it'll take me more than the "couple of days" it would take you to begin to get anywhere useful (though what I was hoping to conversely show is that $D_\infty$ is a retract of $\mathcal{P}(\omega)$, which I'd thought was likely plausible).
John Forkosh
CC BY-SA 4.0
2024-07-22T08:16:32.030Z
$D_\infty$ is a retract of $\mathcal{P}(\omega)$ if, and only if, $D_0$ is a countably-based algebraic lattice (such as $\{\bot, \top\}$).
Andrej Bauer
CC BY-SA 4.0
2024-07-22T12:36:40.280Z
Thanks for the very interesting constraint on $D_0$ that's necessary (and sufficient) such that the $D_\infty$ limit is a proper subdomain of $\mathcal{P}(\omega)$. I was very much looking for $D_\infty$ to be a proper subdomain of $\mathcal{P}(\omega)$, but was completely unaware of that (or of any such) condition. So it's very, very interesting to learn about, indeed.
John Forkosh
CC BY-SA 4.0
2024-07-22T13:09:03.990Z
It's not that hard to see: If $D_0$ is a countably-based algebraic lattice then $D_\infty$ will be as well, but $P(\omega)$ is universal for countably-based algebraic lattices, so $D_\infty$ is a retract of it. Conversely, if $D_\infty$ is a retract of $P(\omega)$ then so is $D_0$ (because $D_0$ is a retract of $D_\infty$), but every retract of a lattice is a lattice.
Andrej Bauer
CC BY-SA 4.0
2024-07-21T21:45:34.690Z
2024-07-22T08:42:51.770Z
2024-07-22T08:42:51.770Z
Andrej Bauer
<p>Is Scott's <span class="math-container">$D_\infty$</span> a universal domain like <span class="math-container">$\mathcal{P}\omega$</span> ?<br>
If not universal, is there a (sensible-looking) embedding/projection pair
<span class="math-container">$e/p$</span> to/from <span class="math-container">$\mathcal{P}\omega$</span>? Or choose any other universal domain
<span class="math-container">$U$</span> (e.g., interval domain <span class="math-container">$U\ =\ \mathbf{I}\mathbb{R}$</span>) you like that
permits a more sensible-looking <span class="math-container">$e/p$</span>.</p>
<p>If that can be done, then can it also be done for each iteration of
Scott's <span class="math-container">$D_{n+1}=[D_n\to D_n]$</span> construction, i.e., <span class="math-container">$e_n/p_n$</span> for <span class="math-container">$D_n$</span>?
And in this case, I'd rather not start with Scott's <span class="math-container">$D_0=\mathbb{N_\bot}$</span>,
but instead with the two-element <span class="math-container">$D_0=\{\bot,\top\}$</span>, e.g., as illustrated
at the top of page 5 in<br>    
<a href="https://www.cs.cornell.edu/courses/cs6110/2011sp/lectures/lecture24.pdf" rel="nofollow noreferrer">https://www.cs.cornell.edu/courses/cs6110/2011sp/lectures/lecture24.pdf</a><br>
(Note that the <span class="math-container">$e_n/p_n$</span> discussed there are not to/from <span class="math-container">$\mathcal{P}\omega$</span>.)<br>
Thanks.</p>

CC BY-SA 4.0
2024-07-21T22:08:06.153Z
How is the interval domain universal? That sounds improbable to me.
Andrej Bauer
CC BY-SA 4.0
2024-07-21T23:38:24.277Z
@AndrejBauer Thanks for your answer below. $\mathbf{I}\mathbb{R}$ is discussed in detail, and shown universal, in Chapter 7 of Stoltenberg-Hansen, et al, https://prism.librarymanagementcloud.co.uk/yorksj/items/dda-43/CR9781139166386 (though a slightly more general definition is given by, e.g., https://www.entcs.org/mislove/oxford06.pdf). P.S. I have a legit hardback copy of Stoltenberg-Hansen, but if needed, you can check it out at, e.g., http://libgen.rs/book/index.php?md5=290C8ECFCC5A1DB0BB8687BE99CE7FA6
John Forkosh
CC BY-SA 4.0
2024-07-22T08:17:56.217Z
Stoltenberg-Hansen does not discuss universality of $\mathbf{I}\mathbb{R}$, they describe a different domain, from what I remember, whose elements are collections of disjoint half-open intervals. I'll double check.
Andrej Bauer
CC BY-SA 4.0
2024-07-22T08:24:59.713Z
Yup, I double-checked The universal domain described by Stoltenberg-Hansen is the ideal completion of the domain of *finite unions of half-open intervals*. This is **not** the interval domain. And Mislove's slides have nothing to do with universal domain (they just contain the definition of the interval domain.)
Andrej Bauer
CC BY-SA 4.0
2024-07-22T12:17:27.820Z
@AndrejBauer Thanks again. Yup, my bad. My handwritten marginal notes in Stoltenberg-Hansen mention Mislove next to Def.7.1.1 only because I'd noticed their (maybe not-so-slight) difference in definitions of $\mathbf{I}\mathbb{R}$, and so haven't been sure of the "canonical" definition until now. Anyway, I'd mentioned using a universal domain $U$ other than $\mathcal{P}(\omega)$ only with respect to _"sensible-looking"_, since it seemed (to me) that encoding (and preserving the structure of) elements of $D_n,n=0,1,2,\ldots$ as subsets of  $\mathbb{N}$ could get awfully _"messy-looking"_.
John Forkosh
<domain-theory>
Is $D_\infty$ a universal domain?
John Forkosh
# Is $D_\infty$ a universal domain?

(Asked by: username_0 on 2024-07-21)

Is Scott's $D\_\infty$ a universal domain like $\mathcal{P}\omega$ ?  
If not universal, is there a (sensible-looking) embedding/projection pair
$e/p$ to/from $\mathcal{P}\omega$? Or choose any other universal domain
$U$ (e.g., interval domain $U\ =\ \mathbf{I}\mathbb{R}$) you like that
permits a more sensible-looking $e/p$.

If that can be done, then can it also be done for each iteration of
Scott's $D\_{n+1}=[D\_n\to D\_n]$ construction, i.e., $e\_n/p\_n$ for $D\_n$?
And in this case, I'd rather not start with Scott's $D\_0=\mathbb{N\_\bot}$,
but instead with the two-element $D\_0=\{\bot,\top\}$, e.g., as illustrated
at the top of page 5 in  
    
<https://www.cs.cornell.edu/courses/cs6110/2011sp/lectures/lecture24.pdf>  
(Note that the $e\_n/p\_n$ discussed there are not to/from $\mathcal{P}\omega$.)  
Thanks.

**Tags:** domain-theory

> **Comments:**
> **username_1**: How is the interval domain universal? That sounds improbable to me.  
> **username_0**: @AndrejBauer Thanks for your answer below. $\mathbf{I}\mathbb{R}$ is discussed in detail, and shown universal, in Chapter 7 of Stoltenberg-Hansen, et al, https://prism.librarymanagementcloud.co.uk/yorksj/items/dda-43/CR9781139166386 (though a slightly more general definition is given by, e.g., https://www.entcs.org/mislove/oxford06.pdf). P.S. I have a legit hardback copy of Stoltenberg-Hansen, but if needed, you can check it out at, e.g., http://libgen.rs/book/index.php?md5=290C8ECFCC5A1DB0BB8687BE99CE7FA6  
> **username_1**: Stoltenberg-Hansen does not discuss universality of $\mathbf{I}\mathbb{R}$, they describe a different domain, from what I remember, whose elements are collections of disjoint half-open intervals. I'll double check.  
> **username_1**: Yup, I double-checked The universal domain described by Stoltenberg-Hansen is the ideal completion of the domain of *finite unions of half-open intervals*. This is **not** the interval domain. And Mislove's slides have nothing to do with universal domain (they just contain the definition of the interval domain.)  
> **username_0**: @AndrejBauer Thanks again. Yup, my bad. My handwritten marginal notes in Stoltenberg-Hansen mention Mislove next to Def.7.1.1 only because I'd noticed their (maybe not-so-slight) difference in definitions of $\mathbf{I}\mathbb{R}$, and so haven't been sure of the "canonical" definition until now. Anyway, I'd mentioned using a universal domain $U$ other than $\mathcal{P}(\omega)$ only with respect to _"sensible-looking"_, since it seemed (to me) that encoding (and preserving the structure of) elements of $D_n,n=0,1,2,\ldots$ as subsets of  $\mathbb{N}$ could get awfully _"messy-looking"_.  

---

## 1 answers

### Answer by username_1 on 2024-07-21. Score: 3 | Accepted answer

It has been a while, but if I recall correctly, the following paper should be useful in answering the question:

> username_1, Gordon Plotkin, Dana S. Scott: [Cartesian closed categories of separable Scott domains](https://doi.org/10.1016/j.tcs.2014.02.042), Theoretical Computer Science, Volume 546, 2014, Pages 17-29

(In particular, search for "bilimit", there are some useful remarks.)

What ought to happen is that starting with $D\_0$ whose coherence number (as defined in the paper) is $\alpha$, in many cases the resulting $D\_\infty$ should be universal for the $\alpha$-coherent domains. But this is only an informed guess that is probably not 100% correct, perhaps the claim only holds for $\alpha < \omega$ or some such. Nevertheless, I expect the situation to be analyzable with the tools developed in the paper.

Let's look at two examples. First, if we start with $D\_0 = \{\bot, \top\}$ then $D\_\infty$ will be a countably-based algebraic lattice. If we can show that $\mathcal{P}(\omega)$ is a retract of $D\_\infty$ (which sounds plausible) then it should easily follow that $D\_\infty$ is universal for countably-based algebraic lattices.

Second, if we start with $D\_0 = \mathbb{N}\_\bot$, then my guess is that $D\_\infty$ will be universal for 2-coherent domains, because the coherence number of $\mathbb{N}\_\bot$ is $2$. There are enough lemmas in the paper to get you started on figuring this out.

I hope this is going to be enough help. I am not really inclined to do real thinking, as it looks like it will take a couple of days. Do let us know if you come to any useful conclusions!

> **Comments:**
> **username_0**: Thank you so much. for the reference to your paper and discussion how it's applicable to my problem. Needless to say, it'll take me more than the "couple of days" it would take you to begin to get anywhere useful (though what I was hoping to conversely show is that $D_\infty$ is a retract of $\mathcal{P}(\omega)$, which I'd thought was likely plausible).  
> **username_1**: $D_\infty$ is a retract of $\mathcal{P}(\omega)$ if, and only if, $D_0$ is a countably-based algebraic lattice (such as $\{\bot, \top\}$).  
> **username_0**: Thanks for the very interesting constraint on $D_0$ that's necessary (and sufficient) such that the $D_\infty$ limit is a proper subdomain of $\mathcal{P}(\omega)$. I was very much looking for $D_\infty$ to be a proper subdomain of $\mathcal{P}(\omega)$, but was completely unaware of that (or of any such) condition. So it's very, very interesting to learn about, indeed.  
> **username_1**: It's not that hard to see: If $D_0$ is a countably-based algebraic lattice then $D_\infty$ will be as well, but $P(\omega)$ is universal for countably-based algebraic lattices, so $D_\infty$ is a retract of it. Conversely, if $D_\infty$ is a retract of $P(\omega)$ then so is $D_0$ (because $D_0$ is a retract of $D_\infty$), but every retract of a lattice is a lattice.  

---

