nLab
polynomial functor

This entry is about a notion in category theory. For a different notion of the same name in (stable) homotopy theory see at Goodwillie calculus.

Polynomial functors

Idea

The concept of polynomial functor is a categorification of that of polynomial.

Polynomial endo-functors are used to encode a class of inductive types called W-types.

Definition

Let CC be a locally cartesian closed category. A polynomial functor is specified by the data

WfXgYhZ W \overset{f}{\leftarrow} X \overset{g}{\to} Y \overset{h}{\to} Z

in CC. The resulting functor is the composite

C/Wf *C/XΠ gC/YΣ hC/Z, C/W \overset{f^*}{\to} C/X \overset{\Pi_g}{\to} C/Y \overset{\Sigma_h}{\to} C/Z \,,

where Π g\Pi_g and Σ h\Sigma_h are the dependent product and dependent sum operations, right and left adjoint respectively to pullback functors g *g^* and h *h^*.

When W=ZW=Z, this is a polynomial endofunctor.

Sometimes this general notion is called a dependent polynomial functor, with “polynomial (endo)functor” reserved for the “one-variable” case, when W=Z=1W=Z=1 is the terminal object.

The data ff, gg, and hh which specify a polynomial functor is sometimes referred to as a container (or an indexed container, with container reserved for the case W=Z=1W=Z=1). Other times container is used as a synonym for “polynomial functor”.

If gg is an identity, the functor is sometimes called a linear functor or a linear polynomial functor. Note that this notion makes sense even if CC is not locally cartesian closed; all it needs are pullbacks. More generally, we can make sense of polynomial functors in any category with pullbacks if we restrict gg to be an exponentiable morphism.

Example

On sets

For CC = Set the polynomial functor induced from a function gg

*XgY* \ast \stackrel{}{\leftarrow} X \stackrel{g}{\longrightarrow} Y \stackrel{}{\longrightarrow} \ast

is given by

SP f(S)= yYS X y, S \mapsto P_f(S) = \coprod_{y \in Y} S^{X_y} \,,

where X yX_y is the fiber of gg over yYy \in Y, and where the exponential object S X yS^{X_y} is the function set of functions from the fiber to SS. The cardinality of the set on the right is

P g(S)= yYS X y {\vert P_g(S)\vert} = \sum_{y \in Y} {\vert S\vert}^{\vert X_y\vert}

and it is in this sense that the concept of polynomial functor is a kind of categorification of that of polynomial.

On the other hand the dependent polynomial functor associated to

Ap 1XidXp 2B A \stackrel{p_1}{\leftarrow} X \stackrel{id}{\longrightarrow} X \stackrel{p_2}{\longrightarrow} B

acts by

(S a) aA( bBS a×X ab) bB. (S_a)_{a \in A} \mapsto \left(\coprod_{b \in B} S_a \times X_{a b} \right)_{b \in B} \,.

Under cardinality this becomes matrix multiplication acting on vectors (with entries in the natural numbers). So in this case the dependent polynomial functor is a linear functor of several variables, an integral transform.

The 2-category of polynomial functors

Any polynomial functor, as defined above, is automatically equipped with a tensorial strength, when the slice categories of CC are regarded as tensored over CC in the canonical way. The following theorem is proven in Gambino–Kock:

Theorem

There is a bicategory whose objects are the objects of CC, whose morphisms from WW to ZZ are diagrams of the form

WfXgYhZ, W \overset{f}{\leftarrow} X \overset{g}{\to} Y \overset{h}{\to} Z,

and whose 2-morphisms are diagrams of the form

X Y id W X× YY Y Z X Y. \array{ & & X & \to & Y \\ & \swarrow & \uparrow & & \mathllap{id}\uparrow & \searrow\\ W && X' \times_{Y'} Y & \to & Y && Z\\ &\nwarrow & \downarrow & & \downarrow & \nearrow \\ && X' & \to & Y'. }

This bicategory is equivalent to the 2-category whose objects are slice categories of CC, whose morphisms are polynomial functors regarded as strong functors, and whose 2-morphisms are strength-respecting natural transformations.

Note that the above bicategory contains, as a locally full sub-bicategory, the usual bicategory of spans. Thus, as a special case, the bicategory of spans is equivalent to the 2-category of “linear” polynomial functors. Both of these are instances of Lack's coherence theorem.

  • Polynomial endofunctors are important in the definition of W-types in categories.

  • Polynomial functors are a special case of parametric right adjoints.

  • Polynomial functors can be defined using exponentiable morphisms in a category that may not be locally cartesian closed. See also distributivity pullback.

  • Kripke frames (R,S)(R,S) (with a transition relation RR of arity 22) as studied in modal logic are coalgebras for the power-set functor PP. Kripke frames for a more general modal similarity type tt are a coalgebras of a functor of the form X dtP(S arity(d))X\mapsto \product_{d\in t} P(S^{arity(d)}). Kripke models are coalgebras of functor K:XP(Prop)×P(X)K:X\mapsto P(Prop)\times P(X) where PropProp is the set of propositional variables of the logic in consideration. In particular all the functors appearing here are polynomial functors. So, at least in some aspects, the study of modal logics reduces to the study of (certain) polynomial functors

Examples

References

The relation of plain polynomial functors to trees is discussed in

Dependent (multivariate) polynomial functors are considered in

Generalization to homotopy theory is discussed in

See also

  • Yde Venema, Algebras and Coalgebras, §6 (p.332-426) in Blackburn, van Benthem, Wolter, Handbook of modal logic, Elsevier, 2007.

Revised on March 29, 2014 03:30:47 by Urs Schreiber (185.37.147.12)