Are category-theory and set-theory on the equal foundational footing?

Question

Set-theory is widely taken to be foundational to the rest of mathematics. So is category-theory. My question is: Are they two alternative, rival candidates for the role of a foundational theory of mathematics or is there a sense in which one is more fundamental than the other? 'Fundamentality' can be cached out in terms of expressive power. So another variant on the same question: Do category and set theories share the same expressive power? If not, which one is more expressive?

Answer 1

I think questions like these are often asked by people who don't have a clear/coherent idea of what foundations are and what purpose they serve. This isn't meant as some kind of insult. I think many, probably the majority, of mathematicians are in this situation¹. Specifically, I believe that if you asked most mathematicians which "foundations" they use, they'd say "set theory". If you asked which set theory, they'd say ZFC. If you then asked, what are the axioms of ZFC, they'd have trouble listing them out by name, let alone explicitly giving the axioms. As the coup de grâce, if you ask them why they chose ZFC over, say, Tarski-Grothendieck set theory (TG), or more generally set theory versus category theory or type theory, it will become clear that they didn't make that choice (e.g. because they are not even aware what the alternatives are). They didn't make any choice. In fact, I think most will outright say that they were told that set theory and specifically ZFC can serve as a foundation of mathematics, and they just take it for granted that everything they do can be formulated in ZFC and don't otherwise concern themselves with the issue.

The reason they can do this is that most theorems don't significantly depend on the choice of foundations. Or to put it another way, most theorems of interest to mathematicians can be proven even in fairly weak foundations. You can see this in the exercise of Reverse Mathematics which tries to work out what axioms are actually used by typical theorems.

Turning to your question more specifically. There are a lot of issues, some of which are alluded to in the previous paragraphs. First, which set theory do you mean? There are several named systems as well as many, many more you could create. Similarly, for category theory, though here there aren't too many named systems. Most categorists (let alone mathematicians in general) are perfectly happy to say that category theory is grounded in some set theory, e.g. Mac Lane in "Categories for the Working Mathematician" and Grothendieck. For their purposes, like most other mathematicians, it's just not important what the foundations actually are. Roughly speaking, they are just going to assume the categories they need exist, and they'll take any foundations that establish them. That said, choice of foundations actually matters here. The category of (ZFC) sets does not exist in ZFC. Typically, to formulate category theory as used into something like ZFC requires axiomatically adding inaccessible cardinals or even Grothendieck universes. On the other hand, the way category theory is typically used already assumes set theory. If you want a foundational system on par with set theory, you can use the Elementary Theory of the Category of Sets (ETCS). ETCS is equivalent to Bounded Zermelo set theory (BZ) which is weaker than ZFC. Really, most people when they talk about category theory serving as a "foundation" for mathematics, usually say things like "practical foundations" and they mean something like category theory can serve as a framework for organizing mathematics. Set theory is just a rung in this framework, not a competing system from this perspective. Often "categorical foundations" really means "topos theoretic foundations" or closely related concepts, e.g. via the free topos. Pushed further, you may get some "competition" between set theory and, really, type theory which is its own approach to foundations, but is intimately related to category theory. There are aspects about typical set theoretic reasoning that are a bit anathema to type theory and category theory.

The next issue is you talk about "expressive power" but you don't really define it. This isn't necessarily as straightforward as you might think. For example, type theory and set theory are different sorts of things. Type theory is more like an extension of logic, while set theory is usually presented as a first-order theory within classical first-order logic. This is less of an issue for category theory, where e.g. ETCS is also a first-order theory of classical first-order logic. Nevertheless, let's continue on the assumption of some workable notion of "expressive power". Your question gives the impression that you believe that "expressive power" gives a total ordering on theories. It can easily be that neither is "more expressive", i.e. that two theories are incomparable. Most pertinently from a philosophical perspective, the entire approach suggested is a backwards. From a philosophical perspective, you decide what "mathematical objects" or "mathematics" is, and then you find/make a foundations that reifies that understanding. Less "expressive" foundations are then overly conservative, while more "expressive" foundations are making unjustified assumptions (and incomparable foundations are grounds for a holy war). For example, consider constructivists. They have a take on what "doing math" means which leads them to reject the law of excluded middle. Classical logics that accept the law of excluded middle are therefore trivially more "expressive", in that you can prove more theorems, but this is a defect from a constructivist's perspective. Some constructivists go further and assume anti-classical axioms which leads to incomparable foundations. Personally, I think mathematicians are missing a lot of mathematical value by constantly working in overly powerful foundations. At any rate, Gödel's Incompleteness theorem guarantees that there is always a "more expressive" foundations. A line needs to be drawn somewhere.

Finally, I wonder what you plan to do with an answer to your question. Let's say I said "set theory is more 'fundamental' than category theory". Now what? Are you not going to learn category theory then? That would be as absurd as deciding not to learn differential geometry because set theory is "more fundamental". My impression is that nowadays most mathematicians have a cosmopolitan attitude toward foundations (usually via apathy, but even when restricting to those who do care). There are many foundations, and it's interesting to see how they relate and how each views the mathematical landscape. Shifting between approaches can be quite useful. For example, consider Synthetic Differential Geometry (SDG). Much of its development was motivated by category theoretic (specifically topos theoretic) thinking. By using the tool of internal languages, we can make a constructive type theory in which we can do differential geometry in a way that looks a lot like "normal" math (we just need to be careful to use constructive reasoning) but where "magical" and extremely handy things exist. For example, there is a type, $D$, that's analogous to $\{x\in\mathbb{R}\mid x^2=0\}$ but, in this type theory, is distinct from $\{0\}$ (which is an anti-classical result). With $D$, a tangent vector in a manifold $M$ is just a function $D\to M$, thus the tangent bundle of $M$ is just the type of functions, $M^D$. This approach can dramatically simplify the proof of some results. Basically, things which are intuitions in classical differential geometry are theorems in SDG.² For example, elements of $D$ behave like "infinitesimals" to some degree, e.g. the derivative of $f$ is defined to be the unique function $f'$ such that $\forall d\in D.f(x+d)=f(x)+f'(x)d$. Of course, we'll want to connect this back to classical differential geometry which we can do with the notion of a well-adapted model. The end result is we can prove many (but not all) results of classical differential geometry by using category theory as a bridge to a constructive type theory where these results are much easier to prove, and, via a "meta-theorem", we are assured that there is a "classical" proof of the result, but we don't need to find it and it is likely much uglier. Doing things like this is a much more valuable use of "foundations" than trying to rank-order them in terms of "fundamentality".

¹ The ones that aren't are likely logicians, set theorists, or type theorists, or at least have gone a decent ways beyond an introduction to these fields.

² A similar thing happens with synthetic topology and Homotopy Type Theory.