# Category of all categories vs. Set of all sets

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?

-
Perhaps this wikipedia page and references therein would help a bit? –  Marek Nov 11 '10 at 20:09

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

-
Awesome link! Thanks for that alone! +1 –  BBischof Nov 12 '10 at 18:41

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.

-
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). –  Arturo Magidin Jan 14 '11 at 16:59
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. –  arsmath Jan 14 '11 at 20:27

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 no need to be bothered about lurking contradictions. They may well, like Russell's 'paradox', simply be dialetheias.

The 'law' of non-contradiction is an unnecessary axiom in logic, leave it out and you have a perfectly good logic system - and contradictions do not, despite the mythology, lead to an 'explosion' that allows you to prove anything.

So there's no problem with a set that's the set of all sets. The idea that it's a problem is the result of a very long-standing flaw in logic, caused by Aristotle and only recently resolved by, inter alia, but particularly, Graham Priest. See dialethism.org

-
Funny, isn't it, how people find dialetheism difficult to understand and threatening. If you believe that the answer is wrong, why not say exactly what the flaw is to help everybody? It's a good exercise, actually, rather than a knee-jerk objection, try to think why it upsets you, and what, exactly, your objection is, and, if you can work that out, if there's any defence that's logical. –  Peter Brooks Oct 23 at 22:55
I appreciate your answer and did not downvote it. However, from some googling around it's not clear how legitimate dialethism is as a formal alternative logical foundation for mathematics. If a formal statement is both true and false, then (under normal formal logic rules) any statement can be proven true and false, so the whole system is useless. The wikipedia article says that dialethism rejects this "principle of explosion", but how? If you set up a system of rules that lead to a result you don't like, you can't just decide to "reject" the result... –  Nick Alger Oct 24 at 0:29
That's not correct - it is a common misunderstanding, the notion that 'explosion' happens. That is that if there is one proposition, such as 'This sentence is false' that is both true and false, then everything is. It's wrong to say that dialethism 'rejects' it. What happens is much simpler than that, once you remove the unnecessary axiom of non-contradiction, logic continues to work - the explosion only results from that axiom - and it's OK to have some statements which are both true and false. –  Peter Brooks Oct 25 at 13:38
Ok, so we have 3 categories - true, false, and both, and a statement $p$ that is both. How can we overcome the following argument (from the wiki page) that every other statement $q$ is in both? $p$ being true implies $(p \text{ or } q)$ is true. At the same time, $p$ being false and $(p \text{ or } q)$ being true implies that $q$ is true. Since $q$ is arbitrary, this means every statement is true. Of course, this includes all the negations of every statement, so every statement is both true and false. –  Nick Alger Oct 25 at 20:44
Have a look at dialetheism.org –  Peter Brooks Oct 26 at 4:27