# What's a reasonable category that is not locally small?

Recall that a category C is small if the class of its morphisms is a set; otherwise, it is large. One of many examples of a large category is Set, for Russell's paradox reasons. A category C is locally small if the class of morphisms between any two of its objects is a set. Of course, a small category is necessarily locally small. The converse is not true, as Set is a counterexample.

Now, I can construct categories that are not locally small. However, what's the most common or most reasonable such category?

-
I might be totally off the mark here, but isn't it true that every concretizable category is locally small? (Since we can't injectively take bigger hom-classes to hom-sets...) So, since the categories that we're most used to dealing with are concretizable, this seems like a nontrivial upper bound to reasonableness. –  Harrison Brown Oct 29 '09 at 16:40
Good point. Wikipedia does mention some categories that aren't concretizable (notably hTop), but it seems that even the ones mentioned there are locally small. –  aorq Oct 29 '09 at 17:05

The category of multi-spans spans (thanks to everyone below for correcting my terminology). The objects are sets, and a map from A to B is a set X equipped with a map X --> A x B. The composition of X --> A x B and Y --> B x C is X x_B Y --> A x C.

I am stealing notation from algebraic geometry here: X x_B Y is the limit of the diagram X --> B <-- Y.

Admittedly, I've never wanted to allow X to be an arbitrary set. I usually want it to be something like a finite set, a finite simplicial complex or a scheme of finite type. But it is certainly natural to define the category without any restrictions.

-
I just call them "spans". Also, you need to take isomorphism classes of spans over A x B, or you won't get a 1-category. The result is still not locally small, though. –  Reid Barton Oct 29 '09 at 16:49
In case you're curious, I had thought that Spans was the category where Hom(A,B) is the set of subsets of A x B, and X \circ Y is the image of X x_B Y in A x C. (Using the above notations.) But I could be wrong. –  David Speyer Oct 29 '09 at 17:40
What is this category used for? –  Andrew Critch Oct 29 '09 at 17:44
David, that category is usually called Rel, since its morphisms are binary relations. Reid is right: in category theory, what you described are usually called spans. –  Tom Leinster Oct 29 '09 at 18:46
Lots of stuff! I'll give a couple of ex's. The Span construction makes sense on any category with pullbacks. When you take Span(FinSet) of finite sets, you get matrices of natural numbers, with pullback doing matrix multiplication. If you take Span(Set) and don't quotient, like Reid mentioned, you get a (weak) 2-category. The monads (1-endomorphisms with 2-morphisms mu, eta that do the monad thing...) in this category are actually categories. Good thing it isn't locally small! If you take the monads in Span(Mon), you can the categories internal to Mon, the strict monoidal ones. –  Aleks Kissinger Oct 29 '09 at 18:48

If C is a locally small category and W is a class of morphisms, we could try to form a category C[W-1] by "formally inverting" the morphisms in W. The resulting category has the same objects as C, and it's sort of clear what the morphisms should be: some kind of zigzags of morphisms, where the backwards morphisms are required to be in W, modulo some equivalence relation (so that the backwards morphisms actually are inverses to the morphisms of W).

The trouble is, there will generally be a proper class of zigzags between any two objects X and Y; for instance there might be a proper class of objects Z which each give at least one zigzag X → Z ← Y. After taking equivalence classes, it's very unclear whether the Hom classes of the resulting category C[W-1] are actually sets. In general, they certainly don't have to be.

Now there are very non-trivial techniques for proving that C[W-1] actually is a locally small category in many cases of interest, such as hTop (as mentioned in a comment). So this is just an illustration of what might have gone wrong.

-
oops, sorry, I posted my reply along the same line before having seen this one. –  Urs Schreiber Oct 29 '09 at 17:54

A one-object category consists of a class of arrows equipped with an associative unital binary operation --- namely, composition. It's a 'possibly-large monoid', if you like. And it's locally small iff this class is small (i.e. a set).

So, to produce a reasonable non-locally-small category, it's enough to produce a reasonable non-small monoid. The monoid of cardinals under addition is one. The monoid of cardinals under multiplication is another.

Cardinals are just isomorphism classes of sets, and we can produce similar examples by taking isomorphism classes in other categories. For instance, we could take the monoid of isomorphism classes of groups, with direct product as multiplication, or the monoid of isomorphism classes of vector spaces over Z/23Z, with direct sum as multiplication, etc etc.

-

The category Cat, whose objects are categories and whose morphisms between two categories consist of functors.

Whether this is "reasonable" is up to you to judge.

-
You're right, A. Rex, the category of locally small categories is not locally small. To see this, let C be a category that is locally small but not small, and let 1 be the terminal category (one object, one arrow). Then functors 1 --> C are simply objects of C, so the class of such functors is large. –  Tom Leinster Oct 29 '09 at 17:13
I would strongly contend that it's not reasonable. Locally small categories don't even form a class, they form a collection of classes. This collection doesn't even exist without passing to some higher universe. –  Eric Wofsey Oct 29 '09 at 17:17
The category Cat of categories and functors is certainly a category. The reason given that it is not -- "foundational reasons" -- is not a reason: Which foundations? You can use a Grothendieck universe, for example. Also, many category theorists reject the idea that the foundations have to start with sets. Topos theory is a suitable foundation, and there are toposes in which the set of all sets exists (the effective topos, for example). –  SixWingedSeraph Oct 29 '09 at 17:24
But if you're going to go to a higher Grothendieck universe, the notion of "locally small" becomes pretty meaningless. If the objects of your category don't even exist in your base universe, it's rather silly to ask whether the category is small in any sense. To see it another way, the morphisms in locally small categories don't even form classes--they're not just large, but larger than large. For example, if you take a large discrete category, its endofunctors are basically all functions from the universe to itself, which is strictly larger than the universe. –  Eric Wofsey Oct 29 '09 at 17:38
@SixWingedSeraph: Even in a topos there can be no set of all sets. Cantor's diagonal argument is valid in any topos. What's true in the effective topos is that there is a small full subcategory which is complete and cocomplete, i.e. has all small limits and colimits (not just those indexed by its own objects). –  Mike Shulman Dec 18 '09 at 17:02

The category of Grothendieck topoi and (equivalence classes of) geometric morphisms. For example, if $A$ is the classifying topos for abelian groups, the geometric morphisms from $Set$ to $A$ are in bijection with isomorphism classes of abelian groups, which is certainly not a set.

-