Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Background

For my PhD dissertation, I've developed a categorical generalization of many different systems of denotational semantics for light linear logic (LLL). I'd like to see if I can use this generalization to find a more "natural" (in the colloquial sense of the word) denotational semantics for LLL. At its core is a symmetric monoidal closed category with two functors on it. One of the functors is monoidal, and the other is not (well, it could be monoidal, but then it's a trivial example). There are some other requirements, but for the moment, I'm mostly curious about how common it is to have non-monoidal functors in the first place.

Question

If you know of an example where someone uses a non-monoidal functor $T$ on a symmetric monoidal closed category $\mathbb{C}$, I'd like to hear about it. If you know of such a $T$ with natural transformations $d_A:TA \to TA\otimes TA$ and $e_A:TA \to 1$ forming comonoids for every object $A$, even better. If the category $\mathbb{C}$ also comes with a monoidal functor $S$, that would be even more fantastic. And if there's a natural transformation $T\Rightarrow S$, then I'll buy you dinner.

I've got examples (fibered phase spaces, stratified coherent spaces and locally bounded stratified cliques, games and discreet strategies, light length spaces), but they're all specifically created for this purpose, and I'm curious to see just how natural this kind of construction is.

share|improve this question
3  
Could you clarify a couple of points of terminology? First, some people use "monoidal functor" to mean what's sometimes called "lax monoidal" (so that you have not-necessarily-invertible maps $TA \otimes TB \to T(A \otimes B)$), while others use it to mean what's sometimes called "strong monoidal" (so that you have isomorphisms $TA \otimes TB \to T(A \otimes B)$). Second, what do you mean by a functor "on" a category $C$? Do you mean an endofunctor of $C$, or a functor $C \to \text{Set}$, or just a functor with domain $C$? –  Tom Leinster Mar 20 '12 at 14:02
4  
Actually, the more I think about this question, the more strange it seems. Take Set, with cartesian product. There are very many useful/natural endofunctors T of Set, and many of them aren't monoidal. Every set is a comonoid in a unique way, and for any endofunctor T of set, there are unique nat transfs d and e satisfying your conditions. Moreover, Set comes with a monoidal endofunctor S: the identity. It's surely the case that for some non-monoidal endofunctors T of Set, there exists a nat transf T => id. But I won't attempt to think of any, as I've just had lunch. –  Tom Leinster Mar 20 '12 at 14:57
4  
Because he's interested in models of linear logic, I'm going to speculate that Erik wants his symmetric monoidal category to not be cartesian. But what about $T(A)=$ the cofree comonoid on $A$? –  Mike Shulman Mar 20 '12 at 20:58
1  
By "monoidal", I mean lax monoidal, not strong monoidal, and by "a functor on $\mathbb{C}$, I mean an endofunctor on $\mathbb{C}$. Mike is absolutely correct. I'd prefer for the symmetric monoidal category to not be cartesian. Although now that I think about it, I forgot to mention that it should be a symmetric monoidal <em>closed</em> category. Technically, it's still a light linear category if it's cartesian, but it's not very interesting as a model of LLL. The same goes for when $S$ is the identity (it gets closer to a model for ordinary linear logic in that case). –  Erik Wennstrom Mar 21 '12 at 13:54
1  
@Erik guess Mike means $C$ symm monoidal closed such that $U \colon C \to \mathbf{Comon}(C)$ has a right adjoint $!$. Then you get a comonad $T = U\circ !$ on $C$. We obviously have $d_A \colon TA \to TA \otimes TA, e_a \colon TA \to A$ as you require, and these being nat transformations to the comonoid morphism eqs for each $!f$. This looks like Lafont categories but without cocommutativity. However, I think that $T$ will be monoidal anyway; as ($C$ being symmetric) the left adjoint $U$ is strong monoidal and then by doctrinal adjunction $!$ is lax monoidal, so $T= U\circ !$ lax monoidal –  Eduardo Pareja Tobes Mar 23 '12 at 15:38
show 4 more comments

3 Answers

As in my comment above, I'm not sure precisely what's being asked, so the following might or might not be a useful answer. In any case, it doesn't get me dinner.

Let $\mathbf{D}$ be the category of finite totally ordered sets, which is monoidal under disjoint union. It doesn't matter whether you take "all" finite totally ordered sets or just a skeleton, but the important thing is that the empty set is included — so $\mathbf{D}$ is not $\Delta$.

Small theorem: colax monoidal functors $\mathbf{D} \to \mathbf{Set}$ (yes, covariant) are the same thing as simplicial sets.

Generally, for any category $\mathcal{E}$ with finite products, colax monoidal functors $\mathbf{D} \to \mathcal{E}$ amount to simplicial objects in $\mathcal{E}$. (Proof: Proposition 3.1.7 of this, where I'm afraid $\mathbf{D}$ is called $\Delta$ and $\Delta$ is called $\Delta^+$.)

For a functor $T$ to be colax monoidal means that it comes equipped with maps $$ T(A \otimes B) \to TA \otimes TB, \qquad T(I) \to I $$ satisfying coherence axioms. In this case, they're not invertible unless the corresponding simplicial set is the nerve of a monoid. So, whether by "monoidal" you meant "lax monoidal" or "strong monoidal", the functors $\mathbf{D} \to \mathbf{Set}$ corresponding to simplicial sets are not usually monoidal.

Edit I see that Erik wanted examples of non-monoidal functors on symmetric monoidal categories. The monoidal category $\mathbf{D}$ isn't symmetric, so my example won't do. But there's something analogous in the symmetric world, concerning not simplicial sets but the $\Gamma$-sets of Segal.

Let $\mathbf{F}$ be the category of finite sets (including $\emptyset$), which is symmetric monoidal under disjoint union. Then a symmetric colax monoidal functor $\mathbf{F} \to \mathbf{Set}$ turns out to be the same thing as a $\Gamma$-set. Again, you can replace $\mathbf{Set}$ by any other category with finite products, and again these functors are not in general monoidal.

share|improve this answer
add comment

It seems like many of the standard examples of monads in functional programming can be transported to linear logic to produce examples of non-monoidal functors.

E.g., the linear state monad $T_S(A) = S \multimap S \otimes A$ has two evident natural transformations $T_S(A) \otimes T_S(B) \to T_S(A \otimes B)$ (corresponding to evaluating the left or the right argument first), but neither one will satisfy the coherence properties needed to be a monoidal functor. Likewise, the linear exception monad $E(A) = 1 \oplus A$ doesn't even have a natural transformation of the right type, and is not even strong.

Is there some extra condition you want? Perhaps if you could say something about the operational intuition I could be more helpful (your $T$ looks like the restricted exponential of light logic, and I guess $S$ is the "paragraph" modality?)

share|improve this answer
    
You're right; $T$ represents the restricted $!$ exponential of LLL and $S$ is the neutral $\mathsection$ exponential ("paragraph"). I kind of hinted at it above, but here it is explicitly: All I need to model intuitionist multiplicative light linear logic is a symmetric monoidal closed category equipped with a (not necessarily monoidal) endofunctor $T$, a monoidal endofunctor $S$, and natural transformations $d_A: TA\to TA\otimes TA$, $e_A: TA\to 1$, and $l_A: TA\to SA$ such that for every object $A$, $(TA,d_A,e_A)$ forms a commutative comonoid. –  Erik Wennstrom Mar 22 '12 at 15:35
    
(That "\mathsection" is supposed to be the section symbol, by the way. I wish you could preview comments.) <br> Of course, you can get these easily if you pick trivial versions. If $T$ is monoidal, then you end up with a model for elementary linear logic (by just ignoring $S$). And if in addition you've got a symmetric (lax) monoidal comonad, you get a model for non-light (heavy?) linear logic. <br> So that's why I'm looking for a specifically non-monoidal endofunctor. Most of the rest of the requirements are pretty ordinary, but I've never really worked with non-monoidal functors before. –  Erik Wennstrom Mar 22 '12 at 15:43
    
I've only ever encountered CS monads in passing before. Is the exception monad the same as the "maybe" monad? If not, could you point me at a good place to read up on it? –  Erik Wennstrom Mar 24 '12 at 16:58
1  
Yes, it's the same thing. If you want a nice collection of examples, see Philip Wadler's notes "Monads for Functional Programming" <homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/…;. These notes will probably seem slow-paced to you, but there were (and still are) a lot of programming language researchers who don't know much category theory. –  Neel Krishnaswami Mar 24 '12 at 18:44
1  
I should add that Wadler's comments about "single-threadedness" are exactly about requiring a functor to be non-monoidal as part of accurately model computation. –  Neel Krishnaswami Mar 24 '12 at 18:45
add comment

Consider the category of algebras over a fixed field k. Taking the dual as a k-vectorspace gives a (contravariant) monoidal functor that can be your S. On the other hand, you can also consider the ''finite dual'', usually denoted as ^\circ. As the finite dual turns every algebra into a coalgebra, this can act as your functor T. Moreover, the finite dual is a subspace of the dual vectorspace, this gives you your natural transformation T\to S. As you want to obtain cocommutative coalgebras, you can restrict to commutative algebras in the first place. The problem in this example is to get the functors as endofunctors on a suitable (sub)category. I don't know how essential this point is for you. If you start with (all) algebras, or (all) commutative algebras as above, then taking the linear dual or finite dual gets you to vectorspaces or coalgebras. The finite dual is however an endofunctor on the category of Hopfalgebras, so here you are out of problems. For the linear dual, I would suggest to replace it by the ''restricted dual'' on the category of multiplier Hopf algebras, and I think on this category you will have your example.

share|improve this answer
    
I'm not sure a contravariant functor could do the job here. Are these duals involutive? –  Erik Wennstrom Mar 24 '12 at 17:01
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.