Category of all categories vs. Set of all sets

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).

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.

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.

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.

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.