First: upper-star, then: lower-star, finally: lower-shriek

2010-08-13T19:37:09Z

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?

Thanks.

Answer by Todd Trimble for First: upper-star, then: lower-star, finally: lower-shriek

2010-09-12T00:25:30Z

First of all: yes, there's certainly a connection. See http://ncatlab.org/nlab/show/polynomial+functor. 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?

First: upper-star, then: lower-star, finally: lower-shriek - MathOverflow

First: upper-star, then: lower-star, finally: lower-shriek

Answer by Todd Trimble for First: upper-star, then: lower-star, finally: lower-shriek