(Another) one to miss …

If any title in the Cambridge Elements series was especially designed to catch my interest, it would be Theoretical Computer Science for the Working Category Theorist. Not, of course, that I am in any sense a ‘working category theorist’, but I’m certainly interested, and know just a bit. And I know a smidgin too about computability theory. So I, for one, should be an ideal reader for an accessible short book which sets out to give more insights as to how the two are related. The introduction notes that there are a number of texts aimed at the computer scientist learning category theory (like the excellent Barr and Wells, Category Theory for Computing Science); but Noson Yanofsky promises something quite different, aimed at someone who already knows the basics of category theory and who wants to learn theoretical computer science.

It most certainly didn’t work for me. The author has a line about the central relevance of the notion of a monoidal category here, but makes it quite unnecessarily hard going to  extract the key ideas. Indeed, overall, this  just strikes me as very badly written. Careless too. What, for example, are we to make of slapdash remarks like “the German mathematician Georg Cantor showed that sets can be self-referential” or “Kurt Gödel showed that mathematical statements can refer to themselves”? (And on Gödel, I doubt that anyone who isn’t already familiar with the proof of  Gödelian incompleteness theorems from the unsolvability of the Halting problem is going to get much real understanding from the discussion on pp. 71–72.)

I could go into a lot more detail, but to be honest I found the book far too disappointing to want to put in the effort required to disentangle things enough to make for useful comments. Sorry to be so negative. And your mileage, of course, might vary …

[Also see Peter F’s comment.]

5 thoughts on “(Another) one to miss …”

  1. I also was excited to check out this book when I first learned of the series and also was fairly disappointed by it for similar reasons. One of the main offenders for me is the handling of the Church-Turing thesis on page 31, which, like the other examples you gave, is muddled and vague. I know that this series is supposed to be compact, but I don’t think it’s morally correct to try to fit a description of the definition/theorem debate around the Church-Turing thesis into a single paragraph when the subject matter of the book is the theory of computation.

    The author is writing another book called [Monoidal Categories: A Unifying Concept in Mathematics, Physics, and Computing](http://www.sci.brooklyn.cuny.edu/~noson/MCtext.html), which is supposed to be a slow build up from first principles that eventually gets to applications of monoidal categories in various other fields. From reading the sections the author put online, I am honestly left confused as to who the book is for. It’s described as a ‘gentle introduction’ (!) assuming no particular background, but it also goes straight into a discussion of homotopy theory on the first page proper. Granted, it’s not trying to *teach* homotopy theory, and is merely using it as historical context, but I still feel like the uninitiated reader is going to get absolutely nothing from the discussion. Still though, it does seem a lot better than the *Elements* book.

    As a final comment, and I don’t want to be too harsh because I am very empathetic to the plight of fighting against TikZ et al., but one of my main complaints against the *Elements* book as well as the draft of the other is that a lot of the diagrams have clipping/intersecting arrows and other typographical issues that make looking at them unpleasant, and some of the notation just looks very noisy.

  2. Thank you for taking an interest in my books. Obviously, my TCS book is not for everyone.

    I am wondering if Peter F. would send me a private email with some details as to the problems with the arrows and diagrams in the “Monoidal Categories” book. I don’t see what he is referring to. I really would like to get the kinks out of it.

    Again, thank you for taking an interest.

  3. After a brief ‘look inside’, I immediately ordered a copy.

    The title suggests almost the opposite of what the book actually is. Usually a book with a title of the form Subject A for the working practitioner of subject B treats A as helpful and enlightening to the practitioner of B. Categories for the Working Mathematician, for example, presents categories as something that working mathematicians will find interesting and useful: “This book aims to present those ideas and methods that can now be effectively used by mathematicians working in a variety of other fields of mathematical research.” (p vii)

    The mathematicians would use categories in their work as mathematicians.

    Is this book saying category theorists will find elements of theoretical computer science useful in their work as category theorists? That they will want to learn theoretical CS because it will help them do category theory. No!

    But neither is it quite the other way around, written to computer scientists and saying they will find category theory useful and enlightening. It assumes they already do and indeed that “category theorists” — category theorists, not computer scientists using some category theory — “have made tremendous advances in computer science”.

    Nor is it about “insights as to how the two are related”. (At least not very generally.) It even says it’s not, on p 3: “This is not a textbook about the relationship between category theory and computer science.”

    So what is it about? What is its aim? It seems that the aim is to advance and promote an ideological position, that category theory provides the best way, the right way, to understand theoretical computer science.

    See p 1 in the Preface, for example — It’s easy! It’s short! It gives you the right perspective! It gets to the core of the issues! It connects better with other areas of science and math! — and p 4: “Category is uniquely qualified to present the ideas of theoretical compouter science.” Or:

    This element will not only use the language of categories, it will also use the mindset of categories. … a unique way of seeing things. … category theory has a knack for getting to the essence of a problem while leaving out all the dross that is related to a subject. Theoretical computer science stands to gain from this mindset. (p 6)

    It can be made to seem that theoretical CS will seem almost trivial once it’s placed in a category-theoretic framework. More from p 1:

    With some of the simple concepts of category theory in hand, the reader will be able to understand all the ideas and theorems that are taught in a year-long course of theoretical computer science.

    Once the categories and functors of the different models of computation are set up, the concepts of theoretical computer science simply emerge.

    The powerful language of category theory ensures us that what is usually taught in a large textbook can be taught in these few pages.

    And on p 2 in a comment reminiscent of Lawvere’s “we demystified the incompleteness theorem of Godel and the truth-definition theory of Tarski by showing that both are consequences of some very simple algebra”,

    Although the diagonal arguments come in many different forms, we show that they are all instances of a simple theorem of category theory.

    Why bother with the specifics of what Godel, Tarski, Cantor, Kleene and others did with diagonal arguments? They’re all instances of a simple theorem of category theory!

    From the POV of making category theory seem the best way to approach theoretical CS, it might even make sense to try (as Peter F put it) “to fit a description of the definition / theorem debate around the Church-Turing thesis into a single paragraph” rather than go into issues that don’t have a category-theoretic resolution. Perhaps (though I wouldn’t agree) it even seems morally correct.

    So why do I want a copy? Though I am not in sympathy with the book’s ideological position or with the category-theoretic mindset — I find that the level of abstraction and generality reached in category theory often makes it harder to understand something, rather than easier — I want to have a better understanding of why people find those things appealing, and this book is available, short, reasonably inexpensive, in a subject area I know something about, and (unlike certain other books that push category theory) not so annoying that I want to throw it across the room.

    1. I think the natural interpretation of a title of the form “Subject S for Audience A” is simply that S will be presented in a way that specifically takes into account who A is. In *some* cases S will be presented as being especially useful to A, but in many cases the idea is just that S is especially accessible to A–that S can be learned without reinventing the wheel that A already has.

      As I look on MathSciNet at the examples where A=”mathematicians”, I get the impression that most fall into this latter category, but I could be wrong.

      1. I think you’re right that titles of the more general title form, Subject S for Audience A, can have a variety of aims. Still, when it’s a book, and the title is specifically “for the working member of Audience A”, the model (especially in a category-theoretic context) is Mac Lane’s Categories for the Working Mathematician, where the idea does seem to be that working mathematicians would find categories useful in their work as mathematicians.

        (Other books that fit the pattern are Krzysztof Ciesielski’s Set Theory for the Working Mathmatician — “This text presents methods of modern set theory as tools that can be usefully applied to other areas of mathematics.” — and (less explicitly) Categories for the Working Philosopher. An example that points in a different direction is Bourbaki’s address to the Association for Symbolic Logic, “Foundations of Mathematics for the Working Mathematician”. However, it’s much older (1948) and isn’t a book.)

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top