Can we always make a strictly functorial choice of pullbacks/re-indexing?

Question

$\newcommand{\C}{\mathbf{C}} \newcommand{\D}{\mathbf{D}}$ Let $\C$ be a category with pullbacks. Taking any choice of pullbacks gives us re-indexing functors $f^* \colon \C /Y \to \C/X$, and these will be functorial in $f$ up to natural isomorphism, in that $g^* \cdot f^* \cong (f \cdot g)^*$. However, these will usually not be strictly functorial in $f$; that is, $g^* \cdot f^*$ and $(f \cdot g)^*$ will not be literally equal. Strict functoriality also requires that $1_X^* = 1_{\C/X}$; while this typically does hold on the nose, it’s still not automatic.

My main question: Is there always some choice of pullbacks that make re-indexing strictly functorial? I believe the answer should be “no”, but I don’t know any counterexample. Even in the case of $\mathbf{Set}$, it’s not obvious whether there’s a choice that works.

An equivalent phrasing of the question is: can the codomain fibration $\mathrm{cod} \colon \C^\rightarrow \to \C$ be equipped with a splitting? It can always be replaced by an equivalent split fibration over $\C$; but splitting the codomain fibration itself seems hard.

Answer 1

No, it is not always possible to make a strictly functorial choice of pullbacks. Four years later, I found a simple (if contrived) counterexample for this:

Let $\newcommand{\C}{\textbf{C}}\C$ be any full subcategory of $\textbf{FinSet}$ containing infinitely many sets of size 2, and at least one set of every finite size, but only one set of size 4. Certainly $\C$ has all pullbacks, since it is equivalent to $\textbf{FinSet}$.

Now pick specific 1- and 2-element sets $\newcommand{\one}{{1}}\newcommand{\two}{{2}}\one$, $\two$. Let $r : \two \to \one$ be the unique possible map, and $s : \one \to \two$ either of the two possible such maps. Then $s$, $r$ form a section-rectraction pair $\one \to \two \to \one$, with $rs = \newcommand{\id}{\mathrm{id}}\id_\one$.

If $\C$ had a strictly functorial choice of pullback functors, then the functors $r^* : \C/\one \to \C/\two$ and $s^* : \C/\two \to \C/\one$ would also be a (strict) section-retraction pair, with $s^* r^* = \id_{\C/\one}$. In particular, this would exhibit the subcategory of $\C/\one$ on 2-element sets (which is infinite) as a strict retract of the subcategory of $\C/\two$ on “maps into $\two$ where each fiber has size 2”, which has only 3 objects since $\C$ had only one object of size 4. But this is impossible: an infinite category can’t be a strict retract of a finite one.

Answer 2

Many years ago, Peter Freyd published (I think he published it) a paper in which he showed that while it was possible to replace any category with products by a category with canonical products, the same could not be done for pullbacks. The only thing I remember about the paper was the use of the word "table" for some construction. If you can't find it, write to Peter directly.

Answer 3

Here's an argument (assuming global choice) that the codomain fibration will always be split in "natural" cases. Perhaps it's well-known, or perhaps it has an important shortcoming (such as the use of choice?). Or perhaps there's an error -- strictification is tricky!

---

Claim: Let $C$, $D$ be categories with pullbacks, and suppose there is a functor $p: C \to D$ with the following properties:

1. $p$ preserves pullbacks.

2. $p$ is an isofibration, and induces an isofibration on all slices (perhaps this is redundant?).

3. $p$ reflects identities (i.e. if $f: c \to c$ is an endomorphism in $C$, and $pf: pc \to pc$ is an identity, then so is $f$).

4. There is a cardinal $\kappa$ such that for every $f: x \to c \in C^{[1]}$, the isomorphism class $[f]$ of $f$ in the fiber category $p^{-1}(pf) \subseteq C/c$ has cardinality $\kappa$.

The claim is that if $D$ admits strict reindexing, then so does $C$, and $p$ preserves the strict reindexing.

---

Upshot: Most "natural" categories $C$ admit such a functor $p: C \to \mathsf{Set}$, with $\kappa$ being the cardinality of the universe (perhaps with an exception for objects over $\emptyset$, which often doesn't matter because there are few maps into $\emptyset$). I'm assuming that $\mathsf{Set}$ admits strict reindexing (right?). So most "natural" categories do as well.

EDIT: $\mathsf{Set}$ does indeed admit strict reindexing. To see this, as in the comment below, note that the fibration $\mathsf{Set}^{(-)} \to \mathsf{Set}$ admits a splitting, and the fibration $\mathsf{Set}/(-) \to \mathsf{Set}$ is isomorphic as a fibered caegory -- the fact that it's equivalent as a fibered category is standard, and each isomorphism class in each fiber category has the cardinality of the universe, in both fibrations, so an isomorphism of fibrations exists. So $\mathsf{Set}/(-) \to \mathsf{Set}$ also admits a splitting as desired.

So indeed, most "natural" categories admit a strict reindexing. Of course, it's completely undecideable to compute it because the choice function must solve the isomorphism problem!

---

Proof of Claim: Let $()^\ast$ be a system of strict reindexing in $D$. Fix enumerations of the isomorphism classes of the fibers of $p$ by $\kappa$ (using condition (4) and choice). Now, if $\gamma : c' \to c$ is a morphism in $C$ and $f: x \to c \in C/c$, take an arbitrary pullback of $f$ along $\gamma$. Because $p$ is an isofibration (condition (2))and $p$ preserves pullbacks (condition (1)), we can correct this choice to lie over the canonical pullback $(p\gamma)^\ast(pf)$. Moreover, we can choose a representative which has the same index under our enumeration as $f$ does; let's call it $\gamma^\ast(f)$. It remains only to nail down the lift of the other leg of the pullback square, but any two choices differ by an automorphism of $\gamma^\ast(f)$ which lies over the identity on $(p\gamma)^\ast(pf)$, so by condition (3) this choice is uniquely determined.

It's now obvious that the lifted operation $()^\ast$ is strictly functorial, because it preserves the indexing by our enumerations.