# Logical problems in category theory [duplicate]

Possible Duplicate:
Set theory for category theory beginners

It is frustrating to hear people speak of Yoneda embedding, category of all categories/functors, n-categories, infinity categories and all that jargon, without giving proper logical justifications.

I learned category theory from N. Jacobson, Basic Algebra - II. The justification given therein, that one uses the Godel-Bernays distinction of sets and classes, simply does not work for the above cases.

This is really frustrating. How do people deal with it? It seems many times it is skipped simply, giving the impression that it is too unimportant to be dealt with.

How did then the more foundational guys, for instance, Grothendieck deal with it? What are the "universes" one hears from time to time?

-

## marked as duplicate by Anton GeraschenkoJan 2 '10 at 22:53

This question seems closely related: mathoverflow.net/questions/6423/… –  Reid Barton Jan 2 '10 at 21:30
Yes it could be considered potentially offensive. I have edited. –  Anweshi Jan 2 '10 at 21:52
I'm closing it as a duplicate because it looks like the answers there address the underlying question, which seems to be "what are the set-theoretic underpinnings of category theory?" In general, I would keep two substantially different versions of the same question open, but this is just too imprecise. I feel like it's mostly a tirade without any backup. To quote Ilya's answer, "perhaps you could provide logical inconsistencies in Lurie's Higher Topos Theory?" As usual, if the question is edited into shape, or if enough people want it, I (or somebody else) will reopen it. –  Anton Geraschenko Jan 2 '10 at 22:52
Let me explain how I think this could be made into a good question. Make it specific. Rather than saying, "nobody ever gives logical justification for anything," say, "Here's a specific thing that Lurie does that doesn't look justified to me. I've read this and that about Grothendieck universes, which are supposed to resolve the problem, but it seems to me that isn't enough because of X." Even better, ask, "Is X (same X as before) true?" and give all that stuff as motivation and background for why you want to know if X is true. –  Anton Geraschenko Jan 2 '10 at 22:59
@Anweshi: please read at least the first eight sections of Mike Shulman's paper linked to from his answer to the other question, and if you have any specific questions after reading it, feel free to ask them! –  Reid Barton Jan 3 '10 at 2:05

Short answer: category theorists often elide the extra annotations when employing typical ambiguity or universe polymorphism. Proof theorists demand that these annotations be provided, and study how they behave.

If you want to be pedantic, then you have to annotate all instances of "category of sets" or "category of categories" with the additional word "small". Then the objects of the category of small sets do not form a small set, and the category of small categories is not a small category.

The next step is to replace "small" with an arbitrary natural number, where the objects of the "category of 0-small sets" form a 1-small set. Often, when fully annotated, it turns out that a proof will work for any value of "N" (where all the references to Set or Cat in the proof involve "offsets" from that N, such as "(N+3)-small sets"). Proofs which are parametric in this N (or some sequence N,M,... with inequality constraints between them) are called universe-polymorphic proofs, and are quite similar to a phenomenon in Principia Mathematica called typical ambiguity (although PM asserted a staggeringly powerful axiom about typical ambiguity without any sort of formal justification). You can re-apply these proofs at arbitrary levels in the transfinite hierarchy of universes, and they still hold.

That said, nobody has yet proven that a category of ALL categories (of every "smallness") cannot exist in the way that Russell proved that a set of all sets cannot exist. However, there is some evidence that you would have to omit certain axioms that might seem to be "obvious" at first glance.

-

I think you are just reading the wrong books. The most common solution to these problems is indeed Grothendieck universes. Really, these issues are not that big a deal, not because they are logically unimportant, but because there are well-understood ways of dealing with them, which generally are extremely effective, and so it's not worth saying more than "small", "large", "very large", etc.—to do so would be distracting. (You can probably find many such informal uses of language in other fields as well.)

-
I don't know if they're always effective. The collection of all semigroupoid homomorphisms themselves form a semigroupoid (under composition), and one cannot state this fact -- even using universes. It is disturbing to have a proposition be neither true nor false but simply arbitrarily excluded from consideration like that. –  Adam Jan 3 '10 at 7:40
I don't know what a semigroupiod is, but why should one be any more able to state that fact than "the collection of all sets is a set", and what's wrong with instead stating the equivalent of "the collection of all U-sets is a V-set, where U and V are Grothendieck universes with U in V"? –  Reid Barton Jan 3 '10 at 16:20
en.wikipedia.org/wiki/Semigroupoid Sets have vastly more structure than semigroupoids. For example, the category of sets is cartesian closed (a fact which is used in the proof of Russell's paradox) while the category of semigroupoids is not. –  Adam Jan 3 '10 at 20:31
We must be having some terminological misunderstanding, because that article implies that the collection of all semigroupoids doesn't form a semigroupoids, because a semigroupoid has a set of objects. –  Reid Barton Jan 4 '10 at 5:19

Every question asked can be divided into two parts: what is known, and what is asked.

I think your question's "what is known" part is by no means universally agreed. It's not frustrating to hear people talk about categories or $\infty$-categories anymore than hear people talk about sets.

Yes, when you talk about sets, sometimes you can make mistake if you consider "the set of all sets", but if you're using set theory only to teach algebraic topology, you chances of making such a mistake while proving any interesting theorem aren't big. What's the reason the same doesn't apply here?

If you're unconvinced, perhaps you could provide logical inconsistencies in Lurie's Higher Topos Theory? (This is what I read for $\infty$-categories)