Reference Polynomial functors and polynomial monads [kock-poly-classical]

Abstract

  • January , 2013
  • Nicola Gambino, Joachim Kock

We study polynomial functors over locally cartesian closed categories. After setting up the basic theory, we show how polynomial functors assemble into a double category, in fact a framed bicategory. We show that the free monad on a polynomial endofunctor is polynomial. The relationship with operads and other related notions is explored. 

 @article
{kock-poly-classical, title={Polynomial functors and polynomial monads}, volume={154}, ISSN={0305-0041, 1469-8064}, DOI={10.1017/S0305004112000394}, abstractNote={We study polynomial functors over locally cartesian closed categories. After setting up the basic theory, we show how polynomial functors assemble into a double category, in fact a framed bicategory. We show that the free monad on a polynomial endofunctor is polynomial. The relationship with operads and other related notions is explored.}, url={https://arxiv.org/abs/0906.4931}, number={1}, journal={Mathematical Proceedings of the Cambridge Philosophical Society}, author={Gambino, Nicola and Kock, Joachim}, year={2013}, month={Jan}, pages={153–192} }

Backlinks

Review of Categorical Systems Theory [efr-0023]

We will give a review of the framework called categorical systems theory, due to Myers (Reference [myers-cst]).

Definition Theory of Dynamical Systems [efr-000A]

A theory of dynamical systems is an indexed category \mathcal {A}: \mathcal {C}^\mathrm {op} \to \mathsf {Cat} equipped with a section of its Grothendieck construction T: \mathcal {C} \to \int \mathcal {A}.

It is called monoidal if \mathcal {C} is a monoidal category, and \mathcal {A} is a lax monoidal functor. It is further called symmetric monoidal if \mathcal {C} is a symmetric monoidal category and \mathcal {A} is a symmetric lax monoidal functor. Note that this is equivalent to requiring \int \mathcal {A} \to \mathcal {C} to be a (symmetric) monoidal fibration in the sense of Reference [shulman-monfibs] (see also Reference [moeller-vasilakopoulou]).

Definition Lenses and charts [efr-0024]

Let \mathcal {A}: \mathcal {C}^\mathrm {op} \to \mathsf {Cat} be an indexed category. A chart is simply a morphism in the Grothendieck construction \int \mathcal {A}. A lens is a morphism in the fiberwise opposite \int \mathcal {A}(-)^\mathrm {op}.

Definition Arenas [efr-0025]

Given an indexed category \mathcal {A}: \mathcal {C}^\mathrm {op} \to \mathsf {Cat}, the double category \mathsf {\mathbb Arena} of arenas has

  1. Objects the objects of \int \mathcal {A}---note that these are the same as the objects of \int \mathcal {A}(-)^\mathrm {op}
  2. Vertical morphisms the lenses
  3. Horizontal morphisms the charts
  4. The double category is thin. Given a square of this form
    we can first project it to a square in \mathcal {C}. If this commutes, we can pull the lenses and charts back to a square in \mathcal {A}(A_1). The above square of lenses and charts will be said to commute if both of these squares commute.

We will write arenas either as {\bar {A} \in \mathcal {A}(A) \choose A \in \mathcal {C}}, or, for brevity when there is no need to discuss the two levels separately, simply with a symbol A. We will also write both {\bar {TS} \choose S} and TS as the situation calls for---there should be no confusion resulting from this.

Definition Dynamical system with interface A [efr-0028]

Let A be an arena. A dynamical system with interface A is an object S \in \mathcal {C} and a lens TS \leftrightarrows A. A morphism of systems is a map S \to S' so that this square commutes in \mathsf {\mathbb Arena}:

The category of systems with interface A is denoted \mathsf {Sys}(A)

Proposition [efr-0029]

Given a lens A \leftrightarrows A', postcomposition gives a functor \mathsf {Sys}(A) \to \mathsf {Sys}(A'). Given a chart A \rightrightarrows A', there is a profunctor \mathsf {Sys}(A) \nrightarrow \mathsf {Sys}(A'), where the set over TS \leftrightarrows A and TS' \leftrightarrows A' is the set of maps S \to S' so that this square commutes:

This defines a double functor \mathsf {Sys}: \mathsf {\mathbb Arena} \to \mathsf {\mathbb Cat}.

The fibration \int \mathcal {A} \to \mathcal {C} encodes what sort of information can be "indexed over a space", while the section T: \mathcal {C} \to \int \mathcal {A} tells us what sort of information (such as a next step, or a gradient vector) must be produced to give a dynamical system. In this respect, the theory is very similar to the coalgebraic approach to dynamical systems, or systems that "do something", and indeed we have the following:

Example [efr-0026]

Let F: \mathsf {Set} \to \mathsf {Set} be a functor. Then there is a dynamical systems theory where \mathcal {C} = \mathsf {Set}, \mathcal {A} is constant at \mathsf {Set}, and T(X) = (X,F(X)). It is easy to see that the category of closed dynamical systems in this theory is equivalently the category of F-coalgebras.

Of course, coalgebras can already encode systems with input and output---the point of the CST framework is to separate out the input and output of systems so that they can be acted on in a compositional manner.

Example The theory of discrete dynamical systems [efr-002F]

There is a theory of dynamical systems with category of spaces \mathcal {C} = \mathsf {Set}, category of bundles \mathcal {A}(X) = \mathsf {Set}_{/X} (with pullbacks for reindexing), and tangent bundle TX = X \times X \xrightarrow {\pi _0} X. We call this the theory of discrete dynamical systems. (In the sense that they are both discrete-time and discrete-space).

In another direction, we have the following comparison result:

Example [efr-0027]

In the theory of discrete dynamical systems:

  1. The category of lenses \int \mathcal {A}(-)^\mathrm {op} is equivalently the category of polynomial functors and natural transformations between them.
  2. Using this equivalence, the category of dynamical systems with interface p is exactly the category of p-coalgebras and homomorphisms

The first part here (which works, suitably formulated, for any locally Cartesian closed category), is a classical part of the theory of polynomial functors, see eg Reference [kock-poly-classical]. The second part is due to Spivak, see Reference [spivak-poly-abundant]. There is an extensive body of work on the description of interacting (discrete, deterministic) dynamical systems in terms of polynomial functors, see e.g. also Reference [shapiro-spivak-dynamic-operads].

Example The theory of stochastic discrete dynamical systems [efr-GXJ0]

There is a systems theory where \mathcal {C} = \mathsf {Set}, \mathcal {A}(X) = Kl(\Delta )^X (with the evident reindexing maps) and T(X) = X \times X.

In this theory, a closed dynamical system is a set equipped with a map X \to \Delta (X). An open dynamical system has stochastic update function, but output which depends deterministically on the current system state.

In fact this example works for any monad on the category of sets.

Example The theory of smooth dynamical systems [efr-KZEM]

There is a dynamical systems theory where \mathcal {C} = \mathsf {SmMfd} is the category of smooth manifolds, \mathcal {A}_X is the category of fiber bundles over X, with f^*: \mathcal {A}_Y \to \mathcal {A}_X given by pullback along f: X \to Y (note that pullbacks of bundles always exist), and with TX being the tangent bundle of X in the ordinary sense. In this case, closed dynamical systems are manifolds equipped with (smooth) vector fields, which is what is classically thought of as a smooth dynamical system.

Example Clock system [efr-9WQU]

Consider the theory of discrete-time, discrete dynamical systems from Example [efr-002F]. Let \xi : TS \leftrightarrows {I \choose O} be a system. Consider the system c: T\mathbb {N} \leftrightarrows {* \choose \mathbb {N}} given by n \mapsto n in the forwards direction, and (n,*) \mapsto n+1 in the backwards direction. (To be clear, the object denoted {* \choose \mathbb {N}} is the map \mathbb {N} \to \mathbb {N}---it is a singleton in each fiber). Then a morphism of systems c \to \xi consists of the following data:

  1. A function x: \mathbb {N} \to S.
  2. Another function o: \mathbb {N} \to O.
  3. A third function i: \mathbb {N} \to I so that i(n) \in I_{o(n)}.
  4. So that o(n) = \xi (x(n)) and \xi ^\#(x(n),i(n)) = x(n+1)

That is, it is a choice of a sequence x_n of points in the state-space, and a sequence of inputs i_n compatible with the outputs, so that this sequence obeys the dynamics. In other words, it is a trajectory of the system.

Because of this, one views a generic chart map as a generalized trajectory, of a type given by the domain system. As another example, taking the state space to be \{1,2, \dots , n\} with an update map that carries n to 1, one finds a system which classifies n-periodic trajectories. Similarly, in the smooth case, the system (\mathbb {R}, d/dt: \mathbb {R} \to T\mathbb {R}) classifies solutions of a smooth differential equation (those which extend to infinity). Recent work by Lynch, Myers, Staton, and the author (Reference [lynch-myers-rischel-staton-stoch-clocks]) constructs clock systems for theories of stochastic, discrete-time doctrines, although we will not delve into this here.

Because this thesis is about Markov fibrations, we have chosen to present these ideas in terms of fibrations equipped with sections. Myers' book Reference [myers-cst] actually prefers the presentation in terms of indexed categories. Similarly, we construct a double category of systems which is fibred (in a certain sense) over the double category of arenas. Myers instead displays this as a doubly indexed category \mathsf {\mathbb Arena} \to \mathsf {\mathbb Cat}, which carries lenses to functors and charts to profunctors.

In a recent paper Reference [double-operadic-systems], Myers and Libkind further develop the category theory of what they term double operadic categorical systems theory, which again concerns notions of "composable system" which are described in terms of such doubly indexed category (although for technical reasons, they use the language of right modules in that paper and a somewhat different presentation, the concept is the same.)