43
$\begingroup$

In naieve set theory, you quickly run into existence trouble if you try to do meta-things things like take "the set of all sets". For example, does the set of all sets that don't contain themselves contain itself? (see, Russell)

On the other hand, people have no trouble casually talking about the "category of all categories", etc. How do we know there isn't a contradiction lurking somewhere here - especially since many books define categories in terms of sets?

$\endgroup$
  • 1
    $\begingroup$ Perhaps this wikipedia page and references therein would help a bit? $\endgroup$ – Marek Nov 11 '10 at 20:09
31
$\begingroup$

If you base your mathematics on Set Theory, then you run into the same foundational issues in Category Theory as you do in Set Theory (since Categories will have to be modeled "with" Set Theory in some sense).

You can go the other way, though: you can base your mathematics with Category Theory, and develop the Category of Sets through it, as Lawvere does here. Then your primitive notions, the bedrock of your theory, is not Set Theory but Categories. There are precise ways in which you can talk about "Category of all categories", analogous to the way in which you can talk about "the class of all sets" if you start with Set Theory instead.

How do we know there are no problems lurking in this viewpoint? Well, we don't, just like we don't know that there are no serious problems lurking in Set Theory (e.g., that it is not consistent).

$\endgroup$
  • 3
    $\begingroup$ Awesome link! Thanks for that alone! +1 $\endgroup$ – BBischof Nov 12 '10 at 18:41
31
$\begingroup$

In general there are two ways to make foundations of category theory precise. The first one is to make use of Grothendieck universes, which is just a way to limit the number of sets we are considering. So when we say the category of sets (groups, modules, ...) is implicit that we are restricting ourselves to some universe which is a set in the usual sense. This approach isn't all nice, since we cannot prove in ZFC that every set $S$ belongs to some universe $\mathcal{U}$, so we need to take it as an axiom. However people seems to prefer this one.

The second one is the Neumann–Bernays–Gödel set theory (NBG). It is an axiomatic set theory where class is the primitive concept. Then we say that a class $S$ is a set if there is a class $C$ such that $A \in C$. Thus a set is a particular kind of class and a class that is not a set is called proper class. Using this axiomatic, the collection of all sets is a proper class. So when we say the category of sets (rings, topological spaces, ...) we have a proper class of objects. However we cannot speak of the class of all classes and we introduce the name small category to refer to categories with a set of objects. Then we can speak of the category of all small categories and functors between them.

NBG does not mess the other things we already have in mathematics since it is a conservative extension of ZFC. Meaning that all theorems we already know in ZFC are still valid in NBG and if we prove a theorem in NBG using only the language of ZFC then it is a theorem in ZFC.

But you don't need to worry too much with these things. In my opinion they are very technical for a first course and in most cases they are not really important. Just treat your categories in the same naive way almost everyone treats sets and remember that things can be done precisely.

$\endgroup$
18
$\begingroup$

I'm not sure what Arturo has in mind with his link (which is an axiomatization of set theory, not of category theory), but it's well-known that there is the same issues with the category of all categories that there is with the set of all sets. It doesn't normally arise because the types of constructions that you would want to do don't lead to contradiction, but the same thing is true of set theory.

The existence of a contradiction seems to be folklore, but this message by Steve Simpson on the Foundation of Mathematics mailing list gives a contradiction in pretty careful detail. Carsten Butz replies saying that this type of example is well-known.

People seem to be increasingly careful about the issue, and emphasizing that they are taking about a "large" category of "small" categories, where "large" and "small" can be made precise in the two different ways that Nuno discusses.

$\endgroup$
  • 1
    $\begingroup$ What I had in mind is exactly what I said I had in mind: Lawvere axiomatizes set theory taking Category theory for granted; that is, he bases set theory on categories (rather than the approach in, say, Mac Lane, which bases Category Theory in set theory). $\endgroup$ – Arturo Magidin Jan 14 '11 at 16:59
  • 7
    $\begingroup$ Sorry, I don't see how that answers the original question. How does that help you avoid the Russell paradox? "Naive category theory" will have the paradox, just as naive set theory will. $\endgroup$ – arsmath Jan 14 '11 at 20:27
2
$\begingroup$

You can talk about "the category of all categories" with the proviso "in a given universe". "Our universe" is big enough to include the set of natural numbers and all the usual operations you do with sets (union, intersection...) See Mac Lane's "Categories for the working mathematician", first chapter, for the details.

$\endgroup$
0
$\begingroup$

There's a big distinction between sets and categories. Russell paradox makes sense in sets because of Separation Axiom. Nothing like this is needed in categories. Russell paradox just cannot be formulated, you cannot talk about "the category of such categories that...". So what would be the problem is categories are not based on set theory? None. Set theory is not based on set theory. I believe it's a pretty legit category.

More, nobody doubts that a category Set is a legitimate category, whatever the definition. It does contain "all sets". But it's not a set, so Separation Axiom is not a part of its description.

$\endgroup$
  • $\begingroup$ P.S. I wonder what caused all these negative reactions to my, I thought, simple explanation. $\endgroup$ – Vlad Patryshev Mar 2 '18 at 2:02
  • $\begingroup$ It seems to me that we use some analog of the Separation axiom quite often when we construct a category. For ex., when you say "category of groups", you mean the collection of all pairs of sets (G, *) such that... $\endgroup$ – Mihail Feb 4 at 23:47
  • $\begingroup$ @Mihail this is a very good point, but that's if you define a group as a set. More, if you define a group as a set with an operation, "such that". There's more than one approach. We can define a category of groups in a given, e.g., topos. $\endgroup$ – Vlad Patryshev Feb 6 at 0:04
  • $\begingroup$ Could you suggest a link where I can read about alternative definition of a category of groups? $\endgroup$ – Mihail Feb 6 at 0:29
  • $\begingroup$ See e.g. ncatlab.org/nlab/show/Grp and ncatlab.org/nlab/show/group and andrew.cmu.edu/course/80-413-713/notes/chap04.pdf and any example from model theory taking group theory as a theory and its models in a topos. $\endgroup$ – Vlad Patryshev Feb 10 at 1:10

Not the answer you're looking for? Browse other questions tagged or ask your own question.