Do Functors in Set-like Categories Preserve Injections and Surjections?

Question

I understand that the notions of injective/surjective do not make much sense in arbitrary categories. I am especially interested in the case where they make sense and are defined in the set-theoretic sense.

For simplicity let's just think this question through in $\mathcal{Set}$. I think I found an argument why the statement would hold there.

Assume we have two objects $A,B \in \mathcal{Set}$ and an injective function $i: A\to B$. Because $i$ is injective, there will be a surjective function $j: B\to A$, such that $j\circ i = 1$. If we now apply a functor $F:\mathcal{Set}\to\mathcal{Set}$ on the sequence $$A\to_i B \to_j A,$$ the sequence $$ F(A)\to_{F(i)} F(B) \to_{F(j)} F(A)$$ will yield the identity from $F(A) \to F(A)$ because functors preserve the identity. Then, $F(i)$ has a leftinverse and is injective. Thus, functors in $\mathcal{Set}$ preserve injectivity. We can argue analogously to obtain the statement: Functors in $\mathcal{Set}$ preserve surjectivity.

Are the above argument and the conclusion correct?

If they are correct, what other set-like categories exist in which this argument works?

Answer 1

As others have noted, what your argument shows is that split monomorphisms (those with left inverses) are preserved by all functors. In $\mathsf{Set}$, a function $A\to B$ is a split monomorphism if and only if it is an injective function and if $A$ is empty; then $B$ is empty. So your proof is not quite right, because it assumes every injective function is a split monomorphism - you've neglected to handle the case when $A$ is empty and $B$ is non-empty - and in fact, there are counterexamples to the claim.

Consider the functor $F\colon\mathsf{Set}\to\mathsf{Set}$ which adds a new element to every non-empty set and adds two new elements to the empty set:

$$F(A)=\begin{cases} A\cup \{*_A\}&\text{if }A\neq\varnothing\\ \{*_\varnothing, *_\varnothing'\}&\text{if }A=\varnothing\end{cases}$$

To define the action of $F$ on morphisms, let $f\colon A\to B$ be a function. If $A$ is non-empty, $F(f)$ sends $a\in A$ to $f(a)\in B$ and sends $*_A$ to $*_B$. If $A$ and $B$ are both empty, then $f$ is the identity function on $\varnothing$, and $F(f)$ is the identity function on $F(\varnothing)$. If $A$ is empty and $B$ is non-empty, then $F(f)$ sends both $*_\varnothing$ and $*_\varnothing'$ to $*_B$. Note that in this last case, $f$ is injective, but $F(f)$ is not injective.

Answer 2

Your argument mostly works (see the caveats below) and generalizes to split epimorphisms and split monomorphisms, which are morphisms with right and left inverses respectively. In fact, arbitrary functors preserve these kinds of morphisms and the objects in the category don't need to be particularly set-like.

Let $F \colon \mathcal C \to \mathcal D$ be a functor between any two categories. Suppose that $f \colon c \to c'$ is a split monomorphism in $\mathcal C$, meaning that there exists a morphism $g \colon c' \to c$ such that $g \circ f = \operatorname{id}_{c}$ . Then

$$ F(g) \circ F(f) = F(g \circ f) = F(\operatorname{id}_{c}) = \operatorname{id}_{F(c)} $$

so there exists a left inverse for $F(f)$ as well, so $F(f)$ is a split monomorphism too.

The same argument shows that if $g$ is a split epimorphism then $F(g)$ is also a split epimorphism.

---

The caveats mentioned above both relate to the question of when a injection has a left inverse and when a surjection has a right inverse.

Every surjection having a right inverse is equivalent to the axiom of choice. One way to see this is that the existence of a right inverse to $f$ is a choice of some element of $f^{-1}(y)$ for each y in the codomain of f. Given an arbitrary indexed collection of nonempty sets $\{A_i\}_i$, we can define a particular surjective function $f$ such that $f^{-1}(i) = A_i$, and so a right inverse to $f$ is a choice function.

Not every injection between sets has a left inverse. Assuming the law of excluded middle, the injections with a left inverse are precisely those whose domain is nonempty or whose codomain is empty. I'm not sure if there's a characterization of split monomorphisms in $\mathcal{Set}$ in a constructive framework.

To specify a left inverse of an injection $f$ with a nonempty domain, choose $g(y)$ to be the unique element of $f^{-1}(y)$ if it's nonempty, or an arbitrary element of the domain of $f$ if $f^{-1}(y)$ is empty.

On the other hand, if the codomain is empty, then the domain must be empty too (otherwise, what is $f(x)$?). And so $f$ is the identity on the empty set, which obviously is its own left inverse.

For the other direction of the proof, if the domain is empty and the codomain is nonempty, then no left inverse to $f$ can exist, since there are no functions from nonempty sets to the empty set.

---

The one part of your argument that doesn't generalize quite as well is the correspondence between injections and right invertible morphisms (and the dual). I'll add some details to the case mentioned in the comments: vector spaces.

Let $T \colon V \to W$ be a linear map. assuming enough choice for the necessary bases, the rank-nullity theorem says that $V \cong \ker T \oplus \operatorname{im} T$. If $T$ is surjective, then $\operatorname{im} T$ is all of $W$, so composing this isomorphism with the inclusion of $\operatorname{im} T$ into $\ker T \oplus \operatorname{im} T$ gives a suitable right inverse.

If $T$ is instead injective, the projection of $W$ onto the image of $T$ gives the necessary left inverse. Once again, this needs some choice (depending on the spaces and what other structure there is) to get the bases needed to define this projection.

I'm not aware of any other set-like categories (other than subcategories of the category of vector spaces) where every injection has a left inverse and every surjection has a right inverse. I can think of some possibilities (e.g. toposes where the axiom of choice holds, modulo the same restriction that holds in $\mathcal{Set}$), but I'm not sure how set-like such examples are and I'd rather not write out the details right now.