8
$\begingroup$

How to write the covariant power set functor (restricted to finite sets for simplicity) $$P : \mathsf{FinSet} \to \mathsf{Set}$$ concisely as a colimt of representable functors? There is an epimorphism $$\coprod_{n \geq 0} \hom(\{1,\dotsc,n\},-) \to P,$$ mapping $f \in \hom(\{1,\dotsc,n\},X)$ to $\mathrm{im}(f) \in P(X)$. This already provides a generating set of $P$. Compare this with the contravariant power set functor, which is already a representable functor.

This question is motivated by the exercise to find all morphisms of functors $P \to P$ without too much calculations.

$\endgroup$
3
  • $\begingroup$ I believe the only thing you have to factor out is identifying all $\{1,...,n\}\twoheadrightarrow\{1,...,m\}\hookrightarrow X$ with $\{1,...,m\}\hookrightarrow X$. That is, restrict the diagram to those $f$ only which are inclusions, and factor out by all permutations of the domains of the $f$s. $\endgroup$ Commented Oct 30, 2017 at 9:57
  • $\begingroup$ I want to have representable functors, which contain all $f$s. So you say that the epimorphism is the coequalizer of the two evident morphisms $$\coprod_{g : \{1,\dotsc,n\} \twoheadrightarrow \{1,\dotsc,m\}} \hom(\{1,\dotsc,m\},-) \rightrightarrows \coprod_{n \geq 0} \hom(\{1,\dotsc,n\},-)~?$$I assume that this can be simplified further, using "generators of the epimorphisms". $\endgroup$
    – HeinrichD
    Commented Oct 30, 2017 at 10:10
  • $\begingroup$ I tried to make this an answer. Not 100% sure, though - did not check everything yet... $\endgroup$ Commented Oct 30, 2017 at 10:11

1 Answer 1

9
$\begingroup$

It helps a lot that in this case $\hom(\{1,...,n\},-)\cong\hom(\{1\},-)^n$. Denote $\hom(\{1\},-)$ by $X$ and take more generally in any category with finite products and countable colimits distributing over each other the free monoid on $X$, that is, $1\sqcup X\sqcup X^2\sqcup X^3\sqcup\cdots$. Now in addition factor out by the following: identify, for any surjection $\pi:\{1,...,m\}\twoheadrightarrow\{1,...,n\}$, the summand $X^n$ with its image under $X^\pi:X^n\rightarrowtail X^m$ (note that in particular this forces quotienting $X^n$ by the action of the $n$th symmetric group, so we get the free commutative monoid on $X$ as an intermediate step).

I believe what we get is the free internal semilattice on $X$, and for $X=\hom(\{1\},-)$ one obtains the covariant powerset. This answers the question since the diagram we start from consists of representables since, as already said, $X^n$ is isomorphic to $\hom(\{1,...,n\},-)$.

As HeinrichD notes in the comment below, we probably only need quotients by $X^k\times\text{switch}\times X^l:X^k\times X^2\times X^l\to X^k\times X^2\times X^l$ and by $X^n\times\text{diagonal}:X^n\times X\to X^n\times X^2$, although I fail to organize this into a honest diagram for the moment.

In any case, seems like the resulting description of natural transformations $P\to F$ is as follows: they are in one-to-one correspondence with families $$ \left(\xi_n\right)_{n=0,1,2,...}\in\prod_{n=0}^\infty F(n)^{\Sigma_n} $$ satisfying $$ F(\pi)(\xi_{n+1})=\xi_n $$ for all $n>0$, where $\pi:\{1,...,n+1\}\to\{1,...,n\}$ is given by $1\mapsto1,...,n\mapsto n,n+1\mapsto n$.

Later:

Here is a sketch of an alternative calculation for the above $\hom$, using the fact that $P\cong i_!(1)$, where $i:\mathsf{Finepi}\hookrightarrow\mathsf{FinSet}$ is the embedding of the subcategory with the morphisms surjections only, while $i_!$ is the left adjoint to the restriction $i^*:\mathsf{Set}^{\mathsf{FinSet}}\to\mathsf{Set}^{\mathsf{Finepi}}$.

Indeed, using the left Kan extension formula,$$i_!(1)(n)=\varinjlim\left(i/n\xrightarrow{\text{(take domain)}}\mathsf{Finepi}\xrightarrow{\text{constant $1$}}\mathsf{Set}\right);$$ now every object $f:i(m)\to n$ of $i/n$ admits a morphism to the object $\operatorname{image}(f)\hookrightarrow n$, so that we may restrict from $i/n$ to its cofinal subcategory whose objects are inclusions of subsets into $n$. From this it is easy to see that indeed $P=i_!(1)$.

Using this then, $\hom(P,F)$ $=$ $\hom(i_!(1),F)$ $=$ $\hom(1,i^*(F))$ $=$ $\varprojlim(i^*(F))$, which more or less amounts to the same expression as in the first version above.

$\endgroup$
5
  • 1
    $\begingroup$ Ok, this is good. Can we reduce the set of surjections here? Probably we only need the transpositions (as generators for the permutations) and the maps $\{1,\dotsc,n+1\} \to \{1,\dotsc,n\}$, $k \mapsto k$ (for $k \leq n$) resp. $n+1 \mapsto n$? $\endgroup$
    – HeinrichD
    Commented Oct 30, 2017 at 10:26
  • $\begingroup$ Good point. As said, we just need the free semilattice on $\hom(1,-)$. So this just amounts to ensuring commutativity and $xx=x$, so you must be right here. $\endgroup$ Commented Oct 30, 2017 at 10:28
  • 1
    $\begingroup$ Alright, and there are exactly two morphisms $P \to P$. $\endgroup$
    – HeinrichD
    Commented Oct 30, 2017 at 13:23
  • $\begingroup$ In other words, there are no non-identitiy morphisms $P^+\to P^+$, where $P^+$ is the subfunctor of nonempty subsets (since $P=1\sqcup P^+$). $\endgroup$ Commented Oct 30, 2017 at 13:26
  • $\begingroup$ (And also that $\hom(1,P^+)=\varnothing$, but this is clear since $P^+(0)=\varnothing$) $\endgroup$ Commented Oct 30, 2017 at 14:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .