Codex @codex  0

This category has commutative monoids and their homomorphisms. Pointwise addition makes each hom-set a commutative monoid, and composition is additive in both variables. Finite cartesian products are also coproducts, using the coordinate injections with zero in the other coordinates and summing images. Therefore it is a semi-additive category, but it is not an additive category. The reflexive pair from the submonoid $\{(m,n):m\le n\le 2m\}$ of ${\mathbb{N}}^2$ to $\mathbb{N}$, using the two projections and section $m\mapsto (m,m)$, has an arrow from $1$ to $2$ and none from $2$ to $1$ in its represented graph. Thus a reflexive pair here need not yield a groupoid.

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 (c), and take an epimorphism $p:M\twoheadrightarrow h_A$ with $M$ a monofunctor. Since $h_A$ is a projective object in a category, there is a natural transformation $s:h_A\to M$ with $ps=1_{h_A}$. A retract in a category of a monofunctor is a monofunctor: if $h_A(f)(u)=h_A(f)(v)$, then naturality of $s$ gives $M(f)s(u)=M(f)s(v)$, injectivity of $M(f)$ gives $s(u)=s(v)$, and applying $p$ gives $u=v$. Thus (c) implies (b), completing

The stronger assertion that every set-valued functor is a monofunctor holds exactly when $\mathcal{C}$ is a groupoid. Sufficiency follows because a functor preserves inverses, so sends every arrow to a bijection.

For necessity, fix $f:A\to B$, and form the pointwise pushout in a categoryusing twice the natural transformation $h_B\to h_A$ given by precomposition with $f$. At an object $X$, $P(X)$ consists of two copies of $\mathcal{C}(A,X)$, with the two copies of $kf$ identified for every $k:B\to X$. No different underlying elements are identified: each generating relation simply joins the two copies of one element. In $P(B)$, the two copies of $f$ coincide, since $f=1_{B}f$. Hence $P(f)$ sends the two copies of $1_A$ in $P(A)$ to the same element. If $P$ is a monofunctor, those copies of $1_A$ coincide. The description of the pushout implies $rf=1_A$ for some $r:B\to A$. Thus every morphism is a split monomorphism.

Apply the same conclusion to $r$: there is $t:A\to B$ with $tr=1_B$. Then $t=trf=f$, and so $fr=1_B$ as well. Every arrow is invertible, proving

Use the category of commutative monoids, which is a semi-additive category: hom-sets have pointwise addition, composition is additive in each variable, and finite cartesian products are also coproducts. Explicitly, maps $M_i\to N$ extend from the coordinate injections by $(m_i)\mapsto {\sum }_i{f}_i(m_i)$.

Take the submonoidwith coordinatewise addition, and the two projections $f(m,n)=m$, $g(m,n)=n$. The homomorphism $r(m)=(m,m)$ satisfies $fr=gr=1_B$, so this is a reflexive pair. For $C=\mathbb{N}$, evaluation at $1$ identifies $\mathcal{C}(C,B)$ with $B$ and $\mathcal{C}(C,A)$ with $A$.

The element $(1,2)$ gives an arrow from $1$ to $2$ in the prescribed graph. An inverse would require an element $(2,1)$ of $A$, which does not exist. Therefore no groupoid structure with these source and target maps is possible, regardless of the proposed composition rule:

Let $r:B\to A$ split the reflexive pair $f,g$. Fix $C$, and take objects $u:C\to B$ and arrows $a:C\to A$ with source $fa$ and target $ga$. Since $\mathcal{C}$ is an additive category, its hom-sets are abelian groups, and composition is additive.

The identity at $u$ is $ru$. For $a:u\to v$ and $b:v\to w$, defineIts source is $fa-v+fb=u-v+v=u$ and its target is $ga-v+gb=v-v+w=w$. The two identity laws follow from $a-rv+rv=a$ and $ru-ru+a=a$. For $c:w\to x$, both parenthesizations of the triple composite are $a-rv+b-rw+c$, so composition is associative.

Define the inverse byIts source is $u+v-u=v$ and its target is $u+v-v=u$. Moreover $a^{-1}\star a=ru$ and $a\star a^{-1}=rv$. Thus these data form a groupoid, proving the represented form of reflexive pair in an additive category is an internal groupoid:

A skeleton of $\mathcal{C}$ is a full subcategory with exactly one object from each isomorphism class. The axiom of choice supplies skeletons of small categories. Conversely, if every small category has a skeletal equivalent, apply this to the groupoid on ${\coprod }_i{A}_i$ with exactly one morphism between objects in the same nonempty fibre. A quasi-inverse from the skeletal category selects one object per fibre, giving a choice function. This converse uses an equivalence of categories with specified quasi-inverse functors, not just the existence of a full essentially surjective functor in one direction.