Want to take part in these discussions? Sign in if you have an account, or apply for one below
Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.
Added some structure and references to Barr embedding theorem.
Amusingly, Makkai has published at least 4 proofs of Barr’s embedding theorem:
Full embeddings I, which uses ultraproducts of models of the internal logic of regular categories;
Full continuous embeddings of toposes, where he gives two different proofs, first as a corollary of an embedding theorem for coherent prime-generated toposes, and then as model-theoretic recasting of Barr’s proof (interestingly, he says that the key construction in Barr’s proof is analogous to Morley’s construction of prime models for totally transcendental theories);
Stone duality for first-order logic, where he obtains the result from Full embeddings I via the machinery of ultracategories.
Which of those is the nicest? :-)
I’m not sure I’ve ever pored over all the details carefully (it’s in Mac Lane and Moerdijk of course), but I’ve seen it mentioned that you need a classical metalogic to prove it. Which sort of goes under the “no free lunch” principle, I suppose.
I’m not sure about nicest, but the most straightforward (and by that I mean the only one I can currently understand) is Full embeddings I.
It’s looking like my master’s thesis is going to be about Makkai duality, though, so maybe after I understand ultramorphisms the latter two will become clearer :^)
Awodey and Forssell discuss Makkai duality as they propose their own form of duality for first-order logic. Presumably, you take there to be more mileage in Makkai’s approach.
I don’t know yet about Makkai’s approach having more mileage. The main application I have in mind is testing if a functor is actually evaluation-at-an-object-of-. Preservation of ultraproducts and ultramorphisms seems like a nice way to go about this. Maybe testing if such a functor is actually a formal sheaf (in Awodey and Forssell’s terminology) on the topological groupoid would be nicer. I should definitely find out!
Many thanks for these valuable comments.
The footnote currently at Barr embedding theorem doesn’t look right to me. I understand an “embedding” of categories to mean a fully faithful functor. “Faithful” doesn’t mean injective on morphisms but rather injective on each hom-set as a function . Nowadays (although maybe not always in the past), embedding usually means “full embedding”. And I understand the notion of embedding to be agnostic on the issue of injective-on-objects.
Thanks for raising this point.
The footnote currently at Barr embedding theorem doesn’t look right to me.
Would you please clarify whether you mean “not logically right” or “not right in its claim of this being the usual notion of embedding”.
To me the logical implication stated there seems obviously right. (It is a functor whose morphism-class-function is injective, then in particular the restriction to any hom-set is injective, hence it is faithful. And even more particularly, the restriction of the morphism-class-function of to the class of all identity-morphism is injective, if is, because of the bijective correspondence between objects and identity arrows, hence the injective-on-objects claim.)
Is there something eluding me, logically I mean?
I agree that the condition given is somewhat stronger than fully-faithful functor.
To me there seems not to be a logical mistake.
Would you please clarify whether you mean “not logically right” or “not right in its claim of this being the usual notion of embedding”.
The latter: that is simply not what an embedding of categories is, at least not in the language I am used to. Sorry for leaving that ambiguous.
Yes, I agree that your implication is correct, but I don’t think it’s the right notion.
Todd, Barr in his article “Embedding of categories” (pdf) uses at times the term “full embedding”. That seems to mean that for him an embedding is not generally a full functor.
Unfortunately the article seems to never define “embedding”.
Re # 10: thanks for clarifying.
As an exercise, I tried to remember why it was written like that. Oddly, I seem to recall that I consciously decided not to write that embedding is the same is faithful functor, and that I was taking the present version from a publication, but, oddly, I do not recall what a reason was.
I agree that this looks like something like misleading-emphasis. And the “In category theory […]” is a bit odd in a lab book on category theory. I think that was a result of over-conscientiously trying to wrap the definition into a context.
It would be good if you improve the footnote.
Re #8:
I understand an “embedding” of categories to mean a fully faithful functor.
This puzzles me. To me, the by far most usual definition “embedding” is “faithful functor”, without “full”. (Cf. e.g. Mac Lane, 2nd ed. p. 15, line 1). I know that some treatments of the Yoneda embedding can lead one to believe that “embedding” in particular implies “full”, but this seems not the default. Whence usages like “full embedding”. Would you please clarify?
I’m happy to be corrected, and I agree the term “full embedding” is frequently found in the literature – which does raise the question! But certainly I would think that the injective-on-morphisms is not what is commonly accepted these days.
I think it’s become more common in recent years to consider an embedding of categories as meaning full by default, but this deserves further discussion.
Mac Lane’s book in its first edition is a notable example of the more old-fashioned usage. The 2nd edition was written in the 1990’s, when Mac Lane was rather old (I saw him every week in those days) and there may have been somewhat less editorial oversight than for the first edition. (The book is still deservedly a classic.) The whole business of what we at the nLab have sometimes referred to as “evil” or the principle of equivalence was not prominent in his mind – I am reasonably sure of this, based on conversations I had with him.
By the way: embedding, while it has some good points, doesn’t really discuss the case of categories yet.
Let’s hear from a few others before making changes. The whole issue of what we mean by a “subcategory” is an interesting one; see for example this MO discussion.
Thanks for clarifying.
By the way: embedding, while it has some good points, doesn’t really discuss the case of categories yet.
Now that you say that: I recall that I visited that nLab page before writing the footnote, found nothing “authoritative” (as they say) in there, and had recourse to some source I do not recall. The “In category theory, …” was sort of a reflex and gives a misleading air of authoritativeness to the footnote.
Rummaging turned up what probably was my source: TheJoyOfCats has it literally this way: 3.27 says “ is called an embedding provided that is injective on morphisms.”
Aware that this seems at least wrong-in-spirit, I probably felt I had better comment on “faithful”, and fascinated by objects-are-identity-morphisms I was led to even mention objects.
Wow! Okay… that’s interesting. Thanks for digging that up!
I still think that’s a little weird, and still think further discussion is called for. I mean, up to set-theoretic implementations/hacks, we can arrange for (something isomorphic to) the forgetful functor to be an embedding in this sense. Does anyone find that a good use of language?
In short, this notion of embedding ignores principle of equivalence, and I think that’s an issue.
Yes, an “embedding” of categories should definitely refer to an equivalence-invariant notion, and I would personally define it to mean a fully faithful functor. Joy of Cats is generally not very good with terminology, IMHO.
I think we should continue searching the literature.
In view of Urs’s #11, I decided to look in Toposes, Theories, and Triples. What I found was interesting: Barr and Wells say an embedding is a faithful functor which takes non-isomorphic objects to non-isomorphic objects (page 89, or 102/302 of the pdf). They call it a “common convention”; where else is this attested?
And then there is good old Wikipedia, which lists four conventions.
They call it a “common convention”; where else is this attested?
It can’t be that common; I’ve never heard of it before. It seems bizarre to me (and not just because of the totally unnecessary contrapositive); wouldn’t it be much more natural to talk about a pseudomonic functor that is full on specific isomorphisms rather than merely about the property of being “isomorphic”?
I only see three conventions on wikipedia: full and faithful, full and faithful and injective on objects, and faithful and injective on objects. Requiring injectivity on objects would mean, in particular, that the “Yoneda embedding” is not necessarily an embedding, or at least that whether or not it is always an embedding depends on the set-theoretic details of how we define “category” — specifically, whether we require distinct hom-sets of a category to be disjoint. If it can happen that two distinct (but necessarily isomorphic) objects and have as sets for all , then the Yoneda embedding would not be injective on objects since it would take and to literally the same presheaf. (This equality of hom-sets is not as weird as it might sound; for instance, when regarding a preordered set as a category it’s natural to define every nonempty homset to be the same terminal set.)
Injectivity on objects is just not a sensible condition to require of non-strict categories, and “embedding” is a word that we want to apply to non-strict categories. And mere faithfulness doesn’t seem to me strong enough to merit being called an “embedding”. I could perhaps see an argument for pseudomonicness, but in general I think of an “embedding” as meaning “all relevant structure on the domain is induced by the codomain” and to me in the case of categories that structure includes “the hom-sets”.
In any case, whatever we decide, we should record the reasons and possible variations on the lab for the benefit of future readers.
Re # 19.
I think we should continue searching the literature.
Well, I’ve got a little list.
But please do not take this as the findings of a night-long literature-search, or anyting like that, I merely surveyed a few well-known sources, without method of search, for a set time of half an hour this morning (and stuck to that, breaking off the compilation when the time had come).
And, to say a needless-to-say thing, there is not the true definition of a word, and matters of truth are not decided by majority votes. And I am unsure about the point of doing this; but certainly understanding can come of discussing this (a bit), though not necessarily of a rigid survey of definitions in the literature.
So, here goes:
Prouté in his French lecture notes on categorical logic, seems not to give a definition of “plongement” as such, but somehow leads readers to believe that there is an absolute meaning of “plongement” when he says in a footnote “On justifiera le mot “plongement” un peu plus loin.” [We will justify the word “embedding” a little further below.] and then before Proposition 148, which says “Le foncteur de Yoneda est plein et fidèle.” he says “C’est la raison pour laquelle on l’appelle “plongement” “.
Schubert, Kategorien I, defines it to mean injectivity of the restrictions to the hom-sets, i.e., if I am not mistaken, Schubert has Mac Lane’s (embedding)(faithful functor).
Brandenburg, Kategorientheorie seems noncommittal; I did not find (not searching long) “Einbettung” being defined absolutely.
Shapira, herein takes a micro-local approach to this issue, mentioning the word “embedding” only once, packaged into “Yoneda embedding”.
Asperti and Longo, in “Categories, Types and Structures”, apparently define “embedding” only part-and-parcel with “full”: below 3.1.3 Proposition one reads: “A functor is a full embedding iff it is full and faithful, and it is also injective for objects.” Here, the injectivity-on-objects condition raises its head again. (And “injective for objects” is unusual.
Riehl, Category Theory in Context, SEction 1.5 writes “A faithful functor that is injective on objects is called an embedding and identifies the domain category as a subcategory of the codomain;” So this author for some reason was led to go beyond Mac Lane’s (embedding)(faithful functor) by a somewhat-doubly-**** formulation “injective on objects” (shudder). [I seem to recall that when the fateful footnote was written, I had had a look in Riehl’s book too, and found my doubts about mentioning objects dispelled by finding them mentioned there, too.] [And of course, to be hyper-correct, Riehl only tells readers that if a faithful functor is injective on objects, into the bargain, then it is called “embedding”. Logically, the author does not tell readers how to complete (embedding)=>?, but this is a near-universal abuse of language.] Riehl then goes on to write
[…] identifies the domain category as a subcategory of the codomain; in this case faithfulness implies that the functor is (globally) injective on arrows. A full and faithful functor, called fully faithful for short, that is injective-on-objects defines a full embedding of the domain category into the codomain category. The domain then defines a full subcategory of the codomain.
In particular, this author takes the global injective-on-morphisms-definition, that JoyOfCats takes to be the definition, to be a consequence of faithfulness.
I could go on and (try) to condense all of this, but (for the time being), won’t since the set time is up.
I only see three conventions
You’re right. The fourth was a repeat of the first. :-)
Isn’t this a strange and surprising situation? You’d a’ thunk that a basic-sounding notion like “embedding of categories” had been firmly settled by now. (Obviously, up until yesterday I thought it had been, as a fully faithful functor, although I had the sense that some of the older books had a different convention.)
I agree with Mike that the nLab, dictionary-like, should dutifully record the variations we see occurring.
I can’t remember seeing an “embedding theorem” where the embedding wasn’t full though. And this injective-on-objects business continues to be weird and surprising to me. Mike, would it be possible to ask Emily her reasoning?
Worth bringing up at the Categories list? Although I tune in very rarely myself.
Just to remind us of something many of us likely know: it might be seen as a (post-)modern approach to not try to “settle” this in the sense of finding—or even decreeing—an absolute definition the term “embedding”, but rather take the stance that it is alway only defined within a context, in particular, to take the stance that “embedding” on its own is simply undefined, and forever will be, and only exists …err…embedded? into a certain context.
But I personally like this “record”ing/documenting/commenting/situating-the-published-literature-idea that Todd is mentioning, at least because of the educational value of the process of doing so (within reason).
Just to add a bit more context:
in [Awodey. Category Theory, OUP, second edition, below 8.1], the injective-on-objects-condition raises its head again: “A functor is called an embedding if it is full, faithful, and injective on objects.”
The Elephant seems noncommital on the issue (though it uses the formulation “full embedding”, making it seem that it does not by default take “embedding” to imply fullness), at least it does not trumpet its views on this (neither in its introductory, convention-establishing pages, nor in its index).
Another lens to be viewing this through is stuff, structure, property. The fully-faithful version is mandated if categorical embeddings are considered as corresponding to, morally speaking (i.e., up to equivalence), a property or set of properties that carve out the subcategory.
Some of the notions might be justified by viewing as a 1-category only, ignoring the 2-categorical aspects. What do regular monomorphisms in the 1-category look like?
I find Steve’s definition understandable, especially when viewed in the context of teaching beginners. Embeddings which are non-injective on objects might be hard for beginners to swallow! And (assuming AC) any fully-faithful functor is isomorphic to an Awodey-embedding, so he’s “not far off”. :-)
And (assuming AC) any fully-faithful functor is isomorphic to an Awodey-embedding, so he’s “not far off”.
Naturally. But would he allow (beginners to use) AC?
I won’t have time for this. But you who care about it should please start adding all this material into embedding of categories.
To start with, I have removed that footnote at Barr embedding theorem and instead hyperlinked “embedding” right away.
Re #29: I expect so. It’s part of standard mathematics after all.
There may be some category theorists who are opposed to AC on “religious grounds”, so to speak, but I expect most aren’t. That said, I think category theorists tend to be highly attuned to when AC and excluded middle are involved, since an argument which doesn’t use these principles will be available in wider categorical contexts than otherwise. That is unquestionably the case for categorical logicians like Steve.
Thanks for the nudge, Urs. I was going to get to that anyway (and it’s good to collect our thoughts here as well).
I changed the wording in the idea section of embedding of categories, added a little to a definitions section, and added two references so far. Quite a bit remains.
And (assuming AC) any fully-faithful functor is isomorphic to an Awodey-embedding
No wait, what am I saying? That’s obviously nonsense.
I think every fully faithful functor is equivalent to one that’s injective on objects, without any need for choice. Let be fully faithful, and let be the “mapping cylinder” category, whose objects are the disjoint unions of those of and , with and embedded fully-faithfully (and of course injectively on objects), and and . Full-faithfulness of allow us to compose all arrows in making it a category. There is a projection that is the identity on and acts by on , and which is an inverse equivalence to the inclusion . Thus, is equivalent, in the 2-category whose objects are functors and whose morphisms are pseudo-commutative squares, to the inclusion functor , which is fully faithful and injective on objects.
Good. That should be added to the article at some point.
What are the regular or extremal monos in the 1-category Cat? Those seem like also a natural candidate for a 1-categorical notion of “embedding of categories”.
(I too asked about regular monos in in #27.)
Oh, I missed that, sorry.
I added #35 and some more possible definitions to embedding of categories, and tried to make it a bit more agnostic as to which definition is “correct”.
Great! Seems to be coming together, although there are still unanswered questions.
1 to 41 of 41