The n-Category Café

Today (Thursday) the topic of my lecture was the category of sets, following Chapter 3 of Tom’s book. As a response to the first slogan posted by Tom, here is the analogous slogan one categorical dimension down:

Equality is the right notion of “sameness” of elements in a set

It’s a silly slogan on its own, because there is no other notion of sameness there, so its purpose is rather to put the higher slogans in perspective by providing a safe basis for the inductive ascent up through the categorical dimensions. After

Isomorphism is the right notion of “sameness” of objects of a category

comes

Equivalence is the right notion of “sameness” between categories

(in turn just a special case of saying that Equivalence is the right notion of “sameness” of objects in a 2-category. But that’s only a teaser for the moment. We will come to 2-categories at the end of the course.)

Thanks, David. Here are Lambek and Scott’s six slogans:

I. Many objects of interest in mathematics congregate in concrete categories.

Hard to argue with that.

II. Many objects of interest to mathematicians are themselves concrete categories.

Less obvious. I might prefer the slightly less specific statement that many objects of interest are small categories. I guess what they have in mind is things like: every group can be viewed as a category of a special kind, as can every poset and — if you allow enriched categories — every metric space. (If I had their book with me, guessing would be unnecessary, but I don’t.)

III. Many objects of interest to mathematicians may be viewed as functors from small categories to Set.

Right: so an action of a group or a sheaf on a topological space can be viewed as a functor into Set.

IV. Many important concepts in mathematics arise as adjoints, right or left, to previously known functors.

This is a bit less cryptic and a bit less dramatic than Mac Lane’s “adjoint functors arise everywhere”.

V. Many equivalences and duality theorems in mathematics arise as an equivalence of fixed subcategories induced by a pair of adjoint functors.

I’d have loved to have had time to cover this in my class today. If anyone from the class is reading this, I encourage you to try Exercise 2.2.11, which explains what this slogan means. This is probably my favourite example.

VI. Many categories of interest are the Eilenberg-Moore categories [$=$ categories of algebras] of triples [$=$ monads] on familiar categories.

No arguments with that!

David wrote:

They attribute the idea of conveying category theoretic precepts through “slogans” to Lawvere’s Adjointness in Foundations.

That puzzles me, first, because I think of Lawvere as being rather anti-slogan, and second, because in that paper of his, the word “slogan” only seems to appear once, and not in an especially slogan-promoting way.

I like the practice of summarizing important mathematical ideas as slogans. I think that some mathematicians get too fixated on only making statements that are completely precise and always true, and overlook the value of shorty, pithy statements that encapsulate big ideas, even if there are exceptions and addenda. I try to incorporate slogans in my teaching a lot, but I find that it often takes me several times through teaching a subject to figure out what I think the slogans should be.

Category theory may well be uniquely well suited to this kind of sloganeering, but it certainly has a role in other areas. It might be an interesting/useful project to collect such slogans for various areas somewhere.

Today was the Yoneda lemma. As I mentioned in class, Always consider the identity has an important special case:

A natural transformation $Hom(-, A) \to X$ is determined by its value at $id_A$.

Here $A$ is an object of a category $\mathcal{A}$ and $X$ is a functor $\mathcal{A}^{op} \to Set$.

A curious thing: in the four classes so far, the number of students attending has been, respectively, 19, 17, 15, 13. Assuming that the arithmetic progression continues, our final class will have $-1$ student. Some of Joachim’s colleagues have expressed an interest in coming along to see what $-1$ student looks like. This presents problems of a philosophical type.

Hi, and thanks for the question!

For a FIXED object $A$ in $\mathcal{A}$ it works. The assignment sending $B$ to $Hom_\mathcal{B}(F(A), B)$ is a functor from $\mathcal{B}$ to $Set$.

Right! For any object $X$ of $\mathcal{B}$, there’s a functor

$$\mathcal{B}(X, -): \mathcal{B} \to Set.$$

On objects, it sends $B \in \mathcal{B}$ to the set $Hom_{\mathcal{B}}(X, B)$. On morphisms, it sends $g: B \to B'$ to the map of sets

$$Hom_{\mathcal{B}}(X, B) \to Hom_{\mathcal{B}}(X, B')$$

defined by $q \mapsto g \circ q$.

That’s a lot to swallow, and we’ll get to it on Tuesday. I didn’t want to attempt to explain all this today, which is why I didn’t refer to it when I explained the naturality part of adjointness.

In particular, all this is true when $X = F(A)$, for some functor $F: \mathcal{A} \to \mathcal{B}$.

Also the assignment sending $B$ to $Hom_\mathcal{A}(A, G(B))$ is a functor from $\mathcal{B}$ to $Set$. And the bijection for each $B$ is a natural transformation between these two functors.

Yes indeed. Indeed, an adjunction between $F$ and $G$ (with $F$ on the left and $G$ on the right) defines a natural isomorphism

$$Hom_\mathcal{B}(F(A), -) \to Hom_\mathcal{A}(A, G(-))$$

for each $A \in \mathcal{A}$. This is a natural isomorphism between the two functors

$$Hom_\mathcal{B}(F(A), -), Hom_\mathcal{A}(A, G(-)): \mathcal{B} \to Set.$$

The naturality of this isomorphism corresponds, explicitly, to one of the two equations that I wrote on the board today and labelled as (#).

But that is only for fixed $A$. If $A$ varies it is not functorial in $A$. What am I missing something?

I think the thing you’re missing is contravariance. Exactly the same story can be told if we fix $B$ and let $A$ vary. We have two functors

$$Hom_\mathcal{A}(-, G(B)), Hom_\mathcal{B}(F(-), B): \mathcal{A}^{op} \to Set.$$

Generally, for any object $X$ of any category $\mathcal{A}$, the construction $A \mapsto Hom(A, X)$ defines a contravariant functor from $\mathcal{A}$ to $Set$. In symbols, it’s a functor $\mathcal{A}^{op} \to Set$. For instance, in the category of vector spaces over a field $k$, the construction $V \mapsto Hom(V, k)$ is contravariant in $k$: a linear map $V \to W$ gives rise to a map $Hom(W, k) \to Hom(V, k)$ in the other direction. That’s why it’s contravariant.

But the contravariance doesn’t cause any problems! It’s just a fact of life that some things are contravariant, and it’s no big deal.

Does that answer it?

(Incidentally, if you want to do a curly/calligraphic A here, you can’t just type AA: as in Latex, you have to type \mathcal{A}, between dollar signs.)

You might also enjoying looking at this alternate definition of “adjunction” which uses naturality in the sense of natural transformations.

An adjunction between $F: \mathcal{A} \to\mathcal{B}$ and $G: \mathcal{B} \to \mathcal{A}$ is a natural isomorphism between these functors: $(\mathcal{A}^{op} \times G) \circ Hom_\mathcal{A}: \mathcal{A}^{op} \times \mathcal{B} \to \mathcal{A}^{op} \times \mathcal{A} \to Set$ $(F^{op} \times \mathcal{B}) \circ Hom_\mathcal{B}: \mathcal{A}^{op} \times \mathcal{B} \to \mathcal{B}^{op} \times \mathcal{B} \to Set$

Oops, that was supposed to be two lines.

$(\mathcal{A}^{op} \times G) \circ Hom_\mathcal{A}: \mathcal{A}^{op} \times \mathcal{B} \to \mathcal{A}^{op} \times \mathcal{A} \to Set$

$(F^{op} \times \mathcal{B}) \circ Hom_\mathcal{B}: \mathcal{A}^{op} \times \mathcal{B} \to \mathcal{B}^{op} \times \mathcal{B} \to Set$

I guess that’s what I get for previewing my post in a half-screen window :)

Here is a slogan to atone for my formatting mishap:

Category theory often lets us transform a complicated idea in simple setting into a simple idea in a more complicated setting.

The usual definition of an adjunction has a simple setting (just the hom sets your categories) but makes it seem like a complicated idea (a family of bijections, plus the naturality conditions).

In the definition I just gave, the setting is more complex (two composite functors in a functor category) but the idea is simple (just an isomorphism).

The benefit is not immediate because you have to come to grips with the more complicated setting, but once you are there the idea becomes easier to understand.

For example, it is pretty obvious that all terminal objects in a category must be isomorphic, but not so obvious that all limits of a diagram must be isomorphic. It becomes obvious once you are comfortable viewing limits as terminal objects (in a category more complicated than the original one).

Well, that’s fun. In case that link expires, it’s a talk of Jan Rutten’s called “The Method of Coalgebra” (or to give it its full ominous and humorous title, “The Method of Coalgebra — In Some Detail”).

I can’t resist talking through Rutten’s “Category theory in 10 slogans”:

1. Always ask: what are the types?

I’m not 100% convinced that’s category theory rather than type theory, but yeah, in category theory you always have to think about where things live. Today I was introducing adjoint functors with the usual kind of free-forgetful examples: specifically, the free-forgetful functor between commutative rings and sets. And in order to do this, I had to be careful about the distinction between a ring and its underlying set, much more careful than one would normally be.

I spent years saying “where does this thing live?” rather than “what is this thing’s type?”, until a category theorist mocked me gently and I changed my way of speaking.

2. Think in terms of arrows rather than elements.

Agreed. But it’s also fine to define an “element” of an object $A$ as an arrow into $A$, àla Lawvere.

3. Ask what mathematical structures do, not what they are.

Right. That’s the slogan mentioned in my post, which Joachim put in front of the class on day one.

4. Categories as mathematical contexts.

5. Categories as mathematical structures.

I guess these are the same as Lambek and Scott’s Slogans I and II.

6. Make definitions and constructions as general as possible.

I disagree. I prefer Mac Lane’s remark at the end of Chapter IV of Categories for the Working Mathematician:

good general theory does not search for the maximum generality, but for the right generality.

Back to Jan Rutten’s list:

7. Functoriality!

8. Naturality!

9. Universality!

Good war-cries! Didn’t I hear Mel Gibson shouting these in some film, as he came running over a hill in blue face-paint?

10. Adjoints are everywhere.

Absolutely!

Maybe it might help to ask: how many $0\times n$ matrices are there?

Let’s see. An $m \times n$ matrix over a ring $k$ is a function $\mathbf{m} \times \mathbf{n} \to k$, where $\mathbf{m}$ denotes an $m$-element set. When $m = 0$, the set $\mathbf{m}$ is empty, so $\mathbf{m} \times \mathbf{n} = \emptyset$. So, a $0 \times n$ matrix must be a function $\emptyset \to k$. There’s exactly one of these, so there’s exactly one $0 \times n$ matrix. It doesn’t matter what we call it.

In linear algebra, the $m \times n$ matrices correspond in a natural one-to-one way with the linear maps $k^n \to k^m$. When $m = 0$, there’s exactly one $0 \times n$ matrix. There’s also exactly one linear map $k^n \to k^0$, since $k^0$ is a one-element set. So, the correspondence still works perfectly when you include $m = 0$. The same is true for $n = 0$.

So yes, I did mean to allow $m = 0$ and $n = 0$.

The way I just explained it makes it sound like it’s just luck that everything works for $m = 0$ or $n = 0$. But it’s not! In the usual proof that $m \times n$ matrices correspond to linear maps $k^n \to k^m$, there’s no reason to exclude $0$ as a value of $m$ or $n$. (I know this because I just taught it in my introductory linear algebra class last semester.)

If it helps, vector spaces are like pointed sets (which in a sense are vector spaces over the mythical field with one element). An $n$-dimensional space is then like a pointed set of $n+1$ elements. Maps of such pointed sets must preserve the base point, so there is no choice when mapping out of or into the $0$-dimensional space.

Anonymous wrote, anonymously:

What is an $0 \times n$ matrix? It should be a matrix with zero rows but if it has zero rows then it also has zero columns.

No. It certainly has zero entries, but it still has $n$ columns. They’re just very skinny.

For example, suppose you have $m$ men and $n$ women. Then you can make an $m \times n$ matrix whose entries are all the ways a man and a woman can form a married pair. If there are 0 men and 3 women there are no possible married pairs, but don’t go berserk and claim there are no women!

The rhetorical form of this switching, usually not to equate but to contrast, is called ‘antimetabole’:

• The weapon of criticism cannot replace the criticism of weapons.

• It is not the consciousness of men that determines their being, but their being that determines their consciousness.

• Philosophy can only be realized by the abolition of the proletariat, and the proleteriat can only be abolished by the realization of philosophy.

All due to Karl Marx.

Another one from John Baez: category theory is that branch of mathematics where the examples require examples.

How about John Baez’s Every sufficiently precise analogy is yearning to become a functor?

For anyone in our class who doesn’t know the verb to yearn, it means something like to desire in a strong and dreamy way, maybe anhelar. It’s an unusually emotional word for a functor.

Anyway, I don’t get what John means. Here are the first two mathematical analogies that came into my head. Neither seems to yearn to become a functor, at least as far as I can see. But maybe someone can set me straight.

Suppose you’re an undergraduate learning ring theory. You already know some group theory, and the more you learn about rings, the more you notice similarities between the two subjects. A ring is a set equipped with some operations satisfying some equations; so is a group. You have homomorphisms between rings, just like you do for groups. You can take products of rings, which are rather like direct products of groups. Ring homomorphisms have kernels, just like group homomorphisms do. Ideals of rings seem to play the same role as normal subgroups of groups, and you can take quotients by ideals or normal subgroups in a similar way. There are first isomorphism theorems in both subjects, and they’re highly analogous too.

If I wanted to make this analogy precise, I’d use the notion of algebraic theory. Now it’s true that however you approach algebraic theories, there are functors kicking around: a model of a Lawvere theory is a functor out of it, and a monad is an endofunctor equipped with some stuff. And it’s also true that somewhat by coincidence, these two algebraic theories, rings and groups, are linked by forgetful functors

$$Ring \to AbGrp \to Grp.$$

But I don’t think any of these can be the functors that John had in mind — the functor that the analogy between rings and groups is yearning to become.

The second analogy that came into my head was the one between metric spaces and categories. A metric space has a collection of points; a category has a collection of objects. For any two points $a, b$ of a metric space, there’s a real number $d(a, b)$; for any two objects $A, B$ of a category, there’s a set $Hom(A, B)$. For any three points $a, b, c$ of a metric space, there’s the triangle inequality

$$d(a, b) + d(b, c) \geq d(a, c);$$

and for any three objects $A, B, C$ of a category, there’s a composition operation

$$Hom(A, B) \times Hom(B, C) \to Hom(A, C).$$

Now as you and I know, this analogy is made precise by observing that both metric spaces and categories are special cases of enriched categories. But what’s the functor that the analogy between metric spaces and categories is yearning to become?

• A4 (tomorrow): presheaves, sheaves, knowledge representation and databases

at the course page clicking on Bibliography gives;

A4: [M. La Palme Reyes, G. Reyes and H. Zolfaghari: Generic figures and their glueings: A constructive approach to functor categories. Polimetrica, 2004]

Is it normal to have a course bibliography contain books that have been out of print for a good while and very difficult to find?

Maybe this book would be a good candidate for being republished online.

The book’s in the university library, and Joachim has a copy. So students in the class can access it.

I haven’t read this book myself, but I’m intrigued by it.

I would say you could just leave the “but” out. It’s true that the process of generalization takes more work than for some other aspects, but limits do also generalize to enriched categories of course.

Today Tom talked about algebraic theories, monads and operads. It was very nice to see algebraic theories described exactly as operads, but with functoriality in all maps between finite sets instead of only functoriality in bijections.

Here is a slogan related to today’s topics:

Monads make the world go ‘round

(It sounds best in a proper Australian English, pronounced ‘monnads’, not ‘mownads’ like Tom and many people do.)

Shouldn’t a program be an element of a terminal coalgebra?

Would anyone care to elaborate on these two slogans, especially the second? I’d be very grateful.