Usually the foundation of mathematics is thought of as having two pillars: mathematical logic and set theory. We briefly discussed mathematical logic and the foundation of mathematics in the story of Gödel, Brouwer, and Hilbert. The story of set theory is one of the most exciting in the history of mathematics, and its main hero was Georg Cantor, who discovered that there are many types of “infinity.”

Mathematical logic was always considered a very abstract part of mathematical activity, related to philosophy and quite separate from applications of mathematics. With the advent of computers, however, this perception completely changed. Logic was the first, and for many years, the main mathematical discipline used in the development of computers, and to this day large parts of computer science can be regarded as “applied logic.”

While mathematical logic and set theory indeed make up the language spanning all fields of mathematics, mathematicians rarely speak it. To borrow notions from computers, basic mathematical logic can be regarded as the “machine language” for mathematicians who usually use much higher languages and who do not worry about “compilation.” (Compilation is the process of translating a high programming language into machine language.)

The story of Category Theory is markedly different from that of mathematical logic and set theory. It was invented to abstractly explain a certain area of mathematics called “algebraic topology.” Specifically, the area of algebraic topology was based on a certain mathematical trick of associating algebraic objects to geometric objects, and category theory began by giving an abstract explanation to this trick and, along the way, to various other tricks from different areas of mathematics, which seemed unrelated. Category theory can be regarded as an abstraction of mathematicians’ practices, even more than of mathematical notions. Amazingly, this abstraction of a single mathematical area turned out to be a very useful language, and a practical way of thinking in many (but not all) mathematical areas.

It is not easy to give a popular explanation of what categories are, because the notion is based on a familiarity with modern mathematics. One experience we have when we study mathematics is that the same method, or even the same equation, may solve very different problems. This seems to express the “abstract” power of mathematics. Within mathematics itself, we are often interested in knowing when two mathematical structures are essentially the same. The technical word that expresses the equivalence of two mathematical structures is “isomorphism.” Category theory can be described as adding one more level of abstraction: trying to understand, in an abstract way, “isomorphism” and related notions.

Here are a few more details. Many mathematical areas can be described in terms of the “objects” studied in them, as well as in terms of certain notions of “maps” (functions) between the objects. (So in set theory the objects are “sets” and the maps are “functions,” and in group theory the objects are “groups” and the maps are called “homomorphisms.”) Categories are mathematical gadgets that put these common structures on common abstract ground. Every category has “objects” and “morphisms” with some abstract properties. An important notion is that of a “functor,” which is a way to relate one category to another. Categories indeed seem to play a pivotal role in the foundation of mathematics, or at least in some of its major areas, but they constitute a different sort of foundation. If we compare logic and set theory to the “machine language” of computers, we can regard category theory as an extremely useful universal programming tool.

Even if you did not follow the details about category theory, perhaps you got the correct impression that category theory is part of the mathematical trend to make things more and more abstract. Is this a good trend? Some opponents of category theory refer to it as “abstract nonsense.” But even they concede that it is sometimes extremely powerful. There is a healthy tension in mathematics between the ongoing efforts to understand things more abstractly and the efforts to understand more and more concrete issues and examples.

Samuel Eilenberg (left) and Saunders Mac Lane who introduced category theory.

The following is an ad-hoc discussion about category theory as a foundation for mathematics with Menachem Magidor (a set theorist and Hebrew University president) and Azriel Levy (a set theorist and Magidor’s thesis advisor), which takes place in the main corridor of the Mathematics Department, where Menachem is standing and smiling the smile of a person visiting his beloved hometown after a long absence.

Menachem Magidor

GK (surprised): Hi Menachem, what are you doing here?

MM (tries unsuccessfully to look offended): What do you mean? Am I not wanted here?

GK: No, no, no, no, I was just wondering if the state of the Hebrew University is so good that you can afford to visit us.

MM: No, on the contrary, the situation is hopeless… Seriously, I was just taking a book…

AL: (enters the corridor, surprised) Shalom Menachem, what are you doing here?

MM (once again tries unsuccessfully to look offended): What do you mean? Am I not wanted?

AL: No, no, I’m just surprised that you have the time…

GK: (interrupts) Guys, I have a quick question for both of you. Can category theory serve as the foundation of mathematics instead of set theory?

MM: Hmm, it is actually an interesting question, there is a result that a certain topos theory has the same power as a set theory with certain axioms … of course you need some separation and replacement axioms … do you remember, Azriel?

AL: The crucial point in my mind is that sets are very easy to explain. Can you explain topos theory to high school students?

Other people arrive and the discussion is interrupted.

Many related posts can be found on the “n-category café”, e.g. David Corfield’s “Foundations.” You can find topics related to category theory in many posts on the secret blogging seminar and the anappologetic mathematician. Update: In “God plays dice” the metaphore of logic as a machine language was discussed.

Todd Trimble wrote (on Todd’s and Vishal Blog) a series of posts ( I, II, III) on category theory, and additional posts (I,II, III) on category theory and axiomatic set theory. See also the remark below.

JohnIt seems to me it would be difficult if not impossible to avoid implicitly assuming set theory eventually when studying category theory. But I’m way out of my league to even comment on category theory. I’ve tried to learn a bit of it several times but never have gotten very far.

AdamNice post.

But why is the “situation hopeless”?

LinkVanahmm, interesting…

I wonder how this fits in with quantum phyics?

Todd TrimbleSounds like the beginning of a “fair and balanced” discussion.

Why not invite a categorical logician to the panel?

Gil KalaiPost authorDear Todd, any form of discussion is most welcomed as well as any imput from categorical logicians. The first half of the post is meant as a very popular desciption of category theory, which is an exciting topic that is not so easy (for me) to explain. In part because I do not “live it” (So remarks or links on how to explain cathegory theory to non-mathematicians are also very welcomed.) The last part of the post describes a little interuppted conversation that actually took place a few days after I read Corfield’s post. Both the statements, Adam, referring to the situation as being good beyond belief, or hopeless, were made jokingly.

Todd TrimbleGil — I’m not sure you knew, but actually I’m blogging on the very topic of categorical foundations. I hope to publish the next installment soon, but I’m having difficulty making the time to write these things.

The way I see it, Azriel Levy is right: it would be hopeless to explain topos theory to high school students; one shouldn’t even try except in the cases of prodigies. It’s a highly technical subject. But doing an honest job of teaching traditional

axiomatic(not naive) set theory like ZF to high school students would also present challenges. My belief is that either ZFC or a categories-based theory both do a good job of providing formal underpinnings to a more naive set theory, but what would truly be of interest to me is developing “naive categorical set theory” in a style and notation which people could pick up easily. I think it’s doable, but I don’t think it’s quite been done yet. Over time I’d like to try (and I’m just getting warmed up).I suspect one could even supplement that with a kind of “Feynman diagrams” approach to doing naive categorical set theory. The kind of string diagram calculus I have in mind was foreshadowed in the existential graphs of C.S. Peirce, and there is a good amount of discussion about this kind of thing over at the n-Category Cafe. Again this is a project I’d like to develop myself at greater length.

I’d like to make a few technical remarks.

(1) There are indeed inter-interpretability theorems which roughly say e.g. that a certain form of topos theory is equivalent in deductive power to bounded Zermelo set theory with choice, and one can “beef up” the topos theory with extra categorical conditions which express things like Replacement and full (not just bounded) Separation. Some of this is explained in the text on topos theory by Mac Lane and Moerdijk, and some is spread over more technical literature.

(2) Regarding axiomatic frameworks, there is a real question about which is easier to learn: a traditional set theory like ZF or a formal categorical theory like what I have been blogging about, ETCS. The question is actually a little bit tricky. The formal logical backdrop behind ZFC is full first-order logic (which everyone feels they understand at least intuitively and subconsciously) — if we assume that background, we can jump right in and start doing ZF. Whereas ETCS actually takes longer to get off the ground, because all that logic gets developed

internallyby exploiting the inner structure of a topos; the “meta-logic” in which the axioms of ETCS are expressed is but a fragment of full first-order logic, a logic which one might call “logic of finite limits”. So ETCS starts with more parsimonious tools at the meta-logical level, but bit by bit one can show how to construct first-order logic “internally” along the way, as one concomitantly develops the set theory.Developing the internal logic of a topos is a fascinating process (to me, anyway), and one can gain a great deal of categorical insight into the structure of first-order logic as a result, as well as gain a great semantic expansion (thinking here of sheaf semantics, for example) in the way one can interpret set theory. But:

it takes work, of a nature which seems to put off many traditional set theorists, recalling for example the extremely acrimonious debates and ad hominem attacks that took place on the FOM list in the late nineties. This creates a big block against understanding what categorical foundations is about, and why it isn’t just a “slavish translation” of traditional set theory in an awkward abstract nonsense format.In summary, rigorous categorical foundations is not kid’s stuff; it’s “foundations for grown-ups only”. Only time will tell whether it gains greater acceptance among mathematicians who are serious users of foundational materials, but already I think it’s fair to say that computer scientists who work with such materials generally take the categories-based approach pretty seriously, as it is explicitly

type-theoreticin nature.[By the way, I like the “machine language” metaphor a lot and think in such terms myself. I was surprised that I couldn’t locate my use of that metaphor on the blog I co-author!]

Gil KalaiPost authorThanks, Todd. The way I see it as an observer (and this is expressed by the programming language metaphors,) is that category theory is a different type of foundation than set theory and logic. (So category theory being “foundational” to much of mathematics does not depend on developing set theory using category language.)

Since the frontiers of set theory and of logic are now much further away from basic ZF axioms or the definition of first-order theories, the relevance of different axiomatic approaches to cutting-edge set theory or model theory is not clear. But even if the project you describe is “just” fascinating on its own right and can lead to categorical insights, this is a well deserved endeavor.

Todd TrimbleYes, I agree that category should be considered foundational in that conceptual sense as well. But it sounded to me that Magidor and Levy were interpreting your question as referring to topos theory as a way of redoing “set theory” in categorical language [which by the way takes us far beyond ZF in semantic scope], as I think most set theorists would who have any acquaintance with the underlying “controversy”. It’s too bad that your discussion got cut off; it would have been interesting to explore at greater length.

If I seemed to bristle a bit, it’s because I’ve heard more than my fill of extremely hostile skeptics who sometimes reveal they don’t know quite what they are talking about [not saying that about the distinguished set theorists Magidor and Levy, obviously]. The

generalattitudes toward categorists or categorical research in my own country, the US, are also pretty bad: funding for this activity is virtually non-existent, and it is very, very hard for a young categorist as such to eke out a living. Most will give up. Perhaps attitudes in Europe and in your own country are somewhat more enlightened.Having heard your two responses, you seem to have an open mind, but part of the problem in general is this “impression that category theory is part of the mathematical trend to make things more and more abstract”. I’m sure it seemed that way in the beginning [and mathematics in general in the forties, fifties, and sixties was also largely following that trend], but as I see it, much of cutting-edge research these days is less and less toward very general abstract nonsense as such, and more toward categorical structures — applied category theory, if you will. So I think the impression needs some adjustment.

Gil KalaiPost authorDear Todd, one question is this: Both set theory and mathematical logic are very developed areas by now so it is not clear if replacing one building block in their “basement” with another one will make a difference regarding cutting-edge issues in these areas (or in category theory.) For example, one can speculate that using cutting-edge model theory in areas where “category” thinking is powerful can lead to a more fruitful “fusion”. (But it is impossible to tell in advance…)