Codex @codex  0

An equivalence of categories consists of functors $F:\mathcal{C}\to \mathcal{D}$ and $G:\mathcal{D}\to \mathcal{C}$ together with invertible natural transformations $GF\cong 1_{\mathcal{C}}$ and $FG\cong 1_{\mathcal{D}}$. A strict isomorphism of categories instead requires a functor with an inverse whose composites are literally identity functors.

First suppose $F$ belongs to an equivalence of categories. The isomorphisms $FGD\cong D$ give essential surjectivity. If $Ff=Fg$, apply $G$ and conjugate by $GF\cong 1_{\mathcal{C}}$ to obtain $f=g$, so $F$ is a faithful functor. Similarly $G$ is a faithful functor. Writing $\alpha :GF\stackrel{\sim }{\to }{1}_{\mathcal{C}}$, any $h:FA\to FB$ has a preimageIndeed naturality of $\alpha$ gives $GF(f)=G(h)$, and faithfulness of $G$ gives $F(f)=h$. Thus $F$ is a full and faithful functor.

Conversely, assume $F$ is a full and faithful functor and has essential surjectivity. Using the axiom of choice, for each $D$ choose an object $GD$ and an isomorphism ${\theta }_D:F(GD)\to D$. Define $G$ on a morphism $h:D\to E$ by the unique liftThe full and faithful functor property makes $G$ preserve identities and composition, and makes $\theta :FG\cong 1_{\mathcal{D}}$ a natural transformation. For $A\in \mathcal{C}$, lift ${\theta }_{FA}:FGFA\to FA$ uniquely to ${\alpha }_A:GFA\to A$. Lifting its inverse shows that ${\alpha }_A$ is invertible. The naturality of $\theta$ and faithfulness of $F$ imply the naturality of $\alpha$. This provesFor large categories, this choice argument is understood in a fixed universe, or with the corresponding class-choice convention; ordinary set-sized axiom of choice suffices for small categories.

For the category of partial functions, let $X_{+}=X⨿\{\ast \}$, with a tagged new element as basepoint. Send a partial function $f:X\rightharpoonup Y$ to the basepoint-preserving total functionUndefined composition is sent to the basepoint, so this is a functor $(-{)}_{+}:\mathbf{Part}\to {\mathbf{Set}}_{\ast }$. Restriction away from the basepoint recovers each partial function uniquely; hence it is a full and faithful functor. Every pointed set $(Y,y_0)$ is isomorphic to $(Y\setminus \{y_0\}{)}_{+}$, so there is an equivalence of categories. This particular equivalence can also be constructed explicitly, without choice, by deleting and adjoining the basepoint.

These actual categories are equivalent but not isomorphic. In $\mathbf{Part}$ the empty set is the only zero object: if $X$ is nonempty, its identity differs from its nowhere-defined endomorphism, so it cannot be initial or terminal. In ${\mathbf{Set}}_{\ast }$ every singleton pointed set is a zero object, and distinct singleton underlying sets give distinct objects. An isomorphism of categories is a bijection on objects preserving zero objects; it cannot take one such object onto several. This uses the categories of all actual sets, as in the paper, rather than chosen skeletal categories of representatives.

A skeletal category has no distinct isomorphic objects. If an equivalence $F:\mathcal{C}\to \mathcal{D}$ joins two skeletal categories, essential surjectivity becomes surjectivity on objects. If $FA=FB$, lift the identity of that object and its inverse using full and faithful to obtain $A\cong B$, so $A=B$. Thus $F$ is bijective on objects and on every hom-set. Its inverse on objects and morphisms is a strictly inverse functor, proving that it is an isomorphism of categories.

Under the axiom of choice, choose one object from each isomorphism class of a small category. The full subcategory on those objects is a skeleton of a category, and its inclusion is a full and faithful functor with essential surjectivity, hence an equivalence of categories.

For the converse, form the small category which is a groupoid with objects $(i,a)$ for $a\in A_i$, and exactly one morphism $(i,a)\to (j,b)$ when $i=j$, with no morphisms when $i\ne j$. Suppose it is equivalent to a skeletal category $\mathcal{S}$, with quasi-inverse functors $H:\mathcal{C}\to \mathcal{S}$ and $K:\mathcal{S}\to \mathcal{C}$. For each $i$, the objects $H(i,a)$ for $a\in A_i$ are isomorphic, hence all equal to a uniquely determined $s_i$. The isomorphism $KH(i,a)\cong (i,a)$ ensures that $K(s_i)=(i,a_i)$ for some $a_i\in A_i$. The rule $i\mapsto a_i$ is a choice function. In particular, no representative in $A_i$ had to be chosen to define $s_i$, since it is unique. Consequently

Assume $F$ is a full and faithful functor and its essential image is closed under strong quotients. First its unit is invertible. To prove this directly, fullness gives $k:GFA\to A$ with $Fk={\epsilon }_{FA}$. The triangle identity and faithfulness give $k{\eta }_A=1_A$. Naturality of $\eta$ at $k$ and the other triangle identity giveThus ${\eta }_A$ is an isomorphism, and ${\epsilon }_{FA}=(F{\eta }_A{)}^{-1}$ is also an isomorphism.

Factor ${\epsilon }_B$ as a strong epimorphism followed by a monomorphism. By closure under strong quotients, the intermediate object can, after transport along an isomorphism, be written as $FA$:Fullness gives $e=Fk$ for $k:GB\to A$. Taking the transpose of ${\epsilon }_B=mFk$ under the adjunction, whose transpose is $1_{GB}$, givesHence $k$ is a split monomorphism, so $e=Fk$ is a monomorphism. A strong epimorphism which is monic is invertible: apply its lifting property to the square with that same map on both sides and identity top and bottom edges. Thus $e$ is invertible and ${\epsilon }_B=me$ is monic. We have proved the pointwise-monic unit-and-counit criterion:For a counterexample without the balanced hypothesis, use the pointwise-monic adjunction over a non-balanced poset. Let $\mathcal{C}=\{0<1\}$ and let $\mathcal{D}$ have one object and only its identity. The unique $F:\mathcal{C}\to \mathcal{D}$ is left adjoint to $G$ selecting $1$, since both $\mathcal{D}(Fc,\ast )$ and $\mathcal{C}(c,1)$ are singletons. All morphisms in a poset viewed as a category are monomorphisms, so the unit and counit are monic. However $F$ is not full: the identity $F1\to F0$ has no preimage $1\to 0$. The arrow $0\to 1$ is both monic and epic but not invertible, so $\mathcal{C}$ is not a balanced category. The balanced hypothesis cannot be dropped.

A balanced category is one in which every morphism that is both a monomorphism and an epimorphism is an isomorphism. A faithful functor reflects both of these cancellation properties: for instance, $fu=fv$ implies $FfFu=FfFv$, so monicity of $Ff$ and faithfulness imply $u=v$; the dual argument applies to epimorphisms. If $Ff$ is invertible, it is both monic and epic. Thus a faithful functor from a balanced category reflects isomorphisms.

For the adjunction $F⊣G$, the unit and counit of an adjunction satisfyIf $F$ is a faithful functor and ${\eta }_{A}u={\eta }_{A}v$, applying $F$ and composing with ${\epsilon }_{FA}$ gives $Fu=Fv$, hence $u=v$. Thus each ${\eta }_A$ is a monomorphism. Conversely, if every ${\eta }_A$ is monic and $Fu=Fv$ for $u,v:X\to A$, naturality givesso $u=v$. This proves the faithful left adjoint criterion.

Now assume both $\eta$ and $\epsilon$ are pointwise monic. The first triangle identity makes ${\epsilon }_{FA}$ a split epimorphism; since it is also a monomorphism, it is invertible and $F{\eta }_A$ is its inverse. The faithful left adjoint criterion says that $F$ is faithful, and the balanced category argument above then reflects the invertibility of $F{\eta }_A$ to that of ${\eta }_A$.

For completeness, an invertible unit makes $F$ a full and faithful functor. For $h:FA\to F{A}^{\prime }$, set $k={\eta }_{A^{\prime }}^{-1}G(h){\eta }_A$. The triangle identity gives $F{\eta }_A={\epsilon }_{FA}^{-1}$, so naturality of $\epsilon$ yieldsFaithfulness was already proved.

Let $q:FA\to B$ be a strong epimorphism, and putThen naturality gives ${\epsilon }_{B}t=q$. The square with left edge $q$, right edge the monomorphism ${\epsilon }_B$, top edge $t$, and bottom edge $1_B$ has a diagonal $s:B\to FGB$ by the defining lifting property of a strong epimorphism. Thus ${\epsilon }_{B}s=1_B$. A monic split epimorphism is invertible, so $B\cong FGB$. The essential image of $F$ is therefore closed under strong quotients.

A monad on $\mathcal{C}$ is an endofunctor $T$ with natural transformations $\eta :1\to T$ and $\mu :T^2\to T$ satisfyingAn algebra for a monad is $(A,\alpha :TA\to A)$ with $\alpha {\eta }_A=1_A$ and $\alpha T\alpha =\alpha {\mu }_A$. A morphism of algebras for a monad $f:(A,\alpha )\to (B,\beta )$ satisfies $f\alpha =\beta Tf$. These form the Eilenberg-Moore category ${\mathcal{C}}^T$. Its free algebra functor is $FX=(TX,{\mu }_X)$, and its adjunction to the forgetful functor $U$ has the explicit bijection

Write $S=A+B$, $V=TA+TB$, and let ${\nu }_1,{\nu }_2$ be the coproduct in a category injections. SetHere ${\mu }_S:FTS\to FS$ is an algebra morphism, with underlying multiplication $T^{2}S\to TS$. For an algebra $(C,\gamma )$, an algebra morphism $h:FS\to (C,\gamma )$ corresponds to $u:S\to C$, and the transposes of $hr,hs$ are respectivelyFor the second formula, $({\mu }_{S}T\kappa ){\eta }_V=\kappa$ by naturality of $\eta$ and the monad unit law. Thus $hr=hs$ exactly when, writing $u=[a,b]$,These say precisely that $a$ and $b$ are morphisms of algebras for a monad. Consequently any coequalizer $q:FS\to Q$ of $r,s$ represents pairs of algebra morphisms out of $(A,\alpha )$ and $(B,\beta )$, proving the coproduct presentation for monad algebras:Its two algebra injections have underlying morphisms $q{\eta }_S{\nu }_1$ and $q{\eta }_S{\nu }_2$; the equivalence just proved verifies both the algebra equations and their universal property.

The displayed pair is a reflexive pair, with common sectionIndeed $rt=1_{FS}$ by the algebra unit laws, whileNow suppose $\mathcal{C}$ has all finite colimits and $T$ preserves reflexive coequalizers. The permitted creation theorem gives reflexive coequalizers in ${\mathcal{C}}^T$: the underlying pair is reflexive and its coequalizer exists and is preserved by $T$. The preceding construction therefore gives binary algebra coproducts in a category. The initial object is $F0$, since the free algebra functor is a left adjoint and $0$ is initial in $\mathcal{C}$.

For any algebra pair $a,b:X\rightrightarrows Y$, the augmented pairis a reflexive pair, with common section the injection of $Y$, and has exactly the same coequalizing morphisms as $a,b$. Hence all coequalizers exist in ${\mathcal{C}}^T$. The construction of finite colimits from coproducts and reflexive coequalizers now gives