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.

July 30, 2011

Coinductive Definitions

Posted by Mike Shulman

I’ve come to believe, over the past couple of years, that anyone trying to study ω\omega-categories (a.k.a. (,)(\infty,\infty)-categories) without knowing about coinductive definitions is going to be struggling against nature due to not having the proper tools. But although coinductive definitions are a basic notion in mathematics, for some reason they don’t seem to be taught, even to graduate students. Write something like

A 1-morphism f:xyf\colon x\to y in an (n+1)(n+1)-category is an equivalence if there exists a 1-morphism g:yxg\colon y\to x and equivalences 1 xgf1_x \to g f and fg1 yf g\to 1_y in the relevant hom-nn-categories; and every 1-morphism in a 0-category is an equivalence

and any mathematician (who has some inkling of what nn-categories are) will be happy. If you ask why this definition isn’t circular, since it defines the notion of “equivalence” in terms of “equivalence”, the mathematician will say “it’s an inductive definition” and expect you to stop complaining. But if you write something like

A 1-morphism f:xyf\colon x\to y in an ω\omega-category is an equivalence if there exists a 1-morphism g:yxg\colon y\to x and equivalences 1 xgf1_x \to g f and fg1 yf g\to 1_y in the relevant hom-ω\omega-categories

the same mathematician will object loudly, saying that this definition is circular. (In fact, not very long ago, that mathematician was me.) But actually, this latter is a perfectly valid coinductive definition.

One way of saying what an inductive definition means is that it defines the smallest class of things that is closed under some “constructor” operations. That is, the above definition of equivalences in nn-categories for finite nn says, when unraveled a bit, that the class of “equivalences in nn-categories” is the smallest class \mathcal{E} such that

  1. Every morphism in a 0-category is in \mathcal{E}, and
  2. If f:xyf\colon x\to y has the property that there exists g:yxg\colon y\to x, and also morphisms 1 xgf1_x \to g f and fg1 yf g\to 1_y that are in \mathcal{E}, then ff is in \mathcal{E}.

As usual, “smallest” means “minimum”, i.e. it is contained in every other such class \mathcal{E}. How do we know that there is a smallest such class? Because of the nature of the closure conditions (each of them takes some input consisting of things in \mathcal{E} and produces something else in \mathcal{E}), the collection of classes \mathcal{E} satisfying them is closed under intersection; thus we can take the intersection of all such \mathcal{E} to obtain the smallest one.

Inductive definitions are best-adapted to proving stuff about things which satisfy the definition. Namely, if we want to prove that all equivalences in nn-categories have property PP, all we need to do is prove that morphisms in 0-categories have property PP, and (2) given f:xyf\colon x\to y and g:yxg\colon y\to x, and 1 xgf1_x \to g f and fg1 yf g\to 1_y with property PP, also ff has property PP. Then the class of things satisfying PP will be one of the classes \mathcal{E}, and hence contain the class of equivalences. This is called a proof by induction.

Dually, a coinductive definition defines the largest class of things that is closed under some “destructor” operations. Thus, the above definition of equivalences in ω\omega-categories says that the class of “equivalences in ω\omega-categories” is the largest class \mathcal{E} such that

  1. If f:xyf\colon x\to y is in \mathcal{E}, then there exists a g:yxg\colon y\to x, and also morphisms 1 xgf1_x \to g f and fg1 yf g\to 1_y that are in \mathcal{E}.

As usual, “largest” means “maximum”, i.e. containing every other such class \mathcal{E}. How do we know that there is a largest such class? Because of the nature of the closure conditions (each of them takes one input in \mathcal{E} and produces some number of other things in \mathcal{E}), the collection of classes \mathcal{E} satisfying them is closed under unions; thus we can take the union of all such \mathcal{E} to obtain the largest one.

Coinductive definitions are best-adapted to proving that things do satisfy the definition. Namely, if we want to prove that some morphism ff in an ω\omega-category is an equivalence, all we need to do is prove that ff belongs to some class \mathcal{E} of morphisms with the above property. Then \mathcal{E} will be contained in the class of equivalences, so that ff is an equivalence. This is called a proof by coinduction.

The theory of ω\omega-categories is full of concepts that are naturally defined coinductively. For instance:

  • A functor f:CDf\colon C\to D between ω\omega-categories is an equivalence if (1) for each yDy\in D, there exists an xCx\in C and an equivalence f(x)yf(x) \to y, and (2) for each x 1,x 2Cx_1,x_2\in C, the functor f:C(x 1,x 2)D(f(x 1),f(x 2))f\colon C(x_1,x_2) \to D(f(x_1),f(x_2)) is an equivalence between ω\omega-categories.

  • The schematic definition of n-fibration makes perfect sense as a definition of ω\omega-fibration, if interpreted coinductively.

In fact, ω\omega-categories themselves are naturally defined coinductively!

  • An ω\omega-category is a category enriched over ω\omega-categories.

This requires a more general kind of coinductive definition, though, since now we are defining a structure coinductively, rather than a property of elements of some existing structure.

Here’s a way of rephrasing the inductive definition of equivalences in an nn-category. Consider the poset of “classes of morphisms in nn-categories” for finite nn, and given such a class \mathcal{E}, let F()F(\mathcal{E}) be the class of all morphisms which are either (1) morphisms in 0-categories, or (2) are morphisms f:xyf\colon x\to y such that there exists g:yxg\colon y\to x, and also morphisms 1 xgf1_x \to g f and fg1 yf g\to 1_y that are in \mathcal{E}. Then FF is an endofunctor of this poset, and the inductive definition says that the equivalences are the initial algebra for this endofunctor, i.e. the smallest \mathcal{E} such that F()F(\mathcal{E})\subseteq \mathcal{E}.

Similarly, we can consider the poset of “classes of morphisms in ω\omega-categories” and define G()G(\mathcal{E}) to be the class of all morphisms f:xyf\colon x\to y such that there exists a g:yxg\colon y\to x, and also morphisms 1 xgf1_x \to g f and fg1 yf g\to 1_y that are in \mathcal{E}. Then the coinductive definition says that \mathcal{E} is the terminal coalgebra for the endofunctor GG, i.e. the largest \mathcal{E} such that G()\mathcal{E}\subseteq G(\mathcal{E}).

The generalization to structure, rather than properties, is now immediate: in general, an inductively defined gadget is an initial algebra for some endofunctor, and a coinductively defined gadget is a terminal coalgebra for some endofunctor. Of course, we need some conditions on the endofunctor to ensure that initial or terminal coalgebras exist; usually one asks them to be polynomial.

For instance, the natural numbers are the initial algebra for the endofunctor XX+1X\mapsto X+1 of SetSet. This automatically gives us the principle of definition by iteration or recursion.

Similarly, we can exhibit ω\omega-categories as the terminal coalgebra for an endofunctor of a suitable category. The above coinductive definition suggests that the endofunctor in question should take CC and output the collection of CC-enriched categories. Thus, CC must belong to a category of “things we can enrich over.” If we take our endofunctor to live on the category of cartesian monoidal categories (or, I think, even all symmetric monoidal categories), and use the usual notion of enrichment, then we obtain as terminal coalgebra the category of strict ω\omega-categories. And Eugenia and Tom showed here that if we use Todd Trimble’s notion of operadic iterated enrichment, then we obtain a Trimblean model for weak ω\omega-categories.

Posted at July 30, 2011 8:11 PM UTC

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

14 Comments & 0 Trackbacks

Re: Coinductive Definitions

Nice post! I occasionally run into computer sciencey types who fling around coinduction with gay abandon, and I admit that it makes me a bit nervous. It probably comes down to a lack of practice.

Posted by: Tom Leinster on August 1, 2011 2:15 AM | Permalink | Reply to this

Re: Coinductive Definitions

Coinduction is right at the top of my list of mathematics that computer scientists keep secret from mathematicians. I’m glad to see someone helping to leak it.

Posted by: Dan P on August 1, 2011 5:57 AM | Permalink | Reply to this

Re: Coinductive Definitions

Induction can be explained to a high-school student using simple examples, like proving simple inequalities or divisibilities for positive integers.

Can you think of any simple examples of coinduction? (At very least, they shouldn’t mention categories.)

If not, do you think there’s a reason why coinduction can’t be applied to “simple” things?

Posted by: Roman Cheplyaka on August 1, 2011 7:54 AM | Permalink | Reply to this

Re: Coinductive Definitions

Because coinduction is about the largest class closed in a certain way, it’s often about large objects, typically infinite ones. So that’s why it tens to apply to more “complex” things.

People programming in some programming languages routinely use induction to guarantee their computer programs give well-defined functions. Eg. a program to sum the elements of a finite array can be proved to terminate by showing it works for zero length arrays, and then by showing that if it works for size n arrays, it must work for size n+1 arrays.

Programmers working with infinite stream datatypes frequently use coinduction. For example, consider a cash register that receives numbers entered by a user one by one and maintains a tally of all of the entries so far. Such a machine is not designed to ever terminate, but keep on running as long as it is used. An argument about finite arrays can’t be used directly for an open system like this. You could use induction to argue about it being correct up to time T. But it’s easier just to use a coinduction argument to show that if it works for the next entry, and works for all subsequent entries, then it works for all entries.

Posted by: Dan P on August 1, 2011 4:22 PM | Permalink | Reply to this

Re: Coinductive Definitions

We had a discussion back here about using coinduction for simple arithmetic in the case of one of the simplest coalgebraic entities – the extended natural numbers. If you work through things, you realise that little is gained over induction since here the infinite extended natural number is easily treated by itself.

As Dan says, coinduction works well on (possibly) infinitely large entities – trees, streams, etc.

Posted by: David Corfield on August 5, 2011 2:02 PM | Permalink | Reply to this

Re: Coinductive Definitions

I have been playing with coq recently (Isn’t that a great line) and in the manual they give the coinductive definition of a stream - this is also example 1 of the Leinster/Cheng PDF -

A stream of Ms is an object such that consists of an M followed by a stream of Ms

Notice the similarity to a list of Ms. A list of M is the empty list or an M followed by a list of Ms.

Thus a list of Ms is any finite sequence of Ms while a stream of Ms is any infinite sequence of Ms

I am still not sure I understand this properly so I am going to suggest that if the natural numbers are the initial algebra on the succesor operation, the terminal coalgebra for it consists of the lower sets on the integers with the usual order?

Posted by: Roger Witte on August 1, 2011 9:03 AM | Permalink | Reply to this

Re: Coinductive Definitions

If you think about it, that is the same as ω{ω}\omega \cup \{\omega\} — more familiar sometimes as {}\mathbb{N}\cup\{\infty\}, which has indeed been noted elsewhere nearby as the terminal coalgebra of the successor-set endofunctor on SetSet. In this context you might call it the “length” coalgebra — given a successor-set coalgebra AA+1A\to A+1, the canonical map A{}A\to \mathbb{N}\cup\{\infty\} tells you how long a thing is.

Posted by: some guy on the street on August 1, 2011 5:28 PM | Permalink | Reply to this

Re: Coinductive Definitions

Does Coq somehow force types to be minimal? In Haskell lists defined that way can be infinite.

Posted by: Tom Ellis on August 1, 2011 6:14 PM | Permalink | Reply to this

Re: Coinductive Definitions

Here’s one way to think of it:

  1. Every element of an inductive type, or a coinductive type, is obtained by applying some constructor of that type. It can always be examined to find out what constructor was applied to build it and what arguments were passed.

  2. In the case of an inductive type, if you look at those arguments of the constructor which happen to belong to the inductive type themselves, then the analogous arguments of the constructors used to build those, and so on, then along every branch the process eventually terminates (i.e. ends up with a constructor having no recursive arguments). Not so in the case of a coinductive type.

Thus, the definition

Inductive nat : Type :=
| O : nat
| S : nat -> nat.

defines an inductive type with two constructors, one of which takes no arguments, and one of which takes one recursive argument. Thus every natural number is either zero or a successor; and if it is a successor, and you look at the number of which it is a successor, and so on, you must eventually stop, by reaching zero. So the natural numbers are O, S(O), S(S(O)), S(S(S(O))), etc.

The analogous definition

CoInductive nat : Type :=
| O : nat
| S : nat -> nat.

includes all the natural numbers, but also the ill-founded “conatural number” S(S(S(S(…)))).

Posted by: Mike Shulman on August 2, 2011 4:05 AM | Permalink | Reply to this

Re: Coinductive Definitions

In September last year, I asked for a coinductive definition of the functor omega-category [C,D] where C and D are omega-categories. The reply by Ross Street was “since mathematicians traditionally like to describe constructions in terms of elements rather than co-elements, …” and he went on with an inductive definition. I was very happy to get this reply, but still I’d love to see a coinductive definition of [C,D]. I searched for it by myself for some time but I could only arrive at (really) circular definitions. Any idea?


Posted by: David Leduc on August 1, 2011 2:17 PM | Permalink | Reply to this

Re: Coinductive Definitions

Good question! I don’t know. It feels intuitively to me as though the theorem “if V is cartesian closed and complete, then V-Cat is cartesian closed” should be coinductive-ifiable to prove that ω\omegaCat is cartesian closed, but I don’t immediately see how to do it.

Posted by: Mike Shulman on August 2, 2011 4:15 AM | Permalink | Reply to this

Re: Coinductive Definitions

I have an interesting example of (what I suspect is) a coinductive definition.

Consider the bicategory Cat anaCat_{ana} of anafunctors, and the inclusion CatCat anaCat \to Cat_{ana}. Here we negate (or at least neglect) Choice in CatCat. This locally fully faithful 2-functor (which we can assume strict), is a localisation, sending essentially surjective and fully faithful functors to equivalences in Cat anaCat_{ana}. But are these the only functors sent to equivalences? Unless I’m being thick, I haven’t seen this proved. However, I was able to come up with a nice characterisation of the class AA of functors sent to equivalences: (F:CD)A(F:C \to D) \in A \Leftrightarrow if there is a surjective-on-objects, fully faithful functor Q:DDQ:D' \to D, a functor F:DCF':D' \to C in AA and a natural isomorphism FFQFF' \Rightarrow Q.

The \Rightarrow implication is still true if we replace ‘functor in AA’ by ‘ess. surj. + fully faithful’, and it is easy to see that all functors in AA are essentially surjective, but either I’m having a bad day, heven’t thought hard enough, or it is simply not true, because I can’t see that all functors in AA are fully faithful.

Note that if we allow Choice, then we know that the equivalences in CatCat are precisely the fully faithful, ess. surj. functors. Also, if we assume the presentation axiom (i.e. the existence of enough ‘projectives’), then any functor between categories with ‘projective’ collections of objects is an equivalence if and only if it is fully faithful and essentially surjective.

Posted by: David Roberts on August 2, 2011 5:54 AM | Permalink | Reply to this

Re: Coinductive Definitions

Is something wrong with the following argument? Suppose f:CDf\colon C\to D is a functor which becomes an equivalence in Cat anaCat_{ana}, let x,yCx,y\in C and let gg be an anafunctor which is pseudo-inverse to ff. Pick ξ,ζ\xi,\zeta that are specifications for gg applied to f(x)f(x) and f(y)f(y), respectively, so that we have objects g(f(x);ξ)g(f(x);\xi) and g(f(y);ζ)g(f(y);\zeta) in CC. Since gfg\circ f is naturally isomorphic to the identity, we have isomorphisms g(f(x);ξ)xg(f(x);\xi) \cong x and g(f(y);ζ)yg(f(y);\zeta)\cong y, composition with which gives an isomorphism C(x,y)C(g(f(x);ξ),g(f(y);ζ))C(x,y) \cong C(g(f(x);\xi), g(f(y);\zeta)). Naturality of these isomorphisms implies that a map ϕ:xy\phi\colon x\to y corresponds to g(f(ϕ);ξ,ζ)g(f(\phi); \xi,\zeta). Therefore, f:C(x,y)C(f(x),f(y))f \colon C(x,y) \to C(f(x),f(y)) is injective, since it has a retraction; so ff is faithful. I think a similar argument should work for fullness.

Posted by: Mike Shulman on August 2, 2011 9:17 PM | Permalink | Reply to this

Re: Coinductive Definitions

The opposition to coinductive definitions appears to go back a long way. I mentioned the hard time some of Hilbert’s followers gave to Finsler over his maximizing definitions back here. I wonder if there’s some residual fear of those ontological arguments from theology which reason to the existence of a perfect infinite Being.

Posted by: David Corfield on August 5, 2011 2:43 PM | Permalink | Reply to this

Post a New Comment