I met Xiaodong Jia (remotely) on April 18th, 2025, and he told me that Rongqi Xiao, one of his students, had asked him the following question: can you find a continuous dcpo that is countable but not algebraic? All the examples we ever take of countable continuous dcpos are algebraic.
X. Jia told me he knew that he could find copies of a countably infinite, dense chain in any continuous, non-algebraic dcpo, and I suggested that he should then be able to find a copy of [0, 1] by taking a rounded ideal completion (but he would have found of that soon enough anyway), and then the following result was proved:
Theorem. Every countable continuous dcpo is algebraic.
I will explain how this works in more detail below. I believe it deserves to be known. Wei Luan proposed to show a bit more, by the way, and they obtained a stronger result in [1], which I will explain, too.
Continuous and algebraic posets
The way-below relation ≪ on a poset P is defined by x≪y if and only if every directed family D with a supremum and such that y≤sup D contains an element above x. P is continuous if and only if every point x of P is the supremum of some directed family D of elements way-below x. (Being a supremum of elements way-below x is not enough: the chosen family of elements must be directed.) For example, [0, 1] with its usual ordering is continuous, and the way-below relation there is given by x≪y if and only if x=0 or x<y.
For all points x and y in a poset P, x≪y implies x≤y. Also, the way-below relation is compatible with the ordering in the sense that x≪y≤z implies x≪z and that z≤x≪y implies z≪y. I will use that implicitly in what follows.
If P is continuous, then for every point x of P, there is a canonical directed family of points way-below x whose suprema is x, and that is ↡x, the collection of all points way-below x. That is the definition I took of continuous posets (Definition 5.1.5) in the book: a poset is continuous if and only if for every point x of P, ↡x is directed and sup ↡x = x. The equivalence with the previous definition is Trick 5.1.20 in the book.
A finite element of a poset P is an element x such that x≪x. P is algebraic if and only if every point x of P is the supremum of a directed family D of finite points below x. Every finite point below x is also way-below x, so every algebraic poset is continuous, but the converse fails: the only finite element of [0, 1] is 0, whence 0 is the only point of [0, 1] that we can obtain as a directed supremum of finite elements, showing that [0, 1] is not algebraic. (And, to get back to the topic of this post, notice that [0, 1] is not countable.) The collection of natural numbers N, with its usual ordering, with an additional element ω above all natural numbers, is an algebraic dcpo, whose finite elements are the natural numbers (not ω).
A fundamental property of continuous posets is interpolation (see Proposition 5.1.15 in the book): for all points x and y in a continuous poset P, if x≪y then there is a point z in P such that x≪z≪y. We will use that below.
Right now, we notice that it implies that the sets ↟x ≝ {y ∈ P | x≪y} are Scott-open in any continuous dcpo P. A Scott-open subset of P is a subset U of P that is upwards-closed and such that for every directed family D in P with a supremum such that sup D ∈ U, some point of D is already in U. And indeed, if sup D ∈ ↟x, namely if x ≪ sup D, then x ≪ z ≪ sup D for some point z by interpolation; then z is below some element d of D by definition of ≪, so x ≪ d.
This can be reinforced: in a continuous poset, the subsets ↟x form a base of the Scott topology, namely of the topology whose open sets are the Scott-open sets (Theorem 5.1.17 in the book).
The proof
The argument of the Jia-Li-Luan theorem proceeds as follows. The key point is the following lemma.
Lemma A. Let P be a continuous poset, and let us assume that P is not algebraic. There are two points x and y in P such that x≪y and such that no element z of P such that x≤z≤y is finite.
Proof. We assume that: (*) for every point y in P, for every x ∈ ↡y, there is a finite point z of P such that x≤z≤y; and we aim for a contradiction. Let us fix an arbitrary point y of P. Since P is continuous, ↡y is directed and y = sup ↡y. Let D be the family of finite points below (namely, less than or equal to) y. D is included in ↡y, because every point z of D is such that z≪z≤y, hence z≪y.
We claim that D is cofinal in ↡y, namely that (it is included in ↡y and) every element x of ↡y is below some element z of D. Indeed, let x be any point in ↡y. Since x≪y=sup ↡y, there is a point d of ↡y such that x≤d. Since d≪y, we can use (*), and we obtain a finite point z such that d≤z≤y. Hence z is in D, and above x.
Every family that is cofinal in a directed family is itself directed and has the same supremum. Let me spell this out in the case at hand. D is non-empty: since ↡y is directed, ↡y is non-empty, and we have just seen that we could find an element of D above any chosen element of ↡y. For any two elements d and d’ of D, d and d’ are in ↡y, so there is an element d” of ↡y above the two of them, since ↡y is directed; by cofinality there is an element of D above d”, hence above both d and d’. This shows that D is directed. Since D ⊆ ↡y, sup D ≤ sup ↡y = y, and cofinality entails that sup ↡y ≤ sup D.
Hence we have obtained a directed family D of finite points such that sup D = y. The point y is arbitrary, so we have shown that P is algebraic. But we have explicitly assumed that P is not algebraic, and thus we have reached the desired contradiction. ☐
Let D2 be the collection of dyadic numbers in [0, 1], namely the collection of numbers of the form p/2n, where n ∈ N and 0≤p≤2n.
Lemma B. Let P be a continuous poset, and let us assume that P is not algebraic. There is a family of non-finite points (xd)d ∈ D2 in P such that for all d<d’ in D2, xd≪xd’, in particular xd<xd’.
Proof. The fact that xd<xd’ follows from xd≪xd’ is justified as follows. Since xd≪xd’, in particular xd≤xd’. Then either xd<xd’ or xd=xd’. But xd=xd’ is impossible, as this together with xd≪xd’ would imply that xd is finite.
Hence we concentrate on building the non-finite points xd so that for all d<d’ in D2, xd≪xd’.
By Lemma A, we can find two points, which we will now call x0 and x1, such that x0≪x1 and no point between x0 and x1 is finite. By interpolation, there is a point x1/2 such that x0≪x1/2≪x1. By interpolation again, there are points x1/4 and x3/4 such that x0≪x1/4≪x1/2≪x3/4≪x1. And so on and so forth, creating a family of points (xd)d ∈ D2 in P such that for all d<d’ in D2, xd≪xd’. They are all between x0 and x1, hence none of those points are finite. ☐
The family D2 is a basis of the continuous dcpo [0, 1], meaning that every point x in [0, 1] is the supremum of a directed family of elements of D2 way-below x. Hence D2, with the restriction of the way-below relation of [0, 1] to D2, forms an abstract basis, whose rounded ideal completion coincides with [0, 1] (see Proposition 5.1.33 in the book). The way-below-preserving bijection d ↦ xd then extends to a Scott-continuous embedding of [0, 1] into P, provided that P is not just a continuous poset, but a continuous dcpo (namely, if all directed families have suprema). This shows that P cannot be countable.
That argument is perhaps a bit quick, and I will prove it in more detail below, by replaying the argument leading to the more general statement of [1]: this embedding is the section part of a Scott-retraction. A Scott-retraction of a dcpo P onto a dcpo Q is a pair of Scott-continuous maps r : P → Q and s : Q → P such that r o s = idQ. I will also say that r itself is the Scott-retraction, with section the function s, and that Q is a Scott-retract of P.
We rephrase their result as an alternative.
Theorem C. Let P be a continuous dcpo. Then either P is algebraic or [0, 1] is a Scott-retract of P.
Proof. Let us assume P continuous but not algebraic. Let (xd)d ∈ D2 be the family we obtained in Lemma B. We define r : P → [0, 1] by:
r(x) ≝ sup {d ∈ D2 | xd ≪ x} if x0≪x and r(x) ≝ 0 otherwise,
and s : [0, 1] → P by:
s(t) ≝ sup {xd | d ∈ D2, d=0 or d<t}.
(“d=0 or d<t” means that d is way-below t in [0, 1], but we prefer to avoid the notation d≪t in order to avert a confusion with the way-below relation ≪ on P.)
- We claim that r is Scott-continuous. It suffices to show that it is continuous with respect to the underlying Scott topologies, namely that r–1(]t, 1]) is Scott-open for every t ∈ ]0, 1[. But r–1(]t, 1]) = {x ∈ P | xd ≪ x for some d ∈ D2 such that d>t} is the union of the Scott-open sets ↟xd where d ranges over the elements of D2 such that d>t. This is Scott-open, so r is continuous.
- We claim that s is Scott-continuous. It suffices to show that the inverse image s–1(U) of any Scott-open subset U of P are Scott-open in [0, 1]. But s–1(U) = {t ∈ [0, 1] | xd ∈ U for some d ∈ D2 such that d=0 or d<t} is the union of the Scott-open intervals ]d, 1] such that d ∈ D2 and xd ∈ U if x0 ∉ U, and the whole of [0, 1] if x0 ∈ U, and is open in any case.
- We claim that r o s = id[0, 1]. For every t ∈ [0, 1], we compute (r o s) (t).
- If s(t)=x0, then (r o s) (t) = 0. But s(t)=x0 implies that for every d ∈ D2 such that d=0 or d<t, xd≤x0. If t>0, then we can find a d ∈ D2 such that 0<d<t; in that case, we know that x0<xd, contradicting xd≤x0. Therefore t=0. In particular, (r o s) (t) = t.
- If s(t)≠x0, then (r o s) (t) is the supremum of all the elements d ∈ D2 such that xd ≪ s(t).
If d is such an element, then there is an element d’ ∈ D2 such that (d’=0 or d’<t) and xd≤xd’, by definition of s and the way-below relation. From xd≤xd’, we deduce that d≤d’; otherwise we would have d’<d, hence xd’<xd. From (d’=0 or d’<t), we obtain that d’≤t, so d≤t. Taking suprema over d, we obtain that (r o s) (t) ≤ t.
If that inequality were strict, there would be a non-zero dyadic number d ∈ D2 such that (r o s) (t) < d < t, and then a second one, d’ such that d < d’ < t. Since d’<t, xd’≤s(t) by definition of s. Since d<d’, we have xd≪xd’, by construction of the family (xd)d ∈ D2. Hence xd≪s(t). By definition of r, (r o s) (t) ≥ d, but this contradicts the fact that (r o s) (t) < d.
Hence (r o s) (t) = t. ☐
Another way of stating this is by using the language of forbidden substructures: for a continuous dcpo P, P is algebraic provided that it does not admit [0, 1] as a (Scott-)retract.
A final remark
Theorem C requires P to be a dcpo, while the previous lemmata worked in the more general setting of posets. As one can convince oneself, the proof of Theorem C really needs P to be a dcpo, otherwise the definition of r makes no sense. Hence one may ask whether Theorem C would still hold for continuous posets instead of dcpos.
The answer is no. The simplest example is D2 itself, with its usual ordering. Let us discover what the way-below relation on D2 is. Let us write it as ≪, as usual. If d≪d’ in D2, then d≤d’, and we claim that if d≠0, then this entails that d<d’. Indeed, let us assume that d=d’, and that d≪d’, namely that d is finite. Since 0<d, there is a natural number n0 such that 1/2n0≤d; then the points d–1/2n with n≥n0 are all in D2, their supremum is d, and none of these points is above d: so d is not finite after all. Hence d≪d’ in D2 implies that d=0 or d<d’. The reverse implication is obvious. Hence D2 is a continuous poset. Its only finite element is 0, so D2 is not algebraic. And D2 is countable.
- Xiaodong Jia, Qingguo Li, Wei Luan. Separating domains from algebraic domains. arXiv report 2504.04189 [math.GN], April 2025.
— Jean Goubault-Larrecq (May 20th, 2025)