Past exam of the mathematics course of the University of Cambridge / 2004 / iii / Paper 23 / Section B

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.

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

Suppose $F=GJ=G^{\prime }{J}^{\prime }$ are two final-discrete-fibration factorizations. Apply the orthogonality of final functors and discrete fibrations to the square with left side $J$, top $J^{\prime }$, bottom $G$ and right side $G^{\prime }$. It gives a unique $S:\mathcal{E}\to {\mathcal{E}}^{\prime }$ satisfying $SJ=J^{\prime }$ and $G^{\prime }S=G$. Reversing the roles gives $T:{\mathcal{E}}^{\prime }\to \mathcal{E}$.

Both $TS$ and $1_{\mathcal{E}}$ fill the same square for $J,G$, so uniqueness gives $TS=1_{\mathcal{E}}$; similarly $ST=1_{{\mathcal{E}}^{\prime }}$. This proves the uniqueness of a final-discrete-fibration factorization: the connecting functor is a canonical isomorphism, not just a noncanonical equivalence.

An adjunction $L⊣U$ induces the monad $T=UL$ with unit $\eta$ and multiplication $U\epsilon L$. The Eilenberg-Moore comparison functor sends $B$ to $(UB,U{\epsilon }_B)$. A monadic adjunction is one for which that comparison is an equivalence of categories. Iterating comparisons, when their left adjoints exist, gives a tower; its monadic length is the number of steps until equivalence, with length zero for an equivalence and length one for a monadic adjunction that is not already an equivalence.

The precise monadicity theorem says that a right adjoint is monadic exactly when it reflects isomorphisms and creates coequalizers of pairs whose images admit split coequalizers.

Write $U_r:{\mathcal{C}}_r\to {\mathcal{C}}_{r-1}$ for one-step forgetting. For $r=1$, the free extension of nested partial unary operations is the familiar set $A\times \mathbb{N}$, with ${\alpha }_1(a,j)=(a,j+1)$ and unit $a\mapsto (a,0)$. A map into a set with endomorphism ${\beta }_1$ extends uniquely by $(a,j)\mapsto {\beta }_1^{j}f(a)$.

For $r\ge 2$, letKeep $A$ and all its old operations, and adjoin the disjoint set $S(A)\times \mathbb{N}$. On the new points define ${\alpha }_1(a,j)=(a,j+1)$; every old operation ${\alpha }_i$ with $i\ge 2$ is undefined there. Define the new top operation only at the old eligible points, by ${\alpha }_r(a)=(a,0)$ for $a\in S(A)$.

These domains satisfy the defining rules of the nested partial unary operation category: the new points have no ${\alpha }_1$-fixed points, so none has any higher operation defined. Given $f:A\to U_{r}B$, extend it byThe expression is defined because $f$ sends eligible points to eligible points and ${\beta }_1$ is total. It preserves every defined operation; preservation of ${\alpha }_r$ at old points determines $j=0$, and preservation of ${\alpha }_1$ determines the whole chain. Thus it is the unique extension, proving $L_r⊣U_r$.

For monadicity, $U_r$ reflects isomorphisms: an isomorphism of the lower structures takes $S(A)$ bijectively to $S(B)$, so the inverse of a map preserving the new operation preserves it too.

Next prove the split-coequalizer lifting for a fixed-point-domain operation. Let $f,g:A\rightrightarrows B$ be ${\mathcal{C}}_r$-morphisms and suppose their lower images have a split coequalizer $q:U_{r}B\to Q$, with $s:Q\to U_{r}B$, $t:U_{r}B\to U_{r}A$ satisfyingEquip $Q$ with ${\beta }_Q(z)=q{\beta }_B(sz)$ on its required eligible domain. The lower-structure maps $s,t$ preserve eligibility. For eligible $x\in B$,so $q$ preserves the top operation. If $h:B\to D$ coequalizes $f,g$, its lower factor $\overline{h}:Q\to U_{r}D$ satisfiesThus it is a morphism of the full structures. Uniqueness of the lifted operation follows from the eligible section $s$ and surjectivity of $q$. This creates the specified coequalizer, so the Beck monadicity theorem proves each one-step adjunction is monadic.

Finally, every free top operation just constructed has no fixed points: for $r=1$ it shifts the free chain, while for $r\ge 2$ it sends old eligible points to new distinct points and is undefined on the new points. Freely adjoining any further operation therefore changes nothing, since its required domain is empty. For $n>m$, the monad induced on ${\mathcal{C}}_m$ by the long free-and-forgetful adjunction is consequently the same monad, including unit and multiplication, as that for ${\mathcal{C}}_{m+1}\to {\mathcal{C}}_m$.

The first comparison category is thus equivalent to ${\mathcal{C}}_{m+1}$. Its algebra action evaluates the new formal value by ${\alpha }_{m+1}$, so the comparison from ${\mathcal{C}}_n$ retains precisely that next operation and is the remaining forgetful functor. Iteration recovers one additional operation at each step. These remaining comparisons are not equivalences while an operation is still forgotten: take a two-element set with all retained operations equal to the identity, and choose the next operation to be the identity in one extension and the transposition in another. Higher operations can be identities in the first case and undefined in the second. The identity on the retained structure is not a morphism between these extensions, so the forgetful functor is not full. This includes ${\mathcal{C}}_1\to \mathbf{Set}$.

The monadic tower for nested partial unary operations therefore has exactly the claimed length:

A filtered category is nonempty, every pair of objects maps to a common object, and every parallel pair becomes equal after postcomposition. Equivalently every finite diagram in a category has a cocone.

For a filtered set diagram $D:I\to \mathbf{Set}$, the finite-stage equality in a filtered set colimit says that representatives $x\in D(i)$ and $y\in D(j)$ define the same element exactly when their images agree at some common stage. Indeed, equality in the ordinary disjoint-union-and-quotient construction is witnessed by a finite zigzag; filteredness moves its objects to a common stage and equalizes the finitely many competing arrows.

For a finite categorical product, choose a common stage for all coordinate representatives to obtain surjectivity of the colimit-to-product comparison. Finitely many coordinate equalities can then be realized together at one later stage, proving injectivity. The empty product is preserved because a nonempty filtered category is connected. For an equalizer, an element whose two images agree in the colimit reaches a stage where they agree, so it is represented by an element of the stagewise equalizer; the same equality criterion proves injectivity. Finite products and equalizers construct every finite limit. Hence filtered colimits commute with finite limits in sets.

We prove the equivalence by the cycle solution, solution, solution, solution, then back to solution.

Assume $F$ preserves finite limits. Given any finite diagram in the comma category $(A\downarrow F)$, first take its underlying limit $c$ in $\mathcal{C}$. Its structure maps $A\to F{c}_j$ form a cone, and preservation gives a unique map $A\to Fc$. This object and the underlying projections satisfy the limiting universal property in the comma category. The construction also includes the empty diagram, since $F$ sends a terminal object to a singleton. Thus $(A\downarrow F)$ has finite limits for every set $A$, proving (ii).

Take $A=1$. The category of elements $\int F=(1\downarrow F)$ has finite limits. Reversing its limiting cones gives cocones over every finite diagram in $(\int F{)}^{\mathrm{op}}$; a terminal object before reversal ensures nonemptiness. Its opposite category is therefore a filtered category, proving (iii).

Use the covariant density presentation. An object of $\int F$ is $(c,x)$ with $x\in Fc$; an arrow $(c,x)\to (d,y)$ is $u:c\to d$ with $F(u)x=y$. For each such object the Yoneda lemma gives a natural transformation $\mathcal{C}(c,-)\to F$. An arrow $u$ induces $\mathcal{C}(d,-)\to \mathcal{C}(c,-)$ by precomposition, so these transformations form a cocone indexed by $(\int F{)}^{\mathrm{op}}$.

At $a$, send a representative $(c,x,v:c\to a)$ to $F(v)x$. Every $z\in Fa$ comes from $(a,z,1_a)$. If two representatives have the same value $z$, their arrows to $(a,z)$ in $\int F$ identify both with that same representative in the opposite-indexed colimit. Thus the map is bijective and natural, provingThe index is small because $\mathcal{C}$ is small and every $Fc$ is a set. By (iii) it is a filtered category. This proves (iv).

Every covariant representable functor $\mathcal{C}(c,-)$ preserves categorical limits, since a morphism out of $c$ into a limit is precisely a compatible cone. A filtered colimit of these functors is computed pointwise, and filtered colimits commute with finite limits in sets. Interchanging the finite limit and filtered colimit therefore proves that $F$ preserves finite limits, which is (i). This completes the cycle. It is also the flat functor and finite-limit preservation criterion for a finitely complete small category.

Work in ordinary set theory with the axiom of choice. A regular category has finite limits, image factorizations as regular epimorphisms followed by monomorphisms, and pullback-stable regular epimorphisms. A regular functor preserves finite limits and regular epimorphisms.

A capital regular category is one whose well-supported objects are well-pointed objects in a category. Here well-supported means $A\to 1$ is a regular epimorphism; well-pointed means a subobject of $A$ containing every point $1\to A$ must be the whole object. This is the convention of Definition 1.3. It permits objects of proper support with no points. Replacing this condition by global points detecting every isomorphism would change the assertion: a three-element chain is regular but cannot admit a conservative finite-limit-preserving functor to such a category.

Here is a regular-logic proof sketch of capitalization of a small regular category. Use a sort for every object of $\mathcal{C}$, a function symbol for every morphism, and regular theory axioms for composition, finite limiting diagrams and regular-epimorphism lifting. Its set models are precisely regular functors $\mathcal{C}\to \mathbf{Set}$. Empty sorts must be allowed.

The key separation lemma is the regular-logic separation of a proper subobject. For $m:S\hookrightarrow A$ proper, the sequentis not derivable: interpreting a derivation in $\mathcal{C}$ would make the monomorphism $m$ a regular epimorphism, hence an isomorphism. The chase completeness for regular logic supplies a set model in which it fails. Briefly, start with a named antecedent element, adjoin witnesses for the existential axioms, and quotient by required equalities. Every consequent about the original parameter arising at a finite stage has a finite proof; thus a nonderivable consequent remains false. The filtered union is the desired model. This witness construction, rather than an assumption that every sort is inhabited, is what keeps proper supports distinguishable.

Since $\mathcal{C}$ is small, choose a set-indexed family $(M_i{)}_{i\in I}$ of regular functors, one detecting each proper monomorphism, and formIt is regular by coordinatewise finite limits and surjections. It reflects invertibility of monomorphisms. If $P(f)$ is invertible, apply this fact to the image inclusion of $f$ and to the diagonal of its kernel pair. They are invertible, so $f$ is both a regular epimorphism and a monomorphism, hence invertible. Thus $P$ is a conservative functor.

The target is a power of sets as a capital regular category. A well-supported family has every coordinate nonempty, and choice extends any coordinate element to a global tuple. A subobject containing every tuple must consequently contain every coordinate element. Therefore it is capital, giving the required isomorphism-reflecting regular functor. This is the separation aspect of the regular representation results originating in Barr's embedding work; full faithfulness is unnecessary here.

The stronger target of a single set category has a precise restriction: $\mathcal{C}$ admits a conservative regular functor to the Category of sets exactly when it is an almost totally supported regular category. This means every object is well-supported or a strict initial object. Here are necessity and sufficiency.

Suppose $V:\mathcal{C}\to \mathbf{Set}$ is regular and conservative. If $VA$ is nonempty, its support in sets is $1$. Since $V$ preserves images, it sends the support inclusion $\sigma (A)\hookrightarrow 1$ to an isomorphism; conservativity makes $\sigma (A)=1$, so $A$ is well-supported.

If $VA$ is empty, every projection $A\times X\to A$ is sent to the unique bijection between empty sets, hence is invertible. This supplies a morphism $A\to X$ for every $X$. The equalizer of any two such morphisms is also sent to a bijection, hence is invertible, proving uniqueness. Thus $A$ is initial. Every arrow $Y\to A$ forces $VY$ to be empty and is then sent to a bijection; conservativity makes it invertible. So $A$ is strict initial.

Conversely suppose this support condition holds. Use $P$ above and takeProducts preserve finite limits and, by choice, coordinatewise surjections, so $V$ is regular. A well-supported object has all coordinates nonempty. A proper strict initial object has a subterminal image in every coordinate, with at least one empty coordinate: otherwise its arrow to $1$ would be sent by $P$ to an isomorphism, contradicting conservativity.

If $Vf$ is a bijection between well-supported objects, the conservativity of set products on totally supported families makes each $M_i(f)$ bijective: a missing coordinate preimage or a pair of equal-image coordinate elements extends to a tuple witnessing failure of surjectivity or injectivity. Hence $P(f)$ is invertible and so is $f$. An arrow between strict initial objects is already invertible; an arrow from a strict initial object to a well-supported object cannot become a bijection between empty and nonempty sets. An arrow into a strict initial object is invertible by definition. These cases prove conservativity and the conservative regular representation in sets criterion.