## 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

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

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

In $Set$ 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 $\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

### 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 ‘$A$’ 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 $A$. 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 $X \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 $i$?

$n$Lab 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 $Set$, $Cat$, $Ab$, $Graph$, $Poset$ are locally finitely presentable, but that $Top$ and $FinSet$ 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 $Cat$ 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 $n$Lab 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 $\mathbf{A}$ and $\mathbf{B}$ be categories. A module $M$ from $\mathbf{A}$ to $\mathbf{B}$, written $M: \mathbf{A} \Rightarrow \mathbf{B},$ is a functor $M: \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 $(\mathbf{B}, \mathbf{A})$-bimodule, or a profunctor or distributor from $\mathbf{A}$ to $\mathbf{B}$, or indeed from $\mathbf{B}$ to $\mathbf{A}$). For $a \in \mathbf{A}$ and $b \in \mathbf{B}$, we write $m: a \Rightarrow b$ to mean $m \in M(a, b)$. Then the ‘scalar multiplication’ (functorial action) of the module looks like this: $a' \stackrel{f}{\to} a \stackrel{m}{\Rightarrow} b    gives    a' \stackrel{m f}{\Rightarrow} b$ (where $f: a' \to a$ is an arrow in $\mathbf{A}$), and similarly $a \stackrel{m}{\Rightarrow} b \stackrel{g}{\to} b'    gives    a \stackrel{g m}{\Rightarrow} b'.$ For $M$ to be a functor means that every string of arrows $a \to \cdot \to   \cdots   \to \cdot \Rightarrow \cdot \to   \cdots   \to \cdot \to b$ has a well-defined composite $a \Rightarrow b$.

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

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

The key point of the talk, as I see it, is this. Suppose that we have a coalgebra $X$ for $M \otimes -$. Then for each element $x \in X(a)$ of the coalgebra, we obtain an infinite ‘complex’ $\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 $x$ of an $(M \otimes -)$-coalgebra gives rise to a complex of elements of the module $M$. You can think of this complex as the ‘observable behaviour’ of $x$. 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 \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:A \to Set$ and apply a module $M: A^{op} \times A \to Set$ so as to generate a new functor $M \otimes X: A \to Set$.

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

So what about my $\Phi(X) = 1 + X + X^2$ as an endofunctor of $Set$. Do you mean I need to take $A$ to be $1$? But then isn’t a module just a set, say $S$? But then $M \otimes X$ is just $S \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 $A$ to be 1?

No. If you take $A$ to be $1$ then $Flat(A, \mathbf{Set}) = 1$. In order to get $Flat(A , \mathbf{Set}) = \mathbf{Set}$, you need to take $A$ to be the free finite-limit completion of $1$, which is $\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'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