» Publishers, Monetize your RSS feeds with FeedShow: More infos (Show/Hide Ads)
My new book is out!
Click the image for more information.
It’s an introductory category theory text, and I can prove it exists: there’s a copy right in front of me. (You too can purchase a proof.) Is it unique? Maybe. Here are three of its properties:
- It doesn’t assume much.
- It sticks to the basics.
- It’s short.
I want to thank the $n$-Café patrons who gave me encouragement during my last week of work on this. As I remarked back then, some aspects of writing a book — even a short one — require a lot of persistence.
But I also want to take this opportunity to make a suggestion. There are now quite a lot of introductions to category theory available, of various lengths, at various levels, and in various styles. I don’t kid myself that mine is particularly special: it’s just what came out of my individual circumstances, as a result of the courses I’d taught. I think the world has plenty of introductions to category theory now.
What would be really good is for there to be a nice second book on category theory. Now, there are already some resources for advanced categorical topics: for instance, in my book, I cite both the $n$Lab and Borceux’s three-volume Handbook of Categorical Algebra for this. But useful as those are, what we’re missing is a shortish book that picks up where Categories for the Working Mathematician leaves off.
Let me be more specific. One of the virtues of Categories for the Working Mathematician (apart from being astoundingly well-written) is that it’s selective. Mac Lane covers a lot in just 262 pages, and he does so by repeatedly making bold choices about what to exclude. For instance, he implicitly proves that for any finitary algebraic theory, the category of algebras has all colimits — but he does so simply by proving it for groups, rather than explicitly addressing the general case. (After all, anyone who knows what a finitary algebraic theory is could easily generalize the proof.) He also writes briskly: few words are wasted.
I’m imagining a second book on category theory of a similar length to Categories for the Working Mathematician, and written in the same brisk and selective manner. Over beers five years ago, Nicola Gambino and I discussed what this hypothetical book ought to contain. I’ve lost the piece of paper I wrote it down on (thus, Nicola is absolved of all blame), but I attempted to recreate it sometime later. Here’s a tentative list of chapters, in no particular order:
- Enriched categories
- 2-categories (and a bit on higher categories)
- Topos theory (obviously only an introduction) and categorical set theory
- Fibrations
- Bimodules, Morita equivalence, Cauchy completeness and absolute colimits
- Operads and Lawvere theories
- Categorical logic (again, just a bit) and internal category theory
- Derived categories
- Flat functors and locally presentable categories
- Ends and Kan extensions (already in Mac Lane’s book, but maybe worth another pass).
Someone else should definitely write such a book.
How can we discuss all the kinds of matter described by the ten-fold way in a single setup?
It’s bit tough, because 8 of them are fundamentally ‘real’ while the other 2 are fundamentally ‘complex’. Yet they should fit into a single framework, because there are 10 super division algebras over the real numbers, and each kind of matter is described using a super vector space — or really a super Hilbert space — with one of these super division algebras as its ‘ground field’.
Combining physical systems is done by tensoring their Hilbert spaces… and there does seem to be a way to do this even with super Hilbert spaces over different super division algebras. But what sort of mathematical structure can formalize this?
Here’s my current attempt to solve this problem. I’ll start with a warmup case, the threefold way. In fact I’ll spend most of my time on that! Then I’ll sketch how the ideas should extend to the tenfold way.
Fans of lax monoidal functors, Deligne’s tensor product of abelian categories, and the collage of a profunctor will be rewarded for their patience if they read the whole article. But the basic idea is supposed to be simple: it’s about a multiplication table.
The $\mathbb{3}$-fold way
First of all, notice that the set
$\mathbb{3} = \{1,0,-1\}$
is a commutative monoid under ordinary multiplication:
$\begin{array}{rrrr} \mathbf{\times} & \mathbf{1} & \mathbf{0} & \mathbf{-1} \\ \mathbf{1} & 1 & 0 & -1 \\ \mathbf{0} & 0 & 0 & 0 \\ \mathbf{-1} & -1 & 0 & 1 \end{array}$
Next, note that there are three (associative) division algebras over the reals: $\mathbb{R}, \mathbb{C}$ or $\mathbb{H}$. We can equip a real vector space with the structure of a module over any of these algebras. We’ll then call it a real, complex or quaternionic vector space.
For the real case, this is entirely dull. For the complex case, this amounts to giving our real vector space $V$ a complex structure: a linear operator $i: V \to V$ with $i^2 = -1$. For the quaternionic case, it amounts to giving $V$ a quaternionic structure: a pair of linear operators $i, j: V \to V$ with
$i^2 = j^2 = -1, \qquad i j = -j i$
We can then define $k = i j$.
The terminology ‘quaternionic vector space’ is a bit quirky, since the quaternions aren’t a field, but indulge me. $\mathbb{H}^n$ is a quaternionic vector space in an obvious way. $n \times n$ quaternionic matrices act by multiplication on the right as ‘quaternionic linear transformations’ — that is, left module homomorphisms — of $\mathbb{H}^n$. Moreover, every finite-dimensional quaternionic vector space is isomorphic to $\mathbb{H}^n$. So it’s really not so bad! You just need to pay some attention to left versus right.
Now: I claim that given two vector spaces of any of these kinds, we can tensor them over the real numbers and get a vector space of another kind. It goes like this:
$\begin{array}{cccc} \mathbf{\otimes} & \mathbf{real} & \mathbf{complex} & \mathbf{quaternionic} \\ \mathbf{real} & real & complex & quaternionic \\ \mathbf{complex} & complex & complex & complex \\ \mathbf{quaternionic} & quaternionic & complex & real \end{array}$
You’ll notice this has the same pattern as the multiplication table we saw before:
$\begin{array}{rrrr} \mathbf{\times} & \mathbf{1} & \mathbf{0} & \mathbf{-1} \\ \mathbf{1} & 1 & 0 & -1 \\ \mathbf{0} & 0 & 0 & 0 \\ \mathbf{-1} & -1 & 0 & 1 \end{array}$
So:
- $\mathbb{R}$ acts like 1.
- $\mathbb{C}$ acts like 0.
- $\mathbb{H}$ acts like -1.
There are different ways to understand this, but a nice one is to notice that if we have algebras $A$ and $B$ over some field, and we tensor an $A$-module and a $B$-module (over that field), we get an $A \otimes B$-module. So, we should look at this ‘multiplication table’ of real division algebras:
$\begin{array}{lrrr} \mathbf{\otimes} & \mathbf{\mathbb{R}} & \mathbf{\mathbb{C}} & \mathbf{\mathbb{H}} \\ \mathbf{\mathbb{R}} & \mathbb{R} & \mathbb{C} & \mathbb{H} \\ \mathbf{\mathbb{C}} & \mathbb{C} & \mathbb{C} \oplus \mathbb{C} & \mathbb{C}[2] \\ \mathbf{\mathbb{H}} & \mathbb{H} & \mathbb{C}[2] & \mathbb{R}[4] \end{array}$
Here $\mathbb{C}[2]$ means the 2 × 2 complex matrices viewed as an algebra over $\mathbb{R}$, and $\mathbb{R}[4]$ means that 4 × 4 real matrices.
What’s going on here? Naively you might have hoped for a simpler table, which would have instantly explained my earlier claim:
$\begin{array}{lrrr} \mathbf{\otimes} & \mathbf{\mathbb{R}} & \mathbf{\mathbb{C}} & \mathbf{\mathbb{H}} \\ \mathbf{\mathbb{R}} & \mathbb{R} & \mathbb{C} &\mathbb{H} \\ \mathbf{\mathbb{C}} & \mathbb{C} & \mathbb{C} & \mathbb{C} \\ \mathbf{\mathbb{H}} & \mathbb{H} & \mathbb{C} & \mathbb{R} \end{array}$
This isn’t true, but it’s ‘close enough to true’. Why? Because we always have a god-given algebra homomorphism from the naive answer to the real answer! The interesting cases are these:
$\mathbb{C} \to \mathbb{C} \oplus \mathbb{C}$ $\mathbb{C} \to \mathbb{C}[2]$ $\mathbb{R} \to \mathbb{R}[4]$
where the first is the diagonal map $a \mapsto (a,a)$, and the other two send numbers to the corresponding scalar multiples of the identity matrix.
So, for example, if $V$ and $W$ are $\mathbb{C}$-modules, then their tensor product (over the reals! — all tensor products here are over $\mathbb{R}$) is a module over $\mathbb{C} \otimes \mathbb{C} \cong \mathbb{C} \oplus \mathbb{C}$, and we can then pull that back via $f$ to get a right $\mathbb{C}$-module.
What’s really going on here?
There’s a monoidal category $Alg_{\mathbb{R}}$ of algebras over the real numbers, where the tensor product is the usual tensor product of algebras. The monoid $\mathbb{3}$ can be seen as a monoidal category with 3 objects and only identity morphisms. And I claim this:
Claim. There is an oplax monoidal functor $F : \mathbb{3} \to Alg_{\mathbb{R}}$ with $\begin{array}{ccl} F(1) &=& \mathbb{R} \\ F(0) &=& \mathbb{C} \\ F(-1) &=& \mathbb{H} \end{array}$
What does ‘oplax’ mean? Some readers of the $n$-Category Café eat oplax monoidal functors for breakfast and are chortling with joy at how I finally summarized everything I’d said so far in a single terse sentence! But others of you see ‘oplax’ and get a queasy feeling.
The key idea is that when we have two monoidal categories $C$ and $D$, a functor $F : C \to D$ is ‘oplax’ if it preserves the tensor product, not up to isomorphism, but up to a specified morphism. More precisely, given objects $x,y \in C$ we have a natural transformation
$F_{x,y} : F(x \otimes y) \to F(x) \otimes F(y)$
If you had a ‘lax’ functor this would point the other way, and they’re a bit more popular… so when it points the opposite way it’s called ‘oplax’.
(In the lax case, $F_{x,y}$ should probably be called the laxative, but we’re not doing that case, so I don’t get to make that joke.)
This morphism $F_{x,y}$ needs to obey some rules, but the most important one is that using it twice, it gives two ways to get from $F(x \otimes y \otimes z)$ to $F(x) \otimes F(y) \otimes F(z)$, and these must agree.
Let’s see how this works in our example… at least in one case. I’ll take the trickiest case. Consider
$F_{0,0} : F(0 \cdot 0) \to F(0) \otimes F(0),$
that is:
$F_{0,0} : \mathbb{C} \to \mathbb{C} \otimes \mathbb{C}$
There are, in principle, two ways to use this to get a homomorphism
$F(0 \cdot 0 \cdot 0 ) \to F(0) \otimes F(0) \otimes F(0)$
or in other words, a homomorphism
$\mathbb{C} \to \mathbb{C} \otimes \mathbb{C} \otimes \mathbb{C}$
where remember, all tensor products are taken over the reals. One is
$\mathbb{C} \stackrel{F_{0,0}}{\longrightarrow} \mathbb{C} \otimes \mathbb{C} \stackrel{1 \otimes F_{0,0}}{\longrightarrow} \mathbb{C} \otimes (\mathbb{C} \otimes \mathbb{C})$
and the other is
$\mathbb{C} \stackrel{F_{0,0}}{\longrightarrow} \mathbb{C} \otimes \mathbb{C} \stackrel{F_{0,0} \otimes 1}{\longrightarrow} (\mathbb{C} \otimes \mathbb{C})\otimes \mathbb{C}$
I want to show they agree (after we rebracket the threefold tensor product using the associator).
Unfortunately, so far I have described $F_{0,0}$ in terms of an isomorphism
$\mathbb{C} \otimes \mathbb{C} \cong \mathbb{C} \oplus \mathbb{C}$
Using this isomorphism, $F_{0,0}$ becomes the diagonal map $a \mapsto (a,a)$. But now we need to really understand $F_{0,0}$ a bit better, so I’d better say what isomorphism I have in mind! I’ll use the one that goes like this:
$\begin{array}{ccl} \mathbb{C} \otimes \mathbb{C} &\to& \mathbb{C} \oplus \mathbb{C} \\ 1 \otimes 1 &\mapsto& (1,1) \\ i \otimes 1 &\mapsto &(i,i) \\ 1 \otimes i &\mapsto &(i,-i) \\ i \otimes i &\mapsto & (1,-1) \end{array}$
This may make you nervous, but it truly is an isomorphism of real algebras, and it sends $a \otimes 1$ to $(a,a)$. So, unraveling the web of confusion, we have
$\begin{array}{rccc} F_{0,0} : & \mathbb{C} &\to& \mathbb{C}\otimes \mathbb{C} \\ & a &\mapsto & a \otimes 1 \end{array}$
Why didn’t I just say that in the first place? Well, I suffered over this a bit, so you should too! You see, there’s an unavoidable arbitrary choice here: I could just have well used $a \mapsto 1 \otimes a$. $F_{0,0}$ looked perfectly god-given when we thought of it as a homomorphism from $\mathbb{C}$ to $\mathbb{C} \oplus \mathbb{C}$, but that was deceptive, because there’s a choice of isomorphism $\mathbb{C} \otimes \mathbb{C} \to \mathbb{C} \oplus \mathbb{C}$ lurking in this description.
This makes me nervous, since category theory disdains arbitrary choices! But it seems to work. On the one hand we have
$\begin{array}{ccccc} \mathbb{C} &\stackrel{F_{0,0}}{\longrightarrow} &\mathbb{C} \otimes \mathbb{C} &\stackrel{1 \otimes F_{0,0}}{\longrightarrow}& \mathbb{C} \otimes \mathbb{C} \otimes \mathbb{C} \\ a &\mapsto & a \otimes 1 & \mapsto & a \otimes (1 \otimes 1) \end{array}$
On the other hand, we have
$\begin{array}{ccccc} \mathbb{C} &\stackrel{F_{0,0}}{\longrightarrow} & \mathbb{C} \otimes \mathbb{C} &\stackrel{F_{0,0} \otimes 1}{\longrightarrow} & \mathbb{C} \otimes \mathbb{C} \otimes \mathbb{C} \\ a &\mapsto & a \otimes 1 & \mapsto & (a \otimes 1) \otimes 1 \end{array}$
So they agree!
I need to carefully check all the other cases before I dare call my claim a theorem. Indeed, writing up this case has increased my nervousness… before, I’d thought it was obvious.
But let me march on, optimistically!
Consequences
In quantum physics, what matters is not so much the algebras $\mathbb{R}$, $\mathbb{C}$ and $\mathbb{H}$ themselves as the categories of vector spaces — or indeed, Hilbert spaces —-over these algebras. So, we should think about the map sending an algebra to its category of modules.
For any field $k$, there should be a contravariant pseudofunctor
$Rep: Alg_k \to Rex_k$
where $Rex_k$ is the 2-category of
$k$-linear finitely cocomplete categories,
$k$-linear functors preserving finite colimits,
and natural transformations.
The idea is that $Rep$ sends any algebra $A$ over $k$ to its category of modules, and any homomorphism $f : A \to B$ to the pullback functor $f^* : Rep(B) \to Rep(A)$.
(Functors preserving finite colimits are also called right exact; this is the reason for the funny notation $Rex$. It has nothing to do with the dinosaur of that name.)
Moreover, $Rep$ gets along with tensor products. It’s definitely true that given real algebras $A$ and $B$, we have
$Rep(A \otimes B) \simeq Rep(A) \boxtimes Rep(B)$
where $\boxtimes$ is the tensor product of finitely cocomplete $k$-linear categories. But we should be able to go further and prove $Rep$ is monoidal. I don’t know if anyone has bothered yet.
(In case you’re wondering, this $\boxtimes$ thing reduces to Deligne’s tensor product of abelian categories given some ‘niceness assumptions’, but it’s a bit more general. Read the talk by Ignacio López Franco if you care… but I could have used Deligne’s setup if I restricted myself to finite-dimensional algebras, which is probably just fine for what I’m about to do.)
So, if my earlier claim is true, we can take the oplax monoidal functor
$F : \mathbb{3} \to Alg_{\mathbb{R}}$
and compose it with the contravariant monoidal pseudofunctor
$Rep : Alg_{\mathbb{R}} \to Rex_{\mathbb{R}}$
giving a guy which I’ll call
$Vect: \mathbb{3} \to Rex_{\mathbb{R}}$
I guess this guy is a contravariant oplax monoidal pseudofunctor! That doesn’t make it sound very lovable… but I love it. The idea is that:
$Vect(1)$ is the category of real vector spaces
$Vect(0)$ is the category of complex vector spaces
$Vect(-1)$ is the category of quaternionic vector spaces
and the operation of multiplication in $\mathbb{3} = \{1,0,-1\}$ gets sent to the operation of tensoring any one of these three kinds of vector space with any other kind and getting another kind!
So, if this works, we’ll have combined linear algebra over the real numbers, complex numbers and quaternions into a unified thing, $Vect$. This thing deserves to be called a $\mathbb{3}$-graded category. This would be a nice way to understand Dyson’s threefold way.
What’s really going on?
What’s really going on with this monoid $\mathbb{3}$? It’s a kind of combination or ‘collage’ of two groups:
The Brauer group of $\mathbb{R}$, namely $\mathbb{Z}_2 \cong \{-1,1\}$. This consists of Morita equivalence classes of central simple algebras over $\mathbb{R}$. One class contains $\mathbb{R}$ and the other contains $\mathbb{H}$. The tensor product of algebras corresponds to multiplication in $\{-1,1\}$.
The Brauer group of $\mathbb{C}$, namely the trivial group $\{0\}$. This consists of Morita equivalence classes of central simple algebras over $\mathbb{C}$. But $\mathbb{C}$ is algebraically closed, so there’s just one class, containing $\mathbb{C}$ itself!
See, the problem is that while $\mathbb{C}$ is a division algebra over $\mathbb{R}$, it’s not ‘central simple’ over $\mathbb{R}$: its center is not just $\mathbb{R}$, it’s bigger. This turns out to be why $\mathbb{C} \otimes \mathbb{C}$ is so funny compared to the rest of the entries in our division algebra multiplication table.
So, we’ve really got two Brauer groups in play. But we also have a homomorphism from the first to the second, given by ‘tensoring with $\mathbb{C}$’: complexifying any real central simple algebra, we get a complex one.
And whenever we have a group homomorphism $\alpha: G \to H$, we can make their disjoint union $G \sqcup H$ into monoid, which I’ll call $G \sqcup_\alpha H$.
It works like this. Given $g,g' \in G$, we multiply them the usual way. Given $h, h' \in H$, we multiply them the usual way. But given $g \in G$ and $h \in H$, we define
$g h := \alpha(g) h$
and
$h g := h \alpha(g)$
The multiplication on $G \sqcup_\alpha H$ is associative! For example:
$(g g')h = \alpha(g g') h = \alpha(g) \alpha(g') h = \alpha(g) (g'h) = g(g'h)$
Moreover, the element $1_G \in G$ acts as the identity of $G \sqcup_\alpha H$. For example:
$1_G h = \alpha(1_G) h = 1_H h = h$
But of course $G \sqcup_\alpha H$ isn’t a group, since “once you get inside $H$ you never get out”.
This construction could be called the collage of $G$ and $H$ via $\alpha$, since it’s reminiscent of a similar construction of that name in category theory.
Question. What do monoid theorists call this construction?
Question. Can we do a similar trick for any field? Can we always take the Brauer groups of all its finite-dimensional extensions and fit them together into a monoid by taking some sort of collage? If so, I’d call this the Brauer monoid of that field.
The $\mathbb{10}$-fold way
If you carefully read Part 1, maybe you can guess how I want to proceed. I want to make everything ‘super’.
I’ll replace division algebras over $\mathbb{R}$ by super division algebras over $\mathbb{R}$. Now instead of 3 = 2 + 1 there are 10 = 8 + 2:
8 of them are central simple over $\mathbb{R}$, so they give elements of the super Brauer group of $\mathbb{R}$, which is $\mathbb{Z}_8$.
2 of them are central simple over $\mathbb{C}$, so they give elements of the super Brauer group of $\mathbb{C}$, which is $\mathbb{Z}_2$.
Complexification gives a homomorphism
$\alpha: \mathbb{Z}_8 \to \mathbb{Z}_2$
namely the obvious nontrivial one. So, we can form the collage
$\mathbb{10} = \mathbb{Z}_8 \sqcup_\alpha \mathbb{Z}_2$
It’s a commutative monoid with 10 elements! Each of these is the equivalence class of one of the 10 real super division algebras.
I’ll then need to check that there’s an oplax monoidal functor
$G : \mathbb{10} \to SuperAlg_{\mathbb{R}}$
sending each element of $\mathbb{10}$ to the corresponding super division algebra.
If $G$ really exists, I can compose it with a thing
$SuperRep : SuperAlg_{\mathbb{R}} \to Rex_{\mathbb{R}}$
sending each super algebra to its category of ‘super representations’ on super vector spaces. This should again be a contravariant monoidal pseudofunctor.
We can call the composite of $G$ with $SuperRep$
$SuperVect: \mathbb{10} \to \Rex_{\mathbb{R}}$
If it all works, this thing $SuperVect$ will deserve to be called a $\mathbb{10}$-graded category. It contains super vector spaces over the 10 kinds of super division algebras in a single framework, and says how to tensor them. And when we look at super Hilbert spaces, this setup will be able to talk about all ten kinds of matter I mentioned last time… and how to combine them.
So that’s the plan. If you see problems, or ways to simplify things, please let me know!
There are 10 of each of these things:
Associative real super-division algebras.
Classical families of compact symmetric spaces.
Ways that Hamiltonians can get along with time reversal ($T$) and charge conjugation ($C$) symmetry.
Dimensions of spacetime in string theory.
It’s too bad nobody took up writing This Week’s Finds in Mathematical Physics when I quit. Someone should have explained this stuff in a nice simple way, so I could read their summary instead of fighting my way through the original papers. I don’t have much time for this sort of stuff anymore!
Luckily there are some good places to read about this stuff:
Todd Trimble, The super Brauer group and super division algebras, April 27, 2005.
Shinsei Ryu, Andreas P. Schnyde, Akira Furusaki and Andreas W. W. Ludwig, Topological insulators and superconductors: tenfold way and dimensional hierarchy, June 15, 2010.
Gregory Moore and Dan Freed, Twisted equivariant matter, January 7, 2013.
Gregory Moore, Quantum symmetries and compatible Hamiltonians, December 15, 2013.
Let me start by explaining the basic idea, and then move on to more fancy aspects.
Ten kinds of matter
The idea of the ten-fold way goes back at least to 1996, when Altland and Zirnbauer discovered that substances can be divided into 10 kinds.
The basic idea is pretty simple. Some substances have time-reversal symmetry: they would look the same, even on the atomic level, if you made a movie of them and ran it backwards. Some don’t — these are more rare, like certain superconductors made of yttrium barium copper oxide! Time reversal symmetry is described by an antiunitary operator $T$ that squares to 1 or to -1: please take my word for this, it’s a quantum thing. So, we get 3 choices, which are listed in the chart under $T$ as 1, -1, or 0 (no time reversal symmetry).
Similarly, some substances have charge conjugation symmetry, meaning a symmetry where we switch particles and holes: places where a particle is missing. The ‘particles’ here can be rather abstract things, like phonons - little vibrations of sound in a substance, which act like particles — or spinons — little vibrations in the lined-up spins of electrons. Basically any way that something can wave can, thanks to quantum mechanics, act like a particle. And sometimes we can switch particles and holes, and a substance will act the same way!
Like time reversal symmetry, charge conjugation symmetry is described by an antiunitary operator $C$ that can square to 1 or to -1. So again we get 3 choices, listed in the chart under $C$ as 1, -1, or 0 (no charge conjugation symmetry).
So far we have 3 × 3 = 9 kinds of matter. What is the tenth kind?
Some kinds of matter don’t have time reversal or charge conjugation symmetry, but they’re symmetrical under the combination of time reversal and charge conjugation! You switch particles and holes and run the movie backwards, and things look the same!
In the chart they write 1 under the $S$ when your matter has this combined symmetry, and 0 when it doesn’t. So, “0 0 1” is the tenth kind of matter (the second row in the chart).
This is just the beginning of an amazing story. Since then people have found substances called topological insulators that act like insulators in their interior but conduct electricity on their surface. We can make 3-dimensional topological insulators, but also 2-dimensional ones (that is, thin films) and even 1-dimensional ones (wires). And we can theorize about higher-dimensional ones, though this is mainly a mathematical game.
So we can ask which of the 10 kinds of substance can arise as topological insulators in various dimensions. And the answer is: in any particular dimension, only 5 kinds can show up. But it’s a different 5 in different dimensions! This chart shows how it works for dimensions 1 through 8. The kinds that can’t show up are labelled 0.
If you look at the chart, you’ll see it has some nice patterns. And it repeats after dimension 8. In other words, dimension 9 works just like dimension 1, and so on.
If you read some of the papers I listed, you’ll see that the $\mathbb{Z}$’s and $\mathbb{Z}_2$’s in the chart are the homotopy groups of the ten classical series of compact symmetric spaces. The fact that dimension $n+8$ works like dimension $n$ is called Bott periodicity.
Furthermore, the stuff about operators $T$, $C$ and $S$ that square to 1, -1 or don’t exist at all is closely connected to the classification of associative real super division algebras. It all fits together.
Super division algebras
In 2005, Todd Trimble wrote a short paper called The super Brauer group and super division algebras.
In it, he gave a quick way to classify the associative real super division algebras: that is, finite-dimensional associative real $\mathbb{Z}_2$-graded algebras having the property that every nonzero homogeneous element is invertible. The result was known, but I really enjoyed Todd’s effortless proof.
However, I didn’t notice that there are exactly 10 of these guys. Now this turns out to be a big deal. For each of these 10 algebras, the representations of that algebra describe ‘types of matter’ of a particular kind — where the 10 kinds are the ones I explained above!
So what are these 10 associative super division algebras?
3 of them are purely even, with no odd part: the usual associative division algebras $\mathbb{R}, \mathbb{C}$ and $\mathbb{H}$.
7 of them are not purely even. Of these, 6 are Morita equivalent to the real Clifford algebras $Cl_1, Cl_2, Cl_3, Cl_5, Cl_6$ and $Cl_7$. These are the superalgebras generated by 1, 2, 3, 5, 6, or 7 odd square roots of -1.
Now you should have at least two questions:
What’s ‘Morita equivalence’? — and even if you know, why should it matter here? Two algebras are Morita equivalent if they have equivalent categories of representations. The same definition works for superalgebras, though now we look at their representations on super vector spaces ($\mathbb{Z}_2$-graded vector spaces). For physics what we really care about is the representations of an algebra or superalgebra: as I mentioned, those are ‘types of matter’. So, it makes sense to count two superalgebras as ‘the same’ if they’re Morita equivalent.
1, 2, 3, 5, 6, and 7? That’s weird — why not 4? Well, Todd showed that $Cl_4$ is Morita equivalent to the purely even super division algebra $\mathbb{H}$. So we already had that one on our list. Similarly, why not 0? $Cl_0$ is just $\mathbb{R}$. So we had that one too.
Representations of Clifford algebras are used to describe spin-1/2 particles, so it’s exciting that 8 of the 10 associative real super division algebras are Morita equivalent to real Clifford algebras.
But I’ve already mentioned one that’s not: the complex numbers, $\mathbb{C}$, regarded as a purely even algebra. And there’s one more! It’s the complex Clifford algebra $\mathbb{C}\mathrm{l}_1$. This is the superalgebra you get by taking the purely even algebra $\mathbb{C}$ and throwing in one odd square root of -1.
As soon as you hear that, you notice that the purely even algebra $\mathbb{C}$ is the complex Clifford algebra $\mathbb{C}\mathrm{l}_0$. In other words, it’s the superalgebra you get by taking the purely even algebra $\mathbb{C}$ and throwing in no odd square roots of -1.
More connections
At this point things start fitting together:
You can multiply Morita equivalence classes of algebras using the tensor product of algebras: $[A] \otimes [B] = [A \otimes B]$. Some equivalence classes have multiplicative inverses, and these form the Brauer group. We can do the same thing for superalgebras, and get the super Brauer group. The super division algebras Morita equivalent to $Cl_0, \dots , Cl_7$ serve as representatives of the super Brauer group of the real numbers, which is $\mathbb{Z}_8$. I explained this in week211 and further in week212. It’s a nice purely algebraic way to think about real Bott periodicity!
As we’ve seen, the super division algebras Morita equivalent to $Cl_0$ and $Cl_4$ are a bit funny. They’re purely even. So they serve as representatives of the plain old Brauer group of the real numbers, which is $\mathbb{Z}_2$.
On the other hand, the complex Clifford algebras $\mathbb{C}\mathrm{l}_0 = \mathbb{C}$ and $\mathbb{C}\mathrm{l}_1$ serve as representatives of the super Brauer group of the complex numbers, which is also $\mathbb{Z}_2$. This is a purely algebraic way to think about complex Bott periodicity, which has period 2 instead of period 8.
Meanwhile, the purely even $\mathbb{R}, \mathbb{C}$ and $\mathbb{H}$ underlie Dyson’s ‘three-fold way’, which I explained in detail here:
- John Baez, Division algebras and quantum theory.
Briefly, if you have an irreducible unitary representation of a group on a complex Hilbert space $H$, there are three possibilities:
The representation is isomorphic to its dual via an invariant symmetric bilinear pairing $g : H \times H \to \mathbb{C}$. In this case it has an invariant antiunitary operator $J : H \to H$ with $J^2 = 1$. This lets us write our representation as the complexification of a real one.
The representation is isomorphic to its dual via an invariant antisymmetric bilinear pairing $\omega : H \times H \to \mathbb{C}$. In this case it has an invariant antiunitary operator $J : H \to H$ with $J^2 = -1$. This lets us promote our representation to a quaternionic one.
The representation is not isomorphic to its dual. In this case we say it’s truly complex.
In physics applications, we can take $J$ to be either time reversal symmetry, $T$, or charge conjugation symmetry, $C$. Studying either symmetry separately leads us to Dyson’s three-fold way. Studying them both together leads to the ten-fold way!
So the ten-fold way seems to combine in one nice package:
- real Bott periodicity,
- complex Bott periodicity,
- the real Brauer group,
- the real super Brauer group,
- the complex super Brauer group, and
- the three-fold way.
I could throw ‘the complex Brauer group’ into this list, because that’s lurking here too, but it’s the trivial group, with $\mathbb{C}$ as its representative.
There really should be a better way to understand this. Here’s my best attempt right now.
The set of Morita equivalence classes of finite-dimensional real superalgebras gets a commutative monoid structure thanks to direct sum. This commutative monoid then gets a commutative rig structure thanks to tensor product. This commutative rig — let’s call it $\mathfrak{R}$ — is apparently too complicated to understand in detail, though I’d love to be corrected about that. But we can peek at pieces:
We can look at the group of invertible elements in $\mathfrak{R}$ — more precisely, elements with multiplicative inverses. This is the real super Brauer group $\mathbb{Z}_8$.
We can look at the sub-rig of $\mathfrak{R}$ coming from semisimple purely even algebras. As a commutative monoid under addition, this is $\mathbb{N}^3$, since it’s generated by $\mathbb{R}, \mathbb{C}$ and $\mathbb{H}$. This commutative monoid becomes a rig with a funny multiplication table, e.g. $\mathbb{C} \otimes \mathbb{C} = \mathbb{C} \oplus \mathbb{C}$. This captures some aspects of the three-fold way.
We should really look at a larger chunk of the rig $\mathfrak{R}$, that includes both of these chunks. How about the sub-rig coming from all semisimple superalgebras? What’s that?
And here’s another question: what’s the relation to the 10 classical families of compact symmetric spaces? The short answer is that each family describes a family of possible Hamiltonians for one of our 10 kinds of matter. For a more detailed answer, I suggest reading Gregory Moore’s Quantum symmetries and compatible Hamiltonians. But if you look at this chart by Ryu et al, you’ll see these families involve a nice interplay between $\mathbb{R}, \mathbb{C}$ and $\mathbb{H}$, which is what this story is all about:
The families of symmetric spaces are listed in the column “Hamiltonian”.
All this stuff is fitting together more and more nicely! And if you look at the paper by Freed and Moore, you’ll see there’s a lot more involved when you take the symmetries of crystals into account. People are beginning to understand the algebraic and topological aspects of condensed matter much more deeply these days.
The list
Just for the record, here are all 10 associative real super division algebras. 8 are Morita equivalent to real Clifford algebras:
$Cl_0$ is the purely even division algebra $\mathbb{R}$.
$Cl_1$ is the super division algebra $\mathbb{R} \oplus \mathbb{R}e$, where $e$ is an odd element with $e^2 = -1$.
$Cl_2$ is the super division algebra $\mathbb{C} \oplus \mathbb{C}e$, where $e$ is an odd element with $e^2 = -1$ and $e i = -i e$.
$Cl_3$ is the super division algebra $\mathbb{H} \oplus \mathbb{H}e$, where $e$ is an odd element with $e^2 = 1$ and $e i = i e, e j = j e, e k = k e$.
$Cl_4$ is $\mathbb{H}[2]$, the algebra of $2 \times 2$ quaternionic matrices, given a certain $\mathbb{Z}_2$-grading. This is Morita equivalent to the purely even division algebra $\mathbb{H}$.
$Cl_5$ is $\mathbb{H}[2] \oplus \mathbb{H}[2]$ given a certain $\mathbb{Z}_2$-grading. This is Morita equivalent to the super division algebra $\mathbb{H} \oplus \mathbb{H}e$ where $e$ is an odd element with $e^2 = -1$ and $e i = i e, e j = j e, e k = k e$.
$Cl_6$ is $\mathbb{C}[4] \oplus \mathbb{C}[4]$ given a certain $\mathbb{Z}_2$-grading. This is Morita equivalent to the super division algebra $\mathbb{C} \oplus \mathbb{C}e$ where $e$ is an odd element with $e^2 = 1$ and $e i = -i e$.
$Cl_7$ is $\mathbb{R}[8] \oplus \mathbb{R}[8]$ given a certain $\mathbb{Z}_2$-grading. This is Morita equivalent to the super division algebra $\mathbb{R} \oplus \mathbb{R}e$ where $e$ is an odd element with $e^2 = 1$.
$Cl_{n+8}$ is Morita equivalent to $Cl_n$ so we can stop here if we’re just looking for Morita equivalence classes, and there also happen to be no more super division algebras down this road. It is nice to compare $Cl_n$ and $Cl_{8-n}$: there’s a nice pattern here.
The remaining 2 real super division algebras are complex Clifford algebras:
$\mathbb{C}\mathrm{l}_0$ is the purely even division algebra $\mathbb{C}$.
$\mathbb{C}\mathrm{l}_1$ is the super division algebra $\mathbb{C} \oplus \mathbb{C} e$, where $e$ is an odd element with $e^2 = -1$ and $e i = i e$.
In the last one we could also say “with $e^2 = 1$” — we’d get something isomorphic, not a new possibility.
Ten dimensions of string theory
Oh yeah — what about the 10 dimensions in string theory? Are they really related to the ten-fold way?
It seems weird, but I think the answer is “yes, at least slightly”.
Remember, 2 of the dimensions in 10d string theory are those of the string worldsheet, which is a complex manifold. The other 8 are connected to the octonions, which in turn are connected to the 8-fold periodicity of real Clifford algebra. So the 8+2 split in string theory is at least slightly connected to the 8+2 split in the list of associative real super division algebras.
This may be more of a joke than a deep observation. After all, the 8 dimensions of the octonions are not individual things with distinct identities, as the 8 super division algebras coming from real Clifford algebras are. So there’s no one-to-one correspondence going on here, just an equation between numbers.
Still, there are certain observations that would be silly to resist mentioning.
The following concept seems to have been reinvented a bunch of times by a bunch of people, and every time they give it a different name.
Definition: Let $C$ be a category with pullbacks and a class of weak equivalences. A morphism $f:A\to B$ is a [insert name here] if the pullback functor $f^\ast:C/B \to C/A$ preserves weak equivalences.
In a right proper model category, every fibration is one of these. But even in that case, there are usually more of these than just the fibrations. There is of course also a dual notion in which pullbacks are replaced by pushouts, and every cofibration in a left proper model category is one of those.
What should we call them?
The names that I’m aware of that have so far been given to these things are:
sharp map, by Charles Rezk. This is a dualization of the terminology flat map used for the dual notion by Mike Hopkins (I don’t know a reference, does anyone?). I presume that Hopkins’ motivation was that a ring homomorphism is flat if tensoring with it (which is the pushout in the category of commutative rings) is exact, hence preserves weak equivalences of chain complexes.
However, “flat” has the problem of being a rather overused word. For instance, we may want to talk about these objects in the canonical model structure on $Cat$ (where in fact it turns out that every such functor is a cofibration), but flat functor has a very different meaning. David White has pointed out that “flat” would also make sense to use for the monoid axiom in monoidal model categories.
right proper, by Andrei Radulescu-Banu. This is presumably motivated by the above-mentioned fact that fibrations in right proper model categories are such. Unfortunately, proper map also has another meaning.
$h$-fibration, by Berger and Batanin. This is presumably motivated by the fact that “$h$-cofibration” has been used by May and Sigurdsson for an intrinsic notion of cofibration in topologically enriched categories, that specializes in compactly generated spaces to closed Hurewicz cofibrations, and pushouts along the latter preserve weak homotopy equivalences. However, it makes more sense to me to keep “$h$-cofibration” with May and Sigurdsson’s original meaning.
Grothendieck $W$-fibration (where $W$ is the class of weak equivalences on $C$), by Ara and Maltsiniotis. Apparently this comes from unpublished work of Grothendieck. Here I guess the motivation is that these maps are “like fibrations” and are determined by the class $W$ of weak equivalences.
Does anyone know of other references for this notion, perhaps with other names? And any opinions on what the best name is? I’m currently inclined towards “$W$-fibration” mainly because it doesn’t clash with anything else, but I could be convinced otherwise.
Nope, this isn’t about gender or social balance in math departments, important as those are. On Friday, Glasgow’s interdisciplinary Boyd Orr Centre for Population and Ecosystem Health — named after the whirlwind of Nobel-Peace-Prize-winning scientific energy that was John Boyd Orr — held a day of conference on diversity in multiple biological senses, from the large scale of rainforest ecosystems right down to the microscopic scale of pathogens in your blood.
I used my talk (slides here) to argue that the concept of diversity is fundamentally a mathematical one, and that, moreover, it is closely related to core mathematical quantities that have been studied continuously since the time of Euclid.
In a sense, there’s nothing new here: I’ve probably written about all the mathematical content at least once before on this blog. But in another sense, it was a really new talk. I had to think very hard about how to present this material for a mixed group of ecologists, botanists, epidemiologists, mathematical modellers, and so on, all of whom are active professional scientists but some of whom haven’t studied mathematics since high school. That’s why I began the talk with an explanation of how pure mathematics looks these days.
I presented two pieces of evidence that diversity is intimately connected to ancient, fundamental mathematical concepts.
The first piece of evidence is a connection at one remove, and schematically looks like this:
maximum diversity $\leftrightarrow$ magnitude $\leftrightarrow$ intrinsic volumes
The left leg is a theorem asserting that when you have a collection of species and some notion of inter-species distance (e.g. genetic distance), the maximum diversity over all possible abundance distributions is closely related to the magnitude of the metric space that the species form.
The right leg is a conjecture by Simon Willerton and me. It states that for convex subsets of $\mathbb{R}^n$, magnitude is closely related to perimeter, volume, surface area, and so on. When I mentioned “quantities that have been studied continuously since the time of Euclid”, that’s what I had in mind. The full-strength conjecture requires you to know about “intrinsic volumes”, which are the higher-dimensional versions of these quantities. But the 2-dimensional conjecture is very elementary, and described here.
The second piece of evidence was a very brief account of a theorem of Mark Meckes, concerning fractional dimension of subsets $X$ of $\mathbb{R}^n$ (slide 15, and Corollary 7.4 here). One of the standard notions of fractional dimension is Minkowski dimension (also known by other names such as Kolmogorov or box-counting dimension). On the other hand, the rate of growth of the magnitude function $t \mapsto \left| t X \right|$ is also a decent notion of dimension. Mark showed that they are, in fact, the same. Thus, for any compact $X \subseteq \mathbb{R}^n$ with a well-defined Minkowski dimension $dim X$, there are positive constants $c$ and $C$ such that
$c t^{dim X} \leq \left| t X \right| \leq C t^{dim X}$
for all $t \gg 0$.
One remarkable feature of the proof is that it makes essential use of the concept of maximum diversity, where diversity is measured in precisely the way that Christina Cobbold and I came up with for use in ecology.
So, work on diversity has already got to the stage where application-driven problems are enabling advances in pure mathematics. This is a familiar dynamic in older fields of application such as physics, but I think the fact that this is already happening in the relatively new field of diversity theory is a promising sign. It suggests that aside from all the applications, the mathematics of diversity has a lot to give pure mathematics itself.
Next April, John Baez and friends are running a three-day investigative workshop on Entropy and information in biological systems at the National Institute for Mathematical and Biological Synthesis in Knoxville, Tennessee. I hope this will provide a good opportunity for deepening our understanding of the interplay between mathematics and diversity (which is closely related to entropy and information). If you’re interested in coming, you can apply online.
The Notices of the AMS has just published the second in its series “Mathematicians discuss the Snowden revelations”. (The first was here.) The introduction to the second article cites this blog for “a discussion of these issues”, but I realized that the relevant posts might be hard for visitors to find, scattered as they are over the last eight months.
So here, especially for Notices readers, is a roundup of all the posts and discussions we’ve had on the subject. In reverse chronological order:
- Should mathematicians cooperate with GCHQ? Part 3
- Should mathematicians cooperate with GCHQ? Part 2
- New Scientist article
- Big data power
- Should mathematicians cooperate with GCHQ?
- The deteriorating relationship between mathematicans and the NSA
- The Electronic Frontier Foundation at the joint meetings
- Academics against mass surveillance
- Severing ties with the NSA.
Here’s another post asking for a reference to stuff that should be standard. (The last ones succeeded wonderfully, so thanks!)
I should be able to say
$C$ is the symmetric monoidal category with the following presentation: it’s generated by objects $x$ and $y$ and morphisms $L: x \otimes y \to y$ and $R: y \otimes x \to y$, with the relation
$(L \otimes 1)(1 \otimes R)\alpha_{x,y,x} = (1 \otimes R)(L \otimes 1)$
Here $\alpha$ is the associator. Don’t worry about the specific example: I’m just talking about a presentation of a symmetric monoidal category using generators and relations.
Right now Jason Erbele and I have proved that a certain symmetric monoidal category has a certain presentation. I defined what this meant myself. But this has got to be standard, right?
So whom do we cite?
You are likely to mention PROPs, and that’s okay if they get the job done. But I don’t actually know a reference on describing PROPs by generators and relations. Furthermore, our actual example is not a strict symmetric monoidal category. It’s equivalent to one, of course, but it would be nice to have a concept of `presentation’ that specified the symmetric monoidal category only up to equivalence, not isomorphism. In other words, this is a ultimately a 2-categorical concept, not a 1-categorical one.
If it weren’t for this, we could use the fact that PROPs are models of an algebraic theory. But our paper is actually about control theory—a branch of engineering—so I’d rather avoid showing off, if possible.
The International Category Theory Conference will take place this coming week, Sunday June 29 - Saturday July 4th, in (old) Cambridge. To those readers who will be in attendance, I hope you’ll stop by to visit the Kan Extension Seminar, which will present a series of eight 15-minute expository talks this coming Sunday (June 29) at Winstanley Lecture Theatre in Trinity College.
We will have tea starting at 2pm with the first talks to commence at 2:30. There will be a short break around 3:50pm with the second series of talks to begin at 4:10. The talks should finish around 5:30, at which point we will walk together to the welcome reception for the CT.
Please join us! We have a fantastic line-up of talks that promise to be interesting and yet understandable with very little assumed background. I’ve listed the speakers and titles below the break. Abstracts and more information can be found here.
2:30-3:50pm
- Fosco Loregian - For the sake of well-completeness
- Tom Avery - The Cauchy completion is the Cauchy completion
- Alexander Campbell - An Exegesis of Yoneda Structures
- Sean Moss - On “On a topological topos”
4:10pm-5:30pm
- Christina Vasilakopoulou - Comma-objects in 2-categories
- Tim Campion - D-Accessible Categories and Free Colimit Completions
- Alex Corner - Coherence for categorical structures
- Clive Newstead - Overview of Lawvere’s ETCS
Please don’t hesitate to get in touch with questions. I hope to see you there!
I’ve just come back from the big annual-ish category theory meeting, Category Theory 2014 in Cambridge, also attended by Café hosts Emily and Simon. The talk I gave there was called The categorical origins of Lebesgue integration — click for slides — and I’ll briefly describe it now.
There are two theorems.
Theorem A The Banach space $L^1[0, 1]$ has a simple universal property. This leads to a unique characterization of integration on $[0, 1]$.
Theorem B The functor $L^1:$ (finite measure spaces) $\to$ (Banach spaces) has a simple universal property. This leads to a unique characterization of integration on finite measure spaces.
The talk’s pretty simple, and I don’t think I can summarize it much better than by repeating the abstract, which went like this:
Lebesgue integration is a basic, essential component of analysis. Yet most definitions of Lebesgue integrability and integration are rather complicated, typically depending on a series of preliminary definitions. For instance, one of the most popular approaches involves the class of functions that can be expressed as an almost everywhere pointwise limit of an increasing sequence of step functions. Another approach constructs the space of Lebesgue-integrable functions as the completion of the normed vector space of continuous functions; but this depends on already having the definition of integration for continuous functions.
So we might wish for a short, direct description of Lebesgue integrability that reflects its fundamental nature. I will present two theorems achieving this.
The first characterizes the space $L^1[0, 1]$ by a simple universal property, entirely bypassing all the usual preliminary definitions. It tells us that once we accept two concepts — Banach space and the mean of two numbers — then the concept of Lebesgue integrability is inevitable. Moreover, this theorem not only characterizes the Lebesgue integrable functions on $[0, 1]$; it also characterizes Lebesgue integration of such functions.
The second theorem characterizes the functor $L^1$ from measure spaces to Banach spaces, again by a simple universal property. Again, the theorem characterizes integration, as well as integrability, of functions on an arbitrary measure space.
Update (6 July 2014) A much shorter version of this post appears in the July edition of the LMS newsletter, along with a further opinion from Trevor Jarvis (Hull).
In April, the newsletter of the London Mathematical Society published my piece “Should mathematicians cooperate with GCHQ?”, which mostly consisted of factual statements based on the Snowden leaks, followed by the mild opinion that as individuals and institutions, we can choose whether to give GCHQ our cooperation. Two mathematicians associated with GCHQ, Richard Pinch and Malcolm MacCallum, have now replied. I will address their points, then make some suggestions for mathematics departments in the post-Snowden era.
Real, not-made-up
logo of US spy satellite
Neither Pinch nor MacCallum disputes any individual factual statement that I made. (In both my earlier article and this one, every factual statement is hyperlinked to supporting evidence.) Neither seriously engages with the fact that the intelligence agencies are collecting not just terrorists’ communications, but everyone’s — by its own account, GCHQ intercepts over 50 billion communication events every day. Neither justifies the total surveillance philosophy pithily described by GCHQ’s closest partner, the US National Security Agency:
Collect it all. Sniff it all. Process it all. Know it all. Partner it all. Exploit it all.
In response to all this, Pinch and MacCallum say, effectively: “Trust us.”
Fortunately, no one needs to trust them, or me, because we now have plentiful documentary evidence of what GCHQ and its partners are doing. So we can simply test claims against the evidence.
For example, on the one hand, Pinch quotes GCHQ director Iain Lobban’s claim that if his staff “were asked to snoop, I would not have the workforce. They would leave the building.” On the other, GCHQ’s own documents detail how it surreptitiously harvested webcam images from millions of ordinary people suspected of no crime, using a system that “does not select but simply collects in bulk.” The documents note how many of the secretly captured images are sexually explicit. If that is not “snooping”, what is?
Although neither Pinch nor MacCallum disputes any factual statement that I made, MacCallum does dispute one I didn’t make, writing: “Both GCHQ and its mathematics staff will be amused by the accusation that mathematicians there have little idea how their work will be used.” In fact, I said “mathematicians working for GCHQ may have little idea …”, and I stand by that: first, for the reason that MacCallum immediately concedes — that information-sharing within GCHQ is limited by “need to know” — and second, based on conversations with mathematicians who have worked for GCHQ over sabbaticals or summers. Some of those mathematicians now regret ever having been involved, having had no idea that they were working for an agency of mass surveillance.
Slide
from NSA presentation to GCHQ and other partners, 2011
We all want spies to spy on known or suspected terrorists. We all agree that the secret services must have secrets. We all support targeted surveillance, under careful legal constraints. But what is at issue here is mass surveillance: the monitoring of everyone, all the time.
Pinch and MacCallum blur that distinction. Thus, MacCallum cites the claim of MI5 head Andrew Parker that the intelligence agencies and police have disrupted many “plots towards terrorism”. But Parker did not say this was due to any mass surveillance programme; on the contrary, he added that almost all the plots came from a known pool of several thousand individuals. Even more tangentially, MacCallum notes the usefulness of phone billing records in criminal trials; but these are obtained from phone companies, not state surveillance of any kind.
MacCallum accuses me of making “multiple contentious statements”, but is careless with the facts himself. As well as mischaracterizing what I wrote about mathematicians working for GCHQ, he is inaccurate when reporting Andrew Parker’s claim about disrupted plots. What Parker actually said was that since July 2005:
I think … there have been 34 plots towards terrorism that have been disrupted in this country, at all sizes and stages. … Of that 34, most of them, the vast majority, have been disrupted by active detection and intervention by the Agencies and the police. One or two of them, a small number, have failed because they just failed. The plans did not come together.
MacCallum renders this as:
I was pleased to hear, in the public session Richard Pinch’s response refers to, that 34 terrorist plots had been thwarted in recent years by the intelligence agencies.
This is inaccurate in at least three respects. First, Parker’s words were “Agencies and the police”, not “intelligence agencies”. Perhaps many plots were disrupted by the police alone. Second, MacCallum forgets to subtract from the 34 the plots that failed of their own accord. Third and most importantly, Parker used the vague form of words “plots towards terrorism”, not “terrorist plots”. It is far from clear what he intended this phrase to encompass (“towards”?), especially in a country where the looseness of the legal definition of terrorism has been a longstanding source of concern, and where anti-terrorism laws have been used to prevent everything from photographing the police to peaceful protest to heckling. Whether the true figure is 3 or 300 makes little difference to the argument, since the disruptions were not claimed to be due to mass surveillance anyway. But when MacCallum is so careless with simple, easily verifiable facts, why should we trust those of his claims that are unverifiable?
Slide on the PRISM programme, outlining how the largest internet
companies provide their users’ data to the NSA
If mass surveillance was known to be an effective tool for preventing terrorism, we could debate whether it was a price worth paying. But the intelligence agencies have been unable to point to success stories so far. In a US court ruling, federal judge Richard Leon noted the “utter lack of evidence that a terrorist attack has been prevented” by the NSA’s bulk data collection (despite the government having been able to submit classified evidence to him). And a CIA report on 9/11 concluded that the agencies had enough information to prevent the attacks, but failed to use it effectively.
At the heart of this discussion is trust. Through systematically monitoring our phone calls, emails, web browsing, location, and so on, the world’s most powerful intelligence agencies hold intimate personal information on much of the population. They have almost limitless power to spy on us. Do we trust them to use that power responsibly?
GCHQ insiders such as MacCallum and Pinch presumably do. They might say that the agencies work hard to prevent terrorism, and are not interested in the mundane details of your life. But between those extremes, there is a large grey area — the area where activism, protest and civil disobedience lie, the area where powers are most likely to be abused.
There is strong evidence that when surveillance powers are exercised in secret, abuse is inevitable: from the FBI recording Martin Luther King’s extramarital affairs and attempting to incite him to suicide over it, to present-day GCHQ undermining the online activism of people not suspected of any crime, to the NSA gathering the pornographic web-browsing habits of Muslims who it explicitly notes are not terrorists. Via GCHQ and NSA bulk collection programmes, agency analysts can access almost anyone’s email. Inevitably, this power has been abused too, with analysts exploiting it to read the mail of their own ex-partners and even Bill Clinton.
Page from NSA guide to the XKeyScore programme, showing staff how
to read an arbitrary person’s email
Perhaps the secret services could be restrained from abusing their powers if there were a really strong external body enforcing strict rules. Insiders such as Pinch and MacCallum may perceive the existing oversight of GCHQ as strict, but few outsiders do. For example, the GCHQ oversight system was recently excoriated by a parliamentary committee as “not fit for purpose” and “embarrassing”. Even GCHQ’s own documents show it using its lax oversight as a selling point to the NSA. According to a senior GCHQ lawyer, “we have a light oversight regime compared with the US” — where for context, the NSA is regulated by a secret court at which only the agencies’ side of the case is represented, without opposition, and which rejects just 1 in 3000 of the NSA’s surveillance requests.
Neither MacCallum nor Pinch addresses anything we have learned from the Snowden documents; they appear to be forbidden to join the conversation that the rest of the world is having. GCHQ routinely refuses to discuss matters of clear public interest that have been all over the news for the last year. Even the NSA is more open, being obliged to submit to genuine adversarial questioning at senate hearings. For instance, it was at one such hearing that the NSA chief conceded that the number of terrorist plots thwarted by bulk surveillance was not 54, as repeatedly claimed, but at most one or two (his best example being a man found giving an alleged terrorist group $8500). On both sides of the Atlantic, senior politicians on national security committees have complained that they were never even informed of the existence of the mass surveillance programmes, let alone authorizing them. We are not in democratic control.
Heads of mathematics departments would probably like to “stay out of politics”. This is wishing for the impossible. It is illogical to maintain that dissenting from cooperation with GCHQ is a political act, but assenting is not. A head of department who runs a working relationship with GCHQ is engaged in a political act just as surely as one who declines.
The very least HoDs can do is to consult openly with their departments. The risks of not doing so have recently been illustrated in London, where Imperial, King’s and UCL have set up joint postdoctoral positions with GCHQ’s Heilbronn Institute. In at least one case, this was done without consulting the department about the ethical implications, causing later resentment and anger. GCHQ may want to normalize the presence of its employees within the academic community, but not all of our community accepts this. It is no longer realistic for HoDs to treat GCHQ as if it was just another partner. Schools of medicine and psychology must routinely assess the ethical risks of their work. Perhaps it is time for mathematics departments to draw up their own ethical policies.
Mathematicians have always had to navigate difficult ethical territory, from ancient military applications to the role of quants in the banking crash. But now that we have detailed documentary evidence of what kind of activities we are supporting when we collaborate with the secret services, we can use it to have a properly evidence-based discussion. Instead of seeking refuge in the comforting myth of political neutrality, we should take responsibility for our actions.
At long last, the following two papers are up:
- Kate Ponto and Mike Shulman, The linearity of traces in monoidal categories and bicategories
- Kate Ponto and Mike Shulman, The linearity of fixed-point invariants
I’m super excited about these, and not just because I like the results. Firstly, these papers are sort of a culmination of a project that began around 2006 and formed a large part of my thesis. Secondly, this project is an excellent “success story” for a methodology of “applied category theory”: taking seriously the structure that we see in another branch of mathematics, but studying it using honest category-theoretic tools and principles.
For these reasons, I want to tell you about these papers by way of their history. (I’ve mentioned some of their ingredients before when I blogged about previous papers in this series, but I won’t assume here you know any of it.)
To begin with, recall that an object $X$ of a symmetric monoidal category is dualizable if, when regarded as a 1-cell in the associated one-object bicategory, it has an adjoint $D X$. Then any endomorphism $f:X\to X$ has a trace defined by
$I \xrightarrow{\eta} X \otimes D X \xrightarrow{f\otimes 1} X\otimes D X \xrightarrow{\cong} D X \otimes X \xrightarrow{\epsilon} I.$
In $Vect$, the dualizable objects are the finite-dimensional ones, traces reproduce the usual trace of a matrix (incarnated as a $1\times 1$ matrix), and in particular $tr(1_X) = dim(X)$. In the stable homotopy category, this is Spanier-Whitehead duality, traces produce the Lefschetz number $L(f)$ (incarnated as the degree of a self-map of a sphere), and we have $L(1_X) = \chi(X)$, the Euler characteristic. The Lefschetz fixed point theorem follows by abstract nonsense.
The recent part of the story began in 2001, when Peter May wrote “The additivity of traces in triangulated categories”. The Euler characteristic (and Lefschetz number) are additive: if $X$ is a cell complex and $A\subseteq X$ a subcomplex, then $\chi(X) = \chi(A) + \chi(X/A)$ and $L(f) = L(f|_A) + L(f/A)$. Peter showed an abstract version of this: if a symmetric monoidal category is compatibly triangulated, then for any distinguished triangle $X\to Y\to Z\to \Sigma X$, we have $\chi(Y) = \chi(X) + \chi(Z)$.
A few years later, Peter and Johann Sigurdsson realized that “Costenoble-Waner duality” for parametrized spaces was naturally about adjunctions in a bicategory whose objects were topological spaces and whose 1-cells from $A$ to $B$ are spectra “parametrized over $A\times B$”. (The 2-cells are fiberwise stable maps; note the conspicuous absence of continuous maps of base spaces.) Peter thus wondered whether additivity generalized to bicategories. In the book that he and Johann wrote, they generalized some of his axioms for triangulated monoidal categories to “locally triangulated” bicategories, but the final axiom (TC5) used the symmetry, which doesn’t make sense in a bicategory. It was also not clear how to generalize “traces”, since the definition of trace also uses symmetry.
Enter Kate Ponto, who was studying topological fixed-point theory. This subject “begins” with the Lefschetz fixed point theorem, but continues with more refined invariants such as the Reidemeister trace, which supports a converse to this theorem (under suitable hypotheses). One definition of the Reidemeister trace uses the Hattori-Stallings trace, which is a sort of trace for matrices over a noncommutative ring: you’d like to sum along the diagonal, but the result is basis-dependent until you map it from $R$ into the quotient abelian group $\langle\langle R \rangle\rangle = R / (r s \sim s r)$. Kate realized that the Hattori-Stallings trace, and hence also the Reidemeister trace, was a sort of “bicategorical trace” that she was able to define for endo-2-cells of dualizable 1-cells in any bicategory equipped with some extra structure that she named a shadow.
Pleasingly to fans of the microcosm principle, a shadow on a bicategory $\mathbf{B}$ is a “categorified trace”, consisting of functors $\langle\langle-\rangle\rangle:\mathbf{B}(A,A) \to \mathbf{T}$ that are “cyclic up to isomorphism”: $\langle\langle X \odot Y \rangle\rangle \cong \langle\langle Y \odot X \rangle\rangle$ plus some coherence axioms. Given this, if $X:A\to B$ has an adjoint $D X$ and $f:X\to X$, Kate defined its trace $\tr(f)$ to be $\langle\langle U_A \rangle\rangle \xrightarrow{\eta} \langle\langle X \odot D X\rangle \xrightarrow{f\odot 1} \langle\langle X\odot D X \rangle\rangle \xrightarrow{\cong} \langle\langle D X \odot X \rangle\rangle \xrightarrow{\epsilon} \langle\langle U_B \rangle\rangle$ where $U_A$, $U_B$ are the unit 1-cells. I blogged about this here. So Kate had solved half of the problem of generalizing additivity to bicategories.
At about the same time, I was intrigued by a different aspect of Peter and Johann’s bicategory. Parametrized spaces and spectra can be “pulled back” and “pushed forward” along maps of base spaces. Moreover, pushforward and “copushforward” generalize homology and cohomology, hence should preserve duality. But how can we show this abstractly, since the maps between base spaces are missing from the bicategory of parametrized spectra? Peter and Johann solved this with “base change objects”: for any continuous map $f:A\to B$ they defined spectra $S_f$ and ${}_f S$ over $B\times A$ and $A\times B$ such that composing with them was equivalent to pulling back and pushing forward. Moreover, $S_f$ and ${}_f S$ are dual; thus, since adjunctions compose, if $X$ is Costenoble-Waner dualizable, so is its pushforward to a point $(\pi_A)_! X$. This clean and easy argument, when they noticed it, replaced a long and messy calculation.
I, however, was unsatisfied with the fact that the maps of base spaces were not actually present in the bicategory, leading me to invent framed bicategories, which are actually double categories with extra properties. The horizontal arrows give it an underlying bicategory, while the vertical arrows supply the missing morphisms, and the additional 2-cells let us characterize the base change objects with a universal property. Soon, I realized that a “framing” on a bicategory was equivalent to giving pseudofunctorial “base change objects” with adjoints, a structure which had been defined by Richard Wood under the name proarrow equipment. However, the double-categorical viewpoint has certain advantages: e.g. it looks a little less ad hoc, it makes it easier to define functors and transformations between such structures (this had already been observed by Dominic Verity), and it generalizes to situations where the horizontal 1-cells can’t be composed.
Another thing that bothered me about Peter and Johann’s bicategory was that, to be honest, they hadn’t finished constructing it. They defined the composition and units and constructed associativity and unit isomorphisms, but didn’t prove the coherence axioms. In order to remedy this cleanly and abstractly, I isolated the properties of parametrized spectra that were necessary for the construction, leading to the notion of monoidal fibration or indexed monoidal category: a pseudofunctor $\mathbf{C}:S^{op} \to MonCat$. The only assumptions needed beyond this are that $S$ is cartesian monoidal and that the “pullback” functors $f^\ast:\mathbf{C}(B) \to \mathbf{C}(A)$ have “pushforward” Hopf left adjoints $f_!$ satisfying the Beck-Chevalley condition for pullback squares (or homotopy pullback squares). Thus, from any such $\mathbf{C}$ we can construct a (framed) bicategory $Fr(\mathbf{C})$, whose objects are those of $S$ and with $Fr(\mathbf{C})(A,B)=\mathbf{C}(A\times B)$. This was the main result of Framed bicategories and monoidal fibrations.
Now since Kate and I were both graduate students of Peter’s at the time, it was natural to put our work together. The mass of material that we produced eventually got sorted into three papers:
Traces in symmetric monoidal categories, an expository paper containing the background we wanted to assume in the other papers, plus some fun unusual examples.
Shadows and traces in bicategories. Kate originally defined shadows and traces in her thesis, but here we took a more systematic category-theoretic perspective. We described a string diagram calculus for shadows, and generalized the basic properties of symmetric monoidal trace that had been axiomatized by Joyal, Street, and Verity in Traced monoidal categories. For example, we showed that if $X$ and $Y$ are right dualizable and $f:X\to X$ and $g:Y\to Y$, then $\tr(f\odot g) = \tr(g) \circ \tr(f)$. You might say the intent was to make bicategorical traces “category-theoretically respectable”.
Duality and traces for indexed monoidal categories, in which we finally combined our theses. Using another string diagram calculus, we showed that $Fr(\mathbf{C})$ has a shadow and related its bicategorical traces to symmetric monoidal traces in the $\mathbf{C}(A)$s.
To elaborate on this last one, any $X\in \mathbf{C}(A)$ can be regarded as a 1-cell in $Fr(\mathbf{C})$ in two ways: from $A$ to $1$ or from $1$ to $A$. We denote these by $\hat{X}$ and $\check{X}$ respectively. Then $\hat{X}$ has a (right) adjoint just when $X$ is dualizable in $\mathbf{C}(A)$. If we think of $X$ as an “$A$-indexed family” $(X_a)_{a\in A}$, or as a map $X\to A$ with fiber $X_a$ over $a\in A$, then this generally means just that each $X_a$ is dualizable. However, the trace of $tr(\hat{f})$ contains more information than $tr(f)$, and sometimes strictly more. The former has domain $\langle\langle U_A \rangle\rangle$, which is generally like the free loop space of $A$, and $tr(\hat{f})$ maps a loop $\alpha$ to the trace of $f_a\circ X_\alpha$, where $X_\alpha$ is the monodromy around $\alpha$ and $f_a$ is the action of $f$ over some point $a\in \alpha$. By contrast, the trace of $f$ in $\mathbf{C}(A)$ only knows about these traces for constant loops.
(Right) dualizability of $\check{X}$ is a stronger condition; in parametrized spectra, for $\check{I_A}$ (with $I_A$ the unit of $\mathbf{C}(A)$) it is Costenoble-Waner duality. The composing-adjunctions argument mentioned above shows that if $\check{X}$ is right dualizable, then $(\pi_A)_! X$ is dualizable in $\mathbf{C}(1)$. In particular, a Costenoble-Waner dualizable space is also Spanier-Whitehead dualizable. Now Kate and I showed that $tr(\check{f})$ also contains more information than $tr((\pi_A)_!(f))$: the latter is the composite $I_1 \xrightarrow{tr(\check{f})} \langle\langle A \rangle\rangle \to I_1$. This also follows completely formally, from the basic property of bicategorical traces that I mentioned above: if you compose two dualizable 1-cells, then the trace of an induced endomorphism is the composite of the original two traces. (The map $\langle\langle A \rangle\rangle \to I_1$ is the trace of the identity map of the base change object for $\pi_A$.) In particular, this explains how the Reidemeister trace refines the Lefschetz number.
As we worked on these papers, Kate and I were also trying to generalize additivity to bicategories. This was harder than we expected, mainly because triangulated categories are no good. Since their axioms are about nonunique existence, when you add more axioms like Peter’s, you get “there exists an X as in axiom A, and also a Y as in axiom B, together satisfying axiom C, and also …”. Peter’s axioms were manageable, but the bicategorical generalization was too much for us. If we had believed triangulated categories were a “correct thing”, we might have pushed through; but clearly the “correct thing” is a stable (∞,1)-category. However, we weren’t really enthusiastic about using those either. This led us to derivators; which may not really be a “correct thing” either, but their structure is categorically sensible and characterizes objects by universal properties, so they are much nicer to work with than triangulated categories.
The obvious place to start was to prove that symmetric monoidal derivators satisfy Peter’s axioms. In May 2011 I visited Kate in Kentucky, and we spent an intense week filling blackboards with string diagrams and checking that squares were homotopy exact. I even wrote a little computer program to do the latter for us. Eventually we joined forces with Moritz Groth, who contributed (among other things) the right definition of “closed monoidal derivator”. But we stayed stuck on things like Peter’s axiom (TC3).
Then in November 2011 we discovered a totally different approach to additivity. Consider the bicategory $Prof(\mathbf{V})$ of categories and profunctors enriched in a symmetric monoidal $\mathbf{V}$. We have embeddings like $\hat{(-)}$ and $\check{(-)}$, but with variance: a functor $X:A\to \mathbf{V}$ becomes a profunctor $\hat{X}:A ⇸ 1$, while a functor $\Phi:A^{op}\to \mathbf{V}$ becomes a profunctor $\check{\Phi}:1 ⇸ A$. As before, $\hat{X}$ is right dualizable when each $X_a$ is dualizable, and $tr(\hat{f})$ records the traces of $f_a\circ X_\alpha$ as $\alpha$ ranges over endomorphisms in $A$. And right dualizability of $\check{\Phi}$ says that $\Phi$ is a weight for absolute colimits in $\mathbf{V}$; thus the composing-adjoints argument implies
Theorem: If $X:A\to \mathbf{V}$ is such that each $X_a$ is dualizable, while $\Phi$ is a weight for absolute colimits, then the weighted colimit $\colim^{\Phi}(X)$ is dualizable.
I would be surprised if no one had noticed this before, but I don’t recall seeing it written down. Even more interestingly, however, the “composition of traces” property now implies:
Theorem: In the above situation, given $f:X\to X$, the trace of $\colim^\Phi(f)$ is the composite $I \xrightarrow{\tr(1_\Phi)} \langle\langle U_A \rangle\rangle \xrightarrow{\tr(\hat{f})} I$.
If $\mathbf{V}$ is additive and $A$ is finite, $\langle\langle U_A \rangle\rangle$ is a direct sum of copies of $I$ over “conjugacy classes” of endomorphisms in $A$. Thus, $\tr(\colim^\Phi(f))$ is a linear combination of the traces of $f_a\circ X_\alpha$, with coefficients determined by $\Phi$. So for completely formal reasons, we have a very general “linearity formula” (hence the paper titles) for traces of absolute colimits. We obtain Peter’s original additivity theorem by generalizing $\mathbf{V}$ to be a symmetric monoidal derivator, with $\Phi$ the weight for cofibers. Absoluteness of this weight is equivalent to stability of $\mathbf{V}$, and its coefficients are $1$ and $-1$, yielding the original formula in a rewritten form:
$L(f/A) = L(f) - L(f|_A).$
Finally, this argument can be entirely straightforwardly generalized to bicategories, since we know how to define “categories and profunctors enriched in a bicategory”.
Before going on, I want to emphasize why I consider this a success story for applied category theory. We started out by looking at something that arose naturally in another branch of mathematics; in this case, the Reidemeister trace in topological fixed-point theory. Its definition looked somewhat ad hoc, but it was a generalization of something that did have a nice category-theoretic description (the Lefschetz number), so we (and here I mean Kate) trusted that it probably had one too. So we (i.e. Kate) wrote down a categorical description of the structure being used, and then abstracted away the particulars to arrive at a general definition: shadows and bicategorical traces.
This general definition might have looked a bit peculiar to a category theorist, but we took it seriously and went on to study it using category-theoretic tools. We proved a coherence theorem (the string diagram calculus), ensuring that the definition was not missing any axioms. We investigated its abstract properties, not because we had any particular reason to need them at the moment, but because past experience suggested that they would eventually be necessary to know, and useful to have collected in one place.
It then turned out that one of these abstract properties — the composition theorem for traces — enabled a clean and essentially completely formal proof, and generalization, of a result (additivity) that used to require long calculations and lots of commutative diagrams. It took us a while to notice this. But I dare say it would have taken much longer if we hadn’t previously written down the composition theorem. That’s why I say it was a success story for applying category theory seriously.
In fact, there are a couple more similar success stories hiding inside this larger story. The first involves shadows on framed bicategories, which were slated for inclusion in Shadows and traces in bicategories but got omitted out of consideration for the intended readership. Such a shadow is easiest to define using the double-categorical perspective: it’s a single functor whose domain is the category whose objects are all the endo-horizontal-1-cells and whose morphisms are the squares with equal horizontal sources and targets:
$\array{ A & \xrightarrow{X} & A \\ ^f\downarrow & \Downarrow & \downarrow^f \\ B & \xrightarrow{Y} & B. }$
Such a shadow can be defined on any double category, but in the framed case, a shadow on the horizontal bicategory extends uniquely to one on the framed bicategory — by the construction of twisted traces! When we first noticed it, this seemed like just a cute bit of trivia. But in the linearity paper, it turned out to be crucial in identifying the components of $\tr(\hat{f})$, which we did by applying the composition theorem again using a base change object, whose trace we identified using this characterization of framed shadows. I’ll omit the details; you can find them in the paper. The point is that just as before, having previously found and studied abstractly the correct categorical structure gave us the tools we needed later on for a concrete result.
The second additional success story has to do with derivator bicategories: bicategories enriched over the monoidal bicategory of derivators. We needed these to get linearity for the Reidemeister trace, which is a bicategorical trace and also requries “stable” additivity. In particular, we needed to extend Peter and Johann’s bicategory to a derivator bicategory. This might have been a lot of work, except that in Framed bicategories and monoidal fibrations I had already shown that $Fr$ was 2-functorial. My motivation for this was pure category-theoretic principle: every construction should be a functor. But now, since a monoidal derivator is a 2-functor $Cat^{op}\to MONCAT$ (with extra properties), we can essentially just apply the 2-functor $Fr$ to an “indexed monoidal derivator” to obtain a derivator bicategory. And the indexed monoidal derivator is essentially right there in Peter and Johann’s book. (When we shared these papers with Peter, he remarkede “so that is what we were doing way back then!”)
I’ll finish this long post by mentioning a story that has yet to be told, relating to the construction of $Prof(\mathbf{V})$ for a derivator $\mathbf{V}$. Kate and I needed this bicategory for the linearity story, so we joined forces with Moritz Groth (who had the first idea of how to construct it) to do it in a separate paper. However, the three of us then discovered that $Prof(\mathbf{V})$ would also solve the original problem of proving that Peter’s axioms hold in a stable monoidal derivator. This seemed a good way to make the bicategory paper stand on its own, so we retitled it The additivity of traces in monoidal derivators (and eventually split it in two as well).
(We still don’t know whether Peter’s proof generalizes directly to bicategorical trace. Even using derivators, there seems to be another roadblock or two. I’d be happy to elaborate if anyone is interested; it’s possible they could be circumvented with a little thought.)
Now unfortunately, the objects of $Prof(\mathbf{V})$ are not actually categories enriched in $\mathbf{V}$, but ordinary unenriched categories. (No one knows how to define “categories (coherently) enriched in a monoidal derivator”; it may be impossible with the current definition of derivator.) Now given a monoidal derivator $\mathbf{V}:Cat^{op}\to MONCAT$, the hom-category $Prof(\mathbf{V})(A,B)$ should be $\mathbf{V}(A\times B^{op})$. This should look familiar! Indeed, a monoidal derivator is a $Cat$-indexed monoidal category, and the construction of $Prof(\mathbf{V})$ is very similar to that of $Fr(\mathbf{C})$ (recall $Fr(\mathbf{C})(A,B) = \mathbf{C}(A\times B)$). However, the pushforward functors in a derivator don’t satisfy the Beck-Chevalley condition for (homotopy) pullback squares, which we required for $Fr$; instead, they satisfy it for comma squares, or more generally homotopy exact squares.
The unit and composition in $Fr(\mathbf{C})$ and $Prof(\mathbf{V})$ also look very similar. For instance, in $Fr(\mathbf{C})$ we compose $X\in \mathbf{C}(A\times B)$ and $Y\in \mathbf{C}(B\times C)$ by pulling them both back to $A\times B\times B\times C$ and tensoring them there, pulling back again along the diagonal to $A\times B\times C$, then pushing forward to $A\times C$. In $Prof(\mathbf{V})$, we compose $X\in \mathbf{V}(A\times B^{op})$ and $Y\in \mathbf{V}(B\times C^{op})$ by pulling them both back to $A\times B^{op}\times B\times C^{op}$ and tensoring them there, pulling back again along the projection of the twisted arrow category to $A\times tw(B)^{op}\times C^{op}$, then pushing forward to $A\times C^{op}$. Note that if $A$, $B$, and $C$ are groupoids, then $B^{op} \cong B$ and $tw(B)\simeq B$, and the two constructions do agree. This leads to a natural
Question: Is there an abstract construction producing a (framed) bicategory from some input data, which reduces in one case to $Fr$ and in another case to $Prof$?
If such a thing existed, maybe we could apply it to “derivators” with $Cat$ replaced by something else, such as the 2-category of internal categories in a topos, or a 2-category of (∞,1)-categories. The latter would include in particular the (∞,0)-categories, i.e. spaces; thus when $\mathbf{V}=Spectra$ it should reproduce Peter and Johann’s bicategory (c.f. also Ando-Blumberg-Gepner).
In fact, Kate and I had already used a version of the linearity story with Peter and Johann’s bicategory replacing $Prof(\mathbf{V})$ to prove the multiplicativity of the Lefschetz number and Reidemeister trace. Roughly, multiplicativity means that given a fibration $E\to B$ with fiber $F$, and compatible endomorphisms $f:E\to E$ and $\bar{f}:B\to B$, we have $L(f) = L(f|_F) \cdot L(\bar{f})$. However, if $B$ is not simply-connected, then $L(f|_F)$ can differ between fibers; thus instead of a simple product we need a sum of fiberwise traces over loops in $B$ — whose coefficients turn out to be none other than the Reidemeister trace of $\bar{f}$. In other words, it is another linearity formula, with $B$ acting like the weight $\Phi$ and the Reidemeister trace acting like its coefficient vector. And we proved it in the same way: composing the Costenoble-Waner dualizable $\check{I_B}:1⇸ B$ with the fiberwise dualizable $\hat{E}:B⇸1$ yields the ordinary space $E:1⇸1$, and we can apply the composition-of-traces theorem.
Now a fibration $E\to B$ is equivalently an (∞,1)-functor $B \to \infty Gpd$, and the total space $E$ is its (homotopy) colimit. Thus, additivity and multiplicativity are really two special cases of a single theorem about absolute colimits of (∞,1)-diagrams; the only thing missing is a construction of the appropriate bicategory.
Guest post by Joe Hannon.
As the final installment of the Kan extension seminar, I’d like to take a moment to thank our organizer Emily, for giving all of us this wonderful opportunity. I’d like to thank the other participants, who have humbled me with their knowledge and enthusiasm for category theory and mathematics. And I’d like to thank the nCafé community for hosting us.
For the final paper of the seminar, we’ll be discussing Mike Shulman’s Enriched Indexed categories.
The promise of the paper is a formalism which generalizes ordinary categories and can specialize to enriched categories, internal categories, indexed categories, and even some combinations of these which have found use recently. In fact the paper defines three different notions of such categories, so-called small $\mathcal{V}$-categories, indexed $\mathcal{V}$-categories, and large $\mathcal{V}$-categories, where $\mathcal{V}$ is an indexed monoidal category. For the sake of brevity, we’ll be selective in this blog post. I’ll quickly survey the background material, the three definitions, and their comparisons, and then I want to look at limits in enriched indexed categories. Note also that Mike himself made a post on this paper here on the nCafe in 2012, hence the title.
Indexed monoidal categories
An $\mathbf{S}$-indexed monoidal category is pseudofunctor $\mathcal{V}\colon\mathbf{S}\to\text{MonCat}$, where $\mathbf{S}$ is assumed to have finite products and be endowed with its cartesian monoidal structure, and $\text{MonCat}$ is the 2-category of monoidal categories and strong monoidal functors (functors who preserve monoidal structure up to coherent isomorphism). We’ll use the script $\mathcal{V}$ for an enriched indexed monoidal category, and bold $\mathbf{V}$ for an ordinary monoidal category.
We will notate the image monoidal category of an object $X\in\mathbf{S}$ as $\mathcal{V}^X$ and arrow $f\colon X\to Y$ goes to $f^\ast\colon \mathcal{V}^Y\to\mathcal{V}^X.$ By the Grothendieck construction we may equivalently regard this as a fibration $\int\mathcal{V}\to\mathbf{S}$ which is strict monoidal (preserves the monoidal structure on the nose), and the monoidal structure preserves the cartesian morphisms of the fibration. We think of $\mathcal{V}^1$ (where $1$ is the terminal object in $\mathbf{S}$) as the underlying monoidal category of our indexed monoidal category, with the other fibers related by pullback by the terminal morphism.
The two principal examples of indexed monoidal categories are $\mathit{Fam}(\mathbf{V})$ and $\mathit{Self}(\mathbf{S})$, out of which we will construct $\mathbf{V}$-enriched categories and $\mathbf{S}$-internal categories, respectively.
For $\mathit{Fam}(\mathbf{V})$, let $\mathbf{S}$ be the category of sets and $\mathbf{V}$ be an ordinary monoidal category, and to a set $X$ associate the category $\mathbf{V}^X$ of $X$-indexed objects in $\mathbf{V}$ and pointwise morphisms, and monoidal structure also given pointwise. If $f\colon X\to Y$ then we have a functor $f^\ast\colon\mathbf{V}^Y\to\mathbf{V}^X$ given by $(f^\ast B)_x=B_{f(x)},$ for $B=(B_y)_{y\in Y}\in\mathbf{V}^Y.$
And for $\mathit{Self}(\mathbf{S})$ let $\mathbf{S}$ be any category with finite limits, and to each object $X\in\mathbf{S}$ associate the category $\mathbf{S}\downarrow X$ with its cartesian structure given by pullbacks. Then for $B\in\mathbf{S}\downarrow Y$ and $f\colon X\to Y$, we have $f^\ast B=X\underset{Y}{\times}B,$ the pullback again.
In any indexed monoidal category our fibers have a monoidal product by assumption, which we will call the fiberwise product, and denote $A\otimes_X B$, for $A,B\in\mathcal{V}^X.$ There is additionally an external product defined on $\int\mathcal{V}$, as was implicit in our claim that the Grothendieck construction yields a strict monoidal fibration. We denote this by $A\otimes B$, for $A\in\mathcal{V}^X$ and $B\in\mathcal{V}^Y$ and call it the external product. It is related to the fiberwise product by the formula $A\otimes B=\pi_A^\ast X\otimes_{A\times B}\pi_B^\ast Y,$ which is familiar from the theory of bundles or sheaves.
Additionally, if $\mathcal{V}$ satisfies some completeness properties (existence of $\mathbf{S}$-indexed coproducts), then there is a third product structure called the canceling product. If every $f^\ast\colon \mathcal{V}^Y\to \mathcal{V}^X$ has a left adjoint $f_!\colon \mathcal{V}^X\to \mathcal{V}^Y$, and for any pullback square
$\begin{matrix} & \overset{h}{\to} & \\ k \downarrow & & \downarrow f\\ & \underset{g}{\to} & \\ \end{matrix}$
in $\mathbf{S}$ the Beck-Chevalley transformation $k_!h^\ast\to g^\ast f_!$ is an isomorphism, then we say that $\mathcal{V}$ has $\mathbf{S}$-indexed coproducts, and we define the canceling product in terms of the external tensor product as $A\otimes_{[Y]}B={\pi_Y}_!\Delta_Y^\ast (A\otimes B),$ for $A\in\mathcal{V}^{X\times Y}$ and $B\in\mathcal{V}^{Y\times Z}$.
In $\mathit{Fam}(\mathbf{V})$, the external product is given by $(A\otimes B)_{(x,y)\in X\times Y}=A_x\otimes B_y$, has indexed coproducts if $\mathbf{V}$ has coproducts, and in that case the canceling product is given by “matrix multiplication” $A\otimes_{[Y]} B=\coprod_{y\in Y} A_{(x,y)}\otimes B_{(y,z)}.$
In $\mathit{Self}(\mathbf{S})$, the external product is just the cartesian product in $\mathbf{S}$, has indexed coproducts, and the canceling product is given by a pullback which forgets the map to $Y$.
The various products can be combined; for $A$ in the fiber over $X\times Y\times Z$ and $B$ over $Y\times Z\times W$, then we can cancel the $Z$ dependence and take the fiberwise product over $Y$, leaving an object over $X\times Y\times W.$
Since we will be enriching over our indexed monoidal categories, we may also ask for an indexed version of closedness. If each fiber is closed as a monoidal category (meaning that the tensor product has a right adjoint), and in addition each pullback functor between fibers preserves this fiberwise hom, then we say the indexed monoidal category is closed. In that case, the other tensor products also admit adjoints: the canceling hom $\mathcal{V}^{[Y]}(B,C)$ is the right adjoint of the external tensor, and the external hom $\mathcal{V}(B,C)$ is the right adjoint of the canceling tensor.
In $\mathit{Fam}(\mathbf{V})$, the external hom is given by $(A\otimes B)_{(x,y)\in X\times Y}=A_x\otimes B_y$, and the canceling hom is given by “matrix multiplication” $A\otimes_{[Y]} B=\coprod_{y\in Y} A_{(x,y)}\otimes B_{(y,z)}.$
In $\mathit{Self}(\mathbf{S})$, the external hom is just the cartesian product in $\mathbf{S}$, has indexed coproducts, and the canceling product is given by a pullback which forgets the map to $Y$.
Small $\mathcal{V}$-categories
Categories
With the notion of an indexed monoidal category in hand, we may now meet the first of the three notions of an enriched indexed category:
A small $\mathcal{V}$-category $A$ is an object $\epsilon A\in \mathbf{S}$ called the extent, an object $\underline{A}\in\mathcal{V}^{\epsilon A\times \epsilon A}$ which we think of as the arrows of $A$, along with morphisms $I_{\epsilon A}\overset{\text{ids}}{\to} \underline{A}$ and $\underline{A}\otimes_{\epsilon A}\underline{A}\to \underline{A}$ satisfying the usual associativity and unital axioms:
$\begin{matrix} \underline{A}\underset{\epsilon A}{\otimes}(\underline{A}\underset{\epsilon A}{\otimes}\underline{A}) & \to & (\underline{A}\underset{\epsilon A}{\otimes}\underline{A})\underset{\epsilon A}{\otimes}\underline{A} & \to & \underline{A}\underset{\epsilon A}{\otimes}\underline{A}\\ \downarrow & & & & \downarrow \\ \underline{A}\underset{\epsilon A}{\otimes}\underline{A}& & \to & & \underline{A} \end{matrix}$
and
$\begin{matrix} \underline{A} & \to & I_{\epsilon A}\otimes_{\epsilon A}\underline{A} & \to & \underline{A}\underset{\epsilon A}{\otimes}\underline{A} & \leftarrow & I_{\epsilon A}\otimes_{\epsilon A}\underline{A}& \leftarrow & \underline{A}\\ & & =\searrow & & \downarrow & & \swarrow = \\ & &&& \underline{A} && \end{matrix}$
Functors
A functor $f\colon A\to B$ of small $\mathcal{V}$-categories is given by the data of a morphism of extents $\epsilon f\colon \epsilon A\to \epsilon B$ in $\mathbf{S}$, and a morphism of arrows $\underline{A}\to\underline{B}$ in $\int\mathcal{V}$ such that $\begin{matrix} I_{\epsilon A} & \to & \underline{A}\\ \downarrow & & \downarrow \\ I_{\epsilon B} & \to & \underline{B} \end{matrix}$ and $\begin{matrix} \underline{A}\otimes_{\epsilon A}\underline{A} & \to & \underline{A}\ar[d]\\ \downarrow & & \downarrow \\ \underline{B}\otimes_{\epsilon B}\underline{B}& \to & \underline{B} \end{matrix}$ commute.
Natural transformations
A natural transformation $\alpha$ between functors $f,g\colon A\to B$ of small $\mathcal{V}$-categories is a morphism $I_{\epsilon A}\to \underline{B}$ so that
$\begin{matrix} \underline{A}& \to & \underline{A}\underset{\epsilon A}\otimes I_{\epsilon A} & \overset{f\otimes\alpha}{\to} & \underline{B}\otimes_{\epsilon B} \underline{B}\\ \downarrow & & & & \downarrow \\ I_{\epsilon A}\otimes \underline{A} & \underset{\alpha\otimes g}{\to} & \underline{B}\otimes_{\epsilon B} \underline{B} & \to & \underline{B} \end{matrix}$
With these definitions, $\mathcal{V}$-categories, functors, and natural transformations constitute an ordinary 2-category.
Discrete enriched category
If $\mathcal{V}$ has $\mathbf{S}$-indexed coproducts preserved by $\otimes$, then for any object $X\in\mathbf{S}$ we have a small $\mathcal{V}$-category $\delta X$ with extent $\epsilon(\delta X)=X$ and $\underline{\delta X}=(\Delta_X)_!I_X.$
Profunctors
A profunctor $H\colon A\nrightarrow B$ is an object $\underline{H}\in\mathcal{V}^{\epsilon A\times\epsilon B}$ with structure morphisms $\underline{A}\otimes_{\epsilon A}\underline{H}\to\underline{H}$ and $\underline{H}\otimes_{\epsilon B}\underline{B}\to\underline{H}$ so that the left and right actions are unital and associative and the left action commutes with the right action: $\begin{matrix} \underline{A}\otimes_{\epsilon A}\underline{A}\otimes_{\epsilon A}\underline{H} & \to & \underline{A}\otimes_{\epsilon A}\underline{H}\\ \downarrow & & \downarrow \\ \underline{A}\otimes_{\epsilon A}\underline{H} & \to & \underline{H} \end{matrix}$ and $\begin{matrix} \underline{H}\otimes_{\epsilon B}\underline{B}\otimes_{\epsilon B}\underline{B} & \to & \underline{H}\otimes_{\epsilon B}\underline{B}\\ \downarrow & & \downarrow \\ \underline{H}\otimes_{\epsilon B}\underline{B} & \to & \underline{H} \end{matrix}$ and $\begin{matrix} \underline{H} & \to & \underline{A}\otimes_{\epsilon A}\underline{H}\\ & \searrow & \downarrow \\ & & \underline{H} \end{matrix}$ and $\begin{matrix} \underline{H} & \to & \underline{H}\otimes_{\epsilon B}\underline{B}\\ & \searrow & \downarrow \\ & & \underline{H} \end{matrix}$ and $\begin{matrix} \underline{A}\otimes_{\epsilon A}\underline{H}\otimes_{\epsilon B}\underline{B} & \to & \underline{H}\otimes_{\epsilon B}\underline{B}\\ \downarrow & & \downarrow \\ \underline{A}\otimes_{\epsilon A}\underline{H}& \to & \underline{H} \end{matrix}$
We can restrict our profunctors as usual. Given $H\colon A\nrightarrow B$ and $f\colon A\to A'$ and $g\colon B\to B'$, then we have a profunctor $H(g,f)$ given by $\underline{H(g,f)}=(\epsilon f\times \epsilon g)^\ast\underline{H}.$ In particular for a functor $A\to B$, we have the representable profunctors $B(1,f)\colon A\nrightarrow B$ and $B(f,1)\colon B\nrightarrow A.$
If our indexed monoidal category has good completeness properties ($\mathbf{S}$-indexed coproducts preserved by $\otimes$, and fiberwise coequalizers) then we define the composition of profunctors as (lemma 3.25) $\underline{H\odot K}=\operatorname{coeq}\left(\underline{H}\otimes_{[\epsilon B]} \underline{B} \otimes_{[\epsilon B]}\underline{K}\rightrightarrows \underline{H}\otimes_{[\epsilon B]}\underline{K}\right).$
If moreover the $\mathcal{V}$ is an $\mathbf{S}$-indexed cosmos (i.e. closed as an indexed monoidal category, symmetric, complete and cocomplete with $\mathbf{S}$-indexed products and coproducts), then $\odot$ has left and right adjoints (lemma 3.27) $\mathcal{V}\text{-}Prof(A,C)(H\odot K,L)\cong \mathcal{V}\text{-}Prof(A,B)(H,K\triangleright L) \cong \mathcal{V}\text{-}Prof(B,C)(K,L\triangleleft H)$ given by $\underline{K\triangleright L}=\operatorname{eq}\left(\mathcal{V}^{[\epsilon C]}(\underline{K},\underline{L})\rightrightarrows\mathcal{V}^{[\epsilon C]}(\underline{K},\mathcal{V}^{[\epsilon C]}(\underline{C},\underline{L}))\right)$ and $\underline{L\triangleleft H}=\operatorname{eq}\left(\mathcal{V}^{[\epsilon A]}(\underline{H},\underline{L})\rightrightarrows\mathcal{V}^{[\epsilon A]}(\underline{H},\mathcal{V}^{[\epsilon A]}(\underline{A},\underline{L}))\right).$
Examples and two more definitions
As mentioned, the basic examples of monoidal indexed categories are $\mathcal{V}=\text{Fam}(\mathbf{V})$, in which a small $\mathcal{V}$-category is a category enriched in $\mathbf{V}$, and $\mathcal{V}=\text{Self}(\mathbf{S})$, which gives a category internal to $\mathbf{S}$. The paper also gives two alternate definitions of enriched indexed categories, which I will cite very briefly. An indexed $\mathcal{V}$-category gives for each $X\in\mathbf{S}$ a category enriched in $\mathcal{V}^X$ and functors relating the categories for each fiber (def 4.1), and this is seen to be a generalization of the ordinary indexed category and in fact every indexed $\mathcal{V}$-category has a natural underlying ordinary $\mathbf{S}$-indexed category (example 7.5).
And a large $\mathcal{V}$-category is a kind of horizontal categorification of a small $\mathcal{V}$-category, with collection of objects $x,y,...$ and for each object an extent $\epsilon x\in\mathbf{S}$ and for each pair of objects $x,y$ an object $\mathcal{A}(x,y)\in\mathcal{V}^{\epsilon x\times\epsilon y}$ satisfying the usual axioms (def 5.1). Then there is a notion of $\mathcal{V}$-fibrations and a Grothendieck-type construction which gives an equivalence between $\mathcal{V}$-indexed categories and large $\mathcal{V}$-categories (theorem 6.10).
The paper has many lovely examples, more than I want to discuss here. I’ll just mention one fun example from topology, one of the motivations for the paper (example 11.25): if we take for $\mathbf{S}$ the category of finite group objects in topological spaces denoted $\mathcal{G}$, and for $\mathcal{V}$ the indexed monoidal category of based spaces with group actions, denoted $Act(\text{Top})_\ast$. We have an $Act(\text{Top})_\ast$-category $\mathcal{I}_\mathcal{G}$ with objects given by finite dimensional real representations $\rho\colon G\to O(n)$, with extent $G$ and hom-object $\underline{\mathcal{I}_\mathcal{G}}(G,G')$ the space of linear isometric isomorphisms $\mathbb{R}^n\to\mathbb{R}^{n'}$ plus basepoint with $G\times G'$ action by conjugation. The fiberwise monoidal structure is given by direct sum of representations. The presheaf category gives Anna Marie Bohmann’s global orthogonal spectra.
Center of the category of modules
This semester I attended a class at Boston University on noncommutative geometry by Ryan Grady. As a homework problem I was asked to show that the center of a category is isomorphic to the center of modules over that category, and then to generalize to the case of enriched categories and internal categories. Repeating a proof which is formally the same for three different contexts cries out for generalizing to a single unifying context, and enriched indexed categories promises to provide that context. So here is a fourth and (perhaps) final sketch of that proof.
The center $Z(C)$ of an ordinary category $C$ is defined to be the endomorphism monoid of the identity functor on $C$. This is a construction worthy of being called the center since for a category with one object it produces the center of the endomorphism monoid. So it is the horizontal categorification of the classical notion. For an ordinary category a functor $M\colon C\to \text{Set}$ defines a notion of a (left) module $M$ over $C$. We have an isomorphism between the center of the category of modules $Z(C\text{-Mod})$ and $Z(C)$.
Briefly, in the case of an ordinary category, for each $z\in Z(C)$ we obtain for each module $M$ a morphism of modules $Mz$ which is just the whiskered product $Mz$ of the functor $M$ with the natural transformation $z$. It is a natural transformation on the identity functor on modules if it commutes with module morphism $f$, which it does since each component of $Mz$ commutes with components of $f$, which it does by centrality of $z$. Conversely, given a central element $\zeta$ in $Z(C\text{-Mod})$, for each module $M$ we have a morphism of modules $\zeta_M\colon M\to M$. Any object $a\in C$ may be viewed as a left module over $C$ by the contravariant Yoneda embedding, so we have $\zeta_a\colon C\to C$. This module morphism as a natural transformation between functors has a component at $a$, which is a function $\hom(a,a)\to\hom(a,a).$ Then $\zeta_a(1)$ gives an element of $Z(C)$. By the Yoneda lemma all left-module morphisms $C\to C$ are given by right multiplication, so we obtain an isomorphism of monoids $Z(C)\cong Z(C\text{-Mod}).$
Categories enriched over $\mathbf{V}$ naturally constitute a category enriched in $\mathbf{V}$-categories, meaning instead of a hom-set of natural transformations between functors $F,G$, we have an object of $\mathbf{V}$, given by the end $\int_c \hom(Fc,Gc)$. If $C$ is a $\mathbf{V}$-category, then so is $C\text{-Mod},$ and $Z(C)\cong Z(C\text{-Mod})$ is an isomorphism is of $\mathbf{V}$-monoids.
In the case of a category $C=(C_0;C_1;\text{ids}\colon C_0\to C_1;s,t\colon C_1\to C_0;\text{comp}\colon C_1\times_{C_0}C_1\to C_1)$ internal to $\mathcal{E}$, a module $M$ over an internal category is also known as an internal diagram, and it is given by the data of a structure morphism $M\to C_0$ such that $\begin{matrix} C_1\underset{C_0}{\times} M & \overset{\text{act}}{\to}& M \\ \downarrow & & \downarrow \\ C_1 & \underset{s}{\to} & C_0 \end{matrix}$ commutes. This action is required to be associative and unital. The category of modules constitutes only an ordinary category, a subcategory of $\mathcal{E}$, and we obtain again an isomorphism of monoids.
Now let $A$ be a small $\mathcal{V}$-category, for $\mathcal{V}$ an indexed monoidal category. Using the notation of the paper a one-sided left $A$-module is a profunctor $M\colon A\nrightarrow I,$ where $I=\delta 1$ is the discrete $\mathcal{V}$-category whose extent is the terminal object of $\mathbf{S}$ and whose arrow object is the monoidal unit $\underline{\delta I}=I\in\mathcal{V}^1=\mathbf{V}.$
A natural transformation of the identity functor $A\to A$ is given by a morphism $I_{\epsilon A}\overset{z}{\to} \underline{A}$ in $\int\mathcal{V}$ so that $\begin{matrix} \underline{A} & \to & \underline{A}\underset{\epsilon A}\otimes I_{\epsilon A} & \to & \underline{A}\underset{\epsilon A}\otimes \underline{A} \\ \downarrow & & & & \downarrow \\ I\underset{\epsilon A}\otimes \underline{A}& \to & \underline{A}\underset{\epsilon A}\otimes \underline{A}& \to & \underline{A} \end{matrix}$
commutes. The collection of such morphisms is the center $Z(A).$ From such an arrow we obtain a morphism
$M\to I_{\epsilon A}\underset{\epsilon A}\otimes M\overset{z\otimes 1}{\to} \underline{A}\underset{\epsilon A}\otimes M\to M.$
This is a morphism of profunctors if it commutes with the profunctor action:
$\begin{matrix} \underline{A}\underset{\epsilon A}{\otimes}M & \to & \underline{A}\underset{\epsilon A}{\otimes}I_{\epsilon A}\underset{\epsilon A}{\otimes}M & \overset{1\otimes z\otimes 1}{\to} & \underline{A}\underset{\epsilon A}{\otimes}\underline{A}\underset{\epsilon A}{\otimes}M & \overset{1\times\text{act}}{\to} & \underline{A}\underset{\epsilon A}{\otimes}\\ {\text{act}}\downarrow & & & & & & \downarrow{\text{act}} \\ M& \to & I_{\epsilon A}\underset{\epsilon A}\otimes M & \underset{z\otimes 1}{\to} & \underline{A}\underset{\epsilon A}\otimes M & \underset{\text{act}}{\to} & M \end{matrix}$ which commutes by a diagram chase.
Conversely, to every natural endomorphism $\zeta_M\colon M\to M$ of the category of profunctors $M\colon A\nrightarrow I,$ we associate an element of $Z(A)$. We notice that our small $\mathcal{V}$-category $A$ may itself be viewed as a profunctor $A\nrightarrow I,$ giving us a component $\zeta_A\colon \underline{A}\to \underline{A}.$ We obtain an element of $Z(A)$ by pre-composition with $I_{\epsilon A}\to \underline{A}$, since the following diagram commutes:
$\begin{matrix} \underline{A} & \to & I_{\epsilon A}\otimes_{\epsilon A} \underline{A} & \overset{\text{ids}\otimes 1}{\to} & \underline{A}\otimes_{\epsilon A}\underline{A} & \overset{\zeta_A\otimes1}{\to} & \underline{A}\otimes_{\epsilon A}\underline{A}\\ \downarrow & & & & & & \downarrow \\ \underline{A}\otimes_{\epsilon A} I_{\epsilon A}& \underset{1\otimes\text{ids}}{\to} & \underline{A}\otimes_{\epsilon A} \underline{A} & \underset{1\otimes\zeta_A}{\to} & \underline{A}\otimes_{\epsilon A} \underline{A}& \to & \underline{A} \end{matrix}$ These maps $Z(A)\leftrightarrow Z(\text{Prof}(A,I))$ are inverse, which establishes the isomorphism, at least in the category of sets. Although this establishes the result for any small $\mathcal{V}$-category, and hence for enriched, internal, indexed category, or combination categories, it is not an isomorphism of objects in the enrichment category. We have defined an ordinary 2-category of small $\mathcal{V}$-categories, but for a full strength general result, we need instead a $\mathcal{V}$-2-category, that is, a category enriched in $\mathcal{V}$-categories, which would strengthen our result to an isomorphism of $\mathcal{V}$-objects.
Equipments
When I first read the abstract for this paper, I guessed naively that a framework that unified enriched categories with internal categories would use the language of monads, since both can be so succinctly described as monads in different 2-categories. Enriched categories are monads in the 2-category $\text{Mat}(\mathbf{V})$ of set indexed matrices with values in monoidal category $\mathbf{V}$, and internal categories in $\mathcal{E}$ are monads in the 2-category $\text{Span}(\mathcal{E})$ of spans in $\mathcal{E}.$
I was disappointed not to see $\mathcal{V}$-categories as monads in the paper. But throughout the paper there are references to the technology of equipments, and one pleasant side effect of understanding enriched indexed categories in terms of equipments is that it becomes perfectly clear how to describe a $\mathcal{V}$-category as a monad, in a way which includes matrices and spans as special cases.
Equipments have also been discussed here by Mike before, and so I want to rely on that background. But here is a brief recap of what is itself a “lightning-fast introduction to formal category theory”. Wood defined a 2-category with proarrow equipment, or an equipment for short, to axiomatize the properties of profunctors, as a functor between 2-categories which is bijective on objects, locally fully faithful, and taking each arrow to a left-adjoint. Such a structure enables the study of formal category theory, because objects, arrows, and 2-cells are not enough to reproduce all the constructions of 1-category theory. One needs something to abstract the behavior of hom-sets and profunctors.
Shulman argues persuasively that the more natural setting for this structure is not a 2-category, but rather a (pseudo) double category (ie a double category where composition of horizontal arrows is weak) whose vertical arrows are the arrows of our 2-category, and whose horizontal arrows are our profunctors. In this setting, here is the axiom that characterizes the profunctors. For any diagram “niche” of the form have also been discussed here
$\begin{matrix} A & & B\\ f \downarrow & & \downarrow g\\ C & \underset{K}{\nrightarrow} & D \end{matrix}$ there exists a filler $K(f,g)$ 1-cell
$\begin{matrix} A & \overset{K(f,g)}{\nrightarrow} & B\\ f \downarrow & \Downarrow & \downarrow g\\ C & \underset{K}{\nrightarrow} & D \end{matrix}$ with the property that any other square whose vertical arrows factor through $f$ and $g$
$\begin{matrix} X & {\nrightarrow} & Y\\ fh \downarrow & \Downarrow & \downarrow gk\\ C & \underset{K}{\nrightarrow} & D \end{matrix}$
itself also factors uniquely
$\begin{matrix} X & {\nrightarrow} & Y\\ h \downarrow & \Downarrow \exists{!} & \downarrow k\\ A & \overset{K(f,g)}{\nrightarrow} & B\\ f \downarrow & \Downarrow & \downarrow g\\ C & \underset{K}{\nrightarrow} & D \end{matrix}$
A double category satisfying this property is called a framed bicategory, which is equivalent to a 2-category with a proarrow equipment.
With this definition in hand, to an indexed monoidal category $\mathcal{V}\colon \mathbf{S}\to \text{MonCat}$ we associate a framed bicategory whose objects $X,Y$ are the objects of $\mathbf{S}$, vertical arrows are the arrows $f,g$ of $\mathbf{S}$, and whose horizontal arrows $X\nrightarrow Y$ are objects in $\mathcal{V}^{X\times Y}.$ Composition of horizontal arrows is given by the canceling tensor product.
As we noted earlier, the canceling product is only defined under some a completeness criteria on $\mathcal{V}$ that are not always satisfied. In general, we would need to consider virtual double categories, which stand in the same relation to framed bicategories that multicategories stand to monoidal categories. In other words, instead of requiring that a composite 1-cell exist for any composible string of 1-cells, we simply consider squares whose top edge is a composible strings of 1-cells. A virtual double category is equivalent to Leinster’s notion of an fc-multicategory, which is a span of the form $TA\leftarrow B \to C$ in the category of graphs where $T$ is the free category monoid.
So in our two principal cases $\text{Fam}(\mathbf{V})$ and $\text{Self}(\mathbf{S})$, we get double categories whose horizontal 2-categories are $\text{Mat}(\mathbf{V})$ and $\text{Span}(\mathbf{S})$
And we can define a monoid in our double category. Following Shulman and Crutwell’s 2010 paper on generalized multicategories (also discussed on the nCafé here) we will not call them monads. A small $\mathcal{V}$-category is a monoid in this virtual double category.
Let me also note that framed bicategories are not the only option for studying formal category theory. As was mentioned by Alex Campbell here on nCafé earlier in the seminar, Yoneda structures provide an alternate (equivalent?) setting for formal category theory.
Limits
Limits in a framed bicategory are defined in a way that generalizes weighted limits. Recall that for ordinary categories, given a functor $J\colon K\to\text{Set}$ and a functor $f\colon K\to C$, the weighted limit is defined to be the representing object $C(-,\lim^Jf)=\text{Set}^K(J,C(-,f-)).$ The motivation for this definition was discussed in Christina’s blog post here at the nCafé. In the context of formal category theory we can almost duplicate this definition, except the formalism of profunctors we are obliged to instead represent the limit with a vertical arrow: if $J\colon A\nrightarrow K$ and $f\colon A\to C,$ then (def 8.1) the $J$-weighted limit of $f$ is a vertical arrow $\ell\colon K\to C$ such that $C(1,\ell)\cong C(1,f) \triangleleft J.$ Similarly the $J$-weighted colimit is given by $C(\ell,1)\cong J\triangleright C(f,1).$
We can recover the classical example of weighted limits in an enriched category by taking $\mathcal{V}=\text{Fam}(\mathbf{V})$ as usual and setting $K=\delta 1$, the unit $\mathcal{V}$-category. In the general case, the generalization of the weights for weighted limits to profunctors (or bimodules) is forced on us because without $\mathbf{S}$-indexed coproducts, $\delta 1$ need not exist.
The generalization turns out to be quite useful, and leads to a more elegant and symmetrical statement of the adjunction between limits and colimits, which in the case of the large enriched indexed categories appears as proposition 8.5: $\mathcal{V}\text{-}CAT(\operatorname{colim}^J f,g)\cong \mathcal{V}\text{-}CAT(f,\lim{}^J g).$
This is a point of view on weighted limits, that the weights should be bimodules, which I first learned of from Riehl’s lecture notes on weighted limits in the context of enriched categories. Those notes were apparently from a category theory seminar by Shulman, and now I think I know where Mike developed this point of view: from his work in formal category theory. Campbell argues the rightness of bimodule weights in his post on Yoneda structures as well.
Enrichment of the 2-category
In classical enriched category theory, we promote our ordinary 2-category of $\mathbf{V}$-categories into a category enriched in $\mathbf{V}$-categories by means of the venerable end: between any two $\mathbf{V}$-categories, we have a $\mathbf{V}$-category whose objects are $\mathbf{V}$-functors $F,G$ and whose hom-objects are given by $\int\hom(F,G).$ I would have liked to have an analogous definition for our enriched indexed categories.
Here we have recalled a formal category theory definition of weighted limits. Can these be used to define an enriched indexed category of enriched indexed functors?
In my first year at Harvard, I had an opportunity to teach a graduate-level topics course entitled “Categorical Homotopy Theory.” Its aim was to highlight areas in which category theoretic abstractions provide a particularly valuable insight into classical homotopy theoretic constructions. Over the course of the semester I gave lectures that focused on homotopy limits and colimits, enriched category theory, model categories, and quasi-categories.
In hopes that attendees would be able to drop in and out without feeling totally lost, I decided to write lecture notes. And now they have just been published by Cambridge University Press as an actual physical book and also as an ebook (or so I’m told).
One of the wonderful things about working with CUP is that they have given me permission to host a free PDF copy of the book on my website. At the moment, this is the pre-copyedited version. There is an extra section missing from chapter 14 and various minor changes made throughout. In a few years time, I’ll be able to post the actual published version.
So what’s in the book? Part I tells a story I learned from a really fantastic paper written by Mike Shulman. It introduces a particular model for the homotopy limit and colimit functors associated to diagrams of any shape with which it is easy to prove their global universal property (as point-set level derived functors) and their local universal property (representing “homotopy coherent cones”). The proof makes use of an independently useful observation of Dwyer-Kan-Hirschhorn-Smith that full model structures are not necessary to define derived functors. In this case, this means that we don’t need to establish model structures on the diagram categories.
Our particular model for homotopy colimits is first defined via the two-sided bar construction, but it is later re-expressed as a weighted colimit, from which viewpoint it is recognizable as the Bousfield-Kan formula. This emphasis might be slightly unusual — a homotopy limit or colimit is something that is weakly equivalent to a particular ur-model — but I think it can be valuable. A number of homotopical theorems have an up-to-isomorphism component, which can be easier to understand. (For instance, the left adjoint of a simplicial Quillen adjunction preserves homotopy colimits, as weighted colimits.)
Part II continues with the study of enriched homotopy theory. We show that the total derived functors of simplicially enriched functors between simplicial model categories are enriched over the homotopy category of spaces. I like to think of this derived enrichment as a proxy for the “homotopical correctness” of the functors. There is also a chapter giving a fairly detailed introduction to weighted limits and colimits, which (unsurprisingly) turn out to be the key categorical tool used in proofs throughout the manuscript.
Part III finally turns focus to Quillen’s model categories, which are black boxed in the first half of the book as good settings in which to implement the Dwyer-Kan-Hirschhorn-Smith axiomatization. Given the wealth of excellent textbooks and surveys on the topic, this section isn’t meant to serve as a comprehensive introduction to model categories. For instance, I say very little about the construction of the homotopy category of a model category. Instead, I develop the theory of weak factorization systems leading up to André Joyal’s definition of a model category: a model category is a homotopical category equipped with classes of cofibrations and fibrations that combine with the weak equivalences to define a pair of weak factorization systems.
As won’t surprise anyone familiar with my thesis work, I spend a fair amount of time discussing the small object argument, both in its original form and in its modern algebraic variant, due to Richard Garner. I then segue into the enriched small object argument and its accompanying enriched weak factorization systems. This definition, which is the obvious enrichment of the usual notion, isn’t well-known, but I think it is interesting. The weak factorization systems in any simplicial model category are automatically enriched. (This is true more generally for any $V$-model category in which tensoring with an object of $V$ defines a left Quillen functor.) Equally interesting is when this does not hold: for instance, for Quillen’s model structure on the category of chain complexes over a ring admitting non-projective modules. In this case it is most productive to think about enrichment over the category of modules (not thought of as a model category). Surprisingly, the usual generating cofibrations and trivial cofibrations for the Quillen model structure also generate the Hurewicz model structure, when we interpret “cofibrant generation” in a non-enriched sense. Some of the details can be found here.
Part III closes with a chapter of Reedy categories that describes a small part of a joint paper with Dominic Verity, connects these ideas to the Bousfield-Kan approach to localizations and completions of spaces, and closes up some loose ends from earlier in the book
The final part is about quasi-categories. My aim here, given the location of the course, was to overlap as little as possible with Higher Topos Theory and so avoid boring Jacob’s students. The first chapter focuses on the construction of and comparison between various models of mapping spaces between vertices in a quasi-category, explaining why quasi-categories are $(\infty,1)$-categories. A second chapter discusses simplicial categories, which provide an important source of examples of quasi-categories, and homotopy coherence.
I then study isomorphisms in quasi-categories, by which I mean 1-simplices that become invertible in the homotopy category of a quasi-category. These are usually called equivalences, but I think this terminology is better. There’s no possibility of confusing with any stricter notion, and it allows for weaker notions of equivalence, which might be of interest for constructing localizations or the like. The final chapter is a very glancing preview of joint with work Dom on the 2-category theory of quasi-categories and its sequels.
For those who are curious, here is the table of contents. Should you happen to read any of this, I hope you enjoy it!
Part I. Derived functors and homotopy (co)limits
Chapter 1. All concepts are Kan extensions
Chapter 2. Derived functors via deformations
Chapter 3. Basic concepts of enriched category theory
Chapter 4. The unreasonably effective (co)bar construction
Chapter 5. Homotopy limits and colimits: the theory
Chapter 6. Homotopy limits and colimits: the practice
Part II. Enriched homotopy theory
Chapter 7. Weighted limits and colimits
Chapter 8. Categorical tools for homotopy (co)limit computations
Chapter 9. Weighted homotopy limits and colimits
Chapter 10. Derived enrichment
Part III. Model categories and weak factorization systems
Chapter 11. Weak factorization systems in model categories
Chapter 12. Algebraic perspectives on the small object argument
Chapter 13. Enriched factorizations and enriched lifting properties
Chapter 14. A brief tour of Reedy category theory
Part IV. Quasi-categories
Chapter 15. Preliminaries on quasi-categories
Chapter 16. Simplicial categories and homotopy coherence
Chapter 17. Isomorphisms in quasi-categories
Chapter 18. A sampling of 2-categorical aspects of quasi-category theory
Guest post by Alex Corner
This is the 11th post in the Kan Extension Seminar series, in which we will be looking at Steve Lack’s paper
- [Lack] Codescent objects and coherence, Stephen Lack, J. Pure and Appl. Algebra 175 (2002), pp. 223-241.
A previous post in this series introduced us to two-dimensional monad theory, where we were told about $2$-monads, their strict algebras, and the interplay of the various morphisms that can be considered between them. The paper of Lack has a slightly different focus in that not only are we interested in morphisms of varying levels of strictness but also in the weaker notions of algebra for a $2$-monad, namely the pseudoalgebras and lax algebras.
An example that we will consider is that of the free monoid $2$-monad on the $2$-category $\mathbf{Cat}$ of small categories, functors, and natural transformations. The strict algebras for this $2$-monad are strict monoidal categories, whilst the lax algebras are (unbiased) lax monoidal categories. Similarly, the pseudoalgebras are (unbiased) monoidal categories. The classic coherence theorem of Mac Lane is then almost an instance of saying that the pseudoalgebras for the free monoid $2$-monad are equivalent to the strict algebras. We will see conditions for when this can be true for an arbitrary $2$-monad.
Thanks go to Emily, my supervisor Nick Gurski, the other participants of the Kan extension seminar, as well as all of the participants of the Sheffield category theory seminar.
Algebras for $2$-monads
When doing $2$-category theory, we often look at weakening familiar notions. We generally do this by replacing axioms that required commutativity of certain diagrams with (possibly invertible) $2$-cells, which themselves are required to satisfy coherence axioms. For instance, given a $2$-monad $T$ (with multiplication $\mu$ and unit $\eta$) on a $2$-category $\mathcal{K}$, a lax algebra for $T$ consists of an object $A$ of $\mathcal{K}$, a $1$-cell $x : TX \rightarrow X$ of $\mathcal{K}$ and $2$-cells $\begin{matrix} T^2X & \overset{Tx}{\longrightarrow} & TX & & X & \overset{1_X}{\longrightarrow} & X \\ {}_{\mu_X}\downarrow & \Downarrow {\chi} & \downarrow^x & & {}_{\eta_X}\searrow & \Downarrow {\chi_0} & \nearrow_x & \\ TX & \underset{x}{\longrightarrow} & X & & \quad & TX & \\ \end{matrix}$ in $\mathcal{K}$ which satisfy suitable axioms. A pseudoalgebra is defined as above but with invertible $2$-cells.
Example We’ll see what’s going on by looking at the free monoid $2$-monad again, call it $M$. A lax algebra for $M$ is a category $X$ and a functor $x : MX \rightarrow X$ with natural transformations $\chi$, $\chi_0$ as above. Now $MX$ is the coproduct $\coprod_{n \in \mathbb{N}} X^n$ meaning that objects in $MX$ are finite lists of objects in $X$, and similarly for morphisms. The functor $x : MX \rightarrow X$ is a functor out of a coproduct so in fact corresponds to a family of functors $(x_n : X^n \rightarrow X)_{n \in \mathbb{N}}$ which we can view as being the $n$-ary tensors of an unbiased lax monoidal category. The natural transformation $\chi$ then has components which are morphisms $\left(\left(a_{11} \otimes \ldots \otimes a_{1k_1}\right) \otimes \ldots \otimes \left(a_{n1} \otimes \ldots \otimes a_{nk_n}\right)\right) \rightarrow \left(a_{11} \otimes \ldots \otimes a_{nk_n}\right)$ in $X$. These are what correspond to the associators in a biased monoidal category. The associativity and unit axioms can then be found to be expressed by the lax algebra axioms.
These differing levels of strictness offer us a whole host of $2$-categories to look at. For our purposes we will be looking at the following $2$-categories:
- $T\text{-Alg}_s$, of strict algebras, strict morphisms, and transformations;
- $\text{Ps-}T\text{-Alg}$, of pseudoalgebras, pseudomorphisms, and transformations;
- $\text{Lax-}T\text{-Alg}_l$, of lax algebras, lax morphisms, and transformations.
Lax codescent objects
The second section of the paper begins by considering lax morphisms of the form $(f, \overline{f}) : (X, x, \chi, \chi_0) \rightarrow (Y,y),$ between a lax algebra $X$ and a strict algebra $Y$. The idea is that lax morphisms of this form in $\text{Ps-}T\text{-Alg}$ can be recast as strict morphisms $(g = y \cdot Tf, \overline{g} = 1_{y} \ast T\overline{f}) : (TX, \mu_X) \rightarrow (Y,y)$ in $T\text{-Alg}_s$. There is an inclusion 2-functor $U : T\text{-Alg}_s \rightarrow \text{Lax-}T\text{-Alg}_l$ and the aim is to construct a left adjoint. To this end, Lack describes a universal property related to $1$-cells in $T\text{-Alg}_s$ of the form $TX \rightarrow X'$ so that there is an isomorphism $T\text{-Alg}_s(X',Y) \cong \text{Lax-}T\text{-Alg}_l(X,Y)$ which is natural in Y. This tells us that if such an object $X'$ exists for every lax algebra $X$, then the left adjoint also exists.
The universal property in question turns out to be that of a lax codescent object in a $2$-category. First we define lax coherence data to be diagrams $\begin{array}{ccccc} \quad & \overset{p}{\rightarrow} & \quad & \overset{d}{\rightarrow} & \\ X_3 & \overset{q}{\rightarrow} & X_2 & \overset{e}{\leftarrow} & X_1\\ \quad & \overset{r}{\rightarrow} & \quad & \overset{c}{\rightarrow} & \end{array}$ accompanied by $2$-cells $\begin{array}{cc} \delta : de \Rightarrow 1_{X_1}, & \gamma : 1_{X_1} \Rightarrow ce, \\ \kappa : dp \Rightarrow dq, & \lambda : cr \Rightarrow cq, \\ \rho : cp \Rightarrow dr. \end{array}$ A lax codescent object is then an object $X$, a $1$-cell $x : X_1 \rightarrow X$, and a $2$-cell $\chi : xd \Rightarrow xc$, all interacting with the $1$-cells and $2$-cells of the lax coherence data. These then also satisfy universal properties of a $2$-categorical nature, much like those we saw in a previous post.
Consider for a moment, an algebra $(A,a)$ for a $1$-monad $S$ on a $1$-category $\mathcal{C}$. We know that this can be expressed as the reflective coequaliser of the diagram $\begin{array}{ccc} \quad & \overset{\mu_A}{\longrightarrow} & \quad \\ S^2A & \overset{S\eta_A}{\longleftarrow} & SA \\ \quad & \overset{Sa}{\longrightarrow} & \quad \\ \end{array}$ in the category $S\text{-Alg}$ of $S$-algebras. However in the case of a lax algebra $(X, x, \chi, \chi_0)$ for a $2$-monad $T$, this won’t be the case. Instead we can form lax coherence data $\begin{array}{ccccc} \quad & \overset{\mu_{TA}}{\rightarrow} & \quad & \overset{\mu_A}{\rightarrow} & \\ T^3X & \overset{T\mu_X}{\rightarrow} & T^2X & \overset{T\eta_A}{\leftarrow} & TX\\ \quad & \overset{T^2x}{\rightarrow} & \quad & \overset{Tx}{\rightarrow} & \end{array}$ in $T\text{-Alg}_s$ when we accompany it with $2$-cells $T\chi_0$ and $T\chi$, where the rest of the $2$-cells are just identities arising from the $2$-monad axioms. The universal property alluded to above is then that the lax codescent object of this lax coherence data is the same as that of the replacement (strict) algebra $X'$ which would give the adjunction previously described.
If all of the mentions of $2$-cells in the above description of a lax codescent object were replaced with invertible $2$-cells, then we would have the notion of a codescent object. This is the analogous situation in the case of pseudoalgebras, where the aim is to find a left adjoint to the inclusion to the inclusion $2$-functor $T\text{-Alg}_s \rightarrow \text{Ps-}T\text{-Alg}.$
A useful observation is that lax codescent objects may be defined using weighted colimits and can be built from coinserters and coequifiers. Also worthy of note is that codescent objects can be built from co-iso-inserters and coequifiers. Now co-iso-inserters exist whenever coinserters and coequifiers do, so that anything we want to prove about lax algebras by utilising such colimits, will also be true for pseudoalgebras.
This section of the paper also includes a number of results concerning adjunctions between the various $2$-categories of algebras, with the following theorem then being the basis for the first characterisation of a coherence theorem.
Theorem: (Lack, 2.4) For a $2$-monad $T$ on a $2$-category $\mathcal{K}$, the inclusion $T\text{-Alg}_s \rightarrow \text{Lax-}T\text{-Alg}_l$ has a left adjoint if any of the following conditions holds:
- $\mathcal{K}$ admits lax codescent objects and $T$ preserves them;
- $\mathcal{K}$ admits coinserters and coequifiers and $T$ preserves them;
- $\mathcal{K}$ is cocomplete and $T$ preserves $\alpha$-filtered colimits for some regular cardinal $\alpha$.
Conditions $2$ and $3$ also give us a left adjoint to the inclusion $T\text{-Alg}_s \rightarrow \text{Ps-}T\text{-Alg}$. Furthermore, we also find that a left adjoint to the inclusion $T\text{-Alg}_s \rightarrow T\text{-Alg}$, which we saw in the paper of Blackwell, Kelly, and Power, also exists under these conditions. Something else that we saw in that paper is the reason for needing $T$ to preserve these colimits - the colimits exist in $T\text{-Alg}_s$ just when $T$ preserves them.
Coherence
The simplest possible characterisation of coherence for $2$-monads would be:
Theorem-Schema: The inclusion $T\text{-Alg}_s \rightarrow \text{Ps-}T\text{-Alg}$ has a left adjoint, and the components of the unit are equivalences in $\text{Ps-}T\text{-Alg}$.
Now this is certainly not true in general. A counter-example (3.1) is given in the paper, whilst Mike Shulman also shows that not every pseudoalgebra is equivalent to a strict one.
Something that is rather nice, though, is that we already have some conditions under which the theorem-schema is satisfied.
Theorem: (Lack, 3.2) If $T$ is a $2$-monad on a $2$-category $\mathcal{K}$ admitting codescent objects, and $T$ preserves them, then the inclusion $T\text{-Alg}_s \rightarrow \text{Ps-}T\text{-Alg}$ has a left adjoint, and the components of the unit are equivalences in $\text{Ps-}T\text{-Alg}$. In particular this is the case if $\mathcal{K}$ has coinserters and coequifiers, and $T$ preserves them.
The proof of this is rather simple and falls out of the two-dimensional universal property of the codescent objects.
I’m going to roll the latter two sections of the paper together now and talk about the other characterisation of coherence, which concerns a general coherence result of Power. That paper looks at $2$-monads on $\mathbf{Cat}^X$ and $\mathbf{Cat}^X_g$, where $X$ is a small set and the latter $2$-category is attained from the first by only considering invertible $2$-cells. Power then shows that if $T$ is a $2$-monad on one of these $2$-categories which preserves bijective-on-objects functors, then every pseudoalgebra for $T$ is equivalent to a strict one.
Some $2$-monads which satisfy these conditions include $\mathbf{Set}$-based clubs, whose strict algebras give such structures as monoidal categories (see the scope of the results below for more monoidal examples) or categories with strictly associative finite products or coproducts. Also described in Power’s paper is a $2$-monad on $\mathbf{Cat}^{X \times X}$ for which the pseudoalgebras are unbiased bicategories with object set $X$. The coherence result then tells us that every bicategory is biequivalent to a $2$-category with the same set of objects.
Comparing Power’s statement to the theorem-schema, we see that they are not quite the same. The schema asks for there to be an adjunction for which the components of the unit give the equivalences we are concerned with. As it turns out, the conditions which Power proposes are indeed enough to give what we desire, and this is what the latter characterisation of Lack looks at.
Recall that every functor can be factored as a bijective-on-objects functor followed by a full and faithful functor. This gives an orthogonal factorisation system $(bo,ff)$ on $\mathbf{Cat}$. However, the $(bo,ff)$ factorisation system has an extra two-dimensional property concerning $2$-cells. If we are given a natural isomorphism $\begin{matrix} A & \overset{R}{\longrightarrow} & C \\ {}_{F}{\downarrow} & {\Downarrow}_{\alpha} & \downarrow^G \\ B & \underset{S}{\longrightarrow} & D \\ \end{matrix}$ where $F$ is bijective-on-objects and $G$ is full and faithful, then there is a unique pair $(H,\beta)$ consisting of a functor $H:B \rightarrow C$ and a natural isomorphism $\beta:GH \Rightarrow S$ such that $HF = R$ and the whiskering of $\beta$ with $F$ gives back $\alpha$. For an arbitrary $2$-category $\mathcal{K}$, an orthogonal factorisation system with such a property is deemed an enhanced factorisation system.
Theorem: (Lack, 4.10) If $\mathcal{K}$ is a $2$-category with an enhanced factorisation system $(\mathcal{L},\mathcal{R})$ having the property that if $j \in \mathcal{R}$ and $jk \cong 1$ then $kj \cong 1$, and if $T$ is a $2$-monad on $\mathcal{K}$ for which $T$ preserves $\mathcal{L}$-maps, then the inclusion $T\text{-Alg}_s \rightarrow \text{Ps-}T\text{-Alg}$ has a left adjoint, and the components of the unit of the adjunction are equivalences in $\text{Ps-}T\text{-Alg}$.
The proof starts by noting that if we have a pseudoalgebra $(X, x, \chi, \chi_0)$ then we can factorise $x:TX \rightarrow X$ as $TX \overset{e}{\longrightarrow} X' \overset{m}{\longrightarrow} X,$ where $e \in \mathcal{L}$ and $m \in \mathcal{R}$. Thus we have an invertible $2$-cell $\begin{array}{ccccc} T^2X & \overset{\mu_X}{\longrightarrow} & TX & \overset{e}{\longrightarrow} & X' \\ {}_{Te}{\downarrow} & \quad & \Downarrow^{\chi} & \quad & \downarrow^{m} \\ TX' & \underset{Tm}{\longrightarrow} & TX & \underset{x}{\longrightarrow} & X \\ \end{array}$ and, since $T$ preserves $\mathcal{L}$-maps, we can use the enhanced factorisation system to get a strict algebra $X'$ which is equivalent to $X$. (See Power’s coherence result for the details on this.)
It is interesting to see the scope of these results and the places in which people have considered this type of coherence problem before.
- Dunn proved the theorem-schema when $\mathcal{K}$ is the $2$-category of based topological categories and for which $T$ is a $2$-monad induced by a braided $\mathbf{Cat}$-operad.
- The theorem-schema was also proved by Hermida, though required much more of both the $2$-category $\mathcal{K}$ and the $2$-monad $T$, such as requiring existence and preservation of various limits and colimits, exactness properties relating these, as well as further conditions on the unit and multiplication of the $2$-monad. Something that does fall out of this alternative setup is that $T$ can be replaced by a new $2$-monad, on a different $2$-category, which is lax-idempotent.
- Rather more recently Nick Gurski and I wrote about operads with general groups of equivariance. Therein we showed that the $2$-monads which arise from $\mathbf{Cat}$-operads in this way satisfy the coherence conditions following the enhanced factorisation system route. These $2$-monads capture many different structures, including monoidal categories, braided monoidal categories, symmetric monoidal categories, and ribbon braided monoidal categories. Thus we can say, for example, that every unbiased braided monoidal category is equivalent to a braided strict monoidal category, and similarly for the other variations.
- The first theorem we mentioned above has three conditions, the third being the requirement that $\mathcal{K}$ is cocomplete and $T$ preserves $\alpha$-filtered colimits for some regular cardinal $\alpha$. We mentioned aboe that it was proved by Blackwell, Kelly, and Power that this is also sufficient to give a left adjoint to the inclusion $U : T\text{-Alg}_s \rightarrow T\text{-Alg}$. They also proved further that if $\mathcal{K}$ is locally $\alpha$-presentable then there is a $2$-monad $T'$ which preserves $\alpha$-filtered colimits and where $T'\text{-Alg}_s = \text{Ps-}T\text{-Alg}$. The result of the theorem we discussed then follows when $\mathcal{K}$ is locally presentable and $T$ preserves $\alpha$-filtered colimits. Lack comments that it is a major unsolved problem as to whether the entire theorem-schema can be shown to be true under these asumptions - and further whether it is true when $\mathcal{K}$ is only cocomplete.
Last summer I gave a little course on something I really like: Jeffrey Morton and Jamie Vicary’s work on the ‘categorified Heisenberg algebra’ discovered by Mikhail Khovanov. It ties together combinatorics and the math of quantum theory in a fascinating way… related to nice old ideas, but revealing a new layer of structure. I blogged about that course here, with links to slides and references.
The last two weeks I was in Paris attending a workshop on operads. I learned a lot, and it was great to talk to Mathieu Anel, Steve Awodey, Benoit Fresse, Nicola Gambino, Ezra Getzler, Martin Hyland, André Joyal, Joachim Kock, Paul-André Melliès, Emily Riehl, Vladimir Voevodsky… and many other people to whom I apologize for not including in this prestigious list! (The great thing about senility is never having to say you’re sorry, but I haven’t quite reached that stage.)
There is a lot I could say… but that will have to wait for another time. For now I just want to point out this annotated video:
• Spans and the categorified Heisenberg algebra.
of a talk at the Catégories, Logiques, Etc… seminar at Paris 7, run by Anatole Khelif. This should be a fairly painless introduction to the subject, since I sensed that lots of people in the audience wanted me to start by explaining prerequisites: categorification, TQFTs, 2-Hilbert spaces and the Heisenberg algebra.
That means I didn’t manage to discuss other interesting things, like the definition of symmetric monoidal bicategory, or the role of combinatorics, especially Young diagrams. For those, go here and check out the links!
There are lots of other videos of talks on the website of Khelif’s seminar (all in French so far, except mine). For example, here are some on Olivia Caramello’s work on topos theory, and its relation to the Langlands program:
- Olivia Caramello, Caractérisation d’invariants toposiques en termes de sites, January 16, 2013.
- Olivia Caramello, Théorie de Galois topologique, January 15, 2013.
- Laurent Lafforgue, Introduction au programme de Langlands et relation avec la théorie de Caramello, February 27, 2013.
And finally, one more digression. I got invited to speak at this seminar thanks to the help of Andrée Ehresmann, whom I recently met at the Dagstuhl workshop Categories at the Crossroads. She also invited me to IRCAM, the big experimental music lab in Paris. I took a photo of her in an anechoic chamber:
If you’re interested in IRCAM or how Moreno Andreatta, Alexandre Popoff and Andrée Ehresmann are working on music theory with the help of categories, you can read a bit about it here.
To make a long story short: a Klumpenhouwer network is a group under a diagram and over $Set$.
Representation theorists make good use of the “category algebra” construction. This is a way of turning a linear category (one whose hom-sets are vector spaces) into an associative algebra. In this post, I’ll describe what the category algebra is and why it seems to be important.
I’ll also ask two basic questions about the category algebra construction. I hope someone can tell me the answers.
First I’ll describe the category algebra construction. To make life easier for all of us, I’ll always use the word category to mean what category theorists would call a “category enriched in vector spaces”: one in which the hom-sets are vector spaces and composition is bilinear. Similarly, functors will be assumed to preserve this linear structure.
The construction takes as input a category $\mathbf{C}$ (assumed to have just a set of objects, not a proper class) and produces as output an associative algebra $\Sigma \mathbf{C}$, called its category algebra. As a vector space,
$\Sigma\mathbf{C} = \bigoplus_{c, d \in \mathbf{C}} \mathbf{C}(c, d)$
— the direct sum or coproduct of all the hom-sets of $\mathbf{C}$ (which, remember, are vector spaces). To define the multiplication on $\Sigma\mathbf{C}$, it’s enough to define the product $g \cdot f$ whenever $g$ and $f$ are maps in $\mathbf{C}$, and we do this by putting
$g \cdot f = \begin{cases} g \circ f &\text{if } domain(g) = codomain(f)\\ 0 &\text{otherwise.} \end{cases}$
In other words, multiplication is composition where that makes sense, and zero elsewhere.
(The notation $\Sigma\mathbf{C}$ for the category algebra is something I just made up. Is there standard notation?)
So far I’ve followed the time-honoured tradition of not bothering to say whether “algebras” are supposed to have a multiplicative identity. But actually, the issue of multiplicative identities is crucial to understanding category algebras.
Let me briefly try to explain why. The first observation is that if the category $\mathbf{C}$ has only finitely many objects, then the algebra $\Sigma\mathbf{C}$ does have a multiplicative identity. It’s $\sum_{c \in \mathbf{C}} 1_c$. If $\mathbf{C}$ has infinitely many objects then this sum makes no sense, so $\Sigma \mathbf{C}$ usually doesn’t have a multiplicative identity.
I’ll assume from now that $\mathbf{C}$ has only finitely many objects, so that $\Sigma\mathbf{C}$ is a unital algebra.
We’ll come back to the significance of identities in $\mathbf{C}$ and in $\Sigma\mathbf{C}$, but for now, let’s just observe:
- Taking the category algebra has the effect of concentrating all the identities of $\mathbf{C}$ into a single identity for $\Sigma\mathbf{C}$, with the individual identities $1_c$ of $\mathbf{C}$ being merely idempotents in $\Sigma\mathbf{C}$.
(The sum of all these idempotents is the multiplicative identity of $\Sigma\mathbf{C}$.) Alternatively, looking at it from the point of view of the algebra $\Sigma\mathbf{C}$:
- The multiplicative identity of $\Sigma\mathbf{C}$ is smeared all across the category $\mathbf{C}$, with one summand of the multiplicative identity $\sum_{c \in \mathbf{C}} 1_c$ attached to each object of $\mathbf{C}$.
Time for some examples.
Let $S$ be a finite preordered set — that is, a finite set equipped with a reflexive, transitive binary relation $\leq$. We can construct a category $\mathbf{C}$ from it as follows. Abstractly: view $S$ as an ordinary, unenriched category, then let $\mathbf{C}$ be the free linear category on it. Concretely, the objects of $\mathbf{C}$ are the elements of $S$, the hom-set $\mathbf{C}(s, t)$ is the ground field $k$ if $s \leq t$ and zero otherwise, and composition (where it’s nontrivial) is multiplication of scalars.
Now, the category algebra $\Sigma\mathbf{C}$ is a subalgebra of the algebra $M_S(k)$ of all $S \times S$ matrices over $k$. It consists of just those matrices $P$ satisfying the condition that $P(s, t)$ is only allowed to be nonzero when $s \leq t$.
A special case of the last example: let $S = \{1, \ldots, n\}$, with the obvious ordering. Then $\mathbf{C}$ is the category that you’d usually draw as $\bullet \to \bullet \to \quad \cdots \quad \to \bullet$ and $\Sigma\mathbf{C}$ is the algebra of $n \times n$ upper-triangular matrices.
Another special case: let $S = \{1, \ldots, n\}$ with the discrete ordering: $s \leq t \iff s = t$. Then $\mathbf{C}$ is the discrete category on $n$ objects — the disjoint union of $n$ copies of the ground field $k$ — and $\Sigma\mathbf{C}$ is the algebra of $n \times n$ diagonal matrices. Equivalently, $\Sigma\mathbf{C}$ is the $n$-fold product $k^n$.
A final special case: let $S = \{1, \ldots, n\}$ with the other trivial ordering: $s \leq t$ for all $s, t$. Then $\mathbf{C}$ is the codiscrete category on $n$ objects (so that all objects are isomorphic and all hom-sets are $k$), and $\Sigma\mathbf{C}$ is the full matrix algebra $M_n(k)$.
Why are category algebras important? I’m not sure I fully know, but here’s a fundamental fact:
A category and its category algebra are Morita equivalent.
What this means is that for any category $\mathbf{C}$, there’s an equivalence of categories
$[\mathbf{C}, \mathbf{Vect}] \simeq {\Sigma\mathbf{C}}\text{-}\mathbf{Mod}$
where the left-hand side is the category of functors $\mathbf{C} \to \mathbf{Vect}$. If you regard the algebra $\Sigma\mathbf{C}$ as a one-object category, then the right-hand side is the category of functors $\Sigma\mathbf{C} \to \mathbf{Vect}$.
So as far as linear representations are concerned, $\mathbf{C}$ and $\Sigma\mathbf{C}$ are the same thing.
How can we prove this equivalence? It’s one of those follow-your-nose proofs… but in following your nose, you discover the pivotal role of the identities.
In one direction, it’s straightforward: given a functor $F: \mathbf{C} \to \mathbf{Vect}$, put $X = \bigoplus_{c \in \mathbf{C}} F(c)$; then $X$ is a $\Sigma\mathbf{C}$-module in what is, if you think about it, an obvious way.
The other direction isn’t quite so obvious. Starting with a $\Sigma\mathbf{C}$-module $X$, how can we manufacture a functor $F: \mathbf{C} \to \mathbf{Vect}$? Given $X$ and an object $c \in \mathbf{C}$, we have to cook up a vector space $F(c)$. The key here is that, for each $c \in \mathbf{C}$, the element $1_c$ of $\Sigma\mathbf{C}$ is idempotent. It follows that $1_c \cdot - : X \to X$ is idempotent. The image of this map (which is also its set of fixed points) is a vector space; and that’s what we take $F(c)$ to be.
The rest of the details of this equivalence are easy enough, and I won’t bother you with them. Instead, I’ll show you one consequence of the equivalence, then ask you two questions.
First, here’s the consequence. It begins with the observation that equivalent categories don’t usually have isomorphic category algebras. Indeed, suppose we have two equivalent categories, $\mathbf{C}$ and $\mathbf{D}$. Then they’re certainly Morita equivalent. So, by using the result above, we get a chain of equivalences:
$\Sigma\mathbf{C}\text{-}\mathbf{Mod} \simeq [\mathbf{C}, \mathbf{Vect}] \simeq [\mathbf{D}, \mathbf{Vect}] \simeq \Sigma\mathbf{D}\text{-}\mathbf{Mod}$
The end result is that the categories $\Sigma\mathbf{C}$-modules and $\Sigma\mathbf{D}$-modules are equivalent. And, since $\Sigma\mathbf{C}$ and $\Sigma\mathbf{D}$ are not usually isomorphic, this isn’t quite trivial.
The most famous example is due to Morita. Say $\mathbf{C}$ is the codiscrete category on $n \geq 1$ objects (so that all hom-sets are the ground field $k$), and $\mathbf{D}$ is the codiscrete category on a single object. Then, as we saw earlier, $\Sigma\mathbf{C}$ is the full matrix algebra $M_n(k)$, while $\Sigma\mathbf{C} = M_1(k) = k$. But $\mathbf{C}$ and $\mathbf{D}$ are equivalent categories (since all objects of $\mathbf{C}$ are isomorphic), so
$M_n(k)\text{-}\mathbf{Mod} \simeq \mathbf{Vect}$
for any $n \geq 1$.
Now here are my two questions.
First question Is there a good categorical explanation of the category algebra construction?
The first observation is that the construction isn’t even functorial, or at least, not in the obvious way. A functor $F: \mathbf{C} \to \mathbf{D}$ does induce a linear map $\Sigma\mathbf{C} \to \Sigma\mathbf{D}$, but it doesn’t usually preserve multiplication. For instance, consider the obvious functor from the discrete category $\mathbf{C}$ on two objects to the discrete category $\mathbf{D}$ on one object. The induced linear map $k^2 \to k$ is addition, which is not a homomorphism of algebras.
Second question Does the category algebra construction suggest that we should study representations of categories rather than representations of algebras?
I need to explain the thinking behind this. The Morita equivalence between a category $\mathbf{C}$ and its category algebra $\Sigma\mathbf{C}$ tells us that from a representation-theoretic viewpoint, it doesn’t much matter which we use. However, if $\mathbf{C}$ has infinitely many objects then $\Sigma\mathbf{C}$ is usually not a unital algebra, and one may view a non-unital algebra as a rather deficient sort of thing. In that case, the thinking goes, it’s better to stick with the original category than pass to the category algebra.
Another way to put it: whenever you see a non-unital algebra (especially an infinite-dimensional one), ask yourself whether it’s the category algebra of some category with infinitely many objects. If it is, you might be better off working with the category rather than the algebra.
I picked up this point of view from a couple of different conversations with algebraists, but I’m not sure I’ve properly understood it. Let me test it out on a couple of examples. One of them kind of “works”, in the sense of corroborating this viewpoint. The other appears not to work at all.
Example Let $L^1(\mathbb{T})$ be the set of complex-valued integrable functions on the circle $\mathbb{T} = \mathbb{R}/\mathbb{Z}$. It’s a $\mathbb{C}$-algebra under addition and convolution.
This algebra has no multiplicative identity. If it did have one, it would be the Dirac delta function — that is, a function $\delta$ such that $\int_\mathbb{T} f \cdot \delta = f(0)$ for all integrable $f$. But, of course, no such delta function exists. This is what gives Fourier analysis its richness.
So we have before us an infinite-dimensional, non-unital algebra. The viewpoint described above tells us to look for a category of which it’s the category algebra. How can we do this?
Well, if $L^1(\mathbb{T}) = \Sigma\mathbf{C}$ for some category $\mathbf{C}$, then each object of $\mathbf{C}$ gives rise to an idempotent in $L^1(\mathbb{T})$. So we start by looking for the idempotents in $L^1(\mathbb{T})$. Since multiplication in $L^1(\mathbb{T})$ is convolution, this means looking for functions $f: \mathbb{T} \to \mathbb{C}$ such that $f \ast f = f.$ Since taking Fourier coefficients turns convolution into multiplication, this implies that each Fourier coefficient of $f$ is a multiplicative idempotent, that is, $0$ or $1$. Let’s write $e_k: x \mapsto e^{2\pi i k x}$ for the $k$th character of the circle ($k \in \mathbb{Z}$). Then $f = \sum_{k \in S} e_k$ for some $S \subseteq \mathbb{Z}$.
My thinking gets a bit fuzzy around here, but I think one can follow the argument through to show that the objects of $\mathbf{C}$ must be the integers (or if you prefer, the characters of $\mathbb{T}$), and that all the hom-sets are zero apart from an endomorphism ring $\mathbb{C}$ on each object. In other words, $\mathbf{C}$ is the discrete category on $\mathbb{Z}$.
The category algebra of this discrete category $\mathbf{C}$ consists of those double sequences $(c_k)_{k \in \mathbb{Z}}$ that are zero in all but finitely many places. Alternatively, you can think of this as the algebra of all trigonometric polynomials (that is, finite linear combinations of characters $e_k$).
This is not, of course, our original algebra $L^1(\mathbb{T})$. Most integrable functions on $\mathbb{T}$ are not trigonometric polynomials. So, you might say that the viewpoint advocated above has failed. However, perhaps it’s achieved some kind of moral victory. Although not every integrable function is a trigonometric polynomial, the whole theory of Fourier series tells us how, under various hypotheses and in various senses, arbitrary integrable functions can be expressed as limits of trigonometric polynomials. So perhaps it’s a category algebra in some suitably analytic sense.
Here’s another sign that this is a good point of view. When $\mathbf{C}$ is a category with infinitely many objects, we want to say that the identity of $\Sigma\mathbf{C}$ is $\sum_{c \in \mathbf{C}} 1_c$, except that this sum, being infinite, doesn’t exist. In the case of our particular $\mathbf{C}$, this sum is $\sum_{k \in \mathbb{Z}} e_k$, the sum of all the characters of $\mathbb{T}$. On the other hand, if the identity for convolution — the Dirac delta function — existed, then all its Fourier coefficients would be $1$. So this is exactly the nonexistent sum that the Dirac delta wants to be.
Non-example Here’s another commonly-encountered non-unital algebra, also arising in a soft-analytic context. But this one doesn’t seem to support the viewpoint advocated at all.
Gelfand duality tells us that the commutative not-necessarily-unital $C^\ast$-algebras are dual to the locally compact Hausdorff spaces, with a space $X$ corresponding to the $C^\ast$-algebra $C_0(X)$ of continuous functions $X \to \mathbb{C}$ that vanish at infinity. (The algebra operations are pointwise.) This restricts to a duality between unital commutative $C^\ast$-algebras and compact Hausdorff spaces.
In particular, if $X$ is a Hausdorff space that is locally compact but not compact, then $C_0(X)$ is a commutative algebra without a multiplicative identity. Concretely, the multiplicative identity of $C_0(X)$ would have to be the function with constant value $1$, but this does not vanish at infinity.
Is $C_0(X)$ a category algebra? Apparently not. Again, if it was one, each object of the category would give rise to an idempotent in $C_0(X)$. But in general, $C_0(X)$ has no nontrivial idempotents. For the algebra structure on $C_0(X)$ is pointwise multiplication, so an idempotent in $C_0(X)$ is just a function taking only the values $0$ and $1$; but assuming $X$ is connected, this forces the function to have constant value zero.
Perhaps this failure is somehow due to my ignoring the extra structure on $C_0(X)$. I’ve been treating it as a mere associative algebra, not a $C^\ast$-algebra. But I’m not convinced… can anyone help?
What I’d most like is for someone to explain a bit more the viewpoint that non-unital algebras are often categories in disguise. And some compelling examples would be even better.
A month ago, the newsletter of the London Mathematical Society published an opinion piece of mine, Should mathematicians cooperate with GCHQ?. It has just published an opposing opinion by Richard Pinch, GCHQ’s Strategic Advisor for Mathematics Research and formerly a number theorist at Cambridge.
Pinch’s reply is short and curiously insubstantial. First he makes a couple of general assertions in opposition to what I wrote. But unlike my piece, which linked heavily to sources, he provides no evidence for his assertions. Nor does he dispute any of the specific facts stated in my article. Then he quotes a politician and the director of GCHQ saying that they believe GCHQ operates with integrity. And that’s it.
So it’s almost too flimsy to be worth answering. However, it’s probably worth rebutting even insubstantial arguments when they come from people in positions of influence. Here’s my rebuttal.
Richard Pinch writes:
Dr Leinster’s opinion piece makes a range of allegations of unethical and unlawful conduct against GCHQ.
Whether GCHQ’s conduct is unlawful is not something I’m qualified to judge, and I didn’t: I wrote that it was “accused of law-breaking on an industrial scale”. Some of those doing the accusing are very well-qualified to do so. E.g. here’s the opinion of a Queen’s Counsel (a high rank of lawyer in the British system) specializing in public law:
- Huge swath of GCHQ mass surveillance is illegal, says top lawyer. The Guardian, 28 January 2014.
Then there’s European law:
- NSA and GCHQ activities appear illegal, says EU parliamentary inquiry. The Guardian, 9 January 2014.
And then there’s GCHQ’s own opinion:
- Leaked memos reveal GCHQ efforts to keep mass surveillance secret. The Guardian, 25 October 2013.
This article describes GCHQ internal memos showing how it feared legal challenge in the European courts if the existence of its mass surveillance programmes became known. So even GCHQ was well aware that its methods were legally precarious, at the very least.
All these articles were linked to in my original piece.
Pinch continues:
The allegations are so widely drawn that it is impossible for GCHQ to recognise them as a description of its activities.
Snowden’s leaks provide detailed documentary evidence for my claims. Neither GCHQ nor the NSA has challenged their authenticity. For every allegation I made in my article, I linked to either the documents or journalism based on them. The leaked documents are available for anyone to read.
Pinch provides no evidence of any kind in his article. Nor does he deny any specific assertion that I made.
Continuing with Pinch’s article:
GCHQ, along with the other intelligence agencies of the UK, is subject to some of the most rigorous legislative and oversight arrangements in the world.
Compare the statement of one of GCHQ’s own lawyers:
“We have a light oversight regime compared with the US”.
(The legal loopholes that allow GCHQ to spy on the world. The Guardian, 21 June 2013.)
How rigorous is “light oversight […] compared with the US”? Well, the secret court that regulates the NSA (and to which the NSA has been legally found to have lied repeatedly) rejects just 1 in 3000 of the NSA’s surveillance requests. And GCHQ claims an oversight regime that’s even lighter.
It’s not just this one GCHQ lawyer who says that GCHQ is more weakly regulated than the NSA:
in the documents GCHQ describes Britain’s surveillance laws and regulatory regime as a “selling point” for the Americans.
(Exclusive: NSA pays £100m in secret funding for GCHQ. The Guardian, 1 August 2013.) Update: See also this comment below.
(Incidentally, it’s not clear whether GCHQ gets away with whole-population surveillance by being so weakly controlled that it can break the law with impunity, or by not needing to break the law because the law’s so weak. As I said, I’m not qualified to judge what’s legal, and actually, legality isn’t of primary interest to me — as we all know, laws can be arbitrary or wrong.)
Pinch continues:
These ensure that all the work of the agencies is carried out in accordance with a strict legal and policy framework so that their activities are at all times legal, authorised, necessary and proportionate.
Whether it’s legal, I’ve already discussed. As for “policy framework”: sure, presumably the vast surveillance programmes being run by GCHQ do fit into some internal policy framework, but it’s no kind of democratic policy. Obviously there was no public discussion, but far more radically, even a senior Member of Parliament on the UK National Security Council claims not to have known:
- Cabinet was told nothing about GCHQ spying programmes, says Chris Huhne. The Guardian, 6 October 2013.
The rest of Pinch’s piece consists of pro-GCHQ quotes from the British Foreign Secretary and the Director of GCHQ. I could say pro-GCHQ things too; like just about everyone, I believe that some of what GCHQ does is worthwhile and justified. But that’s just opinion.
It’s the facts revealed by the Snowden papers that are so shocking. And when it comes to the facts, Pinch has disputed no factual statement about GCHQ made in my article, nor has he given us any reason to disbelieve the evidence before our eyes.
I’ve got a full-page opinion piece in this week’s New Scientist, on why mathematicians should refuse to cooperate with agencies of mass surveillance. If you’re in the US, UK or Australia, it’s the print edition that came out yesterday.
The substance is much the same as my piece for the London Mathematical Society Newsletter, but it’s longer, and it’s adapted for a US readership too.
I don’t currently have much to add to the article or what I wrote about mathematicians and the secret services previously. But I do have some observations to make about the process of writing for New Scientist.
This was my first time writing for a magazine. The article received substantial edits from at least three editors; you can compare it with the version I originally submitted. I have mixed feelings about this process.
On the one hand, it’s great to have the input of experienced magazine journalists, and I can definitely see ways that they improved what I wrote. On the other hand — and despite the editors I dealt with being reasonable, helpful, and pleasant — I found the process pretty frustrating. I think that’s because of where the control lies.
What doesn’t happen is that you submit your piece, the editors read it and give you their critiques, and then you amend your article accordingly. What does happen is that you submit something, the editors change it how they like, and if you don’t like any of their changes, you have to argue for why it should be changed back. This process may be iterated several times, perhaps with different editors with different opinions. Rationally, I know that the article goes out not only under my name but also under the magazine’s, but by the end of the process, I did have the depressing feeling that the article wasn’t entirely mine.
(Small example: there were three words that I disliked and repeatedly removed from the editor’s edits: “moral”, “snoop” and “spook”. The editors I dealt with directly respected my wish to avoid them, after I’d made the case. But in the online version, the headline and the standfirst — which I neither wrote nor saw before publication — managed to use two out of those three words.)
Anyway, it was a new experience.
Comments are open. As ever, if you’re leaving comments on the political aspects, please keep them focused on the relationship between mathematicians and the secret services.
Update Here’s a list of the various press articles that followed on from my original article:
- Mathematician Spies, Slate, 27 April 2014. (Reprint of New Scientist article)
- Mathematicians: refuse to work for the NSA!, Boing Boing, 27 April 2014
- Mathematicians Push Back Against The NSA, Slashdot, 27 April 2014
- Un mathématicien appelle ses collègues à ne plus travailler pour la NSA, Mediapart, 28 April 2014 (free version here)
- Mathematiker ruft zum Geheimdienst-Boykott auf, Zeit Online, 28 April 2014
- Mathematiker-Aufruf: Arbeitet nicht für die Geheimdienste!, Spiegel Online, 28 April 2014.
Congratulations to Mike for being a part of a research team who will receive $7. 5 million to carry on the good work of the IAS Univalent Foundations program. Homotopy Type Theory: Unified Foundations of Mathematics and Computation will run for five years, organised by Steve Awodey at CMU. (Technical portion of the grant proposal is here.)
I hope they’re allowed to use some of that funding to spill into physics a little.
Guest post by Sam van Gool
Monads provide a categorical setting for studying sets with additional structure. Similarly, 2-monads provide a 2-categorical setting for studying categories with additional structure. While there is really only one natural notion of algebra morphism in the context of monads, there are several choices of algebra morphism in the context of 2-monads. The interplay between these different kinds of morphisms is the main focus of the paper that I discuss in this post:
- [BKP] Two-dimensional monad theory, R. Blackwell, G. M. Kelly and A. J. Power, J. Pure and Appl. Algebra 59 (1989), pp. 1-41.
I will give an overview of the results and methods used in this paper. Also, especially towards the end of my post, I will also indicate some points that I think could still be clarified further by formulating some questions, which will hopefully lead to fruitful discussions below.
This post forms the 9th instalment of the series of posts written by participants of the Kan Extension Seminar, of which I’m very glad to be a part. In preparing the post I have greatly benefited from discussions with the other participants in the seminar, and of course with the seminar’s organizer, Emily Riehl. I am very grateful for the enthusiasm, encouragement and guidance that you all offered.
2-monads, their algebras, and their morphisms
Two-dimensional universal algebra goes beyond the $\mathbf{Cat}$-enriched setting in that it allows for non-strict morphisms. Consider the following (very) simple example.
Example. For a category $A$, let $T A$ be the category $A$ provided freely with a terminal object. This assignment can be extended to a 2-monad $T$ on $\mathbf{Cat}$. Then:
- an algebra for $T$ is (entirely determined by giving) a pair $(A,t_A)$ where $A$ is a category and $t_A$ is a designated terminal object in $A$;
- a strict morphism $(A,t_A) \to (B,t_B)$ is a functor $f$ for which $f(t_A) = t_B$;
- a pseudo morphism is a functor $f$ such that $f(t_A)$ is isomorphic to $t_B$;
- a colax morphism is just any functor from $A$ to $B$, with no additional requirement on the terminal object.
If you didn’t know them already, you will probably have guessed the general definitions of strict, pseudo and lax morphisms by now, as well as the definition of 2-cells between them. Note that, in this post, all 2-monads and algebras for them will be strict, as in [BKP].
For any 2-monad $T$, we thus get the following inclusions of 2-categories:
$T\text{-}\mathrm{Alg}_s \to T\text{-}\mathrm{Alg}_p \to T\text{-}\mathrm{Alg}_l.$
(In [BKP], the category $T\text{-}\mathrm{Alg}_p$ is denoted by $T\text{-}\mathrm{Alg}$.) Roughly the first half of the paper [BKP] is devoted to the construction of left adjoints (in the 2-categorical sense) to these inclusion functors.
Note that $T\text{-}\mathrm{Alg}_s$ is simply the Eilenberg-Moore $\mathcal{V}$-category of the $\mathcal{V}$-enriched monad $T$ in the case where $\mathcal{V} = \mathbf{Cat}$, in the sense of the second paper that we read in this seminar. The categories $T\text{-}\mathrm{Alg}_p$ and $T\text{-}\mathrm{Alg}_l$, on the other hand, are special to the $\mathbf{Cat}$-enriched setting.
Limits in $T$-Alg$_p$
The category $T\text{-}\mathrm{Alg}_s$ has all 2-limits that the base 2-category $\mathcal{K}$ has. For $T\text{-}\mathrm{Alg}_p$, the situation is more subtle.
Example (c’t’d). In the example where $T A$ is $A$ provided freely with a terminal object, let $1 = \{\ast\}$ be the terminal category and $I$ the category with two objects $0$, $1$ and a unique isomorphism between them. There are two pseudo-morphisms $(1,\ast) \to (I,0)$, one sending $\ast$ to $0$, the other sending $\ast$ to $1$. However, if $C \to 1$ is any functor which equalizes these two morphisms, then $C$ is empty, and so it does not admit a $T$-algebra structure. Thus, the category $T\text{-}\mathrm{Alg}_p$ does not admit equalizers in general.
Assuming that the $2$-category $\mathcal{K}$ is complete, it is however possible to construct the following limits in $T\text{-}Alg_p$:
- Products,
- Inserters and iso-inserters,
- Equifiers,
and they are created by the forgetful functor $T\text{-}Alg_p \to \mathcal{K}$. As we saw in last week’s post, these PIE-limits allow for the construction of many other limits. In particular, from the results discussed last week, we see that $T\text{-}\mathrm{Alg}_p$ also has inverters and co-tensors, and hence also lax and pseudo limits.
It is also worth noting that each of the results on existence of limits “restricts to strict” (for lack of a better name), by which I mean that, for each of these limits, there exists a limiting cone such that the algebra 1-cells in the limiting cone:
are strict, and
detect strictness.
For example, for any parallel pair $f, g : B \to C$ in $T\text{-}\mathrm{Alg}_p$ there is an inserter $p : A \to B$ such that (1) $p$ is strict, and (2) if $ph$ is strict for some algebra morphism $h : D \to A$, then $h$ is strict.
The pseudomorphism classifier
Example (c’t’d). In the example where $T A$ is $A$ provided freely with a terminal object, note that pseudo-morphisms can be mimicked using strict morphisms: for any algebra $(A,t_A)$, consider the algebra $(A',t_{A'})$, defined by adding one new object $t_{A'}$ and an isomorphism $t_{A} \cong t_{A'}$ to $A$. It is then clear that, for any algebra $(B,t_B)$, strict morphisms $(A',t_{A'}) \to (B,t_B)$ correspond to pseudo-morphisms $(A,t_A) \to (B,t_B)$. In fact, this correspondence is an isomorphism between the categories of morphisms and natural transformations between them.
The following theorem, which is arguably at the heart of the paper [BKP], says that the above phenomenon in fact occurs for any reasonably well-behaved 2-monad.
Theorem. Let $T$ be an accessible 2-monad on a 2-category $\mathcal{K}$ that is complete and cocomplete. Then the inclusion 2-functor $T\text{-}\mathrm{Alg}_s \to T\text{-}\mathrm{Alg}_p$ has a left adjoint.
Proof (Sketch). The proof of the theorem consists of three steps:
- A general fact: in order to find a left adjoint to a 2-functor $G : \mathcal{K} \to \mathcal{L}$, it suffices to find a left adjoint to its underlying ordinary functor $G_o$, provided that $\mathcal{K}$ has cotensors with the walking arrow category $2$ and $G$ preserves them.
- Using (1), one shows that there exists a left adjoint, $()^o$, to the inclusion functor $T\text{-}\mathrm{Alg}_s \to T/{\mathcal{K}},$ where $T/{\mathcal{K}}$ is the comma 2-category.
- The hardest part: pseudo-morphisms out of a $T$-algebra $(A,a)$ can be mimicked by $T/\mathcal{K}$-morphisms out of a certain object $(C,c,Z)$ of $T/{\mathcal{K}}$.
Now, composing (2) and (3), one associates to any $T$-algebra $(A,a)$ the $T$-algebra $(C,c,Z)^o$ and observes that this gives an ordinary (1-categorical) left adjoint to $T\text{-}\mathrm{Alg}_s \to T\text{-}\mathrm{Alg}_p$. Then, by (1) and the fact that cotensors exist in $T\text{-}\mathrm{Alg}_p$, it is also a 2-categorical left adjoint. $\qed$
The image under the left adjoint of an algebra $A$, seen as an object of $T\text{-}\mathrm{Alg}_p$, is denoted by $A'$ and called the pseudo-morphism classifier of $A$. Under the conditions of the Theorem, there is also a lax morphism classifier.
There are more conceptual proofs of these facts, using the concept of codescent objects; see, for example, this paper (which will be discussed in these series in a month or so) and Section 4 of the 2-categories companion by Stephen Lack. The latter paper, by the way, has been an indispensable source for me in preparing this post, and those who are familiar with it will probably recognize its influence throughout the post.
Flexibility
We denote by the letters $p$ and $q$ the unit and co-unit of the adjunction
$J : T\text{-}\mathrm{Alg}_s \leftrightarrows T\text{-}\mathrm{Alg}_p : ()'$
from the above theorem. For any algebra $A$ in $T\text{-}\mathrm{Alg}_p$, the morphism $q_A : A' \to A$ is in fact always a surjective equivalence in the 2-category $T\text{-}\mathrm{Alg}_p$, but in general $q_A$ does not even need to be an equivalence in $T\text{-}\mathrm{Alg}_s$, as we will see shortly. If $q_A : A' \to A$ is an equivalence in $T\text{-}\mathrm{Alg}_s$, then $A$ is called semi-flexible, and $A$ is called flexible if $q_A$ is a surjective equivalence in $T\text{-}\mathrm{Alg}_s$. The flexible objects are the cofibrant objects in a model structure on $T\text{-}\mathrm{Alg}_s$ lifted from the model structure on $\mathcal{K}$, and the pseudomorphism classifier $A'$ is then a special cofibrant replacement of $A$ (see Section 7.3 of the 2-categories companion for more details about this).
Several equivalent characterizations of flexibility and semi-flexibility are given in Theorems 4.4 and 4.7, respectively, of [BKP]. One useful equivalent way to say that a $T$-algebra $A$ is semi-flexible is that every pseudo-morphism out of $A$ is isomorphic to a strict morphism out of $A$. With this definition, we can see that not every $T$-algebra is semi-flexible:
Example. Let $T$ be the 2-monad on $\mathbf{Cat}$ whose algebras are small categories with assigned finite limits. Let $A$ be the terminal category, with finite limits assigned in the only possible way. Let $B$ be any category with assigned finite limits in which $t_B$ is the assigned terminal object and the assigned product $t_B \times t_B$ is not equal to $t_B$ (the two objects will of course be isomorphic). Then the functor $A \to B$ which sends the unique object of $A$ to $t_B$ is a pseudo-morphism, but it is clearly not isomorphic to any strict morphism.
The following example shows that flexibility and semi-flexibility are really different concepts.
Example. Categories whose objects are functors can also often be represented as the $T$-algebras for an appropriate monad $T$ on an appropriate base 2-category $\mathcal{K}$. For instance, there is a 2-monad $T$ on $\mathbf{Cat} \times \mathbf{Cat}$, given on objects by $T(X,Y) := (X,X+Y)$, such that $T$-algebras are functors, a pseudomorphism from $f : A \to B$ to $g : C \to D$ is a diagram of the form $\begin{matrix} A & \overset{f}{\to} & B \\ u \downarrow & \overset{\alpha}{\cong} & \downarrow v \\ C & \overset{g}{\to} & D \end{matrix}$ and such a pseudomorphism is strict exactly when $\alpha$ is the identity. Now, letting $1$ denote the terminal category, it is easy to describe the pseudomorphism classifier of the $T$-algebra $a : A \to 1$: this is the inclusion functor $j : A \to \overline{A}$, where $\overline{A}$ is the indiscrete category on objects $\mathrm{ob}(A) + \{\ast\}$ (As a simple but nice exercise, you may check that, indeed, any pseudomorphism out of the algebra $a : A \to 1$ corresponds uniquely to a strict morphism out of the algebra $j : A \to \overline{A}$.) Now, letting $I$ again denote the category with two objects $0$, $1$ and a unique isomorphism between them, one may check that the algebra $I \to 1$ is equivalent in $T\text{-}\mathrm{Alg}_s$ to the algebra $1 \to 1$, which is flexible, and therefore $I \to 1$ is semi-flexible. However, $I \to 1$ is not flexible. (See example 4.11 in [BKP]).
Biadjunctions and bicolimits in $T\text{-}\mathrm{Alg}_p$
So far, we have only considered limits, which one would expect to exist in a category of algebras. On the other hand, we wouldn’t generally expect colimits to exist in a category of algebras, but as it turns out, in the last section of [BKP], the authors prove that:
- the category $T\text{-}\mathrm{Alg}_p$ admits bicolimits, and
- any strict map of 2-monads $\theta : S \to T$ induces a map $T\text{-}\mathrm{Alg}_p \to S\text{-}\mathrm{Alg}_p$ that has a left biadjoint.
Both of these results are consequences of the following more technical fact:
Theorem. If $G : T\text{-}\mathrm{Alg}_p \to \mathcal{L}$ is a 2-functor so that the composite 2-functor
$\begin{matrix} T-Alg_s & \overset{J}{\to} & T-Alg_p & \overset{G}{\to} & L \end{matrix}$
has a left adjoint $H$, then $H$ maps into flexible algebras, and $J \circ H$ is left biadjoint to $G$.
From the above theorem and the relation between biadjoints and bicolimits that we discussed last week, bicolimits can now be constructed in $T\text{-}\mathrm{Alg}_p$, as claimed in (1) above. To prove (2), one first notices that 2-functor $\theta^* : T\text{-}\mathrm{Alg}_s \to S\text{-}\mathrm{Alg}_s$ extends to a 2-functor $\theta^\# : T\text{-}\mathrm{Alg}_p \to S\text{-}\mathrm{Alg}_p$ making the diagram
$\begin{matrix} T\text{-}\mathrm{Alg}_s & \overset{\theta^*}{\to} & S\text{-}\mathrm{Alg}_s \\ J\downarrow & \quad & \downarrow J \\ T\text{-}\mathrm{Alg}_p & \overset{\theta^\sharp}{\to} & S\text{-}\mathrm{Alg}_p \end{matrix}$
commute. One may then apply the Theorem in the case $G = \theta^\#$.
More examples of 2-monads
Above I motivated the concepts and theorems in [BKP] with some simple examples of 2-monads. The last section of [BKP] contains many more examples. About the general method for constructing such examples, the authors make the following interesting comment.
“In practice one is seldom presented with a 2-monad and invited to consider its algebras; more commonly one contemplates some structure borne by a category (…) and one concludes in certain cases that the structure is given by an action of a 2-monad (…)”
With this comment in mind, one may now construct 2-monads whose algebras are monoidal categories, symmetric monoidal closed categories (here the 2-monad is over the 2-category $\mathbf{Cat}_g$, where the 2-cells are only taken to be natural isomorphisms), and even finitary 2-monads themselves (they are the algebras for a certain 2-monad $R$ on the functor 2-category $[\mathbf{Cat}_f,\mathbf{Cat}]$, where $\mathbf{Cat}_f$ is the full subcategory of $\mathbf{Cat}$ consisting of the finitely presentable objects. This perspective was exploited in a later paper by Kelly and Power on presentations of 2-monads.
A final point of interest is that one may distinguish a special kind of 2-monad $T$, namely those for which the $T$-algebra structure on an object $A$ is unique if it exists. Such 2-monads $T$ define a property of rather than a structure on the objects of the base 2-category $\mathcal{K}$, and may thus be called property-like (as they are in this later paper by Kelly and Lack). As the authors of [BKP] remark, it “may well be a hard problem” how to distinguish the property-like 2-monads $T$ from, say, a presentation for them. A particular class of 2-monads which are ‘property-defining’ are the lax-idempotent 2-monads (which also go by the names “quasi-idempotent” and “Kock-Zöberlein” 2-monads).
Questions
Let me finish with a (non-exhaustive) list of questions that may be interesting to discuss below.
Can the fact that limits in $T\text{-}\mathrm{Alg}_p$ can be chosen with a fair amount of “strictness” be understood using this account of lax / pseudo limits for morphisms between $T$-algebras using $\mathcal{F}$-enrichment?
The flexible algebras are exactly the strict retracts of pseudomorphism classifiers. The latter are “free algebras”, in some sense (at least in the sense that they are the images of a left adjoint). This suggests that one could think of the concept ‘flexible algebra’ as a 2-categorical version of the familiar concept ‘projective algebra’ in the 1-categorical setting. Is this a good intuition, and if so, can it be (or has it already been) made more precise?
In order to better understand the concept of flexible algebra and the biadjunctions in the later part of [BKP], it would probably be useful to study different examples of 2-monads, and in particular, answer the following questions in such examples:
(a) is there a concrete construction of the pseudomorphism classifier?
(b) which algebras are (semi-)flexible?
(c) (for a strict map between 2-monads) what does the biadjunction do?