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$ 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
    Oct 30, 2017 at 10:10
  • $\begingroup$ I tried to make this an answer. Not 100% sure, though - did not check everything yet... $\endgroup$ 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
    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$ Oct 30, 2017 at 10:28
  • 1
    $\begingroup$ Alright, and there are exactly two morphisms $P \to P$. $\endgroup$
    – HeinrichD
    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$ Oct 30, 2017 at 13:26
  • $\begingroup$ (And also that $\hom(1,P^+)=\varnothing$, but this is clear since $P^+(0)=\varnothing$) $\endgroup$ Oct 30, 2017 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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