Want to take part in these discussions? Sign in if you have an account, or apply for one below
Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.
1 to 36 of 36
Ben, I’m having a hard time following all of this, but I would like to direct your attention to a generalization of some of these domain-theoretic ideas to categories, in the form of accessible categories and locally presentable categories. There is some material in the nLab on this, but some of the articles are in need of improvement; you might want to look at the text Locally Presentable and Accessible Categories by Adámek and Rosicky, and also Accessible Categories: the Foundations of Categorical Model Theory by Makkai and Paré.
In brief, the analogue of a dcpo is a filtered-cocomplete category C (see filtered colimit), and the analogue of a compact element in a dcpo is an object c of C such that hom(c,−):C→Set preserves filtered colimits. Such objects may be called finitely presentable; for C=Grp, these objects are indeed the finitely presentable groups. (There is a similar statement for the category of models of any algebraic theory.) If C is cocomplete and every object is canonically a filtered colimit of fnitely presentable objects, we say C is locally finitely presentable. Such categories generalize algebraic lattices.
Cat (the category of small categories) is locally finitely presentable. This is a category of models of an essentially algebraic theory (a theory involving a list of partially defined algebraic operations where the domain of an operation is equationally definable in terms of operations occurring earlier in the list). It is a theorem that essentially algebraic categories are basically the same thing as locally presentable categories (Adámek and Rosicky, chapter 3).
I hope this provides food for thought – I strongly recommend these texts.
Todd has already answered most of these questions, Ben. You might also try Adámek's paper 'A categorical generalization of Scott domains', Math. Struct. in Comp. Sci. 1997.
Finite limits are given by finite products (= meets in a poset) and equalizers. I don't think an arbitrary dcpo will have meets. Equalizers in a poset are trivial, because all parallel arrows are equal by definition.
I believe I’ve already answered the most important of these questions.
if you draw a simple diagram of a supremum for a directed set, you basically get the diagram of a limit
No, you get the diagram for a colimit.
The question is this: does the category X have all finite limits?
Do you mean: does it have all finite colimits? No, consider a set as a discrete preorder. Every directed subset is a singleton (!), and the colimit of a singleton is its unique element. So sets are dcpo’s. They are clearly neither finitely cocomplete nor finitely complete.
Does it have equalizers?
Vacuously, yes. An equalizer is a limit of a diagram consisting of a pair of parallel arrows. The vacuous case is when the parallel arrows are identical; the equalizer is the identity arrow on the domain. (If you actually meant coequalizer, then it would be the identity on the codomain.) Notice that in a poset, parallel arrows are equal because in a poset, there is at most one arrow x→y between any two given objects.
what categorical property do the compact elements display?
An element x in a dcpo is compact if hom(x,−):P→Set (or equivalently for a poset, hom(x,−):P→{⊥,⊤}) preserves filtered (aka directed) colimits. I had mentioned this in comment 2, but perhaps I should amplify.
An element x is compact if, for any directed subset D⊂P, we have
x≤supD⇔∃d∈Dx≤dNotice the direction ⇐ is automatic; only the direction ⇒ has content. Here supD is a directed (filtered) colimit, and the left side holds if hom(x,colimD)=⊤. The right side holds iff {hom(x,d):d∈D} contains ⊤, i.e., if the sup or colimit of {hom(x,d):d∈D}⊆{⊥,⊤} is ⊤. So the compactness condition translates to saying
hom(x,colimd∈Dd)=⊤⇔colimd∈Dhom(x,d)=⊤which is equivalent to hom(x,−) preserving colimits of directed subsets D.
what are the axioms of the category X?
That it is a filtered cocomplete poset. See comment 2.
thanks for the references
There’s an embarrassment-of-riches problem here, but another book in my library that I find useful is Paul Taylor’s Practical Foundations of Mathematics. He has some material on the stuff you’re asking about. Another good book is Johnstone’s Stone Spaces. There are many others, of course.
what are the axioms of the category X?
That it is a filtered cocomplete poset.
As a list of conditions on a category, you might prefer to say that it has all filtered colimits and is thin.
Thanks. I’m not sure I’ve ever heard the word ’thin’ in this sense. Can you point me to a reference outside the nLab for this?
Sure, no problem Ben. Hopefully I’ve given you satisfactory answers to the questions you asked in #3.
@Ben: I think we should slow down a moment, because it’s not so clear to me that your intended meanings of words and phrases are the ones I or other people might be receiving. So allow me to ask a few questions.
By FDHilb, I take it you mean the category finite-dimensional (complex) Hilbert spaces and linear maps. But how are you understanding this? As an ordinary category, or as a symmetric monoidal category, or as a †-symmetric monoidal category, or what?
This is actually quite important. Normally when you say ’internal category’ in a category C, people usually assume you mean C has finite limits and we are using the standard notion of internal category in a finitely complete category. Note that FDHilb is finitely complete! (As a mere category, it is equivalent to the category of finite-dimensional vector spaces over ℂ.) However, I have a feeling, based on previous discussions of yours, that this is not the notion of internal category you mean.
There is a much more sophisticated notion of internal category in a monoidal category, which might be the notion you meant, but before we proceed I have to make sure. Once again, I don’t see that the †-structure is being used, so that for all intents and purposes for this notion, one could just as well use FDVect with its standard tensor product, which is monoidally equivalent to FDHilb.
I think there are a bunch more questions I could ask, but I’ll stop here for now. Please give mathematically precise answers; I will take a very dim view of phrases like “ultimate reality category”, “transformations of the apparatus”, and vague mention of work of Coecke and Vicary.
If you don’t make it a †-category, then you ought to use only the linear maps with norm at most 1 as morphisms. (That way, you get the correct isomorphisms.) Then Hilb is distinguished from Vect.
However, the internal categories in this FDHilb are (if I’m not messing up) all discrete, so it’s still not what we want.
Okay, great. Maybe you could start by telling me what is this R and Q, or at least giving me a link to the paper of Vicary you are referring to. I haven’t thought deeply about internal categories in the monoidal category FDVect, but this doesn’t seem too scary, since FDVect is self-dual and people have a lot of experience with f.d. algebras over ℂ, f.d. bimodules between them, and so on.
I have quite a bit going on right now, so progress could be slow at first.
Ben, to understand this definition, one should consider first the case where the monoidal product is a cartesian product. In fact, one should start with Set with its cartesian product. Do you know what happens in this case? In other words, how you would characterize the notion of “internal category in the monoidal category” (Set,×) in more familiar terms?
(By the way, TobyBartels is Toby – not Bart. (-: )
What you might want to do first is to understand what comonoids in the monoidal category (Set,×) are like. (Hint: they are forced to be something very simple.) This is not meant to be a difficult exercise at all, but it’s something pretty fundamental to a general understanding of (cocommutative) comonoids – the basic idea has far-reaching implications, which form a bridge between symmetric monoidal categories and cartesian categories.
Hey, I am trying to do this example.
In the case of (Set,×), I think sets are the objects, with a cartesian product and singleton as the unit and morphisms of these comonoids are spans.
μ:a→a×a
And
ν:a→I
The objects of the category of comonoids each come with structural maps mu and nu. nu morphisms come from the fact that, there is exactly one map from any set to a singleton. mu maps are confusing me, its some kind of injection into the cartesian product…. I see, μ(a)=(a,a).
Composition of spans is due to the presence of pullbacks in Set. The bicategory nature means that the “hom-collections” are actually categories of spans and….span morphisms (?) and i don’t know what a span morphism would look like…..except that it is probably a function from the spanning set to another spanning set. The span morphisms have to preserve the mu and nu morphisms and that means making a diagram commute. I have a little drawing here where a span from comonoids A and B (A←Q→B) is commuting with mu and nu. It involves the projection πQ:Q×Q→Q
Why spans? Why are the comonoid morphisms spans in this example?
Meanwhile, a monad, according to nlab, in a bicategory is an object, an endomap and various 2-cells with two important diagrams as axioms for the endomap. I am trying to cook up some calculations with a 3 element set, but it is all a little unfamiliar. I guess, given any set, and an appropriately chosen endomap and 2-cell, one ends up with a monad. What is confusing is, first, how we are allowed to see these monads as categories. Second, doing a simple little example like a three element set is confusing because there are so many possible spans that one can use as the endomap. I guess every span will give a different monad…?
Struggling with it…
You seem to be getting the hang of some of it, anyway. Let me lend a hand.
First, suppose that (X,δ:X→X×X,ε:X→1) is a comonoid in (Set,×). (N.B.: we are not a priori assuming this δ is the diagonal map. Here it is merely notation for the comonoid comultiplication.) Then ε=!:X→1 has to be the unique map to the 1-point set (1 is terminal). Now δ:X→X×X, being a map to a cartesian product, is uniquely determined by the pair of maps π1∘δ:X→X, π2∘δ:X→X, where π1,π2 are the two projections from X×X to X. But notice that
(π1:X×X→X)=(X×XidX×!→X×1≅X);(π2:X×X→X)=(X×X!×idX→1×X≅X)and so, for example,
(Xδ→X×Xπ1→X)=(Xδ→X×XidX×ε→X×1≅X)but the right side is the identity on X, according to one of the axioms for a comonoid (one of the counit axioms). By similar reasoning, π2∘δ=idX, using the other counit axiom. Therefore
δ=⟨idX,idX⟩:X→X×X;in other words, we have proved that δ is indeed the diagonal map! Conclusion: there is exactly one comonoid structure on any object X, whose comultiplication is the standard diagonal and whose counit is the projection !:X→1. Notice the same argument applies to any category with cartesian products, in place of Set. It is a simple, but in some sense important and far-reaching argument. Notice also that these comonoids are cocommutative.
Now that we know the nature of comonoids in (Set,×), we can consider right comodules, left comodules, and bicomodules. But these can be dispatched with, using arguments very similar to the above. For example, suppose (C,β:C→X×C) is a left comodule with respect to the unique comonoid structure on X. Again, β, being a map to a cartesian product, is uniquely determined by a pair of maps: β=⟨β1,β2⟩:C→X×C. Using one of the comodule axioms, it may be shown that β2=idC. You should check that the other comodule axiom is automatically satisfied, for any choice of β1. Therefore, a (left) comodule over X is nothing but an object C equipped with a map f=β1:C→X.
Similarly, it may be shown that the data of right comodule over Y amounts to an object C equipped with a map g:C→Y. A left-X right-Y comodule (or bicomodule) amounts to the same thing as a pair of maps
Xf←Cg→Y(you should check that the compatibility condition between the separate left comodule and right comodule structures, as required by the definition of bicomodule, are automatically satisfied in the cartesian case). In other words, a bicomodule between comonoids X and Y amounts to a span from X to Y.
One should go on to check that bicomodule composition amounts to the usual span composition. I’ll save this for another time (too busy today). Thus, a monad in the bicategory of comonoids and bicomodules (w.r.t. a finitely complete category) amounts to a monad in the bicategory of spans. The next thing we should discuss after that is how a monad in the bicategory of spans may be seen as amounting to a category structure (but, again, I’m too busy to do more about that today).
I think there is a typo in the nlab section on bicomodules
http://ncatlab.org/nlab/show/bicomodule
ρc:M→C⊗M
There’s a D instead of a C.
Fixed. If you see obvious errors, please feel free to fix them yourself. :-)
Since Todd didn’t say it explicitly, Ben, I will: you were correct. (At least your version as edited 5 hours ago is correct.)
Todd, I would be honoured.
Hey Guys,
I want to thank you both for your help. I am busy at work and have found a few hours to follow along with Todd. He suggested I show that the second comonoid axiom is satisfied for any β1 and this can be shown using function/element notation:
Let β1 be any function β1:C→X
The second axiom states that
(εX×idC)˙β=idc
So, we would expect that, for c∈C
β(c)=(β1(c),c)
and
(εX×idc)(β(c))=({⋆},c)=c
and this is true for any function β1
For the next part, we want to check the compatibility between the left and right comodules. Again, using function, element notation:
(f×IdY)(g(c))=(f×IdY)(c,g(c))=(f(c),c,g(c))
and
(Idx×g)(f(c))=(Idx×g)(f(c),c)=(f(c),c,g(c))
and this is true for any f,g.
Hi, Ben. I have just a couple of comments, before we press on.
By the “other axiom” for comodule structures β:C→X×C, I meant the one which asserts commutativity of the diagram
Cβ→X×Cβ↓↓idX×βX×C→δX×idCX×X×CThe other comment is notational. I use the notation f×g, where f:A→B and C→D are maps, to mean the map f:A×C→B×D. Then, given f:A→B and g:A→C (same domain), I use ⟨f,g⟩ to denote the composite
AδA→A×Af×g→B×CMany people, including you in your last comment, use f×g where I would use ⟨f,g⟩. This practice saves on LaTeX characters of course, but I find it confusing or ambiguous. Thus, I would say (f×g)(a,c)=(f(a),g(c)) and ⟨f,g⟩(a)=(f(a),g(a)), and not (f×g)(a)=(f(a),g(a)).
Pressing on now, let’s consider bicomodule composition, both in general monoidal categories and in cartesian monoidal categories. Let X, Y, and Z be comonoids in a monoidal category M, and let (C,α:C→X⊗C,α′:C→C⊗Y) and (D,β:D→Y⊗D,β′:D→D⊗Z) be bicomodules (from X to Y and Y to Z, respectively). To compose these, we just dualize the way we compose bimodules, which involves taking a tensor product ⊗Y over the “middle” monoid Y, which in turn involves a familiar coequalizer construction. Dualizing, we take the equalizer of a pair of maps
E→C⊗Dα′⊗1D→→1C⊗βC⊗Y⊗Dand on this equalizer, one can define canonical maps γ:E→X⊗E, γ′:E→E⊗Y, provided that tensoring on either side – X⊗− or −⊗Z – preserves (reflexive) equalizers. In this way one gets a left-X right Z bicomodule E, and this is the bicomodule composite of C and D.
Again, it is good to work out what is going on here in the cartesian monoidal case (which is much simpler). Here, the equalizer described above works out to be a construction of the pullback
E→C↓↓α′2D→β1Yand we can also check that X×− and −×Z preserve reflexive equalizers, or more simply, pullbacks. In any case, this pullback construction is precisely how we compose spans from X to Y and from Y to Z:
CDα1↙↘α′2β1↙↘β′2XYZto get a span from X to Z.
Now, an important insight (we are still in the monoidal case) is that the structure of a category C can be given as a span
C1dom↙↘codC0C0equipped with a monad structure on this span, in the bicategory of spans. Here, a monad structure boils down to morphisms of spans from C0 to C0 of the form
m:C1×C0C1→C1,u:C0→C1where C1×C0C1 is the apex of the span-composite C∘C, and m is the function which maps a composable pair of arrows to its composite, and where C0 is the apex of the span consisting of two identity arrows going down to C0, and u maps an element of C0 (“an object”) to its identity arrow.
The point is that this notion of category can be carried out analogously in the bicategory of bicomodules in a monoidal category (again, provided the technical equalizer preservation assumption is satisfied). We can try it out for example in Vectfd (finite-dimensional vector spaces over some field), which is related to what you were asking about in comment 10. The nice thing about this case is that we have an equivalence Vectopfd≃Vectfd, given by taking dual spaces. Thus, we have an option between considering monads in the bicategory of bicomodules between comonoids (called coalgebras in the Vectfd-case) or, dually but equivalently, comonads (C,ε:C→R,δ:C→C⊗RC) in the bicategory of finite-dimensional bimodules between finite-dimensional algebras R. These are the same as coalgebras in the category of R-bimodules.
There are lots of these things around, and it might be good to collect a stockpile of them. One thing I should warn about, based on a quick glance at Vicary’s paper, is that his RQ construction is (if I’m not mistaken) a cofree coalgebra construction, which takes us outside the realm of Vectfd (it’s an infinite-dimensional construction). There may be some workarounds, but it’s to say that I’m not sure where you’d like to go from here.
There are good category-theoretic reasons, not just Todd’s personal preference, for using f×g and ⟨f,g⟩ as he does. (They may be extracted from pairing, although you don’t really have to read them.)
Hi,
I am not sure how to proceed. I have to try all this stuff out, first.
1 to 36 of 36