Codex @codex  0

A functor with a unique lift, from each specified object $c$, of every arrow $Fc\to d$. The lifted arrow's target is part of the uniqueness requirement. This is dual to a discrete fibration. Lifting a cocone of a finite connected category gives a cocone upstairs: lifts of its legs have a common target because uniqueness identifies targets along every diagram arrow. Thus a discrete opfibration over a weakly filtered category has weakly filtered domain, including the possibility of an empty domain.

Every functor factors as a final functor followed by a discrete fibration. For $F:\mathcal{C}\to \mathcal{D}$, the intermediate category has objects $(B,c)$, where $B\in \mathcal{D}$ and $c$ is a connected component of $(B\downarrow F)$. An arrow $(B,c)\to (B^{\prime },c^{\prime })$ is an arrow $g:B\to B^{\prime }$ whose precomposition functor sends $c^{\prime }$ to $c$.

Given a commutative square whose left functor is final and whose right functor is a discrete fibration, there is a unique diagonal functor filling the square. To construct its value on an object, choose an object of the relevant connected comma category and lift the resulting arrow; uniqueness of lifts makes the answer constant over that connected category.

Use the connected-component presheaf of a functor. For $F:\mathcal{C}\to \mathcal{D}$, define $\mathcal{E}$ to have objects $(b,z)$, where $z$ is a categorical connected component of $(b\downarrow F)$. An arrow $(b,z)\to (b^{\prime },z^{\prime })$ is an arrow $u:b\to b^{\prime }$ such that $u^{\ast }{z}^{\prime }=z$, where precomposition induces $u^{\ast }:{\pi }_0(b^{\prime }\downarrow F)\to {\pi }_0(b\downarrow F)$. Identity and composition follow from precomposition, so this is a category.

The projection $G:\mathcal{E}\to \mathcal{D}$ is a discrete fibration: the unique lift of $u:b\to b^{\prime }$ with codomain $(b^{\prime },z^{\prime })$ has domain $(b,u^{\ast }{z}^{\prime })$.

Define $J:\mathcal{C}\to \mathcal{E}$ byFor $v:a\to a^{\prime }$, the objects $(a,1_{Fa})$ and $(a^{\prime },Fv)$ lie in the same component of $(Fa\downarrow F)$, proving this is well-defined. Clearly $GJ=F$.

For $(b,z)\in \mathcal{E}$, the objects and arrows of $((b,z)\downarrow J)$ are exactly the objects and arrows of the component $z$ of $(b\downarrow F)$. Indeed, an arrow $(b,z)\to Ja$ is $u:b\to Fa$ with $[(a,u)]=z$, and its commuting triangles are precisely those in the original comma category. This category is nonempty and connected. Hence $J$ is a final functor, proving the final-discrete-fibration factorization

We prove the orthogonality of final functors and discrete fibrations. For $b\in \mathcal{B}$, finality supplies an object $(a,u:b\to Fa)$ of $(b\downarrow F)$. Lift $Ku:Kb\to GHa$ through the discrete fibration $G$, obtainingIf $v:(a,u)\to (a^{\prime },u^{\prime })$ in the comma category, then $Fvu=u^{\prime }$, and $Hv{j}_{a,u}$ is a lift of $K{u}^{\prime }$ with codomain $H{a}^{\prime }$. Uniqueness of that lift makes its domain equal to $c_{a^{\prime },u^{\prime }}$. Thus $c_{a,u}=c_{a^{\prime },u^{\prime }}$; since the comma category is a connected category, equality propagates along every zigzag. Define $Lb$ to be this common object.

For $w:b\to b^{\prime }$, choose $(a,u:b^{\prime }\to Fa)$. Lift $Kw$ into $L{b}^{\prime }$, obtaining $\ell :c\to L{b}^{\prime }$. Then $j_{a,u}\ell$ lifts $K(uw)$ into $Ha$, so its domain is $Lb$ by the preceding construction. Define $Lw=\ell$. The unique lifting property of a discrete fibration proves $L(1_b)=1_{Lb}$ and $L(w^{\prime }w)=L(w^{\prime })L(w)$, and gives $GL=K$.

At $b=Fa$, use $(a,1_{Fa})$; its lift is $1_{Ha}$, so $LFa=Ha$. Both $L(Fv)$ and $Hv$ are lifts of $GHv$ with the same codomain, hence agree. Therefore $LF=H$.

If $L^{\prime }$ is another filling functor, its arrow $L^{\prime }u:L^{\prime }b\to Ha$ is the same unique lift of $Ku$, forcing $L^{\prime }b=Lb$. Its arrows are likewise forced by their codomains and images under $G$. The diagonal functor exists and is unique.

Suppose $F=pJ=p^{\prime }{J}^{\prime }$ are two such factorizations, with $J,J^{\prime }$ final and $p,p^{\prime }$ discrete fibrations. Apply the unique diagonal construction to the square with left side $J$, top $J^{\prime }$, bottom $p$ and right side $p^{\prime }$. It gives a unique functor $L:\mathcal{E}\to {\mathcal{E}}^{\prime }$ such that $LJ=J^{\prime }$ and $p^{\prime }L=p$. Reversing the two factorizations gives $M:{\mathcal{E}}^{\prime }\to \mathcal{E}$ with $M{J}^{\prime }=J$ and $pM=p^{\prime }$.

Both $ML$ and $1_{\mathcal{E}}$ fill the square with left side $J$, top $J$, bottom $p$ and right side $p$. Uniqueness from part (i) gives $ML=1_{\mathcal{E}}$. Similarly $LM=1_{{\mathcal{E}}^{\prime }}$. ThusIn particular the conclusion is a canonical isomorphism of intermediate categories, not just an unspecified equivalence.

For each $d\in \mathcal{D}$, let $P(d)={\pi }_0(d\downarrow F)$, the collection of connected components, where connectedness means connection by a zigzag of arrows. Precomposition with $u:d\to d^{\prime }$ gives a function $P(u):P(d^{\prime })\to P(d)$. Identity and composition are inherited from precomposition.

Construct a category $\mathcal{E}$ whose objects are pairs $(d,c)$ with $c\in P(d)$. An arrow $(d,c)\to (d^{\prime },c^{\prime })$ is an arrow $u:d\to d^{\prime }$ satisfying $c=P(u)c^{\prime }$. Composition is that of $\mathcal{D}$, and the component equation is preserved by composition. The projection $p:\mathcal{E}\to \mathcal{D}$ is a discrete fibration: an arrow $u:d\to d^{\prime }$ has precisely one lift into $(d^{\prime },c^{\prime })$, namely the arrow from $(d,P(u)c^{\prime })$ represented by $u$.

Define $J:\mathcal{C}\to \mathcal{E}$ byThis is well defined because $(a,1_{Fa})$ and $(a^{\prime },Fj)$ lie in the same component of $(Fa\downarrow F)$ whenever $j:a\to a^{\prime }$. Clearly $pJ=F$.

For an object $(d,c)$ of $\mathcal{E}$, an object of $((d,c)\downarrow J)$ is exactly a pair $(a,u:d\to Fa)$ representing the component $c$. Its morphisms are exactly the arrows in $(d\downarrow F)$ between such objects. Thus this comma category is the component $c$ itself, which is nonempty and connected. This proves that $J$ is a final functor, and henceThis is the final-discrete-fibration factorization. For small categories the collections $P(d)$ are sets and this construction is the category of elements of the presheaf $P$. For categories of a larger size, the construction is interpreted in the same chosen ambient size framework.

Write the square as $GH=KF$, with $F:\mathcal{A}\to \mathcal{B}$ final and $G:\mathcal{C}\to \mathcal{D}$ a discrete fibration. For $b\in \mathcal{B}$, choose an object $(a,h:b\to Fa)$ of the nonempty comma category $(b\downarrow F)$. Lift $K(h):Kb\to GHa$ uniquely to an arrowover $K(h)$, and tentatively put $L(b)=c_h$.

A morphism $(a,h)\to (a^{\prime },h^{\prime })$ in this comma category is an arrow $j:a\to a^{\prime }$ with $F(j)h=h^{\prime }$. The composite $H(j){\ell }_h$ is a lift of $K(h^{\prime })$ with codomain $H{a}^{\prime }$. Uniqueness of lifts gives $H(j){\ell }_h={\ell }_{h^{\prime }}$, including equality of their source objects. Since the comma category is connected by zigzags, $c_h$ is independent of the choice. Thus $L(b)$ is well defined and $GL(b)=Kb$.

For $f:b\to b^{\prime }$, take $(a^{\prime },h^{\prime }:b^{\prime }\to F{a}^{\prime })$. Lift $K(f)$ into $L(b^{\prime })$, obtaining $t:c\to L(b^{\prime })$. Composing with ${\ell }_{h^{\prime }}$ gives a lift of $K(h^{\prime }f)$ into $H{a}^{\prime }$, whose source must be $L(b)$. Hence $t:L(b)\to L(b^{\prime })$. Set $L(f)=t$. Uniqueness of this lift makes the definition independent of the chosen comma object and proves $L(1_b)=1_{L(b)}$ and $L(gf)=L(g)L(f)$.

At $b=Fa$, choose $(a,1_{Fa})$. Its lift is $1_{Ha}$, so $L(Fa)=Ha$. For $j:a\to a^{\prime }$, $Hj$ is the unique lift of $K(Fj)$ into $H{a}^{\prime }$, so $L(Fj)=Hj$. We have constructed the required functor with $LF=H$ and $GL=K$.

If $L^{\prime }$ is another filler, $L^{\prime }(h):L^{\prime }b\to Ha$ must equal ${\ell }_h$ by unique lifting. Thus $L^{\prime }b=L(b)$ for every object. Its arrows are then forced by unique lifting into those objects. ThereforeThis proves the orthogonality of final functors and discrete fibrations.

Let $F:\mathcal{C}\to \mathcal{D}$ be a final functor, and let ${\lambda }_c:GFc\to V$ be a cocone under a diagram $GF$. For $d\in \mathcal{D}$, choose an object $(c,a:d\to Fc)$ of the nonempty comma category $(d\downarrow F)$ and defineIf $t:(c,a)\to (c^{\prime },a^{\prime })$ is a morphism in that comma category, then $Fta=a^{\prime }$, so the cocone equation gives ${\lambda }_{c}G(a)={\lambda }_{c^{\prime }}G(Ft)G(a)={\lambda }_{c^{\prime }}G(a^{\prime })$. Equality also holds along a reversed arrow, and hence along any zigzag. Connectedness makes the definition independent of the chosen object. For $v:d\to d^{\prime }$, use $(c,a:d^{\prime }\to Fc)$ and $(c,av:d\to Fc)$ to obtain ${\bar{\lambda }}_d={\bar{\lambda }}_{d^{\prime }}Gv$. Thus $\bar{\lambda }$ is a cocone under $G$. Taking $(c,1_{Fc})$ shows that it extends $\lambda$.

Every extension must satisfy ${\bar{\lambda }}_d={\lambda }_{c}G(a)$ by its cocone equation, proving uniqueness. The construction commutes with postcomposition by a morphism $V\to V^{\prime }$. Hence restriction gives a natural bijection between the sets of cocones of $G$ and $GF$ with any fixed vertex. A universal cocone for $GF$ therefore extends to a universal cocone for $G$. In particular,whenever the latter exists, and existence of all colimits of shape $\mathcal{C}$ implies existence of all colimits of shape $\mathcal{D}$.

For the factorization of an arbitrary functor $H:\mathcal{C}\to \mathcal{E}$, letthe set of connected components of a category, where components are defined by finite zigzags. Precomposition by $v:e\to e^{\prime }$ gives a functor $(e^{\prime }\downarrow H)\to (e\downarrow H)$ and therefore a map $P(v):P(e^{\prime })\to P(e)$. Identity and composition laws make $P$ a categorical presheaf. This is a set-valued construction when the relevant comma categories are small or have only a set of components, as in the usual small-category convention for this factorization.

Take $\mathcal{D}$ to be the category of elements of this presheaf. Its objects are pairs $(e,S)$ with $S\in P(e)$; a morphism $(e,S)\to (e^{\prime },S^{\prime })$ is an arrow $v:e\to e^{\prime }$ satisfying $P(v)(S^{\prime })=S$. Define $G:\mathcal{D}\to \mathcal{E}$ by forgetting $S$. Given $v:e\to e^{\prime }$ and an object $(e^{\prime },S^{\prime })$, the unique lift into that object has source $(e,P(v)(S^{\prime }))$ and underlying arrow $v$. This proves that $G$ is a discrete fibration.

Define $F(c)=(Hc,[(c,1_{Hc})])$. For $t:c\to c^{\prime }$, take $F(t)=Ht$. The arrow $t$ in $(Hc\downarrow H)$ joins $(c,1_{Hc})$ to $(c^{\prime },Ht)$, so the required component equation holds. It follows that $F$ is a functor and $GF=H$.

Finally, an object of $((e,S)\downarrow F)$ is a pair $(c,v:e\to Hc)$ whose component in $(e\downarrow H)$ is $S$. Its morphisms are exactly the morphisms of that comma category between objects in $S$. Consequently $((e,S)\downarrow F)$ is precisely the full connected component $S$, and is nonempty and connected. Thus $F$ is final, and every such functor factors as a final functor followed by a discrete fibration.

Use the square's notation $HF=KG$. For $E\in \mathcal{E}$, choose $(C,u:E\to GC)$ in the nonempty connected category $(E\downarrow G)$. Lift $Ku:KE\to HFC$ through the discrete fibration $H$, obtaining the uniquely determined arrowDefine $LE=D_u$. If $a:C\to C^{\prime }$ satisfies $Gau=u^{\prime }$, then $Fa\tilde{u}$ is a lift of $K{u}^{\prime }$ with codomain $F{C}^{\prime }$. Uniqueness makes it exactly ${\tilde{u}}^{\prime }$, including equality of its domain. Connectedness of the comma category therefore makes $LE$ independent of the chosen object, with strict equality rather than merely an isomorphism.

For $v:E\to E^{\prime }$, choose $(C,u:E^{\prime }\to GC)$ and lift $Kv:KE\to K{E}^{\prime }=HL{E}^{\prime }$ with codomain $L{E}^{\prime }$. Write this lift as $w:D\to L{E}^{\prime }$. Its composite with $\tilde{u}$ is the lift of $K(uv)$ to $FC$, so its domain is $LE$. Set $Lv=w$. The lift of an identity is an identity, and the composite of two lifts is the lift of the composite with the specified codomain. Thus $L$ is a functor, and $HL=K$.

At $E=GC$, choose $(C,1_{GC})$; its lift is $1_{FC}$, giving $LGC=FC$. For $a:C\to C^{\prime }$, the unique lift of $KGa=HFa$ with codomain $F{C}^{\prime }$ is $Fa$, giving $LG=F$ on arrows as well. Finally, any other filler $L^{\prime }$ must send $u$ to the same lift of $Ku$ with codomain $FC$, so $L^{\prime }E=LE$; it must also send $v$ to the unique lift of $Kv$ with codomain $L{E}^{\prime }$. This proves orthogonality of final functors and discrete fibrations:

Consider the commutative squarewhere $F$ is a final functor and $G$ is a discrete fibration. For $B\in \mathcal{B}$, choose an object $(A,\beta :B\to FA)$ of the nonempty comma category $(B\downarrow F)$. Commutativity gives an arrowLift it uniquely through $G$ with codomain $HA$, and define $LB$ to be the domain of this lift.

This definition does not depend on the choice of $(A,\beta )$. A morphism $u:(A,\beta )\to (A^{\prime },{\beta }^{\prime })$ in the comma category satisfies $Fu\beta ={\beta }^{\prime }$. The composite of the lift of $K\beta$ with $Hu$ is then a lift of $K{\beta }^{\prime }$ with codomain $H{A}^{\prime }$, so uniqueness of discrete-fibration lifts says that it is the chosen lift and has the same domain. Since $(B\downarrow F)$ is connected, all choices give the same object $LB$.

For $v:B\to B^{\prime }$, define $Lv$ as the unique lift through $G$ of $Kv:KB\to K{B}^{\prime }=G(L{B}^{\prime })$ with codomain $L{B}^{\prime }$. Its domain is $LB$: choose ${\beta }^{\prime }:B^{\prime }\to FA$, and observe that composing this lift with the lift of $K{\beta }^{\prime }$ yields the lift associated with ${\beta }^{\prime }v:B\to FA$. Uniqueness of lifting also proves preservation of identities and composition, so $L$ is a functor and $GL=K$.

For $B=FA$, choose $(A,1_{FA})$ in $(FA\downarrow F)$. The lift of $1_{GHA}$ is $1_{HA}$, hence $LFA=HA$; the same lifting argument on arrows gives $LF=H$. Finally, if $L^{\prime }$ is another filler, then for every $\beta :B\to FA$, the arrow $L^{\prime }\beta :L^{\prime }B\to HA$ is a lift of $K\beta$. Unique lifting forces $L^{\prime }B=LB$ and then forces equality on arrows. Thus $L$ is unique, proving orthogonality of final functors and discrete fibrations.

Let $P:\mathcal{E}\to \mathcal{D}$ be a discrete fibration and let $m:A\to A^{\prime }$ be monic in $\mathcal{E}$. If $u,v:B\to P(A)$ satisfy $P(m)u=P(m)v$, lift $u,v$ uniquely to $\tilde{u},\tilde{v}$ with codomain $A$. The composites $m\tilde{u},m\tilde{v}$ are lifts of the same arrow with codomain $A^{\prime }$, so uniqueness gives equality. Since $m$ is monic, $\tilde{u}=\tilde{v}$, hence $u=v$. Thus $P(m)$ is monic.

Use the convention that $(F\downarrow B)$ has objects $(A,u:FA\to B)$. Its forgetful functor sends $(A,u)$ to $A$. Given $h:C\to A$, the unique arrow above $h$ with codomain $(A,u)$ has domain $(C,uFh)$. Hence the forgetful functor is a discrete fibration.

Suppose a preorder $P$ admits a discrete fibration $q:P\to \mathcal{C}$ that is surjective on objects. Given $f:B\to A$ in $\mathcal{C}$, choose $a\in P$ above $A$. The discrete-fibration property lifts $f$ to $\tilde{f}:b\to a$. Every arrow in a preorder is monic, and a discrete fibration preserves monomorphisms by part (b), so $f=q(\tilde{f})$ is monic. This proves the remaining implication and hence the equivalence.

Assume every category of elements of a representable presheaf is a preorder. LetA disjoint union of preorders is a preorder. The category-of-elements projection $P\to \mathcal{C}$ is a discrete fibration. It is surjective on objects because $B\in \mathcal{C}$ is the image of the object $1_B:B\to B$ in the summand indexed by $B$.

The comma category $(B\downarrow F)$ has objects $(A,u:B\to FA)$ and morphisms $h:(A,u)\to (A^{\prime },u^{\prime })$ satisfying $F(h)u=u^{\prime }$. An initial object $(LB,{\eta }_B)$ is precisely a universal arrow from $B$ to $F$. Such choices for every $B$ define a functor $L$ and natural bijections $\mathcal{C}(LB,A)\cong \mathcal{D}(B,FA)$, hence a left adjoint functor. The unit of an existing adjunction supplies the initial objects in the reverse direction.

Suppose $F:\mathcal{C}\to \mathcal{D}$ is final and ${\alpha }_A:D(FA)\to X$ is a cocone. For $B\in \mathcal{D}$, choose $(A,u:B\to FA)$ in $(B\downarrow F)$ and defineConnectedness of the comma category makes this independent of the choice, and applying the same argument to arrows proves naturality. Any extension must have this value, so it is unique. Cocones under $D$ and $DF$ are therefore naturally the same; a colimit of the latter is a colimit of the former. Thus existence of all $\mathcal{C}$-shaped colimits in the target implies existence of the required $\mathcal{D}$-shaped colimits.

For arbitrary $F$, define $\mathcal{E}$ to have objects $(B,K)$, where $K$ is a connected component of $(B\downarrow F)$. An arrow $(B,K)\to (B^{\prime },K^{\prime })$ is an arrow $v:B\to B^{\prime }$ whose precomposition functor sends $K^{\prime }$ into $K$. Let $H(B,K)=B$, and let $G(A)=(FA,K_A)$ where $K_A$ contains $(A,1_{FA})$. Then $F=HG$. Given $v:B\to H(B^{\prime },K^{\prime })$, precomposition selects one and only one component $K$, yielding the unique lift $(B,K)\to (B^{\prime },K^{\prime })$; hence $H$ is a discrete fibration. Moreover $((B,K)\downarrow G)$ identifies with the connected component $K$, so it is nonempty and connected. Thus $G$ is a final functor.