MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

For a category $\mathcal{C}$, let $\mathcal{C}-Set$ denote the category of functors $\mathcal{C}\to{\bf Set}$. Recall that given a functor $F\colon\mathcal{B}\to\mathcal{C}$, the ``composition with $F$" functor is denoted $F^*\colon\mathcal{C}-Set\to\mathcal{B}-Set.$ It has a left and a right adjoint, $F_!$ and $F_*$. I call these functors the pullback, the left pushforward, and the right pushforward.

Let $p\colon A\to B$ be a function of sets, thought of as a functor $P\colon[1]\to{\bf Set}$, where $[1]$ is the "free-arrow category," $[1]="\bullet\to\bullet$." Suppose one wants to find the image of $p$, but he or she can only use pull-backs, left pushforwards, and right pushforwards to manufacture it. In other words, suppose one wants to find a zigzag of functors $[1]=:C_0\leftarrow C_1\rightarrow C_2\leftarrow C_3\rightarrow\cdots\rightarrow C_n=[0]$ such that if we perform a pullback along all leftward functors and either a left pushforward or a right pushforward along rightward functors, then the end result will be the image set $im(p)$ of $p$ (considered as a functor $[0]\to{\bf Set}$).

This can be done. To do it, I used a sequence of the form $$[1]\leftarrow C_1\rightarrow C_2\rightarrow [0].$$ If the functors are denoted (left to right) by $F,G,$ and $H$, I found that $H_! \circ G_*\circ F^\ast (P)=im(P)$.

I'm not going to bore you with the details of $C_1, C_2$ and $F,G,H$.

Here's the question. I've seen things like $H_! \circ G_*\circ F^\ast$ before in the context of polynomial functors. Unfortunately, I don't know enough about them to know if there's a connection. Is there?

I also don't know if I can get the whole epi-mono factorization somehow. I haven't worked that long at it, but suppose I want not to end up with the set $im(p)$ but instead the maps $A\to im(f)\to B$. Can I achieve that by use of pullbacks and pushforwards as above (with $C_n=[2]$ now)? Is there any rhyme or reason to such constructions?


share|cite|improve this question
+1 for the title alone! – Loop Space Aug 13 '10 at 21:32
Some very vague scraps of memory that might be relevant: polynomial functors can be seen as an internal cousin of familially representable functors. Fam. rep. functors have a nice characterisation as “preserving wide pullbacks” (Carboni/Johnstone). Iirc, there are some nice constructions making the analogy between poly. and fam. rep. functors concrete, and iirc there may have been an internal analogue of the “wide pullbacks” condition. Unfortunately I can't remember the details, or even where/from whom I heard this. I think they said it was from work by Joyal, perhaps? – Peter LeFanu Lumsdaine Aug 14 '10 at 6:16
Since there are three factors, I wonder if someone did/should check whether there's a prop/struct/stuff factorization (aka. Postnikov-Moore!) lurking about? – some guy on the street Aug 16 '10 at 21:47
After stewing on the implicit puzzle, I have to admit I don't see how to get down to three factors. Can you tell me if I seem to understand left/right pushouts well-enough if I say I'm using the as definition of Image "a coequalizer of a kernel pair"? As a bonus, you practically get the requested epic/monic factorization for free; but I think there are at least three extra pull-backs in my recipe. – some guy on the street Sep 2 '10 at 22:31
edit: "the as" $\mapsto$ "as the" – some guy on the street Sep 2 '10 at 22:32
up vote 5 down vote accepted

First of all: yes, there's certainly a connection. See If the base category is $Set$, the composite

$$Set/W \stackrel{f^\ast}{\to} Set/X \stackrel{g_\ast}{\to} Set/Y \stackrel{h_!}{\to} Set/Z$$

first takes a $W$-indexed set $S_w$ to an $X$-indexed set $T_x = S_{f(x)}$, then takes this to the $Y$-indexed set $U_y = \prod_{x: g(x) = y} T_x$, then takes this to the $Z$-indexed set $V_z = \sum_{y: h(y) = z} U_y$. Putting this together, the composite is a family of polynomials, each a sum of monomial terms

$$P(\ldots, S_w, \ldots) = (z \mapsto \sum_{y \in h^{-1}(z)} \prod_{x \in g^{-1}(y)} S_{f(x)})$$

I'll give a quick example. Suppose we want to express the free monoid functor

$$F(S) = \sum_{n \geq 0} S^n$$

in this form. Then we take $W = 1$, $X = \mathbb{N} \times \mathbb{N}$, $Y = \mathbb{N}$, $Z = 1$. There's only one choice for $f$ and $h$, and $g$ is rigged so that the fiber over $n \in \mathbb{N}$ is an $n$-element set: $g(m, n) = m + n + 1$. One can easily check this works.

As for the other question: it would have been nice if you had "bored" us! Because I don't see how to reconstruct what you did. What I have to get the image is a zig-zag of length 4

$$Set^{[1]} \stackrel{F^\ast}{\to} Set^{C_1} \stackrel{G_\ast}{\to} Set^{C_2} \stackrel{H^\ast}{\to} Set^{C_3} \stackrel{J_!}{\to} Set^{[0]}$$

where $C_1$ is the generic cospan $a \to c \leftarrow b$, $C_2$ is the generic commutative square, $C_3$ is the generic span $a \leftarrow d \to b$, and then $G$ and $H$ are the evident inclusion functors, and $F$ takes each arrow of the generic span to the arrow of $[1]$. Then $F^\ast$ takes $p: A \to B$ to the cospan consisting of two copies of $p$; hitting this with $G_\ast$ takes this cospan to the pullback square (pulling back $p$ against itself); hitting this with $H^*$ restricts the pullback square to the span consisting of the pullback projections; finally, hitting this with $J_!$ takes this span to its colimit = pushout, which is the same as the coequalizer of the pullback projections (because they have a common right inverse). (Based on his comment, I'm guessing that some guy on the street was doing more or less the same thing.)

Could you tell us what you had in mind?

share|cite|improve this answer
Actually, Mathieu Anel found a very nice way of getting the image factorization quite naively. Begin with [1]="0-->1". Map it to the "coequalizer category" "-1==>0-->1" and apply the lower star: this gives the kernel. Now map this to "-1==>0-->1/2-->1" again with 1/2 coequalizing the two maps 0==>1. Apply the lower shriek. This is your answer. – David Spivak Sep 12 '10 at 2:29
Nice! Well, that's that! – Todd Trimble Sep 12 '10 at 3:06

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.