My purpose today is to talk about the characterization of certain properties of posets and dcpos by socalled forbidden substructures. Although this is a pretty old theme, Xiaodong Jia really managed to make it shine in his PhD thesis [2].
Here is a trivial example of forbidden substructure. Consider a poset X, and recall that X has the ascending chain condition (a.k.a., the ACC, see Proposition 9.7.6 in the book) if and only if every monotone sequence eventually stabilizes. (Equivalently: there is no infinite strictly ascending sequence in X.) Another way of saying that is that X has the ACC if and only if you cannot find a copy of the poset N of natural numbers inside X, or, in formal terms, there is no orderembedding of N into X. Here N is the forbidden substructure.
Before we come back to order theory, let me mention some exciting examples of forbidden substructures in graph theory. I will then come back to order theory, briefly, and then to domain theory.
Forbidden substructures in graph theory
There is a famous theorem, due to Kuratowski, which says that a graph is planar if and only if you cannot find any copy of K_{5} (the complete graph on 5 vertices) or of K_{3,3} (the complete bipartite graph on 3+3 vertices) in it. I have deliberately removed some of the details (see the Wikipedia page), and in particular I have not said what “in it” means (see later), that is, what the substructure relation is. (The substructure relation was the existence of an orderembedding in our example about the ACC. Here, one requires a certain notion of graph embedding, and there are several.)
What I want to stress is that planarity is characterized by forbidden substructures again: here K_{5} and K_{3,3} are the substructures that are forbidden.
In graph theory, the celebrated RobertsonSeymour theorem states that any minorclosed (i.e., downwardsclosed with respect to the socalled minor embedding relation) family F of graphs can be characterized by finitely many forbidden structures: there are finitely many graphs G_{1}, …, G_{n} such that F is the class of graphs that do not contain any G_{i} as a minor. In the case of planarity, n=2 and the two forbidden graphs are K_{5} and K_{3,3}. (That is Wagner’s theorem, not Kuratowski’s, in that case, if one wants to be precise. I will not define what a minor is.) But the theorem applies to any minorclosed family, and since the proof is not constructive, there are minorclosed families of graphs for which noone knows of any finite class of forbidden minors—although we know that they must exist. That has weird implications in computer science: because testing for minors can be done in polynomial time, there are polynomial time algorithms to test any minorclosed property of graphs — however there are several cases where we do not know what these algorithms are: we have to check for minors, but which ones?
Forbidden structures in order theory
I have already mentioned how one could characterize posets with the ACC by N as a forbidden substructure. Here “substructure of” means “poset that orderembeds into”.
There are many ordertheoretic concepts that one can characterize similarly. For example, a wellfounded poset is one that has Z^{–} as forbidden substructure (the set of negative integers, with the usual ordering). A poset that is wellquasiordered is the same thing as a poset that is wellfounded and has no infinite antichain (Proposition 9.7.17, item 4, in the book), hence is the same thing as a poset in which neither Z^{–} nor N_{=} orderembeds, where N_{=} is the set of natural numbers with = as ordering.
Here is a more interesting one. Recall that a lattice L is distributive if and only if u ⋀ sup(v, w) = sup (u ⋀ v, u ⋀ w) for all u, v, w in L, or equivalently u ⋀ sup(v, w) ≤ sup (u ⋀ v, u ⋀ w) since the converse inclusion always holds. Distributivity can be characterized by the forbidden substructures N_{5} or M_{3} (see Figure 8.1 in the book, or below). This is wellknown, but the way it is proved is interesting, and typical. (Correction, October 18th, 2022: the two lattices are forbidden, not in the sense that they should not orderembed, but that they should not embed through an orderembedding that preserves binary sups and binary infs.)
Proposition. L is not distributive if and only if N_{5} or M_{3} orderembeds in L. (Correction, October 18th, 2022: latticeembeds, not orderembeds: the embedding must also preserve both binary sups and binary infs.)
Here is a proof of the interesting direction. Assume that L is not distributive. L must therefore contain three points a, b, and c such that: (*) b ⋀ sup(a, c) ≰ sup (b ⋀ a, b ⋀ c).
Case 1. If b and c are comparable, say b ≥ c, then (*) simplifies to: (**) b ⋀ sup(a, c) ≰ sup (b ⋀ a, c). If b were equal to c, then that would simplify further to c≰ sup (c ⋀ a, c), which is absurd, so b>c. Similarly, a≥c together with (**) would imply b ⋀ a ≰ sup (b ⋀ a, c), and a≤b would imply b ⋀ sup(a, c) ≰ sup (a, c), both of which are absurd. So a must be incomparable with both b and c. Since L is a lattice, we must also find a point ⊤=sup(a,b) and a point ⊥=a ⋀ c. Therefore L must contain the nondistributive lattice N_{5} as orderembedded poset.
Case 2. b and c are incomparable. If a≥c then (*) simplifies to b ⋀ a ≰ sup (b ⋀ a, b ⋀ c), which is impossible. If a≤c then (*) simplifies to b ⋀ c ≰ sup (b ⋀ a, b ⋀ c), which is impossible again. So a and c are incomparable. If a≥b then (*) simplifies to b ≰ b ⋀ c. If a<b then we recognize a copy of N_{5} again, with b atop a, c on the side, plus a top element and a bottom element. Otherwise, a and b are incomparable, and together with a top and a bottom obtained as sup(a,b,c) and a ⋀ b ⋀ c respectively, one recognizes a copy of M_{3}. ☐
Forbidden substructures in dcpos.
I do not know exactly who was the first to recognize the importance of forbidden structures in domain theory. I had the impression that that should be Achim Jung, but I have found only a few traces of the idea in his PhD thesis [1], and I would have expected to see more of it there.
There is at least one explicit occurrence of the technique there. In Proposition 4.22, page 98, Achim shows that a pointed continuous dcpo with property m is a continuous Ldomain if and only if it does not contain a certain dcpo X_{⊥}^{⊤} as a retract (see below for X_{⊥}^{⊤}; the picture is taken straight from Achim’s PhD thesis).
And there is the new feature: by a substructure A of B, we no longer mean that A orderembeds into B, rather that A is a retract of B.
That is a strictly stronger property, and this is exactly the kind that we need in the study of function spaces in domain theory. The reason is that if X embeds as a retract inside X’, and if Y embeds as a retract inside Y’, then the continuous function space [X → Y] embeds as a retract inside [X’ → Y’]. A similar property would fail with mere orderembeddings.
There are several properties of (certain classes of) dcpos that one can characterize by forbidden retracts. For example, improving upon the result we have just mentioned, Xi and Yang show [3] that a bicomplete dcpo (a poset X is bicomplete if and only if both X and X^{op} are dcpos) is a pointed Ldomain if and only if it does not contain any of the following dcpos as retract: X_{⊥}^{⊤}, the twoelement antichain {a, b}, and the threeelement poset {a, b, ⊤} (with ⊤ above a and b, and a and b incomparable).
Meetcontinuity
I have talked about meetcontinuous dcpos last month. Here is an example of a nonmeetcontinuous dcpo. We take any wellfounded chain C without a top element. Call its least element 0. We add a fresh element a on the side, that is, incomparable with every element of C, and a fresh element ⊤ above a and all elements of C. Call M(C) the resulting dcpo. This is the dcpo shown below, left. Note that the chain C need not be just a copy of the natural numbers: we allow any ordinal here.
Let us verify that M(C) is not meetcontinuous. We use Kou, Liu and Luo’s definition [4]: a dcpo is meetcontinuous if and only if for every directed family D and every y ≤ sup D, y ∈ cl (↓D ∩ ↓y). For D, we take the chain C itself, so sup D = ⊤. We take y=a, so y ≤ sup D indeed, but ↓D ∩ ↓y is empty, so certainly y cannot be in cl (↓D ∩ ↓y).
If we add a fresh element ⊥ below all the elements of M(C), we obtain another dcpo M(C)_{⊥} (see above, right). Then M(C)_{⊥} is a lattice, and we can check that M(C)_{⊥} is not meetcontinuous either by simply checking that the map a ⋀ _ is not Scottcontinuous: a ⋀ sup C = a ⋀ ⊤ = a, but sup_{c ∈ C} (a ⋀ c) = 0.
One of the nice results in Xiaodong Jia‘s PhD thesis is that those two objects M(C) and M(C)_{⊥} are exactly the structures that one has to forbid as a retract to define meetcontinuous dcpos.
Theorem ([2], Theorem 3.3.11.) Let X be a dcpo. Then X is meetcontinuous if and only if it admits neither M(C) nor M(C)_{⊥} as retract, for any wellfounded chain C.
The idea of the proof is as follows. If X contains M(C) or M(C)_{⊥} as a retract, then X cannot be meetcontinuous, essentially by replaying the argument we have used for M(C). In the converse direction, assume that X is not meetcontinuous. Then there is a directed family D and a point a such that a ≤ sup D but a is not in cl (↓D ∩ ↓a).
The core of the proof consists in showing that we can replace D by a wellfounded chain C. In other words, we would like to show that there is a wellfounded chain C such that a ≤ sup C but a is not in cl (↓C ∩ ↓a). We shall do that later.
For now, imagine we have such an a and C. That gives us a copy of M(C) orderembedded in X, together with sup C, which we label ⊤ (that need not be the top element of X, though, even if there is one).
If ↓C ∩ ↓a is empty, then M(C) occurs as a retract of X: the retraction maps every element below a to a, every element below some element c of C but not below a to the least such c (which is defined since C is wellfounded), and all other elements to ⊤. (Hmm… you also have to show that the inclusion of M(C) inside X is Scottcontinuous. That only works if C is limitembedded in X, as X. Jia calls it. Let me ignore this point. This only adds minor technical difficulties to the whole construction.)
If ↓C ∩ ↓a is not empty, then M(C)_{⊥} is a retract of X. This is a bit more complicated. We pick b from ↓C ∩ ↓a, then there is a point c in C such that b≤c, and we take the least one. Now we remove c and everything below it from C, and define a retraction by mapping every element of cl (↓C ∩ ↓a) to ⊥; all other elements are mapped to elements of M(C) exactly as in the case where ↓C ∩ ↓a is empty.
Fine, but we still have something to do! We would like to show that if X is not meetcontinuous, then there is a wellfounded chain C such that a ≤ sup C but a is not in cl (↓C ∩ ↓a). (In fact, a limitembedded one.)
This is (half of) Theorem 3.3.8 in Xiaodong Jia’s PhD thesis, and the key is Iwamura’s Lemma.
Find a directed family D of smallest cardinality D (ordinals are wellfounded) such that there is a point a such that a ≤ sup D but a is not in cl (↓D ∩ ↓a). D cannot be finite, since then D would have a largest element d, which would be above a, and cl (↓D ∩ ↓a) would be equal to ↓d. By Iwamura’s Lemma, we can then write D as the union of a chain of directed subsets D_{α}, indexed by ordinals α<D, such that:
 D_{α} < D
 if α<β then D_{α} is included in D_{β}
Let C be the chain consisting of the points sup D_{α}, α<D. (You can make it limitembedded by adding the suprema in X of all subchains of C that have an upper bound in C, but I don’t want to make the exposition too complicated, hence I will ignore this point.)
We claim that a≤sup C (indeed, since sup C=sup D), and that a is not in cl (↓C ∩ ↓a). For that, we reason by contradiction. Assume that a is in cl (↓C ∩ ↓a). Let U be the complement of cl (↓D ∩ ↓a), and notice that this is an open neighborhood U of a—recall that a is not in cl (↓D ∩ ↓a). Since U intersects cl (↓C ∩ ↓a) (at a), it also intersects ↓C ∩ ↓a, say at d. This means that d is in U, below some sup D_{α}, and below a. Because of the fact that D was chosen minimal, and since d≤sup D_{α}, d is in cl (↓D_{α} ∩ ↓d). Hence U intersects cl (↓D_{α} ∩ ↓d), hence also ↓D_{α} ∩ ↓d, hence also the larger set ↓D ∩ ↓d, which is itself included in ↓D ∩ ↓a since d≤a. But that is impossible, in the light of how we defined U. ☐
All CCCs of quasicontinuous domains must consist of continuous domains
That is just one step in X. Jia’s PhD thesis leading to the following wonderful result (Theorem 3.4.3 in [2]):
Any full Cartesianclosed subcategory of the category of dcpos whose objects are all quasicontinuous must in fact consist of continuous dcpos only.
(And therefore, of continuous Ldomains, or of FSdomains, by Achim Jung’s celebrated classification result — at least in the pointed case.)
Here is the argument. Assume that CCC contained a quasicontinuous, noncontinuous dcpo X. Since quasicontinuity+meetcontinuity=continuity (a result by Hui Kou of which Weng Kin Ho had given an improved proof of, and which was the subject of last month’s post), X cannot be meetcontinuous.
Now we know that X must contain M(C) nor M(C)_{⊥} as retract, for some wellfounded chain C. Let L=M(C) or M(C)_{⊥}, depending on the case. Xiaodong Jia shows that [L → L] is not locally compact [2, Proposition 3.4.1]. This is tricky, but doable because of the restricted shape that L has. He also shows that every corecompact dcpo in which every nonempty family has a supremum must be sober, hence locally compact [2, Theorem 2.5.8]. Due to the special form of L, that result applies to [L → L]. If it were corecompact, it would then be locally compact, which it is not. Since [L → L] is a retract of [X → X] , and corecompactness is inherited by retracts, [X → X] cannot be corecompact either, and that contradicts the fact that it lives in a category of quasicontinuous dcpos.
 Achim Jung. Cartesian Closed Categories of Domains. PhD thesis, Technische Universität Darmstadt, 1988.
 Xiaodong Jia. MeetContinuity and Locally Compact Sober Spaces. PhD thesis, University of Birmingham, 2018.
 Xiaoyong Xi and Jinbo Yang. Coincidence of the Isbell and Scott topologies on Domain Function Spaces. Topology and its Applications, 164(2014), 197206.

On MeetContinuous Dcpos. In G. Zhang, J. Lawson, Y. Liu, and M. Luo, editors, Domain Theory, Logic and Computation, volume 3 of Semantic Structures in Computation, pages 117–135. Springer Netherlands, 2003.YingMing Liu, and MaoKang Luo.
— Jean GoubaultLarrecq (March 19th, 2018)