You have probably sweated a lot at trying to understand the constructions of Part IV. They rest on a lot of topology and domain theory. Perhaps surprisingly (if you do not know it already), they are completely generic, and work in any category with enough structure. This is what we learn from Peter Freyd’s adjoint functor theorems, of which there are two: the general one, and the special one.
The General Adjoint Functor Theorem
In Part IV, we have seen that:
- For every T0 topological space X, there is a free T0 topological T-algebra on X.
- For every T0 topological space X, there is a free sober T-algebra on X.
And, in the second case, we retrieve the Hoare powerspace of X for the theory T of unital inflationary semilattices. I should have mentioned that these results (at least for X sober in the case of the second one) follow from more general category-theoretic theorems.
We start with the following General Adjoint Functor Theorem, due to Peter Freyd:
Theorem. Let U be a functor from a category D to a category C. If:
- D is complete and U preserves all limits, and
- (solution set condition) for every object C of C, there is a small family of morphisms fi : C → U (Di), i in I, such that every morphism from C to some object U(D) factors through some fi. (“Small” means that I is a set, not a proper class. This is crucial.)
Then U has a left adjoint F : C → D.
A proof of that theorem, and of several useful variants, can be found on nCatLab.
Therefore, to show the existence of a free T0 topological T-algebra on a T0 space X, it is enough to check that:
- the category of T0 topological T-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);
- the solution set condition holds. To that end, we need to show that every continuous map f : C → U(D) factors through one of a small set of of morphisms of the same form. There is a smallest T0 topological T-subalgebra D’ of D that contains the image of f. It is easy to check that D’ is isomorphic (as a T0 topological T-algebra) to some quotient of a term algebra build on C seen as a set of variables, with some suitable topology. Those 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.
That was only a sketch of an argument. If you look at it more closely, some of the details resemble what we have done in Part IV. (I haven’t dealt with the case of sober algebras which, as before, require to take a sobrification of a space in the process.)
So we would not gain much by using the General Adjoint Functor Theorem after all. In practice, the next theorem is more useful.
The Special Adjoint Functor Theorem
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.
One of those conditions is about subobjects, and is called well-poweredness.
A mono m from an object A to an object B serves as a good specification of the notion of subset (A of B) in the category of sets… except that we obtain all isomorphic copies of the desired subset of B this way at least. Let us say that two monos m from A to B and m’ from A’ to B are equivalent if and only if there is an iso i from A to A’ such that m’ o i = m. A subobject of B is an equivalence class of monos with target B.
This definition works in any category. In the category Set of sets, two monos m and m’ with the same target B are equivalent if and only if they have the same image (a subset of B), so it is safe to equate the notion of subobject in Set with the notion of subset. In the category Top of topological spaces, a subobject is a topological subspace. And so on.
In all those examples, the collection of all subobjects of a given object forms a (small) set, not a proper class. When that happens, we say that the category is well-powered.
Technically, there is a small problem with that definition: the class of monos with target B is not a set, but a proper class, and in fact each equivalence class is a proper class, too. You cannot build the quotient of a proper class in von Neumann-Bernays-Gödel set theory, because you cannot build collections of proper classes in that theory. Instead, the definition of well-poweredness goes through the selection of a representative mono in each equivalence class: a category is well-powered if and only if for each object B, there is a (small) set of monos with target B such that every mono with target B factors through one of those.
The second condition is the existence of a coseparating set of objects. This is a set E of objects such that, whenever you have two distinct morphisms f, g from an object A to an object B, then there is a morphism h from B to some object C in E such that h o f ≠ h o g.
For example, Set has a coseparating set of objects, consisting of the sole object {0, 1}: if f≠g, then f(a)≠g(a) for some a in A, and we can take the characteristic map of {f(a)} for h.
Similarly, the category Top0 of all T0 topological spaces has a coseparating set, consisting of the sole Sierpiński space S: this time, if f(a)≠g(a), then you can find an open subset V that contains f(a) but not g(a), or g(a) but not f(a), then take the characteristic map of V for h. The same coseparating set works for the category of sober spaces, but the category Top of all topological spaces does not have a coseparating set of objects (take functions f, g 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).
Having understood all that, we proceed to the SAFT, again due to Peter Freyd:
Theorem. Let U be a functor from a category D to a category C. If:
- D is complete and U preserves all limits, and
- D is well-powered and has a coseparating set.
Then U has a left adjoint F : C → D.
That is much easier to use! Indeed the existence of the free T0 (resp., sober) topological T-algebra is now immediate from that theorem.
You can find a proof of the SAFT in many books, and also on the Web, for example here.
You will realize that what we have done in Part IV is just an instance of that general construction. Notably, look at the construction of the free T0 (resp., sober) topological T-algebra we have done on a space X in Part IV. Our first step was to embed X into the powerset P(O(X)). We can equate the latter with the product SO(X) of plenty of copies of Sierpiński space S, one per open subset of X.
Remember that S is the unique element of the coseparating set in Top0… this is not merely a coincidence. The 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.
Eventually, we obtain the free whatever-we-are-interested-in as a subobject of that big product.
We have seen other instances of that construction in the book. The most notable is the construction of the Stone-Čech compactification (Exercise 6.7.23) of a space X, namely of a free compact T2 space on a T3½ topological space X. We have built it as a certain subspace of plenty of copies of [0, 1], one per continuous map from X to [0, 1]. Notice that [0, 1] is the unique element of a cogenerating set in the category of T3½ topological spaces… by the definition of T3½ topological space (Exercise 6.2.18).
Happy summer holidays!
I’m going on summer holidays in a few days. Let me wish you happy summer holidays if you take any (in the past or in the future).
When I come back, I’ll go to the Domains XII conference in Cork, Ireland. This is part of the larger Boole conferences, organized on the bicentenary of George Boole’s birth. I’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.
I have plenty of things waiting to be told here. I haven’t yet said why monad algebras are so useful, and how they related to free (topological, sober) algebras. I haven’t talked about some of the other prominent powerspace theories, and notably about the Smyth powerspace. Keye Martin drew my attention to a paper of his about ideal models of spaces: 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. Some 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… that will have to wait.
— Jean Goubault-Larrecq (July 21st, 2015)