Here’s a significantly improved version of the opening chapters of Beginning Category Theory. In particular, Chapter 3 is shorter, better focused, and makes it clearer (I hope) while I’m fussing a bit about e.g. why functions aren’t sets!
Updated The two reported typos corrected (thanks!) and a sentence changed in the the final section.
8 thoughts on “Beginning Category Theory: Chs 1 to 3”
I had already commented on your “Gentle introduction” at April 24, 2019 (https://www.logicmatters.net/2019/04/22/category-theory-page-updated-2/#comment-4557430888798962013) and then again at August 21, 2019 and I had sent you two emails (Oct. 15, 2019 and Jan. 10, 2020), the first email with a proposal of how to clarify your proof of Theorem 58.
It just happened that shortly after my last email I had stopped working on Category Theory for doing more urgent things and have just recently decided to come back to this topic. So, I have checked your blog yesterday just to find out that you too have just decided to restart with this topic. What a coincidence. I reconsidered my proof of your Theorem 58 that I had sent you in Oct 2019 and I have to admit that I don’t understand any longer anything of it. It will take me weeks I guess (or longer) just to get back to the level of understanding I had already reached in 2019. I guess, you know what I am talking about.
Anyway, I still immediately understand my initial qualms about the delicate relation between set theory and category theory. And I seem to worry about the same things you do. So, let me repeat my layman views on the topic, hopefully somewhat more precise than in 2019 and useful for you:
To my view, CT is a parameterised theory, a theory template, just a specification of a full blown mathematical theory that becomes complete only with an instantiation of its parameters (whatever they might be for the moment). And rightly so, as a mathematical theory should always aim at the greatest possible generality. It would be a shortcoming of theory construction in my eyes not to separate CT proper, so to speak, from implementation details whenever possible. So, what are the free parameter(s)? I suspect, it is just the decision of how to implement collections of interest as consistent wholes, as objects in their own right, WHENEVER this is necessary during the development of CT. That is, I fully agree that we should use “plural talk” wherever possible, i.e. at all places where CT does not enforce us to consider the respective collections objects on their own right. For example, the definition of the concept “category”, taken for itself, does not force us to reify the collection of considered objects to an object in its own right since the definition just talks about objects and arrows but not about the collection itself. So we happily get away with plural talk in this case.
However, things change as soon as we try to form, e.g., categories that have (other) categories as their objects. Now, we cannot get away with plural talk, we have to implement categories as objects on their own right, somehow. Or, more precisely, we have to convince ourselves, that some consistent instantiation of this parameter is possible, i.e. an implementation of categories themselves as well-defined mathematical objects, not just their components. The only standard implementation we (at least me) have in mind is that as a kind of set. This narrow focus on a single type of implementation possibly obscures which properties of sets really matter when it comes to the question what it means to be an object. According to my layman understanding, all what is needed is a well-defined identity criterion, a criterion that unambiguously tells different objects apart. For sets this is their extension. Two sets are equal iff they have the same elements. However, it could be any consistent/well-defined criterion, even though I do not have any idea what else that could be.
To sum up: I think a proper development of CT should use plural talk whenever collections need not to be treated as objects in their own right (we agree on that). Whenever, to the contrary, collections (or other fancy structures) need to be referred to as objects in their own right, then we should come up with some implementation (e.g. as a kind of sets) that demonstrates the feasibility of an implementation at all. Having done that, we can step back again and do not commit to this or any other specific implementation but consider it again a free parameter.
In principle, I think, we do not need to require that object implementations are the same for all types of collections/structures we consider in CT. So, it is imaginable to me that we choose (for feasibility demonstration) one implementation for collections of, say, groups and another one for collections of categories. What we need is just a guarantee that for each object type that CT talks about in an intrinsic singular fashion it is possible to tell objects apart that we want to view as being different.
So, are there candidate implementations for the objects that CT deals with other than kinds of sets? I don’t know. However, what I remember is having read (and having understood only to a very limited degree) years ago F.A. Muller’s article “Sets, Classes and Categories” (http://philsci-archive.pitt.edu/1372/1/SetClassCat.PDF) about a set universe (a variant of Ackermann’s set theory that he baptised ARC) that is probably rich enough to implement every collection CT wants to deal with: This universe is inhabited by – besides the Cantorian sets – proper classes which are still well-defined mathematical objects with extension equality as their identity criterion (same as sets) but which might be ultimate in the sense that they cannot serve as elements within any (other) classes and might have other unwanted properties like being not well-founded and so on. However, a particular subtype of these classes, called good classes, behave well. In particular, the class of all sets V (and all its finite power set/class constructions, i.e P(V), P(P(V), …) are good. So, a possible implementation of, say, Set, the category of sets and functions could be an implementation as an (appropriate) quadruple (rather Morse than Kuratowski) with the good class V (i.e. the class of all sets), as first component representing the objects of the category, a certain subclass of the Cartesian product VxV representing the arrows as second component, another subclass of (VxV)x(VxV)x(VxV) representing the category’s composition operator as the third quadruple component and finally the category’s identity operator represented by an element of (VxV)xV as fourth component. Then, since n-tuples of good classes are good classes themselves, the category Set can be implemented this way as a good class and as such can serve as an element of other good classes (that might implement categories that have Set as one of their objects). However, the details are cumbersome, I had worked on spelling out Muller’s proposal some years ago to some extent, given that the Levy-Vaught theorem on which he based all his considerations is actually correct (the latter of which is definitely out of reach for my limited mathematical capabilities).
Thus, a viable way to develop CT might be to pick up Muller’s idea and guarantee case by case that all the collections (and possibly other structures) that need to be treated as objects in their own right can be implemented as good classes. A variant of this method I can imagine is the following: We demonstrate the feasibility to implement the relevant collections as good classes but use otherwise a simple off-the-shelf set theory to implement the usual convenience stuff, say tuples and the like. How that? Let’s treat the relevant collections as urelemente w.r.t the basic background set theory (once their implementation as good classes in ARC is demonstrated). This way, a category, say, could be implemented as an ordinary (Kuratowski-)4-tuple of 4 urelemente as components. This way, we would erect a kind of Chinese wall between the background set theory and our object theory, preventing nonsensical questions of the sort whether an object of a category (in the categorial sense) is also a (set-theoretic) element of the category’s quadruple implementation, which is nonsensical already on the basis that it might depend on the concrete implementation that was chosen.
Many thanks for this! I think it is very helpful, and very much chimes with how I have been thinking about things. I very much take the point that when we move up a level, so to speak, and talk about categories of categories, we need to have something to say about what it comes to when we have to treat categories as “objects in their own right”.
I’m sure that I haven’t yet worked out the best way of starting off the notes to touch on the relation between set theory and category theory. So take the (current, somewhat improved) version of Chap. 3 as a place-holder for something better!
* I think this version is an improvement, and the talk of ‘gadgets’ has been tamed. I think that if it’s to be a philosophical introduction to category theory, it should say that up front, though. If it just meant to be an introduction to category theory, then I think it’s giving too much emphasis to philosophical (even metaphysical) issues. An introduction to category theory needn’t go into such things at all. I don’t think the books by Simmons, Awodey, or Riehl do so. A paragraph or so should suffice.
* I’m still finding it hard to work out how we’re meant to understand “object”. Is a function not an individual, so that it’s not an object-as-individual (p 5)? If a function isn’t an object, is it still a thing or entity of some sort? Unlike virtual classes which aren’t even entities?
I’m happy to go along with a technical sense of “object” that isn’t quite the ordinary meaning, but I’d like to understand what that technical meaning is: and here I don’t.
* What is the intended understanding of “like permutations, i.e. bijections between numbers” on p 6? Seems like it’s saying a permutation is a bijection between numbers: a function that takes a number as its argument and returns a number as its result.
* “Our beef isn’t with the metaphysics of functions etc” (p 24) — It does seem to be. There at least seems to be *a* beef with the idea that functions or relations are sets, and the objection does seem to be metaphysical: that they aren’t really sets: that sets are at best mere surrogates that don’t match the “nature of” functions or relations.
Thanks for this.
The easy one: I think that’s a typo on p. 6: “i.e.” should be “e.g.” — with an intended link back to the example at p.5 line 7. But that I agree that is now not as clear as it could be. [It is of course entirely standard to treat permutations as bijections, so I guess it was the unintended restriction to bijections over some numbers that was the worry.]
On functions vs objects. Maybe there is a culture clash here, logicians steeped in Frege vs those more steeped in thinking about computer languages. Anyway, the Fregean footnotes were supposed to help: objects in the sense that constrast with functions are entities that lack arities (or if you must, have zero arity). And surely there should be nothing controversial about the thought that functions, of their nature, do have arities? But it could be best, looking again at some writings but type theorists, to avoid leaning on “object”!
I don’t want to fight about “philosophical”! But I’d say that it is as much a mathematical point that there are “foundational” enterprises, homotopy type theory, topos theory, deviant set theories, offered as in some sense rivals to standard set theory as providing universes in which we can regiment ordinary mathematics. And it is a mathematical question too what that exactly comes to. So that’s why there is a mathematical point in emphasizing that the apparatus of ordinary mathematics shouldn’t just be identified from the outset as set theoretic in nature.
This does give us a presentational quandary, as I put it, when starting out on category theory. It is quite common, at the outset, to just treat everything as going on in some yet-to-specified universe of sets (keeping fingers crossed behind our backs). But on the other hand, since we are sometimes told much later that category theory can provide a rival (non-set-theoretic) “foundation” for mathematics, it is worth at the outset saying just a little about why our story isn’t irredeemably wedded to thinking of everythign in set-theoretic terms.
The distinction between object and function in the text seems intuitively clear to me, especially with the added comments about Frege (but maybe I’m biased because the saturation/unsaturation distinction is central to how I think about these ideas). Still, I feel like even in an orthodox set-theoretic context if someone said something along the lines of “the interpretation function for this model takes objects from the domain and maps them to constant letters in the language” it would be clear how ‘objects’ in this case refers to different kinds of things than functions, even if functions are again orthodoxically taken to be sets of pairs.
I think it’s clear enough what the distinction is meant to be in §2.2. However, “object” is also used elsewhere in Beginning Category Theory. Is it used with the same meaning or a different one?
The objects in the domain could be functions.
* Re p 6, I messed up in the way I described the issue. What I’m wondering is how we’re meant to understand “bijections between numbers” so that a bijection between numbers can be a permutation. The usual idea of permutations as bijections seems to be that a permutation is a bijection between a set and itself. But you say a bijection between numbers. Is there some plural-speak involved, so that it means a bijection between (plurals / virtual sets of) numbers?
(At this point in BCT, you seem to be using plurals in a way that can be understood without explanation, though I think readers might wonder about some odd-as-English uses of “among”. (Plurals aren’t explained until Ch 3.) And that works for something like “permutations of the first n naturals” on p 5. I don’t think it quite works for “bijections between numbers”, if plurals are involved there.)
* Functions vs objects — What I wonder in cases like this is (1) does this have to be presented at all in an introduction to category theory, and (2) does it have to be presented here, before the reader has learned any category theory?
The use of “object” when talking about programming is based on “object” in ordinary English. It’s just the things / entities / data that can be referred to directly: that can be the value of a variable, passed as an argument to a function, returned as a result, and so on. (There’s sometimes more to it, as in object-oriented programming, but that’s the basic idea.)
It seems category theorists are happy to use “object” in a similarly general way when talking of “objects” and “arrows” (e.g. Awodey, p 4).
(Re arities, it seems to me that functions having arities doesn’t disqualify them from being objects, just as cats having teeth doesn’t disqualify them from being animals. (Not all animals have teeth.))
* There’s a difference between saying (1) that an embedding in set theory shouldn’t be assumed, and perhaps mentioning some issues such as ones of size, and (2) arguing that the set-theoretic approach is wrong, and not just for category theory (saying it’s contrary to the “nature of” functions, etc), even quoting a Fields Medallist to that end.
What you wrote in your reply above makes it seem BCT does (1), but what’s actually in the text is (2). Either way, it could be considerably shorter: a few paragraphs rather than page after page.
I only had the chance to read 3.1 and the first few paragraphs of 3.2 before having to stop, I plan on coming back to it all later, but I just wanted to note two small typos:
On page 18:
“apparent singular talk about set of Xs” perhaps should end “the set of Xs”
“virtual classes is old one” should definitely end “is an old one.”
In terms of content, everything I’ve read so far seems good!