Category theory

Notes on Category Theory v.4

I wasn’t able to do much work in January for family reasons, but levels of concentration and energy are returning. So, much later than I’d hoped, here at last is an updated version of the Notes on Category Theory (still very partial though now 109 pp.). There are three newly added chapters, and some minor tinkering earlier. We now cover:

  1. Categories defined
  2. Duality, kinds of arrows (epics, monics, isomorphisms …)
  3. Functors
  4. More about functors and categories (and the category of categories!)
  5. Natural transformations (with rather more than usual on the motivation)
  6. Equivalence of categories (again with a section on motivation, why we want ‘equivalence’ rather than full isomorphism)
  7. The Yoneda embedding (shown to indeed be an embedding by using an easy restricted version of the Yoneda Lemma)
  8. An aside on Cayley’s Theorem
  9. The Yoneda Lemma (how to get to the full-dress version by two conceptually easy steps from the restricted version).
  10. Representables (definitions, examples, universal elements, the category of elements).
  11. First examples of limits (terminal objects, products, equalizers and their duals)
  12. Limits and colimits defined (cones, limit cones: pullbacks and upshots)
  13. The existence of limits (in particular, having finite products and equalizers implies having all finite limits).

Coming soon: a further chapter on limits (on functors and the preservation of limits) and then a chapter on Galois connections as a nice gentle lead-in to the chapters on adjoints.

What is the category Set?

We all know that we quickly encounter issues of size when we start category theory. Categories, we are told, are collections of objects and morphisms satisfying certain axioms. But we very soon meet, among our very first examples of categories, categories like Set whose objects are too many for the collection of them to itself be a set. So what kind of ‘collection’ do we have here?

But here’s another issue about that initial example of the category Set which is ignored by many writers of introductory texts.

The issue can be posed, bluntly, like this: when the category Set is mentioned early on in an introductory text what category is that?

Typically no explanation is given at this stage. But of course which category we are dealing with depends on our set theory. For an NF-iste, the category of NFsets has very different properties from what is intended (for a start NFsets is not cartesian closed and later we learn that  Set is). But fair enough, in an intro book you aren’t going to mention that in the opening pages! Rather the authors are, surely, intending to point to stuff that their beginning readers can be assumed to know about, and are saying, “Hey, you in fact already know about some categories, for example …” The charitable reading, then, is that authors are relying on their readers to think of  Set as comprising the sets they already know and love.

But what sets are those?

Well, for many readers (if they have done any more than had a bit of set-notation waved at them) the sets they know and love are the  pure sets of the cumulative hierarchy — pure in that there are no urlements, no memberless entities in the universe of sets other than the empty set. If set theories with urelements are mentioned in passing in an intro set-theory course, it is usually only to be dismissed and forgotten about. So: in the absence of special explicit signals to the contrary, we might well reasonably take the category Set mentioned in the very early pages to be a category of pure sets of the usual hierarchy (or at least the hierarchy up to some inaccessible, or whatever). Just sometimes this is made explicit. Thus, Horst Schubert in his terse but very good and clear Categories (§3.1) writes “One has to be aware that the set theory used here has no “primitive (ur-) elements”; elements of sets, or classes …, are always themselves sets.”

But then what are we to make, a bit later in our introductory books, of e.g. the usual presentation of the Yoneda embedding as $latex \mathcal{Y}\colon \mathscr{C} \to [\mathscr{C}^{op}, \mathbf{Set}]$. Putting it this way, if you look at the details, assumes that hom-collections $latex \mathscr{C}(A, B)$ for $latex A, B \in \mathscr{C}$ actually live in $latex \mathbf{Set}$. And since such a hom-collection is a set of $latex \mathscr{C}$-morphisms, that assumes that the $latex \mathscr{C}$-morphisms — irrespective of what the [small] category $\mathscr{C}$ is — must live in the world of pure sets too. [Sure, we may want the relevant hom-collections to be set-sized in the Yoneda embedding case — but being no bigger than set-sized is one thing, living in the universe of pure sets is something else!]

But do we really want to assume that morphisms are always pure sets?

Might we not be looking to category theory for a story about how different bits of the mathematical universe hang together which need not presuppose some over-arching, all-in, set-theoretic reductionism, and so in particular doesn’t presuppose from day one that all morphisms are pure sets?

Now, as I noted, the foundational sections you often meet early in category theory books worry away about questions of size (sets vs classes etc.). But the present worry is orthogonal to all that, and is in a way more basic. If we want to make no assumption that the denizens of different bits of the mathematical universe are all cut from the same cloth, we won’t want to slip into assuming that sets of these denizens are all pure sets. So in particular, do we really want to assume that a collection of morphisms (hom-set) must actually live in Set, if that’s the category mentioned back almost on p.1 of the book which is naturally read (and sometimes explicitly said to be) a category of pure sets? It may be that Set eventually gets to play a special role in the mathematical universe, with other most other categories being representable inside it: but surely this should be something to be shown later, not an assumption to be built in from the start.

In Chapter 3 of his fine Basic Category Theory, Tom Leinster makes the right moves here. Back track. Ask again: what are the sets that, before we start into category theory, we know and love and which are pointed to as constituting an exemplar of a category? Not the sets of pure ZFC (which mathematicians other than set theorists could even spell out the axioms which are supposed to tell you what these are?) but rather what we might call the sets of the working mathematician — sets of naturals, perhaps, or sets of reals, or sets of points in a space, or a set of continuous functions, or … And these are sets with ur-elements, elements that are not themselves presumed to be sets. (Or if we ascend to talk of sets of sets of naturals, for example, it remains the case that when we descend again through members of members … everything typically bottoms out with primitive non-sets.)

We assume various operations are permissible on these sets, and we can codify the permissible operations (for the purposes of the non-set-theorist, falling short of ZFC). Now Leinster associates this with Lawvere’s codification of the Elementary Theory of the Category of Sets (ETCS). But of course, Zermelo was in the same game, aiming to codify the principles of set-building that the working mathematician actually needs, aiming to provide enough to do the usual constructions but not enough to threaten paradox, and Zermelo’s original set theory too allowed for ur-elements. But then, if Set is to be a category of sets-with-urelements, built up using the principles working mathematicians actually need (whatever they are) — which indeed makes some of appeals to Set in category theory much more natural — then this really needs to be said (as Leinster does, and others don’t, and some actually deny).

Of course, we could go Schubert’s way and take hom-sets to be pure sets, so that morphisms and the other apparatus of category theory are all pure sets. But seeing category theory in this way as simply in the service of an across-the-board set-theoretic reductionism would surely be an unhappy way of looking at things: category theory seemed to promise more than that!

Category Theory 2015

My main logical resolution for 2015 is to get to know quite a bit more category theory. Well, it’s fun, I find it aesthetically very appealing, there are some super-smart category theory people here in Cambridge — and there seem to be enough lurking conceptual issues to engage the philosophical bits of my brain, though I want to know (a lot) more category theory before sounding off about them.

I’ve therefore now started a new section of Logic Matters on categories  where I’ll be posting various stuff — starting with my slowly-expanding Notes on Category Theory, and eventually some book notes, links to on-line resources on Category Theory, and so on. Enjoy!

(Other New Year’s resolutions? One is to stop wasting time and endangering my blood pressure reading the comments on various Well Known Philosophy Blogs, comments which seem too often to be getting increasingly bonkers, unpleasant and — let’s hope — unrepresentative. Feeling better already …)

Philosophical remnants/Notes on Category Theory v.3

IMG_0085

So, over the last months, quite a few more large boxes of books have gone to Oxfam. I have kept almost all my logic books. But in three years I must have given away some three quarters of my philosophy books. Very largely unmissed, if I am honest. Those works of the Great Dead Philosophers are no longer reproachfully waiting to be properly read. The more ephemeral books of the last forty years (witnessing passing fashions and fads) are largely disposed of. I’m never going to get excited again e.g. about general epistemology (too arid) or about foundations of physics (too hard), so all those texts can go too. I’m left with Frege, Russell, Wittgenstein, Quine; an amount of philosophical logic and philosophy of maths and related things; and an eclectic mix of unneeded books that somehow I just couldn’t quite bring myself to get rid of (yet). I’m not sure why among the philosophical remnants, Feyerabend for example stays and Fodor goes when I’ll never read either seriously again: but such are the vagaries of sentimental attachment.

But if I’m still rather attached to some authors and topics and themes and approaches, I’m not quite so sure about ‘philosophy’, the institution. Still, that’s another story. And anyway, those lucky enough to have philosophy jobs in these hard times certainly don’t need ancients grouching from the comfort of retirement: they have problems enough. True, judging from what’s been churning around on various Well Known Blogs over the last year, some might perhaps do well to recall Philip Roth’s wise words about  that “treacherous … pleasure: the ecstasy of sanctimony”. But being the season of goodwill, I’ll say no more!

Instead, for your end-of-year delight, here’s an updated version of the Notes on Category Theory (still very partial though now 74 pp.). Newly added: a section on comma categories to Ch.4, a short chapter between the old Chs 7 and 8, and a chapter on representable functors. So far, then, I cover

  1. Categories defined
  2. Duality, kinds of arrows (epics, monics, isomorphisms …)
  3. Functors
  4. More about functors and categories (and the category of categories!)
  5. Natural transformations (with rather more than usual on the motivation)
  6. Equivalence of categories (again with a section on motivation, why we want ‘equivalence’ rather than full isomorphism)
  7. The Yoneda embedding (shown to indeed be an embedding by using an easy restricted version of the Yoneda Lemma)
  8. An aside on Cayley’s Theorem
  9. The Yoneda Lemma (how to get to the full-dress version by two conceptually easy steps from the restricted version).
  10. Representables (definitions, examples, universal elements, the category of elements).

Download the new version of the notes here

Notes on Category Theory, (partial) version #2

After a bit of a gap, I’ve been able to get back to writing up my notes. The current instalment of the notes (61 pp.) corrects some typos in the first six chapters — and it is those needed corrections that prompt me quickly to post another version even though I’ve only added two new chapters this time. So far, then, I cover

  1. Categories defined
  2. Duality, kinds of arrows (epics, monics, isomorphisms …)
  3. Functors
  4. More about functors and categories (and the category of categories!)
  5. Natural transformations (with rather more than usual on the motivation)
  6. Equivalence of categories (again with a section on motivation, why we want ‘equivalence’ rather than full isomorphism)
  7. The Yoneda embedding (shown to indeed be an embedding by using an easy restricted version of the Yoneda Lemma)
  8. The Yoneda Lemma (how to get to the full-dress version by two conceptually easy steps from the restricted version).

It took me a while to see how best(?) to split the proof of the Yoneda Lemma into obviously well-motivated chunks: maybe some others new(ish) to category theory will find the treatment in Chs 7 and 8 helpful.

Download the new version of the notes here

Notes on Category Theory, (partial) version #1

As I said in my last post, I’ve been following some lectures on category theory since the beginning of term. The only way of really nailing this stuff down is to write yourself some notes, work through the proofs, etc. Which I’ve been doing. And then I’ve done some polishing to make the notes shareable with others following the course:

So here are my current notes (50 pp.) on the topics of the first quarter of the course.

Warning: the course I’m following is for the Part III Maths Tripos (i.e. a pretty unrelenting graduate level course for mathematicians with a very strong background). My notes are easier going because I proceed quite slowly and pause to fill in all the proofs where the blackboard notes might well simply read “Exercise!”. But still, this is maths which requires some background to follow (even if perhaps less than you might think).

To be sure, I want to be thinking more in due course about some of the philosophical/foundational issues that category theory suggests: but for the moment my aim is to really get my head round the basic maths more than I’ve done in the past. Hence the notes, which maybe some others might find useful. So far, I cover

  1. Categories defined
  2. Duality, kinds of arrows (epics, monics, isomorphisms …)
  3. Functors
  4. More about functors and categories (and the category of categories!)
  5. Natural transformations (with more than usual on the motivation)
  6. Equivalence of categories (again with a section on the motivation)

Enjoy! (And even better, let me know where I’ve gone wrong and what I can improve.)

Scroll to Top