{"id":719,"date":"2015-07-21T15:39:04","date_gmt":"2015-07-21T13:39:04","guid":{"rendered":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=719"},"modified":"2022-11-19T15:30:00","modified_gmt":"2022-11-19T14:30:00","slug":"powerdomains-and-hyperspaces-v-more-theories","status":"publish","type":"page","link":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=719","title":{"rendered":"Adjoint Functor Theorems: GAFT and SAFT"},"content":{"rendered":"<p>You have probably sweated a lot at trying to understand the constructions of <a title=\"Powerdomains and hyperspaces IV: theories\" href=\"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=664\">Part IV<\/a>. \u00a0They rest on a lot of topology and domain theory. \u00a0Perhaps surprisingly (if you do not know it already), they are completely generic, and work in any category with enough structure. \u00a0This is what we learn from Peter Freyd&#8217;s adjoint functor theorems, of which there are two: the general one, and the special one.<\/p>\n<div>\u00a0<\/div>\n<h2>The General Adjoint Functor Theorem<\/h2>\n<p>In <a title=\"Powerdomains and hyperspaces IV: theories\" href=\"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=664\">Part IV<\/a>, we have seen that:<\/p>\n<ul>\n<li>For every T<sub>0<\/sub> topological space <em>X<\/em>, there is a free T<sub>0<\/sub> topological <strong>T<\/strong>-algebra on <em>X<\/em>.<\/li>\n<li>For every T<sub>0<\/sub>\u00a0topological space\u00a0<em>X<\/em>, there is a free sober\u00a0<strong>T<\/strong>-algebra on\u00a0<em>X<\/em>.<\/li>\n<\/ul>\n<p>And, in the second case, we retrieve the Hoare powerspace of\u00a0<em>X<\/em> for the theory\u00a0<strong>T<\/strong> of\u00a0unital inflationary semilattices. \u00a0I should have mentioned that these results (at least for\u00a0<em>X<\/em> sober in the case of the second one) follow from more general category-theoretic theorems.<\/p>\n<p>We start with the following General Adjoint Functor Theorem, due to Peter Freyd:<\/p>\n<p><strong>Theorem.<\/strong> \u00a0Let\u00a0<em>U<\/em> be a functor from a category\u00a0<strong>D<\/strong> to a category\u00a0<strong>C<\/strong>. \u00a0If:<\/p>\n<ol>\n<li><strong>D<\/strong> is complete and\u00a0<em>U<\/em> preserves all limits, and<\/li>\n<li>(solution set condition) for every object\u00a0<em>C<\/em> of\u00a0<strong>C<\/strong>, there is a small family of morphisms <em>f<sub>i<\/sub><\/em> : <em>C<\/em> \u2192\u00a0<em>U<\/em> (<em>D<sub>i<\/sub><\/em>),\u00a0<em>i<\/em> in\u00a0<em>I<\/em>, such that every morphism from\u00a0<em>C<\/em> to some object\u00a0<em>U<\/em>(<em>D<\/em>) factors through some <em>f<sub>i<\/sub><\/em>. \u00a0(&#8220;Small&#8221; means that\u00a0<em>I<\/em> is a set, not a proper class. \u00a0This is crucial.)<\/li>\n<\/ol>\n<p>Then\u00a0<em>U<\/em> has a left adjoint\u00a0<em>F<\/em> :\u00a0<strong>C<\/strong>\u00a0\u2192\u00a0<strong>D<\/strong>.<\/p>\n<p>A proof of that theorem, and of several useful variants, can be found on <a title=\"Adjoint Functor Theorems\" href=\"https:\/\/ncatlab.org\/nlab\/show\/adjoint+functor+theorem\">nCatLab<\/a>.<\/p>\n<p>Therefore, to show the existence of a\u00a0free T<sub>0<\/sub>\u00a0topological\u00a0<strong>T<\/strong>-algebra on a T<sub>0<\/sub> space <em>X<\/em>, it is enough to check that:<\/p>\n<ol>\n<li>the category of T<sub>0<\/sub>\u00a0topological\u00a0<strong>T<\/strong>-algebras has all limits (equivalently, all products, and subspaces closed under the algebraic operations), and that the underlying topological spaces are the corresponding topological limits (i.e., the corresponding products, the corresponding subspaces);<\/li>\n<li>the solution set condition holds. \u00a0To that end, we need to show that every continuous map <em>f<\/em> : <em>C<\/em> \u2192\u00a0<em>U<\/em>(<em>D<\/em>) factors through one of a small set of of morphisms of the same form. \u00a0There is a smallest\u00a0T<sub>0<\/sub>\u00a0topological\u00a0<strong>T<\/strong>-subalgebra <em>D&#8217;\u00a0<\/em>of\u00a0<em>D<\/em> that contains the image of\u00a0<em>f<\/em>. \u00a0It is easy to check that\u00a0<em>D&#8217;<\/em> is isomorphic (as a\u00a0T<sub>0<\/sub>\u00a0topological\u00a0<strong>T<\/strong>-algebra) to some quotient of a term algebra build on\u00a0<em>C<\/em> seen as a set of variables, with some suitable topology. \u00a0Those quotients form a set, not a class, because there is only a small set of equivalence relations on a given set, and a small set of topologies on a given set.<\/li>\n<\/ol>\n<p>That was only a sketch of an argument. \u00a0If you look at it more closely, some of the details resemble what we have done in <a title=\"Powerdomains and hyperspaces IV: theories\" href=\"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=664\">Part IV<\/a>. \u00a0(I haven&#8217;t dealt with the case of sober algebras which, as before, require to take a sobrification of a space in the process.)<\/p>\n<p>So we would not gain much by using the General Adjoint Functor Theorem after all. \u00a0In practice, the next theorem is more useful.<\/p>\n<h2>The Special Adjoint Functor Theorem<\/h2>\n<p>The Special Adjoint Functor Theorem (or, familiarly, SAFT) follows from the General Adjoint Functor Theorem, and replaces the solution set condition by more manageable conditions.<\/p>\n<p>One of those conditions is about subobjects, and is called <em>well-poweredness<\/em>.<\/p>\n<p>A mono\u00a0<em>m<\/em> from an object\u00a0<em>A<\/em> to an object\u00a0<em>B<\/em> serves as a good specification of the notion of subset (<em>A<\/em> of <em>B<\/em>) in the category of sets&#8230; except that we obtain all isomorphic copies of the desired subset of <em>B<\/em> this way at least. \u00a0Let us say that two monos\u00a0<em>m<\/em> from <em>A<\/em> to <em>B<\/em>\u00a0and\u00a0<em>m&#8217;<\/em> from<em> A&#8217;<\/em> to<em> B<\/em> are <em>equivalent<\/em> if and only if there is an iso\u00a0<em>i<\/em> from\u00a0<em>A<\/em> to\u00a0<em>A&#8217;<\/em> such that\u00a0<em>m&#8217;<\/em> o\u00a0<em>i<\/em> =\u00a0<em>m<\/em>. \u00a0A subobject of\u00a0<em>B<\/em> is an equivalence class of monos with target\u00a0<em>B<\/em>.<\/p>\n<p>This definition works in any category. \u00a0In the category\u00a0<strong>Set<\/strong> of sets,\u00a0two monos <em>m<\/em> and <em>m&#8217;<\/em> with the same target\u00a0<em>B<\/em> are equivalent if and only if they have the same image (a subset of\u00a0<em>B<\/em>), so it is safe to equate the notion of subobject in\u00a0<strong>Set<\/strong> with the notion of subset. \u00a0In the category\u00a0<strong>Top<\/strong> of topological spaces, a subobject is a topological subspace. \u00a0And so on.<\/p>\n<p>In all those examples, the collection of all subobjects of a given object forms a (small) set, not a proper class. \u00a0When that happens, we say that the category is\u00a0<em>well-powered<\/em>.<\/p>\n<p>Technically, there is a small problem with that definition: the class of monos with target\u00a0<em>B<\/em> is not a set, but a proper class, and in fact each equivalence class is a proper class, too. \u00a0You cannot build the quotient of a proper class in von Neumann-Bernays-G\u00f6del set theory, because you cannot build collections of proper classes in that theory. \u00a0Instead, the definition of well-poweredness goes through the selection of a representative mono in each equivalence class: a category is\u00a0<em>well-powered<\/em> if and only if for each object <em>B<\/em>, there is a (small) set of monos with target\u00a0<em>B<\/em> such that every mono with target\u00a0<em>B<\/em> factors through one of those.<\/p>\n<p>The second condition is the existence of a\u00a0<em>coseparating set<\/em> of objects. \u00a0This is a set\u00a0<em>E<\/em> of objects such that, whenever you have two distinct morphisms\u00a0<em>f<\/em>,\u00a0<em>g<\/em> from an object\u00a0<em>A<\/em> to an object\u00a0<em>B<\/em>, \u00a0then there is a morphism\u00a0<em>h<\/em> from\u00a0<em>B<\/em> to some object\u00a0<em>C<\/em> in\u00a0<em>E<\/em> such that\u00a0<em>h<\/em> o\u00a0<em>f<\/em> \u2260\u00a0<em>h<\/em> o\u00a0<em>g<\/em>.<\/p>\n<p>For example,\u00a0<strong>Set<\/strong> has a coseparating set of objects, consisting of the sole object {0, 1}: if\u00a0<em>f<\/em>\u2260<em>g<\/em>, then\u00a0<em>f<\/em>(<em>a<\/em>)\u2260<em>g<\/em>(<em>a<\/em>) for some\u00a0<em>a<\/em> in\u00a0<em>A<\/em>, and we can take<em>\u00a0<\/em>the characteristic map of {<em>f<\/em>(<em>a<\/em>)} for\u00a0<em>h<\/em>.<\/p>\n<p>Similarly, the category <strong>Top<\/strong><sub>0<\/sub> of all T<sub>0<\/sub> topological spaces has a coseparating set, consisting of the sole Sierpi\u0144ski space <strong>S<\/strong>: this time, if\u00a0<em>f<\/em>(<em>a<\/em>)\u2260<em>g<\/em>(<em>a<\/em>), then you can find an open subset\u00a0<em>V<\/em> that contains\u00a0<em>f<\/em>(<em>a<\/em>) but not\u00a0<em>g<\/em>(<em>a<\/em>), or\u00a0<em>g<\/em>(<em>a<\/em>) but not\u00a0<em>f<\/em>(<em>a<\/em>), then take the characteristic map of\u00a0<em>V<\/em> for\u00a0<em>h<\/em>. \u00a0The same coseparating set works for the category of sober spaces, but the category\u00a0<strong>Top<\/strong> of all topological spaces does\u00a0<em>not<\/em> have a coseparating set of objects (take functions\u00a0<em>f<\/em>,\u00a0<em>g<\/em> with target spaces all having the indiscrete topology: you would need isomorphic copies of all sets just to separate those, and those form a proper class).<\/p>\n<p>\u00a0<\/p>\n<p>Having understood all that, we proceed to the SAFT, again due to Peter Freyd:<\/p>\n<p><strong>Theorem.<\/strong>\u00a0\u00a0Let\u00a0<em>U<\/em>\u00a0be a functor from a category\u00a0<strong>D<\/strong>\u00a0to a category\u00a0<strong>C<\/strong>. \u00a0If:<\/p>\n<ol>\n<li><strong>D<\/strong>\u00a0is complete and\u00a0<em>U<\/em>\u00a0preserves all limits, and<\/li>\n<li><strong>D<\/strong> is well-powered and has a coseparating set.<\/li>\n<\/ol>\n<p>Then\u00a0<em>U<\/em>\u00a0has a left adjoint\u00a0<em>F<\/em>\u00a0:\u00a0<strong>C<\/strong>\u00a0\u2192\u00a0<strong>D<\/strong>.<\/p>\n<p>That is much easier to use! \u00a0Indeed the existence of the free T<sub>0<\/sub>\u00a0(resp., sober) topological <strong>T<\/strong>-algebra is now immediate from that theorem.<\/p>\n<p>You can find a proof of the SAFT in many books, and also on the Web, for example <a title=\"SAFT by Julia Goedecke\" href=\"https:\/\/www.dpmms.cam.ac.uk\/~jg352\/pdf\/SpecialAdjointFunctorTheorem.pdf\">here<\/a>.<\/p>\n<p>You will realize that what we have done in <a title=\"Powerdomains and hyperspaces IV: theories\" href=\"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=664\">Part IV<\/a> is just an instance of that general construction. \u00a0Notably, look at the construction of the free T<sub>0<\/sub>\u00a0(resp., sober) topological <strong>T<\/strong>-algebra we have done on a space <em>X<\/em> in <a title=\"Powerdomains and hyperspaces IV: theories\" href=\"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=664\">Part IV.<\/a>\u00a0 Our first step was to embed\u00a0<em>X<\/em> into the powerset <strong>P<\/strong>(<strong>O<\/strong>(<em>X<\/em>)). \u00a0We can equate the latter with the product <strong>S<\/strong><sup><strong>O<\/strong>(<em>X<\/em>)<\/sup> of plenty of copies of\u00a0Sierpi\u0144ski space\u00a0<strong>S<\/strong>, one per open subset of\u00a0<em>X<\/em>.<\/p>\n<p>Remember that\u00a0<strong>S<\/strong> is the unique element of the coseparating set in <strong>Top<\/strong><sub>0<\/sub>&#8230; this is not merely a coincidence. \u00a0The proof of the SAFT works the same way, by building a big product of objects taken from the coseparating set, and indexed by plenty of morphisms.<\/p>\n<p>Eventually, we obtain the free whatever-we-are-interested-in as a subobject of that big product.<\/p>\n<p>We have seen other instances of that construction in the <a href=\"https:\/\/www.cambridge.org\/gb\/knowledge\/isbn\/item7069109\/Non-Hausdorff%20Topology%20and%20Domain%20Theory\/?site_locale=en_GB\">book<\/a>. \u00a0The most notable is the construction of the Stone-\u010cech compactification (Exercise 6.7.23) of a space\u00a0<em>X<\/em>, namely of a free compact T<sub>2<\/sub> space on a T<sub>3\u00bd<\/sub> topological space\u00a0<em>X<\/em>. \u00a0We have built it as a certain subspace of plenty of copies of [0, 1], one per continuous map from\u00a0<em>X<\/em> to [0, 1]. \u00a0Notice that [0, 1] is the unique element of a cogenerating set in the category of T<sub>3\u00bd<\/sub> topological spaces&#8230; by the definition of T<sub>3\u00bd<\/sub> topological space (Exercise 6.2.18).<\/p>\n<p><strong>Happy summer holidays!<\/strong><\/p>\n<p>I&#8217;m going on summer holidays in a few days. \u00a0Let me wish you happy summer holidays if you take any (in the past or in the future).<\/p>\n<p>When I come back, I&#8217;ll go to the <a title=\"Domains XII\" href=\"https:\/\/booleconferences.ucc.ie\/gbmsc2015\/domainsxii\">Domains XII<\/a> conference in Cork, Ireland. \u00a0This is part of the larger <a title=\"Boole conferences\" href=\"https:\/\/booleconferences.ucc.ie\/\">Boole conferences<\/a>, organized on the bicentenary of George Boole&#8217;s birth. \u00a0I&#8217;ve been invited to give a talk there, and because of that, and because of the many things that I will have to do late August and early September, I may be late for my next monthly post.<\/p>\n<p>I have plenty of things waiting to be told here. \u00a0I haven&#8217;t yet said why monad algebras are so useful, and how they related to free (topological, sober) algebras. \u00a0I haven&#8217;t talked about some of the other prominent powerspace theories, and notably about the Smyth powerspace. \u00a0<a title=\"Ideal models of spaces\" href=\"https:\/\/www.keyemartin.com\/\">Keye Martin<\/a> drew my attention to a paper of his about <a title=\"Ideal models of spaces\" href=\"https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0304397502006989\">ideal models of spaces<\/a>: an ideal domain is a dcpo where every point is either finite or maximal; this is a very specific kind of (necessarily algebraic) domain, of which the dcpo of finite and infinite words ordered by prefix is a typical example; he managed to prove, inter alia, that any space that has a countably-based model at all has one that is ideal in this sense, and that the metric spaces that have ideal models are exactly the completely metrizable spaces. \u00a0Some day, I would also like to talk about bitopological spaces, or on some recent results by Kou, Jia, Li, and Jung on cartesian-closed categories of quasi-continuous domains&#8230; that will have to wait.<\/p>\n<p style=\"text-align: right;\">\u2014 <a href=\"https:\/\/www.lsv.ens-paris-saclay.fr\/~goubault\/?l=en\" rel=\"attachment wp-att-993\">Jean Goubault-Larrecq<\/a> (July 21st, 2015)<img loading=\"lazy\" decoding=\"async\" class=\"wp-image-993 alignright\" src=\"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/wp-content\/uploads\/2016\/08\/jgl-2011.png\" alt=\"jgl-2011\" width=\"32\" height=\"44\" \/><\/p>\n\n\n<p class=\"wp-block-paragraph\"><\/p>\n","protected":false},"excerpt":{"rendered":"<p>You have probably sweated a lot at trying to understand the constructions of Part IV. \u00a0They rest on a lot of topology and domain theory. \u00a0Perhaps surprisingly (if you do not know it already), they are completely generic, and work &hellip; <a href=\"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/?page_id=719\">Continue reading <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"open","ping_status":"open","template":"","meta":{"footnotes":""},"class_list":["post-719","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/pages\/719","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=719"}],"version-history":[{"count":13,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/pages\/719\/revisions"}],"predecessor-version":[{"id":5956,"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=\/wp\/v2\/pages\/719\/revisions\/5956"}],"wp:attachment":[{"href":"https:\/\/projects.lsv.ens-paris-saclay.fr\/topology\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=719"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}