Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

July 28, 2009

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 SetSet, 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:abf : a \to b is monic if for every object xx, the function hom(x,a) hom(x,b) g fg \array{ hom(x,a) &\to& hom(x,b) \\ g &\mapsto & f \circ g } is one-to-one.
  • A morphism f:abf : a \to b is epic if for every object xx, the function hom(b,x) hom(a,x) g gf \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 nn-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 CatCat, we get three concepts that are defined a bit like ‘monic’:

  • A morphism f:abf : a \to b is left faithful if for every object xx, the functor hom(x,a) hom(x,b) g fg \array{ hom(x,a) &\to& hom(x,b) \\ g &\mapsto & f \circ g } is faithful.
  • A morphism f:abf : a \to b is left full if for every object xx, the functor hom(x,a) hom(x,b) g fg \array{ hom(x,a) &\to& hom(x,b) \\ g &\mapsto & f \circ g } is full.
  • A morphism f:abf : a \to b is left essentially surjective if for every object xx, the functor hom(x,a) hom(x,b) g fg \array{ hom(x,a) &\to& hom(x,b) \\ g &\mapsto & f \circ g } is essentially surjective.

In CatCat these reduce to the right things… but only if you’re clever:

Theorem. A morphism in CatCat 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:abf : a \to b is right faithful if for every object xx, the functor hom(b,x) hom(a,x) g gf \array{ hom(b,x) &\to& hom(a,x) \\ g &\mapsto & g \circ f } is faithful.
  • A morphism f:abf : a \to b is right full if for every object xx, the functor hom(b,x) hom(a,x) g gf \array{ hom(b,x) &\to& hom(a,x) \\ g &\mapsto & g \circ f } is full.
  • A morphism f:abf : a \to b is right essentially surjective if for every object xx, the functor hom(b,x) hom(a,x) g gf \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 CatCat 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.

Posted at July 28, 2009 6:47 PM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2024

9 Comments & 0 Trackbacks

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.

Posted by: Mathieu Dupont on July 29, 2009 10:55 AM | Permalink | Reply to this

Re: Generalizing “One-to-One” and “Onto”

Yes, it is all already there. Also their characterization of lax epimorphism is nicer, even though their condition 3 is very similar to condition 4.1.2. in my note (the connected components in the slice correspond to the equivalence classes in the coend).

Well, let me at least add that 4.1.2 is interesting because it says precisely that the counit of the adjunction that is induced by F in the bicategory of distributors is an isomorphism.

Posted by: Jonas Frey on July 29, 2009 12:03 PM | Permalink | Reply to this

Re: Generalizing “One-to-One” and “Onto”

By the way, thank you for the references :-). I guess I should have known that I’m not the first to examine these questions. After all, if a question is left open at one place, that doesn’t mean that it’s not answered elswhere.

Concerning the symmetric version of ‘full’ that you mention, could you maybe give a page number? I had a look at your thesis, but it’s 270 pages. I’m sure other people would be interested too.

For the naming, I like your ‘faithful vs cofaithful’ instead of ‘left faithful vs right faithful’, but then how to express the fact that left faithful functors are precisely the faithul ones? On the other hand, I don’t understand the intuition for the term ‘lax epimorphism’ used by Adámek, El Bashir, Sobral and Velebil for fully cofaithful functors.

Posted by: Jonas Frey on July 29, 2009 2:29 PM | Permalink | Reply to this

Re: Generalizing “One-to-One” and “Onto”

(Sorry for the delay, I forgot to post my answer.)

The definition of ‘full’ is p. 157.

To distinguish the left faithful functors when there is a risk of ambiguity, I use ‘representably faithful’. But anyway these terms are not easily generalized to higher dimensions, so I think I prefer now ‘0-monomorphism’, ‘1-monorphism’, and so on.

‘Lax epimorphism’ comes from the fact that epimorphism means that uf = vf implies u = v for all u,v and that laxifying a one-dimensional notion consists in replacing all equations by morphisms not necessarily invertible (plus some coherence conditions). So a lax epimorphism should be something such that for each morphism from uf to vf there is one from u to v such that some conditions are satisfied.

Posted by: Mathieu Dupont on August 2, 2009 10:50 AM | Permalink | Reply to this

Re: Generalizing “One-to-One” and “Onto”

Thanks a lot for the posting!

I just want to correct an error (apparently due to copy and paste) in the statement of the second theorem. The correct form is

* Such a morphism is right faithful if it is essentially surjective.

* It is right faithful and right full if it is full and essentially surjective.

* It is right faithful, right full and right essentially surjective if and only if it is faithful, full and essentially surjective.

Also, the concepts are called 1-epic and 2-epic rather than 0-epic and 1-epic in “n-Categories and Cohomology”.

Posted by: Jonas Frey on July 29, 2009 11:32 AM | Permalink | Reply to this

Re: Generalizing “One-to-One” and “Onto”

Thanks for catching that cut-and-paste error. I could be confused, but it really looks like Mike Shulman raised questions about ‘0-epic’ and ‘1-epic’ functors on page 47 of our paper, not ‘1-epic’ and ‘2-epic’.

It’s too bad that your result has already been proved elsewhere, but it’s good to know the truth… so I’m glad Mathieu told us!

Posted by: John Baez on July 29, 2009 7:26 PM | Permalink | Reply to this

Re: Generalizing “One-to-One” and “Onto”

I could be confused, but it really looks like Mike Shulman raised questions about ‘0-epic’ and ‘1-epic’ functors on page 47 of our paper, not ‘1-epic’ and ‘2-epic’.

I see, I had an older version from 2006, and there the concepts were called 1-epic and 2-epic. But in the current version it’s indeed 0 and 1.

Posted by: Jonas Frey on July 30, 2009 1:22 AM | Permalink | Reply to this

Re: Generalizing “One-to-One” and “Onto”

how the pattern keeps on going when we climb up the ladder of nn-categories.

On the nnLab this is described in the entry kk-surjective functor.

For the globular-shape nn-categories that this is about, kk-surjectivity of an nn-functor f:CDf : C \to D means that each diagram

G[k] C f G[k] D \array{ \partial G[k] &\to& C \\ \downarrow && \downarrow^f \\ G[k] &\to& D }

has a lift

G[k] C f G[k] D. \array{ \partial G[k] &\to& C \\ \downarrow &\nearrow& \downarrow^f \\ G[k] &\to& D } \,.

Here G[k]G[k] denotes the globular kk-globe.

The functors that have this lifting property for all kk are the “surjective ω\omega-equivalences”, these are the acyclic fibrations in the folk model structure on ω\omega-categories.

And one recognizes the great similarity to the more familiar situation for geometric models for higher categories. A morphism f:CDf : C \to D of simplicial sets is an acyclic fibration if it all diagrams

Δ[k] C f Δ[k] D \array{ \partial \Delta[k] &\to& C \\ \downarrow && \downarrow^f \\ \Delta[k] &\to& D }

have a lift

Δ[k] C f Δ[k] D \array{ \partial \Delta[k] &\to& C \\ \downarrow &\nearrow& \downarrow^f \\ \Delta[k] &\to& D }

for all kk, where now Δ[k]\Delta[k] is the kk-simplex.

Posted by: Urs Schreiber on July 29, 2009 2:26 PM | Permalink | Reply to this

Re: Generalizing “One-to-One” and “Onto”

This story even explains why ‘onto’ can be defined in terms of ‘one-to-one’ as above.

But ‘one-to-one’ can also be defined in terms of ‘onto’; this is the approach taken at [[nlab:k-surjective functor]].

Posted by: Toby Bartels on July 29, 2009 7:14 PM | Permalink | Reply to this

Post a New Comment