Separating domains from algebraic domains

Xiaodong Jia, Qingguo Li, Wei luan · 2025

Read Separating domains from algebraic domains by Xiaodong Jia, Qingguo Li, Wei luan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-04189.txt.

Introduction

Xiaodong Jia, Qingguo Li, and Wei Luan settle a structural question about domains in a 2025 paper. Domains are ordered spaces used to give meaning to programs, and the algebraic kind, built from compact pieces, is the tractable kind. The authors prove that any domain failing to be algebraic holds the whole unit interval inside it, as a Scott-continuous retract. One payoff lands at once: every countable domain is algebraic, since a countable space cannot hide an interval in that way.

Catalog record

CREATORXiaodong Jia, Qingguo Li, Wei luan
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE6 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-04189

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Separating domains from algebraic domains
Xiaodong Jia, Qingguo Li, Wei luan

Abstract
. We prove that every domain that fails to be algebraic admits the unit interval [ 0 , 1 ] [0,1] as its Scott-continuous retract. As a result, every countable domain is algebraic.



1991 Mathematics Subject Classification
54B10; 06B35; 06F30, 06A06.

Domain theory
[
2
,
1
,
3
]
, initially invented by Dana Scott, is a theory that studies the structure of different semantic domains and is applied, in particular, to denotational semantics to model programming languages
[
4
]
.

Domains, in a nutshell, are
d
irected-
c
omplete
po
sets (dcpo’s, for short) on which the
way-below relation
is
approximating
. Concretely, a dcpo
P
is a partially ordered set
(P,\leq)
in which every directed subset has a supremum. The way-below relation (in symbol
\ll
) on
P
is defined as
x\ll y
if for every directed subset
D
of
P
, that
y\leq\sup D
implies that
x\leq d
for some
d\in D
. The relation
\ll
on
P
is approximating if the set
\{x\in P\mid x\ll p\}
is a directed set with
p
as its supremum for all
p\in P
. That is,
P
is a domain if and only if
\{x\in P\mid x\ll p\}
is directed and
p=\sup\{x\in P\mid x\ll p\}
for all
p\in P
. Finite posets are examples of domains. The unit interval
[0,1]
is a domain with the usual ordering, and one could see that
x\ll y
if and only if
x<y
or
x=0
.

Algebraic
domains are domains where we put more conditions on the approximating property: a domain
P
is called algebraic if for all
p\in P
, the subset

\{x\in P\mid x\ll x~\text{and}~x\ll p\}
is directed and
p=\sup\{x\in P\mid x\ll x~\text{and}~x\ll p\}
for all
p\in P
. Elements
x
with the property
x\ll x
are called
compact elements
, and hence algebraicity of domains reads as every element can be approximated by compact elements. Every finite poset is algebraic as every element in it is compact, and this applies to posets of finite heights. The unit interval
[0,1]
serves as an example that is a domain but not algebraic, as
0
is the only compact element in it.
Domains and algebraic domains are closely related, in the sense that each domain is actually a
Scott-continuous retract
of an algebraic domain
[
2
, Theorem I-4.17]
. In general, a map
f\colon P\to Q
between dcpo’s
P
and
Q
is Scott-continuous if it preserves directed suprema. That is,
f
is monotone and
f(\sup D)=\sup f(D)
for all directed subsets
D
of
P
; and the dcpo
Q
is called a Scott-continuous retract of
P
provided that there is a Scott-continuous map
g\colon Q\to P
with
f\circ g=\mathrm{id}_{Q}
, and in this case,
f
is called a
retraction
and
g
a
section
.

The smaller collection of algebraic domains are rich enough to denote data types in early programming languages. It was the purpose to model probabilistic behaviours in programming that domains are introduced to encompass the domain of (extended) reals or simply the unit interval
[0,1]
to talk about probabilities. We have seen that
[0,1]
is never algebraic, so it separates domains from algebraic domains. Somewhat to one’s surprise, we report in this note that the unit interval
[0,1]
is
essentially the unique
example that separates domains from algebraic domains:

Theorem
.

The unit interval
[0,1]
is a Scott-continuous retract of every domain that fails to be algebraic.

Proof.

Assume that
P
is a domain and
P
is not algebraic. Then there exist
p,q\in P
such that
p\ll q
and there are no compact elements between them, in particular, neither
p
nor
q
is compact; otherwise, every pair of such
p,q
can be interpolated by compact elements, and then by
[
2
, Proposition I-4.3]

P
would have been algebraic.

Now by the Interpolation Property of the way-below relation on
P

[
2
, Theorem I-1.9 (ii)]
, we could find
a_{\frac{1}{2}}\in P
such that
p\ll a_{\frac{1}{2}}\ll q
. Again by the Interpolation Property, we find
a_{\frac{1}{4}}
and
a_{\frac{3}{4}}
such that
p\ll a_{\frac{1}{4}}\ll a_{\frac{1}{2}}\ll a_{\frac{3}{4}}\ll q
. Repeat this process and we could get a sequence of elements indexed by dyadic numbers in
(0,1)
, and
a_{\frac{l}{2^{n}}}\ll a_{\frac{k}{2^{m}}}
if and only if
\frac{l}{2^{n}}<\frac{k}{2^{m}}
. Moreover, none of them is compact as they are between
p
and
q
, hence they are all distinct from each other.

Let
\mathbb{D}
be the set of all dyadic numbers in
(0,1)
. We consider the map
g\colon[0,1]\to P
:

g(r)=\begin{cases}p,&r=0;\\
\sup\{a_{d}\mid d\in\mathbb{D}~\text{and}~d<r\},&otherwise.\end{cases}

This map is well-defined since the set
\{a_{d}\mid d\in\mathbb{D}~\text{and}~d<r\}
is directed for
r>0
. Obviously,
g
is monotone. Moreover,
g
is Scott-continuous. To see this, we assume
(r_{i})_{i\in I}
is a family of real numbers in
[0,1]
and
r=\sup_{i\in I}r_{i}
. As every dyadic number
d
strictly below
r
must be strictly below some
r_{i}
, so we have
a_{d}\leq g(r_{i})
and this proves that
g(r)\leq\sup_{i\in I}g(r_{i})
. That
g(r)\geq\sup_{i\in I}g(r_{i})
holds since
g
is monotone. So we have proved that
g
is Scott-continuous.

We proceed to define a map
f\colon P\to[0,1]
:

f(x)=\sup\{d\in\mathbb{D}\mid a_{d}\ll x\}.

The map
f
is well-defined since
[0,1]
is a complete lattice. It is easy to see that
f
is monotone.
For Scott-continuity of
f
, we assume that
(x_{i})_{i\in I}
is a directed family in
P
and
x=\sup_{i\in I}x_{i}
. For
a_{d}\ll x
, by the interpolation property of the way-below relation on
P
we could find
y
with
a_{d}\ll y\ll x
. So we know that
a_{d}\ll y\leq x_{i}
for some
x_{i}
. This implies
d\leq f(x_{i})
and hence
f(x)\leq\sup_{i\in I}f(x_{i})
. Again, that
f(x)\geq\sup_{i\in I}f(x_{i})
holds since
f
is monotone. So
f
is indeed Scott-continuous.

Finally, we prove that
f\circ g=\mathrm{id}_{[0,1]}
. Obviously
f(g(0))=f(p)=\sup\emptyset=0
. Now take
r\in(0,1]
. By definition
f(g(r))=\sup\{d\in\mathbb{D}\mid a_{d}\ll g(r)\}
. If
a_{e}\ll g(r)=\sup\{a_{d}\mid d\in\mathbb{D}~\text{and}~d<r\}
for some
e\in\mathbb{D}
, then
a_{e}\ll a_{d}
for some
d\in\mathbb{D}
and
d<r
. So by definition
e<d<r
, and hence
f(g(r))
, as the supremum of all such
e
’s, is below
r
, i.e.
f(g(r))\leq r
. Conversely, we notice that for each
r\in(0,1]
and each dyadic number
e<r
, there exists another dyadic number
d
with
e<d<r
. So
a_{e}\ll a_{d}\leq g(r)
; therefore,
e\in\{d\in\mathbb{D}\mid a_{d}\ll g(r)\}
. Hence
f(g(r))
should be above all such
e
’s and above their supremum
r
.
∎

For the cardinality issue,
[0,1]
cannot be retracts of any countable domains, hence we know the following result, which seems to the authors new to the community.

Corollary
.

Countable domains are algebraic.

Read the complete text