Generalizing “One-to-One” and “Onto”
Posted by John Baez
In mathematics, “one-to-one” and “onto” are a pair of faithful workhorses. They don’t always get the attention they deserve – mainly because it seems hard to say anything new about them. But in fact, plenty of new issues arise as we start categorifying these concepts.
In a paper we wrote together, Mike Shulman and I said a lot about this stuff. On page 47, Mike left open some questions about “0-epic” and “1-epic” functors. Yesterday I talked with Jonas Frey at Université Paris 7. Jonas is a grad student of Paul-André Melliès; coming from a background in topos theory and logic, he’s now busy throwing higher categories and string diagrams into his arsenal of techniques. And, it turned out he has settled the questions Mike left open:
Let me say a bit more..
If we’re working in some category other than $Set$, the easiest analogues of ‘one-to-one’ and ‘onto’ are the concepts of ‘monic” and ‘epic’. Here’s one way to define these:
- A morphism $f : a \to b$ is monic if for every object $x$, the function $\array{ hom(x,a) &\to& hom(x,b) \\ g &\mapsto & f \circ g }$ is one-to-one.
- A morphism $f : a \to b$ is epic if for every object $x$, the function $\array{ hom(b,x) &\to& hom(a,x) \\ g &\mapsto & g \circ f }$ is one-to-one.
In the category of sets, ‘monic’ reduces to ‘one-to-one’, while ‘epic’ reduces to ‘onto’. But note that they’re both defined using the concept of ‘one-to-one’!
What happens if we categorify all this? When we go from functions to functors, the dynamic duo of concepts ‘one-to-one’ and ‘onto’ grows to a trio: ‘faithful’, ‘full’ and ‘essentially surjective’. Our paper explains why this happens and how the pattern keeps on going when we climb up the ladder of $n$-categories. This is a great story, first worked out by James Dolan and Toby Bartels. This story even explains why ‘onto’ can be defined in terms of ‘one-to-one’ as above. I won’t retell this story here.
What if we mimic the concepts of ‘monic’ and ‘epic’ at this categorified level? If we’re working in some 2-category other than $Cat$, we get three concepts that are defined a bit like ‘monic’:
- A morphism $f : a \to b$ is left faithful if for every object $x$, the functor $\array{ hom(x,a) &\to& hom(x,b) \\ g &\mapsto & f \circ g }$ is faithful.
- A morphism $f : a \to b$ is left full if for every object $x$, the functor $\array{ hom(x,a) &\to& hom(x,b) \\ g &\mapsto & f \circ g }$ is full.
- A morphism $f : a \to b$ is left essentially surjective if for every object $x$, the functor $\array{ hom(x,a) &\to& hom(x,b) \\ g &\mapsto & f \circ g }$ is essentially surjective.
In $Cat$ these reduce to the right things… but only if you’re clever:
Theorem. A morphism in $Cat$ is just a functor, and:
- Such a morphism is left faithful if and only if it is faithful.
- It is left faithful and left full if and only if it is faithful and full.
- It is left faithful, left full and left essentially surjective if and only if it is faithful, full and essentially surjective.
Note how we stack these concepts on top of each other. There’s a good conceptual reason for this — part of the great story I’m not telling (because Mike and I already told it). And we need to stack them to get a pretty theorem, since it’s not true that a functor is left full iff it is full. At least that’s what Jonas Frey told me — can you think of a counterexample?
Anyway, Mike also toyed with three other concepts, defined a bit like ‘epic’:
- A morphism $f : a \to b$ is right faithful if for every object $x$, the functor $\array{ hom(b,x) &\to& hom(a,x) \\ g &\mapsto & g \circ f }$ is faithful.
- A morphism $f : a \to b$ is right full if for every object $x$, the functor $\array{ hom(b,x) &\to& hom(a,x) \\ g &\mapsto & g \circ f }$ is full.
- A morphism $f : a \to b$ is right essentially surjective if for every object $x$, the functor $\array{ hom(b,x) &\to& hom(a,x) \\ g &\mapsto & g \circ f }$ is essentially surjective.
These behave in a more quirky manner. Mike showed:
Theorem. A morphism in $Cat$ is just a functor, and:
- Such a morphism is right faithful if it is essentially surjective.
- It is right faithful and right full if it is essentially surjective and full.
- It is right faithful, right full and right essentially surjective if and only if it is essentially surjective, full and faithful.
Note: now, two times out of three we’re saying ‘if’ instead of ‘if and only if’! What about the converses?
This is the question that Jonas Frey’s paper settles.
Re: Generalizing “One-to-One” and “Onto”
Right faithful and right fully faithful functors (which I call cofaithful and fully cofaithful) were already characterized in Cat in “On functors which are lax epimorphisms” by Adámek, El Bashir, Sobral and Velebil.
In Gpd, the situation is much better, since right faithful = (essentially) surjective and right fully faithful = full and (essentially) surjective. I mention this in my thesis [p.65], but the proof is not there. It is in an unfinished paper called “Factorisation systems for groupoids”, but perhaps this is also proved in a different way in the work-in-progress by Mike Shulman on the nLab (I’m not sure).
As for left full, it is in fact equivalent to fully faithful in Gpd (to prove that left full implies faithful, you apply the left fullness to functors with domain the one-object groupoid constructed from the group of integers). But I give in my thesis (and in this unfinished paper) a notion of full (it appears also in Mike’s personal part of the nLab) which, in the case of Gpd (but not of Cat) is such that left faithful + full = left fully faithful and right faithful + full = right fully faithful.