Can every category be regarded as the functor category of another?

Question

Given a category $\mathcal{C}$ is there necessarily another category $\mathcal{D}$ such that $\mathcal{C}$ is equivalent to the functor category $\mathrm{Set}^\mathcal{D}$? If so, is there a natural choice? Is there some hypothesis we could assume for $\mathcal{C}$ to make this question more interesting?

Answer 1

There are a lot of immediate obstacles to such an equivalence. In increasing order of fanciness: such a category can't have a zero object; the initial object must be strict; it must be complete and cocomplete; as the commenters say it must be Cartesian closed and admit a subobject classifier. These conditions already rule out the great majority of natural examples.

If $\mathcal D$ is to be small, such categories may be fully characterized as the cocomplete categories containing a small dense subcategory consisting of small-projective objects, which are the objects $x$ such that for any diagram $D:I\to \mathcal C$, one has $$\mathcal C(x,\mathrm{colim}_I D(i))\cong \mathrm{colim}_I \mathcal C(x,D(i))$$ with the colimit on the right-hand side taken in sets. If $\mathcal D$ is not to be small, such categories are not very natural. Better to take either small functors from $\mathcal D$, in which case essentially the same characterization applies, or functors from $\mathcal D$ into large sets; ditto modulo moving up a Grothendieck universe.

To be small-projective is a vast strengthening of the notion of projectivity familiar from homological algebra, and it's overwhelmingly rare in practice. Such perfectly innocent categories as the categories of sheaves on any nontrivial space and any abelian category have almost no small-projective objects. (For concrete abelian categories, the problem is that not every element of a biproduct comes from one of the factors.) Small-projectives also do not arise in complete posets without extreme assumptions, something like being a finite total order.

In short, very few categories can be realized in this form except those you already know can be: sets and categories of actions of a group, a monoid, or a category on sets.

However, most natural categories do embed fully faithful in such a category. Barr's embedding theorem gives such a result for regular categories, while the ever-popular locally presentable categories are in fact reflectively embedded in such a category, via embeddings preserving certain colimits; on the other side of things Grothendieck toposes are reflectively embedded by an embedding with a reflector preserving certain limits.