{"id":1394,"date":"2018-03-19T18:46:17","date_gmt":"2018-03-19T17:46:17","guid":{"rendered":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=1394"},"modified":"2022-11-19T15:17:31","modified_gmt":"2022-11-19T14:17:31","slug":"forbidden-substructures","status":"publish","type":"page","link":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=1394","title":{"rendered":"Forbidden substructures"},"content":{"rendered":"

My purpose today is to talk about the characterization of certain properties of posets and dcpos by so-called forbidden substructures<\/em>.\u00a0 Although this is a pretty old theme, Xiaodong Jia<\/a> really managed to make it shine in his PhD thesis [2].<\/p>\n

Here is a trivial example of forbidden substructure.\u00a0 Consider a poset X<\/em>, and recall that X<\/em> has the ascending chain condition (a.k.a., the ACC, see Proposition 9.7.6 in the book<\/a>) if and only if every monotone sequence eventually stabilizes.\u00a0 (Equivalently: there is no infinite strictly ascending sequence in X<\/em>.)\u00a0 Another way of saying that is that X<\/em> has the ACC if and only if you cannot find a copy of the poset N<\/strong> of natural numbers inside X<\/em>, or, in formal terms, there is no order-embedding of N<\/strong> into X<\/em>.\u00a0 Here N<\/strong> is the forbidden substructure.<\/p>\n

Before we come back to order theory, let me mention some exciting examples of forbidden substructures in graph theory.\u00a0 I will then come back to order theory, briefly, and then to domain theory.<\/p>\n

Forbidden substructures in graph theory<\/h2>\n

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 K5<\/sub> (the complete graph on 5 vertices) or of K3,3<\/sub> (the complete bipartite graph on 3+3 vertices) in it.\u00a0 I have deliberately removed some of the details (see the Wikipedia page<\/a>), and in particular I have not said what “in it” means (see later), that is, what the substructure relation is.\u00a0 (The substructure relation was the existence of an order-embedding in our example about the ACC.\u00a0 Here, one requires a certain notion of graph embedding, and there are several.)<\/p>\n

What I want to stress is that planarity is characterized by forbidden substructures again: here\u00a0K5<\/sub> and K3,3<\/sub> are the substructures that are forbidden.<\/p>\n

In graph theory, the celebrated Robertson-Seymour theorem<\/a> states that any minor-closed (i.e., downwards-closed with respect to the so-called minor embedding relation) family F<\/em> of graphs can be characterized by finitely many forbidden structures: there are finitely many graphs G<\/em>1<\/sub>, …, Gn<\/sub><\/em> such that F<\/em> is the class of graphs that do not contain any\u00a0Gi<\/sub><\/em> as a minor.\u00a0 In the case of planarity, n<\/em>=2 and the two forbidden graphs are K5<\/sub> and K3,3<\/sub>.\u00a0 (That is Wagner’s theorem, not Kuratowski’s, in that case, if one wants to be precise.\u00a0 I will not define what a minor is.)\u00a0 But the theorem applies to any<\/em> minor-closed family, and since the proof is not constructive, there are minor-closed families of graphs for which noone knows of any finite class of forbidden minors\u2014although we know that they must exist. \u00a0That has weird implications in computer science: because testing for minors can be done in polynomial time, there are polynomial time algorithms to test any minor-closed property of graphs \u2014 however there are several cases where we do not know what these algorithms are: we have to check for minors, but which ones?<\/p>\n

Forbidden structures in order theory<\/h2>\n

I have already mentioned how one could characterize posets with the ACC by N<\/strong> as a forbidden substructure.\u00a0 Here “substructure of” means “poset that order-embeds into”.<\/p>\n

There are many order-theoretic concepts that one can characterize similarly.\u00a0 For example, a well-founded poset is one that has Z<\/strong>\u2013<\/sup> as forbidden substructure (the set of negative integers, with the usual ordering).\u00a0 A poset that is well-quasi-ordered is the same thing as a poset that is well-founded and has no infinite antichain (Proposition 9.7.17, item 4, in the book<\/a>), hence is the same thing as a poset in which neither Z<\/strong>\u2013<\/sup> nor N<\/strong>=<\/sub> order-embeds, where N<\/strong>=<\/sub> is the set of natural numbers with = as ordering.<\/p>\n

Here is a more interesting one.\u00a0 Recall that a lattice L<\/em> is distributive<\/em> if and only if u<\/em> \u22c0 sup(v<\/em>, w<\/em>) = sup (u<\/em> \u22c0 v<\/em>, u<\/em> \u22c0 w<\/em>) for all u<\/em>, v<\/em>, w<\/em> in L<\/em>, or equivalently u<\/em> \u22c0 sup(v<\/em>, w<\/em>) \u2264 sup (u<\/em> \u22c0 v<\/em>, u<\/em> \u22c0 w<\/em>) since the converse inclusion always holds.\u00a0 Distributivity can be characterized by the forbidden substructures N<\/em>5<\/sub> or M<\/em>3<\/sub> (see Figure 8.1 in the book<\/a>, or below).\u00a0 This is well-known, but the way it is proved is interesting, and typical. \u00a0(Correction, October 18th, 2022: the two lattices are forbidden, not in the sense that they should not order-embed, but that they should not embed through an order-embedding that preserves binary sups and binary infs.)<\/p>\n

\"\"<\/a><\/p>\n

Proposition.<\/strong> L<\/em> is not distributive if and only if N<\/em>5<\/sub> or M<\/em>3<\/sub> order-embeds in L<\/em>. \u00a0(Correction, October 18th, 2022: lattice-embeds, not order-embeds: the embedding must also preserve both binary sups and binary infs.)<\/p>\n

Here is a proof of the interesting direction.\u00a0 Assume that L<\/em> is not distributive.\u00a0 L<\/em> must therefore contain three points a<\/em>, b<\/em>, and c<\/em> such that: (*) b<\/em> \u22c0 sup(a<\/em>, c<\/em>)\u00a0\u2270 sup (b<\/em> \u22c0 a<\/em>, b<\/em> \u22c0 c<\/em>).<\/p>\n

Case 1. If b<\/em> and c<\/em> are comparable, say b<\/em> \u2265 c<\/em>, then (*) simplifies to: (**) b<\/em> \u22c0 sup(a<\/em>, c<\/em>)\u00a0\u2270 sup (b<\/em> \u22c0 a<\/em>, c<\/em>).\u00a0 If b<\/em> were equal to c<\/em>, then that would simplify further to c<\/em>\u2270 sup (c<\/em> \u22c0 a<\/em>, c<\/em>), which is absurd, so b>c<\/em>.\u00a0 Similarly, a<\/em>\u2265c<\/em> together with (**) would imply b<\/em> \u22c0\u00a0a<\/em> \u2270 sup (b<\/em>\u00a0\u22c0 a<\/em>, c<\/em>), and a<\/em>\u2264b<\/em> would imply b<\/em> \u22c0 sup(a<\/em>, c<\/em>)\u00a0\u2270 sup (a<\/em>, c<\/em>), both of which are absurd.\u00a0 So a<\/em> must be incomparable with both b<\/em> and c<\/em>.\u00a0 Since L<\/em> is a lattice, we must also find a point \u22a4=sup(a<\/em>,b<\/em>) and a point \u22a5=a<\/em> \u22c0 c<\/em>.\u00a0 Therefore L<\/em> must contain the non-distributive lattice N<\/em>5<\/sub> as order-embedded poset.<\/p>\n

Case 2. b<\/em> and c<\/em> are incomparable.\u00a0 If a<\/em>\u2265c<\/em> then (*) simplifies to b<\/em> \u22c0 a<\/em> \u2270 sup (b<\/em> \u22c0 a<\/em>, b<\/em> \u22c0 c<\/em>), which is impossible.\u00a0 If a<\/em>\u2264c<\/em> then (*) simplifies to b<\/em> \u22c0 c<\/em> \u2270 sup (b<\/em> \u22c0 a<\/em>, b<\/em> \u22c0 c<\/em>), which is impossible again.\u00a0 So a<\/em> and c<\/em> are incomparable.\u00a0 If a<\/em>\u2265b<\/em> then (*) simplifies to b<\/em> \u2270 b<\/em> \u22c0 c<\/em>.\u00a0 If a<\/em><b<\/em> then we recognize a copy of\u00a0N<\/em>5<\/sub> again, with b<\/em> atop a<\/em>, c<\/em> on the side, plus a top element and a bottom element.\u00a0 Otherwise, a<\/em> and b<\/em> are incomparable, and together with a top and a bottom obtained as sup(a<\/em>,b<\/em>,c<\/em>) and a<\/em> \u22c0 b<\/em> \u22c0 c<\/em> respectively, one recognizes a copy of M<\/em>3<\/sub>.\u00a0\u00a0\u00a0\u00a0 \u2610<\/p>\n

Forbidden substructures in dcpos.<\/h2>\n

I do not know exactly who was the first to recognize the importance of forbidden structures in domain theory.\u00a0 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.<\/p>\n

There is at least one explicit occurrence of the technique there.\u00a0 In Proposition 4.22, page 98, Achim shows that a pointed continuous dcpo with property m is a continuous L-domain if and only if it does not contain a certain dcpo X<\/strong>\u22a5<\/sub>\u22a4<\/sup> as a retract<\/em>\u00a0(see below for X<\/strong>\u22a5<\/sub>\u22a4<\/sup>; the picture is taken straight from Achim’s PhD thesis).<\/p>\n

\"\"<\/p>\n

And there is the new feature: by a substructure A<\/em> of B<\/em>, we no longer mean that A<\/em> order-embeds into B<\/em>, rather that A<\/em> is a retract<\/em> of B<\/em>.<\/p>\n

That is a strictly stronger property, and this is exactly the kind that we need in the study of function spaces in domain theory.\u00a0 The reason is that if X<\/em> embeds as a retract inside X’<\/em>, and if Y<\/em> embeds as a retract inside Y’<\/em>, then the continuous function space [X<\/em> \u2192 Y<\/em>] embeds as a retract inside [X’<\/em> \u2192 Y’<\/em>].\u00a0 A similar property would fail with mere order-embeddings.<\/p>\n

There are several properties of (certain classes of) dcpos that one can characterize by forbidden retracts. \u00a0For example, improving upon the result we have just mentioned, Xi and Yang show [3] that a bicomplete dcpo\u00a0(a poset X<\/em> is bicomplete if and only if both X<\/em> and X<\/em>op<\/sup> are dcpos) is a pointed L-domain if and only if it does not contain any of the following dcpos as retract: X<\/strong>\u22a5<\/sub>\u22a4<\/sup>, the two-element antichain {a<\/em>,\u00a0b<\/em>}, and the three-element poset {a<\/em>,\u00a0b<\/em>,\u00a0\u22a4} (with\u00a0\u22a4 above\u00a0a<\/em> and\u00a0b<\/em>, and\u00a0a<\/em> and\u00a0b<\/em> incomparable).<\/p>\n

Meet-continuity<\/h2>\n

I have talked about meet-continuous dcpos last month<\/a>. \u00a0Here is an example of a non-meet-continuous dcpo. \u00a0We take any well-founded chain\u00a0C<\/em> without a top element. \u00a0Call its least element 0. \u00a0We add a fresh element\u00a0a<\/em> on the side, that is, incomparable with every element of\u00a0C<\/em>, and\u00a0a fresh element\u00a0\u22a4 above\u00a0a<\/em> and all elements of\u00a0C<\/em>. \u00a0Call\u00a0M<\/strong>(C<\/em>) the resulting dcpo. \u00a0This is the dcpo shown below, left. \u00a0Note that the chain\u00a0C<\/em> need not be just a copy of the natural numbers: we allow any ordinal<\/a> here.<\/p>\n

\"\"<\/a><\/p>\n

Let us verify that\u00a0M<\/strong>(C<\/em>) is not meet-continuous. \u00a0We use\u00a0Kou, Liu and Luo\u2019s definition [4]: a dcpo is meet-continuous if and only if for every directed family\u00a0D<\/em> and every\u00a0y<\/em>\u00a0\u2264 sup\u00a0D<\/em>, y<\/em>\u00a0\u2208\u00a0cl\u00a0(\u2193D<\/em>\u00a0\u2229\u00a0\u2193y<\/em>). \u00a0For\u00a0D<\/em>, we take the chain\u00a0C<\/em> itself, so sup\u00a0D<\/em> = \u22a4. \u00a0We take\u00a0y<\/em>=a<\/em>, so\u00a0y<\/em>\u00a0\u2264 sup\u00a0D<\/em> indeed, but\u00a0\u2193D<\/em>\u00a0\u2229\u00a0\u2193y<\/em> is empty, so certainly\u00a0y<\/em> cannot be in\u00a0cl\u00a0(\u2193D<\/em>\u00a0\u2229\u00a0\u2193y<\/em>).<\/p>\n

If we add a fresh element\u00a0\u22a5 below all the elements of\u00a0M<\/strong>(C<\/em>), we obtain another dcpo M<\/strong>(C<\/em>)\u22a5<\/sub>\u00a0(see above, right). \u00a0Then M<\/strong>(C<\/em>)\u22a5<\/sub>\u00a0is a lattice, and we can check that M<\/strong>(C<\/em>)\u22a5<\/sub>\u00a0is not meet-continuous either by simply checking that the map\u00a0a<\/em>\u00a0\u22c0 _ is not Scott-continuous:\u00a0a<\/em>\u00a0\u22c0 sup\u00a0C<\/em> = a\u00a0\u22c0\u00a0\u22a4 =\u00a0a<\/em>, but supc \u2208 C<\/sub><\/em> (a<\/em>\u00a0\u22c0\u00a0c<\/em>) = 0.<\/p>\n

One of the nice results in\u00a0Xiaodong Jia<\/a>‘s PhD thesis is that those two objects M<\/strong>(C<\/em>) and M<\/strong>(C<\/em>)\u22a5<\/sub>\u00a0are exactly the structures that one has to forbid as a retract to define meet-continuous dcpos.<\/p>\n

Theorem ([2], Theorem 3.3.11.)<\/strong> \u00a0Let\u00a0X<\/em> be a dcpo. \u00a0Then\u00a0X<\/em> is meet-continuous if and only if it admits neither M<\/strong>(C<\/em>)\u00a0nor M<\/strong>(C<\/em>)\u22a5<\/sub>\u00a0as retract, for any well-founded chain C<\/em>.<\/p>\n

The idea of the proof is as follows. \u00a0If\u00a0X<\/em> contains M<\/strong>(C<\/em>)\u00a0or M<\/strong>(C<\/em>)\u22a5<\/sub>\u00a0as a retract, then\u00a0X<\/em> cannot be meet-continuous, essentially by replaying the argument we have used for\u00a0M<\/strong>(C<\/em>). \u00a0In the converse direction, assume that\u00a0X<\/em> is not meet-continuous. \u00a0Then there is a directed family\u00a0D<\/em> and a point\u00a0a<\/em> such that\u00a0a<\/em> \u2264 sup\u00a0D<\/em>\u00a0but a<\/i>\u00a0is not in cl\u00a0(\u2193D<\/em>\u00a0\u2229\u00a0\u2193a<\/em>).<\/p>\n

The core of the proof consists in showing that we can replace\u00a0D<\/em> by a well-founded chain\u00a0C<\/em>. \u00a0In other words, we would like to show that there is a well-founded chain\u00a0C<\/em> such that\u00a0a<\/em> \u2264 sup C<\/i>\u00a0but a<\/i>\u00a0is not in cl\u00a0(\u2193C<\/i>\u00a0\u2229\u00a0\u2193a<\/em>). \u00a0We shall do that later.<\/p>\n

For now, imagine we have such an a<\/em> and\u00a0C<\/em>.\u00a0\u00a0That gives us\u00a0a copy of\u00a0M<\/strong>(C<\/em>) order-embedded in\u00a0X<\/em>, together with sup\u00a0C<\/em>, which we label\u00a0\u22a4 (that need not be the top element of\u00a0X<\/em>, though, even if there is one).<\/p>\n

If \u2193C<\/i>\u00a0\u2229\u00a0\u2193a<\/em> is empty, then\u00a0M<\/strong>(C<\/em>) occurs as a retract of\u00a0X<\/em>: the retraction maps every element below\u00a0a<\/em> to\u00a0a<\/em>, every element below some element\u00a0c<\/em> of\u00a0C<\/em> but not below\u00a0a<\/em> to the least such\u00a0c<\/em> (which is defined since\u00a0C<\/em> is well-founded), and all other elements to\u00a0\u22a4.\u00a0 (Hmm… you also have to show that the inclusion of M<\/strong>(C<\/em>) inside X<\/em> is Scott-continuous.\u00a0 That only works if C<\/em> is limit-embedded<\/em> in X<\/em>, as X. Jia calls it.\u00a0 Let me ignore this point.\u00a0 This only adds minor technical difficulties to the whole construction.)<\/p>\n

If \u2193C<\/i>\u00a0\u2229\u00a0\u2193a<\/em> is not empty, then\u00a0M<\/strong>(C<\/em>)\u22a5<\/sub>\u00a0is a retract of\u00a0X<\/em>. \u00a0This is a bit more complicated. \u00a0We pick\u00a0b<\/em> from\u00a0\u2193C<\/i>\u00a0\u2229\u00a0\u2193a<\/em>, then there is a point\u00a0c<\/em> in\u00a0C<\/em> such that\u00a0b<\/em>\u2264c<\/em>, and we take the least one. \u00a0Now we remove\u00a0c<\/em> and everything below it from\u00a0C<\/em>, and define a retraction by mapping every element of\u00a0cl (\u2193C<\/i>\u00a0\u2229\u00a0\u2193a<\/em>) to \u22a5; all other elements are mapped to elements of\u00a0M<\/strong>(C<\/em>) exactly as in the case where\u00a0\u2193C<\/i>\u00a0\u2229\u00a0\u2193a<\/em> is empty.<\/p>\n

Fine, but\u00a0we still have something to do! \u00a0We would like to show that if\u00a0X<\/em> is not meet-continuous, then there is\u00a0a well-founded chain\u00a0C<\/em> such that\u00a0a<\/em> \u2264 sup C<\/i>\u00a0but a<\/i>\u00a0is not in cl\u00a0(\u2193C<\/i>\u00a0\u2229\u00a0\u2193a<\/em>).\u00a0 (In fact, a limit-embedded one.)<\/p>\n

This is (half of) Theorem 3.3.8 in Xiaodong Jia’s PhD thesis, and the key is\u00a0Iwamura’s Lemma<\/a>.<\/p>\n

Find a directed family\u00a0D<\/em> of smallest cardinality |D<\/em>| (ordinals are well-founded) such that\u00a0there is\u00a0a point\u00a0a<\/em> such that\u00a0a<\/em> \u2264 sup\u00a0D<\/em>\u00a0but a<\/i>\u00a0is not in cl\u00a0(\u2193D<\/em>\u00a0\u2229\u00a0\u2193a<\/em>). \u00a0D<\/em> cannot be finite, since then\u00a0D<\/em> would have a largest element d<\/em>, which would be above\u00a0a<\/em>, and cl\u00a0(\u2193D<\/em>\u00a0\u2229\u00a0\u2193a<\/em>) would be equal to \u2193d<\/i>. \u00a0By Iwamura’s Lemma<\/a>, we\u00a0can then write D<\/em> as the union of a chain of directed subsets D<\/em>\u03b1<\/sub>, indexed by ordinals \u03b1<|D<\/em>|, such that:<\/p>\n