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.

May 8, 2009

In Search of Terminal Coalgebras

Posted by David Corfield

Tom Leinster has put up the slides for his joint talk – Terminal coalgebras via modules – with Apostolos Matzaris at PSSL 88.

It’s all about establishing the existence of, and constructing, terminal coalgebras in certain situations. I realise though looking through the slides that I never fully got on top of the flatness idea, and nLab is a little reluctant to help at the moment (except for flat module).

So perhaps someone could help me understand the scope of the result, maybe via an example. Say I take the polynomial endofunctor

Φ(X)=1+X+X 2. \Phi(X) = 1 + X + X^2.

Given that terminal coalgebras can be said to have cardinality ii, in which categories will I find such a thing?

In SetSet we have that the initial algebra for Φ\Phi is the set of Motzkin trees. I guess the terminal coalgebra is the set of extended such trees, just as the initial algebra for Ψ(X)=1+X\Psi(X) = 1 + X is the natural numbers and the terminal coalgebra the extended natural numbers.

Posted at May 8, 2009 10:07 AM UTC

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

20 Comments & 0 Trackbacks

Re: In Search of Terminal Coalgebras

Of course, I should read again Tom’s introductory paper, and the longer two it introduces.

Posted by: David Corfield on May 8, 2009 11:53 AM | Permalink | Reply to this

Q: The primordial coalgebra and “tensor calculus”

There’s an unfinished project that bugs me ever since I left university a decade ago. Perhaps somebody has done it. I call it the Total Tensor Calculus (The mathematicians’ and physicists’ calculus get extremely clumsy e.g. when working with Stokes, doing Hilbert space operators, etc. Mathematicians don’t see the forest for all the Lie brackets, Physicists don’t for all the indices. wrrr dada …)

So, my question:
Is anybody aware of the use of shuffle comultiplication on the tensor algebra for higher covariant derivatives of tensor products? (Or, adjointly, the coshuffle multiplication).

The higher tensor product rule is perhaps coalgebraic urknall.

Simplest nontrivial application would be the tensoriality of curvature.


Posted by: Florifulgurator, PhD dropout on May 8, 2009 7:01 PM | Permalink | Reply to this

Re: In Search of Terminal Coalgebras

Thanks, David.

The talk (or my half, anyway) was designed to be comprehensible even if you don’t know what ‘flat’ means. More exactly:

  • If you don’t know what flat means, it’s fine, as long as you’re willing to assume that the category called ‘AA’ has finite limits. Flatness then turns into something more familiar. This gives less general but still interesting statements.
  • If you do know what flat means, you don’t have to make any assumptions on AA. You then get more general statements.

If you’re in the first group of people, there’s good news: you don’t need to know what flat means in order to follow the argument leading to the main result. That’s actually the less general result. Apostolos talked about the more general version.

(The main result is that — deep breath — every finitary endofunctor of a locally finitely presentable category has a terminal coalgebra. As the slides explain, this is an old theorem with a new proof, due not to me but to Panagis Karazeris, Apostolos Matzaris and Jiri Velebil. Its main virtue, I think, is that it constructs this terminal coalgebra.)

So, David, while of course I would do nothing to dissuade you from getting on top of the categorical notion of flatness, and while indeed I am envious of the delights that await you, it’s not necessary in order to comprehend the result stated above.

(And your guess about the terminal coalgebra for X1+X+X 2X \mapsto 1 + X + X^2 is correct. It’s the set of all finite or infinite trees with nullary, unary or binary branching.)

Posted by: Tom Leinster on May 9, 2009 2:47 AM | Permalink | Reply to this

Re: In Search of Terminal Coalgebras

As if by magic, flat functor has appeared.

Is there any locally finitely presentable (lfp) category where we might find a surprisingly nice object of size ii?

nnLab needs a little boosting here. We have that a locally presentable category is a category of models for a limit sketch. Do we slip ‘finite’ into the obvious place?

Judging from what I’ve found out – Yes.

I see SetSet, CatCat, AbAb, GraphGraph, PosetPoset are locally finitely presentable, but that TopTop and FinSetFinSet aren’t. And according to Adamek

…deterministic systems, considered as coalgebras over polynomial functors, turn out to form locally finitely presentable categories.

So there are terminal coalgebras in CatCat treated as a category, but what happens if we treat it as a 2-category? Would anyone know if a categorified theory has been worked out for (terminal) 2-coalgebras?

Posted by: David Corfield on May 11, 2009 9:51 AM | Permalink | Reply to this

Re: In Search of Terminal Coalgebras

Actually, in that entry, the existence of limits is not needed in Condition 1.
Posted by: Marc Olschok on May 11, 2009 8:14 PM | Permalink | Reply to this

Re: In Search of Terminal Coalgebras

So if I (or you) remove “limits and” that leaves a condition equivalent to the other four?

Posted by: David Corfield on May 11, 2009 9:33 PM | Permalink | Reply to this

Re: In Search of Terminal Coalgebras

Yes. Any locally presentable category is equivalent to a
full reflexive subcategory of a suitable presheaf topos
(this is also implicit in Condition 4) and this can be shown
without using the existence of limits.
Hence one gets completeness automatically.

Posted by: Marc Olschok on May 12, 2009 7:25 PM | Permalink | Reply to this

Re: In Search of Terminal Coalgebras

As if by magic, flat functor has appeared.

We need to harmonize the nnLab terminology here or at least insert warning about use of different terminology, because the new entry on flat functor reproduces the definition we had before under [[exact functor]].

Posted by: Urs Schreiber on May 11, 2009 4:33 PM | Permalink | Reply to this

Re: In Search of Terminal Coalgebras

I’ve only ever heard (left and/or right) “exact functor” used when the categories in question actually have the finite limits and/or colimits, with “flat” used for the general case. Is this another Kashiwara-Schapira neologism?

It seems to me more clear to use different words for the two cases, especially since we have “flat” as a perfectly good word for “preserving finite limits whether or not they exist.”

Posted by: Mike Shulman on May 11, 2009 9:58 PM | Permalink | Reply to this

Re: In Search of Terminal Coalgebras

Is this another Kashiwara-Schapira neologism?

Yup. :-)

Posted by: Urs Schreiber on May 11, 2009 11:43 PM | Permalink | Reply to this

Re: In Search of Terminal Coalgebras

I do not think it is that unusual; in ring/module theory and algebraic geometry some do talk “flat functors” though the categories of modules or qcoh sheaves are even abelian, hence the finite limits exist. However the emphasis in algebraic geometry is on flat morphisms of schemes; the corresponding inverse image functor for qcoh sheaves is indeed flat/exact. Hence if we replace schemes by categories of quasicoherent sheaves, and morphisms by geometric morphisms, we are naturally lead to use this terminology. I’d personally use word left exact in nongeometric examples and flat in geometric examples for that reason (note mreover that in all these cases the inverse image functor of course is not only left exact but also having right adjoint).

Posted by: Zoran Skoda on May 12, 2009 6:34 PM | Permalink | Reply to this

Re: In Search of Terminal Coalgebras

Arguably, the two concepts are:

  • finitely continuous (preserving those finite limits that exist),
  • flat (preserving all finite limits in a sense, even those that don't exist).

I generally (perhaps always) see ‘left exact’ (or ‘lex’) used when all finite limits exist, in which case these coincide, but we do still have two notions.

Posted by: Toby Bartels on May 11, 2009 10:23 PM | Permalink | Reply to this

Re: In Search of Terminal Coalgebras

I find the importance of functors preserving whatever finite limits exist between categories that don’t necessary have all finite limits to be debatable.

Posted by: Mike Shulman on May 13, 2009 3:37 AM | Permalink | Reply to this

Quick summary

Here’s a short explanation of the main idea of the talk.

First we need the right point of view on modules. Let A\mathbf{A} and B\mathbf{B} be categories. A module MM from A\mathbf{A} to B\mathbf{B}, written M:AB, M: \mathbf{A} \Rightarrow \mathbf{B}, is a functor M:A op×BSetM: \mathbf{A}^{op} \times \mathbf{B} \to \mathbf{Set}. Really we use a crossed arrow +>-+-> rather than a double arrow \Rightarrow, but I can’t figure out how to get that symbol here. (And others call this a (B,A)(\mathbf{B}, \mathbf{A})-bimodule, or a profunctor or distributor from A\mathbf{A} to B\mathbf{B}, or indeed from B\mathbf{B} to A\mathbf{A}). For aAa \in \mathbf{A} and bBb \in \mathbf{B}, we write m:ab m: a \Rightarrow b to mean mM(a,b)m \in M(a, b). Then the ‘scalar multiplication’ (functorial action) of the module looks like this: afamb  gives  amfb a' \stackrel{f}{\to} a \stackrel{m}{\Rightarrow} b    gives    a' \stackrel{m f}{\Rightarrow} b (where f:aaf: a' \to a is an arrow in A\mathbf{A}), and similarly ambgb  gives  agmb. a \stackrel{m}{\Rightarrow} b \stackrel{g}{\to} b'    gives    a \stackrel{g m}{\Rightarrow} b'. For MM to be a functor means that every string of arrows a    b a \to \cdot \to   \cdots   \to \cdot \Rightarrow \cdot \to   \cdots   \to \cdot \to b has a well-defined composite aba \Rightarrow b.

Now we can begin. Take a category A\mathbf{A} and a module M:AAM: \mathbf{A} \Rightarrow \mathbf{A}.

For every functor X:ASetX: \mathbf{A} \to \Set we obtain by tensor product a new functor MX:ASetM \otimes X: \mathbf{A} \to \Set. (Explicitly, given aAa \in \mathbf{A}, an element of the set (MX)(a)(M \otimes X)(a) is an equivalence class of pairs (m:ba,xX(b))(m: b \Rightarrow a, x \in X(b)), written mxm \otimes x.) So, the module MM induces an endofunctor MM \otimes - of Set A\mathbf{Set}^\mathbf{A}.

The key point of the talk, as I see it, is this. Suppose that we have a coalgebra XX for MM \otimes -. Then for each element xX(a)x \in X(a) of the coalgebra, we obtain an infinite ‘complex’  m 3a 2m 2a 1m 1a 0=a \cdots   \stackrel{m_3}{\Rightarrow} a_2 \stackrel{m_2}{\Rightarrow} a_1 \stackrel{m_1}{\Rightarrow} a_0 = a of elements of the module. I should have given you enough information here to figure out how we obtain such a complex, but it’s also in the slides.

This complex is non-canonical — you have to make lots of choices — but under certain flatness hypotheses, it’s canonical up to a certain sensible equivalence relation.

So, each element xx of an (M)(M \otimes -)-coalgebra gives rise to a complex of elements of the module MM. You can think of this complex as the ‘observable behaviour’ of xx. Now, in general we’re supposed to think of terminal coalgebras as consisting of ‘all possible behaviours’. And indeed, if you work in a certain setting where everything is suitably flat, the terminal (M)(M \otimes -)-coalgebra really does consist of equivalence classes of complexes as above.

I found one set of hypotheses that makes this true, and used it in my work on self-similarity. Panagis Karazeris, Apostolos Matzaris and Jiri Velebil found another, and realized that this construction could be used to reprove the old theorem on terminal coalgebras that I mentioned above. They’ve also been taking it into new territory.

Posted by: Tom Leinster on May 12, 2009 8:43 PM | Permalink | Reply to this

Re: Quick summary

I’m probably ought to work this out myself, but with only 20 minutes free today I’ll ask.

So you have a functor X:ASetX:A \to Set and apply a module M:A op×ASetM: A^{op} \times A \to Set so as to generate a new functor MX:ASetM \otimes X: A \to Set.

And any finitary functor on any lfp category can be represented this way.

So what about my Φ(X)=1+X+X 2\Phi(X) = 1 + X + X^2 as an endofunctor of SetSet. Do you mean I need to take AA to be 11? But then isn’t a module just a set, say SS? But then MXM \otimes X is just S×XS \times X.

Posted by: David Corfield on May 13, 2009 1:47 PM | Permalink | Reply to this

Re: Quick summary

Do you mean I need to take AA to be 1?

No. If you take AA to be 11 then Flat(A,Set)=1Flat(A, \mathbf{Set}) = 1. In order to get Flat(A,Set)=SetFlat(A , \mathbf{Set}) = \mathbf{Set}, you need to take AA to be the free finite-limit completion of 11, which is FinSet op\mathbf{FinSet}^{op}.

Posted by: Tom Leinster on May 17, 2009 7:43 PM | Permalink | Reply to this

Re: Quick summary

Oh, I see. Thanks. Like models for the minimal Lawvere theory.

So much at the Café seems to be about some or other form of categorified linear algebra.

Is there anything to thinking of terminal coalgebras, and more generally fixed points, of a finitary endofunctor as kinds of eigenvector?

Posted by: David Corfield on May 18, 2009 9:11 AM | Permalink | Reply to this

Re: Quick summary

Is there anything to thinking of terminal coalgebras, and more generally fixed points, of a finitary endofunctor as kinds of eigenvector?

I was just reading something about that … where was it?

I'll let you know if I find it, but in the meantime, somebody thinks yes.

Posted by: Toby Bartels on May 18, 2009 7:16 PM | Permalink | Reply to this

Re: Quick summary

Limiting myself to 2 minutes of search, the best I could come up with is Applications of Metric Coinduction.

Posted by: David Corfield on May 19, 2009 4:43 PM | Permalink | Reply to this

Re: In Search of Terminal Coalgebras

Now Panagis Karazeris, Apostolos Matzaris, and Jiri Velebil have brought out a paper – Final coalgebras in accessible categories – on this material.

Posted by: David Corfield on June 1, 2009 2:56 PM | Permalink | Reply to this

Post a New Comment