Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

November 3, 2009

The Arrow of Time in Cat

Posted by David Corfield

Back here we were talking about the symmetry-breaking that takes place in mathematics by the choice of working in SetSet, which John attributed to nothing less than the ‘arrow of time’.

Why do many-to-one but not one-to-many relations get singled out for single treatment and dubbed ‘functions’? Because functions are supposed to be ‘deterministic’: the cause must determine the effect. We don’t care if the effect fails to determine the cause.

Now what is there to be said about the 2-category Cat and its three duals: Cat opCat^{op}, Cat coCat^{co} and Cat coopCat^{co op}?

We can tell a story where coalgebra (in the general sense) was slow to take off because many algebraic structures defined on our favourite SetSet are boring when the arrows are reversed. For example, each set supports precisely one comonoid structure. So we have to leave SetSet behind along with any other cartesian monoidal category if we want interesting comonoids, and look at categories such as Vect.

[Question for experts: Is this right? A comonoid in CC is a monoid in C opC^{op} is a monad in BC opB C^{op} is a monad in (BC) co(B C)^{co} is a comonad in BCB C.]

But slowly people cottoned onto the idea that there’s plenty to say about coalgebras in SetSet if we take endofunctors with less of an ‘algebraic’ flavour. For example,

  • XF(X)=D(X)X \to F(X) = D(X), the set of probability distributions on XX: Markov chain on XX.
  • XF(X)=P(X)X \to F(X) = P(X), the powerset on XX: Binary relation on XX.
  • XF(X)=X A×BX \to F(X) = X^A \times B: Deterministic automaton.
  • XF(X)=P(X A×B)X \to F(X) = P(X^A \times B): Nondeterministic automaton.
  • XF(X)=A×X×XX \to F(X) = A \times X \times X, for a set of labels AA: labelled binary trees.

Now then, will we see the same story played out a level higher with CatCat? Where there are nice juicy examples of 2-algebras (and its variants) from 2-functors which are 2-monads, is it that the dual scene, or 3 dual scenes, are much more barren? Perhaps first something 2-coalgebra-like will emerge in a less cartesian setting. And then yet later people will come to realise that there were plenty of interesting 2-functors on CatCat and so 2-coalgebras there all along.

Posted at November 3, 2009 10:09 AM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2101

27 Comments & 1 Trackback

Re: The Arrow of Time in Cat

JS: We don’t care if the effect fails to determine the cause.

Here’s a couple of other things to think about:

One

Discussions of the 2-place relation “xdeterminesyx \mathop{determines} y” are frequently confounded by several different senses of the word “determine”.

There are at least these two senses:

  1. Formal, informational, or mathematical determination:
    • “two points determine a line”
  2. Material, causal, or physical determination:
    • “push determines shove”

What exactly do we mean by “the” cause and “the” effect, anyway?

Do we mean a totality of events that we call “the cause” of a given effect?

Do we mean a totality of events that we call “the effect” of a given cause?

Two

In the propositions as types analogy, we have a suggestive relation between the function arrow “\to” and the implication arrow “\Rightarrow”.

But if we say that function arrows are arrows of time, do we really want to say that implication arrows are arrows of time, and in the same sense, too?

Posted by: Jon Awbrey on November 3, 2009 1:42 PM | Permalink | Reply to this

Re: The Arrow of Time in Cat

But if we say that function arrows are arrows of time, do we really want to say that implication arrows are arrows of time, and in the same sense, too?

In an analogous sense, yes. If you use PQP \Rightarrow Q, first you have PP, and then you get QQ. Or to prove PQP \Rightarrow Q, first you assume PP, and then you derive QQ. However, if we adopt proof irrelevance (the principle that all proofs of a given proposition are equivalent), then there is nothing resembling cause and effect in this case; there is nothing to be ‘determined’, since QQ has only one proof (if it has any).

Posted by: Toby Bartels on November 3, 2009 5:49 PM | Permalink | Reply to this

Re: The Arrow of Time in Cat

It’s fun to examine what happens in the “constructive classical” world, where negation is interpreted as the type of first-class continuations.

So let’s see how to prove A or not-A. To begin with, let’s give the introduction and elimination rules for the continuation/negation type:

Γ,u:¬Ae:AΓletccu:¬A.e:A\frac{\Gamma, u:\not A \vdash e : A} {\Gamma \vdash letcc u:\not A.\; e : A}

Here, we introduce negation by saying that we can prove AA, if we assume ¬A\not A and show a contradiction by exhibiting AA.

The elimination rule is just the explosion principle:

Γe:A Γe:¬AΓthrow(e,e):B \frac{\array{\Gamma \vdash e : A \;\;\; & \Gamma \vdash e' : \not A }} {\Gamma \vdash throw(e, e') : B}

Now, these rules are enough to let us give a program whose type is A+¬AA + \not A:

letccu:¬(A+¬A). inl(letccv:¬A.throw(inr(v),u)) \array{ \arrayopts{\colalign{left}} letcc u:\not(A + \not A). \\ inl(letcc v:\not A. throw(inr(v), u)) }

The operational behavior of this program is very funny – it gives you a left injection (ie, an AA), with the caveat that if you ever try to use that AA, it will jump back in time, and switch to a right injection. It’s like the program is saying “Did I say I meant AA? I’ll change my mind and say I really meant ¬A\not A all along, which is safe because my since my current continuation now expects an AA (and is hence itself a ¬A\not A), which I can give to the old continuation.”

This term fools the user into doing all the work with a little backtracking!

Posted by: Neel Krishnaswami on November 3, 2009 6:23 PM | Permalink | Reply to this

Re: The Arrow of Time in Cat

Wow, that is cool. I assume that letccu:¬A.e:Aletcc u: \not A.\, e : A is meant to be parsed as (letccu:¬A.e):A(letcc u: \not A .\, e) : A?

Posted by: Mike Shulman on November 3, 2009 6:40 PM | Permalink | PGP Sig | Reply to this

Re: The Arrow of Time in Cat

I like the version of that story Phil Wadler tells in Call-by-value is Dual to Call-by-Name.

Once upon a time, the devil approached a man and made an offer: “Either (a) I will give you one billion dollars, or (b) I will grant you any wish if you pay me one billion dollars. Of course, I get to choose whether I offer (a) or (b).”
The man was wary. Did he need to sign over his soul? No, said the devil, all the man need do is accept the offer.
The man pondered. If he was offered (b) it was unlikely that he would ever be able to buy the wish, but what was the harm in having the opportunity available? “I accept,” said the man at last. “Do I get (a) or (b)?”
The devil paused. “I choose (b).”
The man was disappointed but not surprised. That was that, he thought. But the offer gnawed at him. Imagine what he could do with his wish! Many years passed, and the man began to accumulate money. To get the money he sometimes did bad things, and dimly he realized that this must be what the devil had in mind. Eventually he had his billion dollars, and the devil appeared again.
“Here is a billion dollars,” said the man, handing over a valise containing the money. “Grant me my wish!”
The devil took possession of the valise. Then he said, “Oh, did I say (b) before? I’m so sorry. I meant (a). It is my great pleasure to give you one billion dollars.”
And the devil handed back to the man the same valise that the man had just handed to him.

Posted by: Dan P on November 3, 2009 6:43 PM | Permalink | Reply to this

Re: The Arrow of Time in Cat

Perhaps the two halves of the post are not so much in tune. If we think of which of algebra and coalgebra more closely resembles the arrow of time, it’s the latter.

Maps XFXX \to F X, for some endofunctor FF, are like one step time evolution on a state space, as observed here, and discussed in the paper mention in the comment below that one. But then that’s due to the resemblance between functor applied to object and function applied to element.

Posted by: David Corfield on November 3, 2009 4:13 PM | Permalink | Reply to this

Re: The Arrow of Time in Cat

A comonoid in CC is a monoid in C opC^{op} is a monad in BC opB C^{op} is a monad in (BC) co(B C)^{co} is a comonad in BCB C.

That looks right to me.

Posted by: Toby Bartels on November 3, 2009 5:46 PM | Permalink | Reply to this

Re: The Arrow of Time in Cat

Presumably ‘BB’ is the operation that turns a monoidal category into a one-object bicategory?

Posted by: Tom Leinster on November 3, 2009 10:33 PM | Permalink | Reply to this

Re: The Arrow of Time in Cat

Yes. There was a discussion at nLab as to how to denote it, whose outcome I can’t recall.

Posted by: David Corfield on November 3, 2009 10:45 PM | Permalink | Reply to this

Re: The Arrow of Time in Cat

Posted by: Toby Bartels on November 3, 2009 11:00 PM | Permalink | Reply to this

Re: The Arrow of Time in Cat

OK, thanks. I can see the logic, but I think it’s confusing. To me, BCB C denotes the classifying space of a category CC. Anyway, I know what you mean now.

Posted by: Tom Leinster on November 3, 2009 11:05 PM | Permalink | Reply to this

Re: The Arrow of Time in Cat

There is probably no single choice of notation that will be consistent with every usage out there.

But I think it helps a lot to use the letter BB just to denote delooping (which is the actual nontrivial operation) and not that operation composed with some operation that changes the context by applying one Quillen equivalence or other.

I prefer ||\vert \cdot \vert for denoting geometric realization.

Posted by: Urs Schreiber on November 5, 2009 8:16 AM | Permalink | Reply to this

Re: The Arrow of Time in Cat

If RelRel is the “time-symmetric” version of SetSet, then presumably Prof is the “time-symmetric” version of CatCat?

Of course, the obvious kind of coalgebra in CatCat is basically that mentioned here:

  • XP(X)X\to P(X), the presheaf category: endo-profunctor of XX

We can get some more by composing this PP with some other endofunctors. For instance, if TT is the “free symmetric strict monoidal category” monad, then we have

  • XP(T(X))X \to P(T(X)): generalized structure type

If it’s worth anything, cofibrant replacement is a comonad, and a 2-comonad in appropriate contexts. For instance, there’s a 2-comonad QQ on the 2-category MonCat strMonCat_{str} of monoidal categories and strict monoidal functors whose co-Kleisli 2-category is the 2-category MonCatMonCat of monoidal categories and weak monoidal functors. A QQ-coalgebra (qua pointed endofunctor) is a “flexible” or “cofibrant” monoidal category, i.e. an AA for which every monoidal functor ABA\to B is equivalent to a strict one.

Of course that’s not “honestly 2-categorical” since morally, MonCat strMonCat_{str} is only of technical interest (for instance, as a way to produce and study MonCatMonCat). But the lax and colax versions of this are still interesting even in the fully weak setting. That is, there’s a 2-comonad Q lQ_l on MonCatMonCat whose co-Kleisli 2-category is the 2-category MonCat lMonCat_l of monoidal categories and lax monoidal functors. I haven’t thought much about the coalgebras for Q lQ_l in this case, but Steve Lack and I used the coalgebras for an analogous 2-comonad (on a 2-category of weights) to characterize the limits that lift to 2-categories of algebras and lax morphisms for a 2-monad.

Just thinking out loud (figuratively speaking). (-:

Posted by: Mike Shulman on November 3, 2009 6:32 PM | Permalink | PGP Sig | Reply to this

Re: The Arrow of Time in Cat

Thanks for these examples, Mike! I wonder if there are examples closer to the computer scientists’ ones for automata. A deterministic automaton is a coalgebra for the functor

XX A×B. X \mapsto X^A \times B.

So a coalgebra f:XX A×Bf: X \to X^A \times B may be thought of as a set of states XX, and evolution function ff, which takes a state, xx, to a pair whose first component is a state of readiness, waiting for an input from AA to determine the new state in XX, and whose second component is an output in BB.

Do we feel the need for a similar situation where the state space is a category or groupoid, as are the input and output spaces, AA and BB?

Perhaps enriched categories such as metric spaces or posets would be natural starting points.

Posted by: David Corfield on November 4, 2009 9:24 AM | Permalink | Reply to this

Re: The Arrow of Time in Cat

Do we feel the need for a similar situation where the state space is a category or groupoid, as are the input and output spaces?

Hard for me to say. I’ve never personally felt that need, but then I’ve never felt the need for an ordinary set-based deterministic automaton either. (-:

I know that computer scientists use posets (most usually, directed-complete partial orders) to model partially completed computations. And I know that type theory has groupoid and higher groupoid models, and type theory is often connected with programming language semantics. But that’s about all I can guess in the way of possible connections.

Posted by: Mike Shulman on November 4, 2009 3:51 PM | Permalink | PGP Sig | Reply to this

Re: The Arrow of Time in Cat

In a paper by David H. Wolpert he comments on many-to-one mappings in computation:


we want to be able to initialize the computer to any starting configuration
we desire, regardless of its state at times not during the computation. […] Such initialization constitutes a many-to-one mapping of the state
of the computer, and a many-to-one mapping going backward in time violates the second law. [of thermodynamics]

This might be relevant.

Posted by: Robert on November 4, 2009 3:05 PM | Permalink | Reply to this

Re: The Arrow of Time in Cat

There is an obvious notion of time-symmetric category, or ‘undirected’ category, different from the dagger category concept. An undirected category is defined to have a collection of objects together with a collection of morphisms over every unordered pair of objects. Composition and identities can be taken to be defined in the same way as for ordinary categories.

Has anyone ever worked this out in detail? What about functors between undirected categories and adjointness?

The first problem arises with Rel: we get an undirected category only once we restrict to symmetric endorelations over every object by throwing out non-symmetric ones; the reason being that composition with a non-symmetric endorelation is not well-defined.

Posted by: Tobias Fritz on November 5, 2009 10:18 AM | Permalink | Reply to this

Re: The Arrow of Time in Cat

I confess that I’ve never heard of anyone doing anything with this notion.

To get symmetric relations to work, I think you’d have to take not ordinary composition but the symmetric closure of ordinary composition, since symmetric relations are not closed under composition. A similar comment would apply to spans.

Posted by: Todd Trimble on November 5, 2009 11:55 AM | Permalink | Reply to this

Re: The Arrow of Time in Cat

And off hand it’s not clear that symmetric closure of composition is associative.

Posted by: Todd Trimble on November 5, 2009 11:58 AM | Permalink | Reply to this

Re: The Arrow of Time in Cat

True, I missed that.

Still, the dagger category framework seems a bit overkill to me for Rel, since one relation appears as two morphims.

So then what about passing to a multicategory framework in the following sense: we consider as morphisms all relations of all arities at the same time. Which morphism then lies over which set of objects is encoded in terms of a relation between the collection of morphisms and the collection of objects. Think of an nn-ary relation as a gadget having nn external legs but no directedness. Two such gadgets can be composed by sticking compatible legs together. Not sure this makes sense… sorry for throwing out half-baked ideas.

Posted by: Tobias Fritz on November 5, 2009 1:18 PM | Permalink | Reply to this

Re: The Arrow of Time in Cat

This idea makes a lot of sense, and I believe a similar construction applies to any compact closed symmetric monoidal category (as well as to compact closed symmetric monoidal bicategories). I’m pretty sure this has been discussed elsewhere on this blog (maybe under the canopolis thread, for instance?), but it would help to review this.

For various reasons I’m a little reluctant to say this, but a similar idea goes back to Peirce’s existential graphs (his system Beta for the calculus of relations).

Posted by: Todd Trimble on November 5, 2009 1:27 PM | Permalink | Reply to this

Re: The Arrow of Time in Cat

One possibly relevant term is “modular operad.” See also the ramblings at hyperstructure. I agree that this happens a lot, but precise definitions are tricky to give.

In general I think you don’t want to throw out “directedness” completely, in the sense that you want the “legs” or “bonds” of a gadget to at least be distinguished from each other (so that you can deal with non-symmetric endo-relations). One way to do that is to order them, but you could also say work with FinSetFinSet instead.

Posted by: Mike Shulman on November 5, 2009 2:27 PM | Permalink | PGP Sig | Reply to this

Re: The Arrow of Time in Cat

Interesting stuff! So does the set of tensors on a Riemannian manifold form a modular operad? We can take tensor products of tensors as well as contractions with the metric tensor.

Posted by: Tobias Fritz on November 5, 2009 8:38 PM | Permalink | Reply to this

Re: The Arrow of Time in Cat

So does the set of tensors on a Riemannian manifold form a modular operad?

That is at least one of the central motivations for the discussion at hyperstructure: around here we liked to think of the toy model of this, where one considers finite dimensional tensors over \mathbb{Q}, because these can directly be identified with multispans (see groupoidification for how this identification works).

Posted by: Urs Schreiber on November 5, 2009 8:56 PM | Permalink | Reply to this

Re: The Arrow of Time in Cat

Canopolises cropped up here amongst other places.

Posted by: David Corfield on November 5, 2009 2:42 PM | Permalink | Reply to this

Re: The Arrow of Time in Cat

The thing that comes to my mind when I think of an ‘undirected’ category is just a groupoid.

My brain is hard-wired to think of a category as a “process” where it takes one tick of some clock to traverse a morphism from one object to another. A groupoid tries to snuff out the time evolution because you can go back to where you started from. Even then, I think of “back where you started from” as the same point in “space”, but a different point in time. Groupoids are special because “space” is constant so what you see at each tick of the clock is the same.

More simply, I think of “undirected” and “bidirected” as synonymous. A bidirected category is a groupoid.

Posted by: Eric Forgy on November 5, 2009 3:21 PM | Permalink | Reply to this

Re: The Arrow of Time in Cat

More simply, I think of “undirected” and “bidirected” as synonymous.

I wouldn’t agree here. To me, “bidirected” suggests invariance under time reversal, as in ordinary Lorentzian physics, where the two directions of time are indistinguishable. On the other hand, “undirected” suggests the absence of any notion of time, as in Wick-rotated Euclidean physics.

Posted by: Tobias Fritz on November 5, 2009 8:17 PM | Permalink | Reply to this
Read the post Combinatorial-Game Categories
Weblog: The n-Category Café
Excerpt: Joyal's category of Conway games is the initial "combinatorial-game category." What is the terminal one?
Tracked: November 16, 2009 9:18 PM

Post a New Comment