15
$\begingroup$

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.

$\endgroup$
9
  • 3
    $\begingroup$ 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$? $\endgroup$ Commented Mar 20, 2012 at 14:02
  • 5
    $\begingroup$ 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. $\endgroup$ Commented Mar 20, 2012 at 14:57
  • 4
    $\begingroup$ 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$? $\endgroup$ Commented Mar 20, 2012 at 20:58
  • 1
    $\begingroup$ 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). $\endgroup$ Commented Mar 21, 2012 at 13:54
  • 1
    $\begingroup$ @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 $\endgroup$ Commented Mar 23, 2012 at 15:38

3 Answers 3

9
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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?)

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ Commented Mar 22, 2012 at 15:35
  • $\begingroup$ (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. $\endgroup$ Commented Mar 22, 2012 at 15:43
  • $\begingroup$ 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? $\endgroup$ Commented Mar 24, 2012 at 16:58
  • 1
    $\begingroup$ 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/baastad.pdf>. 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. $\endgroup$ Commented Mar 24, 2012 at 18:44
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Mar 24, 2012 at 18:45
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I'm not sure a contravariant functor could do the job here. Are these duals involutive? $\endgroup$ Commented Mar 24, 2012 at 17:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .