Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

October 17, 2006

Classical vs Quantum Computation (Week 2)

Posted by John Baez

Here are the notes for the latest installment of my course on classical versus quantum computation:

  • Week 2 (Oct. 12) - Monoidal categories versus cartesian categories. Closed monoidal categories.

Last week’s notes are here; next week’s notes are here.

This week we introduced string diagrams for “duplication and deletion of information” in cartesian categories. We also talked about closed monoidal categories, and used string diagrams to show how applying a function to an argument is related to the annihilation of a particle-antiparticle pair!

I’m sorry it took a while to get these written up and scanned in. Our usual note-taker, Derek Wise, was gone, and I ran off to San Francisco right after class to give a talk at the Long Now Seminar.

Posted at October 17, 2006 11:45 PM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/991

83 Comments & 3 Trackbacks

Re: Classical vs Quantum Computation (Week 2)

The “unit” string-diagram laws on page 21 can be paired with an “associativity” string-diagram law stating that (Δ × id) and (id × Δ) become equal when preceded by Δ (both composites simply triple information). Here is a cheap ASCII drawing:

    |         |
   / \       / \
  |   |  =  |   |
 / \  |     |  / \
|   | |     | |   |

These laws should be all that you need to manipulate Δ and ! in string diagrams mechanically.

It would be nice if (in general closed monoidal categories, not just in compact ones) the evaluation map X ⊗ hom(XY) → Y (see the final page) could be drawn invisibly (like the other natural maps in a closed monoidal category). You would need to have the “ribbon” hom(XY) open up; perhaps the correct metaphor is a zipper?

Posted by: Toby Bartels on October 18, 2006 2:32 AM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

Toby wrote:

    |         |
   / \       / \
  |   |  =  |   |
 / \  |     |  / \
|   | |     | |   |

These laws should be all that you need to manipulate Δ and ! in string diagrams mechanically.

Cool!

You just drew the coassociative law, while I drew the counit law:

       |        |         |  
      / \       |        / \ 
     /   |  =   |   =   |   \
         |      |       | 
         |      |       |

Together these say that Δ A\Delta_A and ! A!_A make any object AA in a cartesian category into a comonoid - just like a monoid, but upside down, with Δ A\Delta_A as comultiplication and ! A!_A as counit.

I’m not sure these are all we need to reason with Δ\Delta and !! diagrammatically. I have a characterization of cartesian categories in terms of Δ\Delta and !! on page 47 of my universal algebra notes. My characterization includes the counit law, but not the coassociative law - instead, it requires that ! A!_A and Δ A\Delta_A are monoidal natural transformations. I guess coassociativity follows somehow… is there are alternative characterization the uses coassociativity, and avoids the “universal quantifier over morphisms” built into the definition of “natural transformation”?

It would be nice if (in general closed monoidal categories, not just in compact ones) the evaluation map X ⊗ hom(XY) → Y (see the final page) could be drawn invisibly (like the other natural maps in a closed monoidal category). You would need to have the “ribbon” hom(XY) open up; perhaps the correct metaphor is a zipper?

Indeed, I’ve been spending weeks looking for a beautiful string diagram notation for general closed monoidal categories, hampered by the fact that only the compact ones seems “truly topological in nature”. I’ll keep trying… I like the “zipper” idea.

Posted by: John Baez on October 18, 2006 3:02 AM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

Doesn’t Δ\Delta have to be a symmetric monoidal natural transformation, for your characterisation to work?

Posted by: Robin on October 18, 2006 12:21 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

Robin wrote:

Doesn’t Δ have to be a symmetric monoidal natural transformation, for your characterisation to work?

Damn!

I guess you must be right if I were trying to characterize cartesian categories amongst symmetric monoidal categories, as I claim to be doing on page 47 of those universal algebra notes. Otherwise the symmetry would be an extra structure with nothing to connect it to Δ and ! except its naturality.

But I did a bunch of calculations to check this claim, and I can’t believe I was completely confused. Perhaps I was actually characterizing cartesian categories amongst monoidal ones… which is what’s on my mind now, too.

In my course this fall, I haven’t even mentioned symmetric monoidal categories yet! I’m just comparing monoidal categories to cartesian ones, so far in a very informal way.

There should be lots of different characterizations of cartesian categories. Some should start with symmetric monoidal categories and others with monoidal categories. Some should use coassociativity as Toby suggested - and cocommutativity, in the symmetric case! Others should not. Some should use naturality of Δ and !, but Peter Selinger told me that some don’t.

Does anyone know references for such theorems?

Posted by: John Baez on October 18, 2006 4:32 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

I suspect that the symmetry is indispensible here, because without it I don’t see how to put a monoidal structure on the functor XXXX \mapsto X\otimes X. And without a monoidal structure on that functor, it doesn’t make sense to say that Δ\Delta is any kind of monoidal natural transformation!

Also, at least by my calculation, I need to use the fact that Δ\Delta preserves the symmetry in order to show that the fill-in arrow for the product is unique.

More interestingly: for every symmetric monoidal category \mathbb{C}, there is a symmetric monoidal category Comon()Comon(\mathbb{C}) of commutative comonoids in \mathbb{C}. (Notice that the analogous thing without symmetry is not true: the category of comonoids in a monoidal category is not generally itself a monoidal category.)

This extends to an idempotent 2-comonad ComonComon on SMonCat, and the coalgebras for this comonad are exactly the cartesian categories! (Idempotent comonads are property-like, meaning that the coalgebra structure is unique where it exists, and it exists precisely when the counit component is invertible. So that gives one characterisation of cartesian categories among symmetric monoidal ones.)

Posted by: Robin on October 19, 2006 11:39 AM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

Also, at least by my calculation, I need to use the fact that Δ preserves the symmetry in order to show that the fill-in arrow for the product is unique.

Tom Hirshowitz has very gently pointed out to me that I was mistaken here. There’s no need to assume that Δ\Delta is symmetric monoidal; the argument works perfectly well if it’s merely monoidal. (Looking back at my old continuation report, I see that I used to know this!)

I also think that John’s concern:

Otherwise the symmetry would be an extra structure with nothing to connect it to Δ and ! except its naturality.

is thankfully unwarranted. Any symmetry is forced to be the canonical symmetry map, because of the requirement that

λ Aσ A,I:AIIAA\lambda_A\sigma_{A,I}: A\otimes I \to I\otimes A \to A

be equal to ρ A\rho_A.

In other words, the characterisation in John’s universal algebra notes is absolutely right and I’m an idiot.

Posted by: Robin on October 25, 2006 1:30 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

In other words, the characterisation in John’s universal algebra notes is absolutely right and I’m an idiot.

Yay!

Whoops. I mean, not yay that you’re an idiot (since you’re not), but yay that I was right.

I still haven’t had time to find my old calculations: I have lots of notebooks of old work and I’d have to find the one I was using in Marseille when I gave those talks. But, Tom has emailed me the argument you folks came up with. It’s more elaborate that anything I remember… but you guys didn’t exploit Mac Lane’s coherence theorem.

The proof of this result deserves to be publicly visible. I’ll ask Tom if I can put his email on this blog.

Posted by: John Baez on October 26, 2006 1:04 AM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

Tom Hirschowitz sent me the following in email. With his permission I’ll post it here, just to lessen the work a bit for other people interested in tracking down these issues.

Robin and I seem to agree on the following proof sketch. In case you’re not interested in the details, the conclusion is that you seem to be right, though slightly elliptic.

On page 47, you leave implicit the way in which the functor 
A |→ (A \otimes A) is supposed to be monoidal.  But, 
writing aa for the associator and gg for the symmetry
(or braiding), if one assumes the mediating isomorphism 
Φ\Phi between
(AA)(BB)(A \otimes A) \otimes (B \otimes B)
and
(AB)(AB)(A \otimes B) \otimes (A \otimes B)
to be (fasten your seat belt):
(AA)(BB)(A \otimes A) \otimes (B \otimes B) | | a 1a^{-1} | v A(A(BB))A \otimes (A \otimes (B \otimes B)) | | idaid \otimes a | v A((AB)B)A \otimes ((A \otimes B) \otimes B) | | id(gid)id \otimes (g \otimes id) | v A((BA)B)A \otimes ((B \otimes A) \otimes B) | | ida 1id \otimes a^{-1} | v A(B(AB))A \otimes (B \otimes (A \otimes B)) | | aa | v (AB)(AB)(A \otimes B) \otimes (A \otimes B),
then unicity of the pairing <f,g>=(fg)oΔ&lt;f,g&gt; = (f \otimes g) o \Delta follows from the fact that Δ\Delta is monoidal. There are two points to check here: (1) Φ\Phi makes our functor monoidal and (2) unicity follows. We haven’t checked (1) yet but here is the argument for (2) (shortened):
Δ\Delta being monoidal, the following commutes: ΔΔ\Delta \otimes \Delta ABA \otimes B —————————–> (AA)(BB)(A \otimes A) \otimes (B \otimes B) || | || | Φ\Phi || Δ\Delta v ABA \otimes B —————————–> (AB)(AB)(A \otimes B) \otimes (A \otimes B)
Then, unicity seems to follow from the fact that <π,π>=id&lt;\pi, \pi'&gt; = id. If so, we just have to prove that the following is the identity (writing ee for the eraser, rr for the right unitor, ll for the left unitor):
ABA \otimes B | | Δ\Delta v (AB)(AB)(A \otimes B) \otimes (A \otimes B) | | (ide)(eid)(id \otimes e) \otimes (e \otimes id) | v (AI)(IB)(A \otimes I) \otimes (I \otimes B) | | rlr \otimes l | v ABA \otimes B
Using the previous diagram, this amounts to showing that
ABA \otimes B | | ΔΔ\Delta \otimes \Delta v (AA)(BB)(A \otimes A) \otimes (B \otimes B) | | Φ\Phi v (AB)(AB)(A \otimes B) \otimes (A \otimes B) | | (ide)(eid)(id \otimes e) \otimes (e \otimes id) | v (AI)(IB)(A \otimes I) \otimes (I \otimes B) | | rlr \otimes l | v ABA \otimes B
is the identity. But by the coherence laws of symmetric monoidal categories, and without touching the Δ\Delta’s, this reduces to
ABA \otimes B | | ΔΔ \Delta \otimes \Delta | v (AA)(BB)(A \otimes A) \otimes (B \otimes B) | | (ide)(eid) (id \otimes e) \otimes (e \otimes id) | v (AI)(IB)(A \otimes I) \otimes (I \otimes B) | | rlr \otimes l | v ABA \otimes B
which is the tensor of the hypotheses on Δ\Delta and ee, hence the identity.

This looks promising. And yes, now the details are coming back to me. I wish my weekend were sufficiently relaxed to dig up my Marseille notebook and find/redo those calculations - I’m not sure it will be.

You can lighten your load a bit when doing calculations like this if you take advantage of Mac Lane’s coherence theorem. This says you don’t need to worry about the associator aa and the unitors ll and rr - you can assume they’re all identity morphisms.

More precisely, this theorem says any symmetric monoidal category is symmetric monoidal equivalent to a strict one: one where aa, ll and rr are identities.

So, if you’re proving a result whose conclusions are preserved by symmetric monoidal equivalence - as they always should be - you can just do your calculations in that strict symmetric monoidal category and transfer the results back.

We use this idea implicitly when doing calculations with string diagrams, where aa, ll and rr are suppressed.

Just to be precise: by symmetric monoidal equivalence, I mean an equivalence of categories where the functors and natural transformations involved are all symmetric monoidal, as defined here.

In your email, you note that Mac Lane does not require that Φ x,y:Φ(x)Φ(y)Φ(xy)\Phi_{x,y} : \Phi(x) \otimes \Phi(y) \to \Phi(x \otimes y) be invertible in his definition of a monoidal functor Φ\Phi. I do. If I drop invertibility, I call it a lax monoidal functor. It’s not just me, either - a lot of people talk this way. So, you have be careful.

Perhaps some general philosophy here would be helpful:

There’s the strict world, the weak world and the lax world. In the strict world we use equations between objects; in the weak world we replace equations by isomorphisms; in the lax world we replace equations by morphism - and have to carefully ponder which way these go. There’s also the oplax world where turn all these morphisms around in a systematic way.

My default world is the weak world, so for me a monoidal functor is a one where Φ x,y:Φ(x)Φ(y)Φ(xy)\Phi_{x,y} : \Phi(x) \otimes \Phi(y) \to \Phi(x \otimes y) is an isomorphism. The lax world is rather weird, so I find it odd that Mac Lane would take that one as his default.

Admittedly, the lax world is sometimes very useful. For example, consider a lax functor from the terminal monoidal category to some other monoidal category. What’s that? It’s something we know and love!

But, the lax world seems to be useful in rather specialized ways.

Posted by: John Baez on October 27, 2006 6:35 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

John says:

So, if you’re proving a result whose conclusions are preserved by symmetric monoidal equivalence - as they always should be - you can just do your calculations in that strict symmetric monoidal category and transfer the results back.

I confess I haven’t yet got a grip on the full implications of coherence. Do you have a good reference for understanding this a bit more in depth?

What would it mean, e.g., in this case?

1) The strict monoidal cat which is supposed to be equivalent to our original one, is it explicit? Is it for instance its skeleton?

2) What does it mean to have a property that is preserved by symmetric monoidal equivalence? In our almost concrete case, I guess it is something like this:

We are trying to prove that the above f=(ΔΔ);Φ;((ide)(eid));(rl)f = (\Delta \otimes \Delta); \Phi; ((\mathrm{id} \otimes e) \otimes (e \otimes \mathrm{id})); (r \otimes l) is the identity, where Φ\Phi is the symmetry, surrounded by uses of associativity.

Now, we have a symmetric monoidal equivalence

CFDGC, \mathbf{C} \overset{F}{\rightarrow} \mathbf{D} \overset{G}{\rightarrow} \mathbf{C},

where C\mathbf{C} is our original cat and D\mathbf{D} is its strict equivalent.

This should mean that, when transporting the considered ff to D\mathbf{D} through FF yields the identity, which by naturality of the iso between 1 and GFG \circ F is enough to conclude.

And indeed, after yet another bunch of calculations, I managed to prove that.

What is the general pattern?

Posted by: Tom Hirschowitz on November 3, 2006 10:26 AM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

Tom Hirschowitz wrote:

I confess I haven’t yet got a grip on the full implications of coherence. Do you hoave a good reference for understanding this a bit more in depth?

I guess you need to read around and think about how the different things people say fit together. The original paper is still crucial:

  • Saunders Mac Lane, Natural associativity and commutativity, Rice University Studies, 49 (1963), 28-46.

This is also important, because it explains coherence for braided monoidal categories, and shows how string diagrams get into the game:

  • André Joyal and Ross Street, Braided tensor categories, Advances in Mathematics 102 (1993), 20–78.

Coherence for monoidal categories is a special case of coherence for bicategories - every bicategory is biequivalent to a strict 2-category. There’s a slick proof of coherence for bicategories using the categorified Yoneda lemma; you can find it in the introduction to this:

  • Robert Gordon, A. John Power, and Ross Street, Coherence for tricategories, Memoirs Amer. Math. Soc. 558 (1995).

There are probably other things I’m forgetting. I bet Tom Leinster would know more.

The strict monoidal cat which is supposed to be equivalent to our original one, is it explicit?

Yes, Mac Lane proves his theorem by creating a new monoidal category whose objects are finite lists of objects in the monoidal category he starts with. The new tensor product is just concatenation of lists, so it’s strictly associative.

The categorified Yoneda embedding approach is more highbrow, but still “explicit” in a certain sense: we embed any bicategory BB in Cat B op\mathrm{Cat}^{B^{op}}, which is a strict 2-category. Luckily you don’t need these explicit pictures to use Mac Lane’s theorem. In practice, you just wave a magic wand and say “Abracadabra! Now this monoidal category is strict!”

Is it for instance its skeleton?

No, no, no! Everyone guesses this at first, including me. But in fact, strictness and skeletality are opposed properties! The best way to make anything strict is to make it very unskeletal. That’s what Mac Lane did by throwing in lots of new objects that are lists of old ones.

Every monoidal category is equivalent to a strict one. Every monoidal category is equivalent to a skeletal one. Most monoidal categories are not equivalent to a monoidal category that’s both strict and skeletal.

For 2-groups - monoidal categories where all objects and morphisms are invertible - you can use the associator to construct a 3-cocycle that’s a coboundary iff your 2-group is equivalent to one that’s both strict and skeletal. In other words, we get a cohomology class that vanishes iff we can make our 2-group simultaneously strict and skeletal.

This cohomology class is called the “Sinh invariant”, since this result goes back to Grothendieck’s student, Madame Sinh. For an elementary proof, that doesn’t assume you know anything about the cohomology of groups, try this:

I find this special case enlightening because it makes the tension between skeletality and strictness very clear. Also, it shows that the “3-cocycle condition” in group cohomology is just the pentagon identity!

What does it mean to have a property that is preserved by symmetric monoidal equivalence?

If you have a category theorist’s mindset, you will never want to study properties of symmetric monoidal categories that aren’t preserved by symmetric monoidal equivalence. Such properties are “evil”. They often involve asserting equations between objects, which is the ne plus ultra of evil.

Of course I’m exaggerating a bit: the properties “skeletal” and “strict” are themselves not preserved by symmetric monoidal equivalence! So, according to my last paragraph, Mac Lane should not have proved his coherence theorem! That’s going a bit too far.

A more precise statement is that we can freely assume a monoidal category is skeletal or strict (not both) as a technical tool to simplify the proof of any theorem whose hypotheses and conclusions are invariant under symmetric monoidal equivalence. So, it’s good to state theorems of this type.

Posted by: John Baez on November 3, 2006 4:36 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

John wrote:

strictness and skeletality are opposed properties! … Most monoidal categories are not equivalent to a monoidal category that’s both strict and skeletal.

I just don’t get this. If you strictify a skeleton, it won’t be a skeleton any more; but if you skeletize a strict monoidal category, I don’t see why it won’t still be strict. Surely strictness holds object-wise — we just have to check that the natural isomorphisms are the identity at each object — so it will also hold for any monoidal-closed subcategory, by restricting the natural isomorphisms to the subcategory.

I can understand that things might get difficult if you’ve got a braiding hanging around, but that’s a different matter.

Posted by: Jamie Vicary on March 26, 2008 4:40 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

Jamie wrote:

if you skeletize a strict monoidal category, I don’t see why it won’t still be strict.

“Skeletizing” a category CC means choosing one object from each isomorphism class and forming the full subcategory DD of CC consisting of just those objects. The problem with what you’re suggesting is this: when CC is (strict) monoidal, there’s no reason why DD should be closed under tensor product.

So it isn’t that DD’s not strict — it’s that DD’s not even monoidal.

Posted by: Tom Leinster on March 26, 2008 5:31 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

Tom wrote:

“Skeletizing” a category CC means choosing one object from each isomorphism class and forming the full subcategory DD of CC consisting of just those objects. The problem with what you’re suggesting is this: when CC is (strict) monoidal, there’s no reason why DD should be closed under tensor product.

OK, but this seems easy to fix up — can’t you just redefine the tensor product on DD to always give the chosen object from each isomorphism class?

Posted by: Jamie Vicary on March 26, 2008 9:31 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

You could, but how are you going to redefine the tensor product on maps?

Remember that your tensor product of maps has to be associative and unital.

Posted by: Tom Leinster on March 27, 2008 12:28 AM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

OK, I see. I tried choosing an arbitrary isomorphism from each object to the chosen member of its isomorphism class, but these isomorphisms then have to satisfy coherence equations with respect to the monoidal structure, which won’t happen in general. Perhaps this can be sorted out by introducing associativity and unit natural transformations that ‘cancel out’ these coherence equations — which, of course, means you’re not strict any more.

Thanks, Tom!

Posted by: Jamie Vicary on March 27, 2008 11:01 AM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

Jamie wrote:

if you skeletize a strict monoidal category, I don’t see why it won’t still be strict. Surely strictness holds objectwise…

I guess Tom answered your question already, but I’m back from my travels and here’s my answer.

It sounds like you’re slipping into the mistake of thinking a monoidal category is strict if

(xy)z=x(yz). (x \otimes y) \otimes z = x \otimes (y \otimes z) .

In fact there are plenty of monoidal categories satisfying this equation that aren’t strict! A monoidal category is strict iff the associator

a x,y,z:(xy)zx(yz) a_{x,y,z} : (x \otimes y) \otimes z \to x \otimes (y \otimes z)

is the identity, and the above equation is a necessary but not sufficient condition for that.

So, to see if the skeleton of a strict monoidal category is strict, we need to keep our eyes focused on the associator.

To show that any category XX is equivalent to a skeletal subcategory X˜\tilde{X}, we need to pick a representative for each isomorphism class of objects in XX. These representatives will be the objects in X˜\tilde{X}.

So, each object xXx \in X is isomorphic to its representative, say x˜X˜\tilde{x} \in \tilde{X}.

But that’s not enough! For each object xx we also need to pick an isomorphism

f x:xx˜f_x : x \to \tilde{x}

We need these to construct the natural isomorphisms lurking in the equivalence

XX˜X \simeq \tilde{X}

These isomorphisms f xf_x then show up in our formulas whenever we transfer any sort of structure from XX to X˜\tilde{X}. For example, the structure of being a monoidal category.

So, even if XX is a strict monoidal category, these isomorphisms a xa_x will show up in the associator for X˜\tilde{X}. And that’s why X˜\tilde{X} isn’t strict.

I really urge you — and everyone else in the universe, but especially you — to learn the classification of 2-groups, mentioned above. You’ll see that every 2-group is equivalent to a skeletal one that’s strict in every respect except for the associator. The associator provides a 3-cocycle which is a coboundary if and only if the original 2-group can be made both skeletal and strict.

The reason I want everyone to learn this is because it’s the simplest example of a cool idea: cohomology measures our inability to make categorified gadgets simultaneously skeletal and strict.

(I’ve rhapsodized about this at length elsewhere.)

Posted by: John Baez on March 28, 2008 10:16 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

Ah, the associator. Always been something of an enigma to me. Can anyone help me with the following puzzle: What skeletal monoidal category is monoidally equivalent to the monoidal category Set?

I’ve been confused about this ever since I read that cool example from ‘Categories for the Working Mathematician’, which shows that the associator on Set (you need to have infinite sets for this) is nontrivial.

Consider the monoidal category of finite sets under cartesian product. Normally we wouldn’t bat an eyelid if someone were to just write each set as a natural number nn, and ignore the associator (which can be taken to be the identity). This happens all the time in simplicial mathematics, etc.

But weirdly, you can’t do that for the full category Set which includes infinite sets. Okay… but then what is a skeletal version of Set, which is monoidally equivalent to it? Can you write one down? What is the associator? In other words, and in a horrible abuse of terminology… What are the 6j symbols for Set?

Posted by: Bruce Bartlett on March 29, 2008 1:23 AM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

Bruce wondered:

What skeletal monoidal category is monoidally equivalent to the monoidal category Set?

I’ve been confused about this ever since I read that cool example from ‘Categories for the Working Mathematician’, which shows that the associator on Set (you need to have infinite sets for this) is nontrivial.

This surprised me — which itself is not surprising, given that my intuition for this stuff is clearly not too accurate — so I tracked down the argument in CWM, which is at the bottom of p164 in my copy. Having thought about this a bit, I think I now see why the infinite case is different to the finite case.

The reason that this surprised me is that, after Tom put me straight on why we can’t always have our monoidal categories strict and skeletal, I thought I’d work it through for the category of finite sets. Making this category skeletal means that we need all of our finite sets to be ordered; i.e., come with an explicit bijection to {1,2,3,...,N}\{1, 2, 3, ..., N \} for some finite natural number NN. Given two finite sets AA and BB, I decided to give their product the following ordering, which seemed pretty natural:

(1)A×B={(a 1,b 1),(a 1,b 2),(a 2,b 1),(a 1,b 3),(a 2,b 2),(a 3,b 1),} A \times B = \{ (a_1, b_1), (a_1, b_2), (a_2, b_1), (a_1, b_3), (a_2, b_2), (a_3, b_1), \ldots \}

So first we list the elements of AA and BB whose indices sum to 1, and then those that sum to 2, and so on for ever. I convinced myself that with this choice of ordering, you need nontrivial associators to make things work, because A×(B×C)A\times (B \times C) will have a different ordering to (A×B)×C(A \times B) \times C. This seemed to make sense — I didn’t expect to be able to get rid of the associators, since in general you can’t — so I stopped thinking about it.

In Bruce’s message, however, he said that for the category of finite sets you can get away with trivial associators, and so I took a look at this again. I realised that there’s a different choice you can make for the ordering of A×BA \times B, where AA is of size |A||A| and BB is of size |B||B|:

(2)A×B={ (a 1,b 1),(a 1,b 2),,(a 1,b |B|), (a 2,b 1),(a 2,b 2),,(a 2,b |B|), , (a |A|,b 1),,(a |A|,b |B|)} \begin{aligned} A \times B = \{& (a_1, b_1), (a_1, b_2), \ldots, (a_1, b_{|B|}), \\ & (a_2, b_1), (a_2, b_2), \ldots, (a_2, b_{|B|}), \\ & \ldots, \\ & (a_{|A|}, b_1), \ldots, (a_{|A|}, b_{|B|}) \} \end{aligned}

So first we cycle through the elements of BB, then we choose the next element of AA and cycle through BB again, and so on until the end. Using this choice we don’t need associators, because A×(B×C)A \times (B \times C) comes out identical to (A×B)×C(A \times B) \times C.

If we’re thinking about infinite sets, however, something immediately pops out — this second option doesn’t work, because some finite pairs like (a 2,b 2)(a_2, b_2) are only reached an infinite distance down! So we have to use the first choice, or something like it, that indexes all finite pairs at a finite index in the set.

From this explicit perspective, the correct choice for the associators for infinite sets just jumps out at you: use (1) to work out A×(B×C)A \times (B \times C) and (A×B)×C(A \times B) \times C, and the associator is the bijection that maps between them.

Posted by: Jamie Vicary on March 29, 2008 1:35 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

Jamie, your proposal is very interesting, though I must admit I am more confused than ever. By the way, you wrote:

the correct choice for the associators for infinite sets just jumps out at you: use (1) to work out A×(B×C)A \times (B \times C) and (A×B)×C)(A \times B) \times C), and the associator is the bijection that maps between them.

Remember, what I’d like to see is not the “correct” associator on Set, as such. Surely that’s the ordinary one ((a,b),c)(a,(b,c))((a,b),c) \mapsto (a,(b,c)) using your favourite set-theoretic model of ordered pair…gulp! I’d like to see how this associator explicitly pulls back to Card, the category whose objects are cardinalities (i.e. five, seven, aleph zero, aleph one and so on).

Having mentioned things like “cardinality” and “aleph” it’s clear there is some horrible set theory going down here. I guess the point is that for finite sets, there is somehow a canonical choice for a representative in each isomorphism class. It’s the set

(1)n̲={1,2,3,,n}. \underline{n} = \{1, 2, 3, \ldots, n\}.

For infinite sets, there’s no such canonical choice, right? We can’t write

(2) 0={1,2,3,} \aleph_0 = \{1, 2, 3, \ldots \}

Well we can… but that’s not canonical. I guess this is just the ordinal numbers vs cardinal numbers thing.

Posted by: Bruce Bartlett on March 29, 2008 3:07 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

Bruce explained:

Remember, what I’d like to see is not the “correct” associator on Set, as such. Surely that’s the ordinary one ((a,b),c)(a,(b,c))((a,b),c)\mapsto(a,(b,c)) using your favourite set-theoretic model of ordered pair…gulp! I’d like to see how this associator explicitly pulls back to Card, the category whose objects are cardinalities (i.e. five, seven, aleph zero, aleph one and so on).

Erk… what’s the difference between Card and Set, then? Don’t we have sets of each cardinality?

Posted by: Jamie Vicary on March 29, 2008 5:07 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

Bruce wrote:

I guess the point is that for finite sets, there is somehow a canonical choice for a representative in each isomorphism class.

I don’t understand this stuff nearly as well as I should — and like you, I’m very ashamed about this. But I think the point you just made has got to be wrong.

First of all, from the viewpoint of category theory, I don’t see anything ‘more canonical’ about the finite cardinals

n={0,1,2,,n1} n = \{0, 1, 2, \dots, n-1 \}

than the infinite ones.

(However I like the ordinals I just wrote down better than your sets n={1,2,,n}n = \{1, 2, \dots, n \}, which contains themselves and are thus forbidden by the axiom of well-foundedness. )

Second of all, and more importantly: unless I’m seriously confused, every skeleton of a given category is not only equivalent but isomorphic to every other!

So, I don’t think it can possibly make any difference which sets we take as our favorite ones when forming a skeleton of SetSet. We might as well use the cardinals, since they’re convenient.

The point where we get a choice that really matters is when we pick isomorphisms

f x:xx˜f_x : x \to \tilde{x}

between objects and their representatives. These isomorphisms affect the associator on the skeletal category. And these isomorphisms are just the orderings that Jamie is talking about!

So, I really think Jamie put his finger on the pulse of this problem. He didn’t prove there’s no way to make SetSet skeletal and strict, but he came up with a trick that does the job for FinSetFinSet and fails for SetSet, and that’s a big step — a lot further than I ever got.

Posted by: John Baez on March 30, 2008 4:29 AM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

So, I don’t think it can possibly make any difference which sets we take as our favorite ones when forming a skeleton of Set. We might as well use the cardinals, since they’re convenient.

What I was getting at is that for infinite sets, I didn’t know how to write down an explicit set corresponding to a cardinal (we need to do that if we claim to be able to pick an explicit skeleton of Set), since I thought a cardinal was just an “isomorphism class of sets”. Then Jamie set me right; a bit of Wikipedia and now I see that you can indeed associate to each cardinal a canonical set: its ordinal number (which is actually an ordered set). I guess everyone knew that; I didn’t.

By the way, that seems to imply that Jamie’s first ordering system might indeed still work for these infinite sets corresponding to cardinals… maybe you could get away with some kind of transfinite induction (heh I always wanted to use that word!) I’m way out of my depth here though, so I’ll stop.

By the way, I’m still interested in the more mundane quetsion “What is the moduli space of associators on Numbers? Is it trivial?”

Posted by: Bruce Bartlett on March 30, 2008 4:37 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

Bruce wrote:

I thought a cardinal was just an “isomorphism class of sets.”

Oh, I see. I believe this is how Russell or someone originally wanted to define cardinals. For example, the number 3 would be ‘the set of all 3-element sets’. Unfortunately, Russell later realized that it’s dangerous to talk about ‘the set of all 3-element sets’, because then you can talk about ‘the set of all 3-element sets that don’t contain themselves’, and work your way into paradoxes.

So, in Zermelo-Fraenkel set theory we say the collection of 3-element sets is a proper class, not a set!

It would be rather annoying to have the number 3 be a proper class when you’re trying to base everything on set theory, so von Neumann or someone came up with the idea of letting 0 be the empty set, letting 1 be {0}\{0\}, letting 2 be {0,1}\{0,1\}, and so on, where the ‘and so on’ gets a bit trickier for infinite ordinals, but still quite nice, at least if you have the axiom of choice at your disposal. Then a cardinal is defined to be an ordinal that’s can’t be put in 1-1 correspondence with any lesser ordinal.

So, when you do things this way, the category SetSet comes along with a very nice skeleton, CardCard.

By the way, I’m still interested in the more mundane question “What is the moduli space of associators on Numbers? Is it trivial?”

It sounds like a great question; let me make sure I understand it. As far as I can tell, you want NumbersNumbers to be a certain skeletal strict monoidal category that’s equivalent, as a monoidal category, to FinSetFinSet. I would be very happy if the italicized phrase characterizes NumbersNumbers up to isomorphism of strict monoidal categories. That would allow me to worry a bit less about the clever tricks we use to define this category, and focus on its properties.

In fact, I’ll conjecture that it’s true: any two skeletal strict monoidal categories that are equivalent, as monoidal categories, to FinSetFinSet are isomorphic as strict monoidal categories.

Given this, take any one of these guys and call it NumbersNumbers.

Then, starting from this strict monoidal category NumbersNumbers, we can ask about the ‘moduli space of possible associators’ that would give other weak monoidal categories. Presumably we want to count these up to equivalence of monoidal categories.

Hmm, this should be made more precise… but I should do my taxes first, just like Jamie needs to write his thesis.

Posted by: John Baez on March 30, 2008 10:54 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

Anyhow, let me throw all that infinite stuff aside, and concentrate on finite sets. Suppose we consider the monoidal category (Numbers, ×\times, 1). Objects are positive natural numbers, morphisms are functions f:{1,2,,n}{1,2,,m}f: \{1,2,\ldots, n\} \rightarrow \{1,2,\ldots,m\}. The monoidal product is just product of numbers, and the associator is the identity.

You are saying there is another associator, another gismo which solves the pentagon equation, which is equivalent to the trivial one. It’s the “reindexing” thing you outlned above. It’s certainly not the identity. It’s got a nasty formula, i.e.

(1)a p,q,r:pqrpqr a_{p,q,r} : pqr \rightarrow \pqr

is a nontrivial bijection. My thoughts are the following:

1. I don’t this this will work; I can’t see how such a complicated formula could solve the naturality and the pentagon equations… but I may be wrong.

2. I think there is up to monoidal isomorphism only one associator on Numbers… right?

3. In fact I think there is only one associator on Numbers… the trivial one. Nothing else solves naturality and the pentagon equations.

4. I am a bit ashamed I don’t know the answers to this stuff.

Posted by: Bruce Bartlett on March 29, 2008 3:11 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

Bruce said:

Suppose we consider the monoidal category (Numbers,×,1, \times, 1). Objects are positive natural numbers, morphisms are functions f:{1,2,,n}{1,2,,m}f:\{1,2,\ldots,n\} \Rightarrow \{1,2,\ldots,m\}. The monoidal product is just product of numbers, and the associator is the identity.

But what does the tensor product give on morphisms? I don’t see how to work that out from what you’ve given.

Posted by: Jamie Vicary on March 29, 2008 5:02 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

You’re right I must be more specific. The tensor product on morphisms uses the

(1)(1,1),(1,2),,(1,n),(2,1),(2,2),(2,n),,(m,1),(m,2),(m,n) (1,1), (1,2), \ldots, (1,n), (2,1), (2,2), \ldots (2,n), \ldots, (m,1), (m,2), \ldots (m,n)

ordering convention you give above. As for the monoidal category Card, don’t worry about it, it’s just meant to be a skeleton of Set. I don’t think there’s any explicit way to write it down without using some kind of axiom of choice. On the other hand, we can at least explicitly write down the monoidal category Numbers as we did above, which is a skeleton of FiniteSets. (Of course, to show that Numbers is a skeleton of FiniteSets, we need to pick a bijection X{1,,n}X \cong \{1, \ldots, n\} for every finite set XX - but I’m not talking about that here, I’m just talking about defining Numbers in the first place).

Posted by: Bruce Bartlett on March 29, 2008 6:18 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

OK, I see. If you use that convention, or the opposite one (permuting the first index in preference to the second), the associator is trivial. But if you define your tensor product some other way, using a different ordering convention, your associator might well not be trivial. I don’t see a problem with that: different tensor product structures would be expected to give rise to different associators, right?

With respect to the skeletal category Card: what goes wrong if you define each cardinal as the ordered set of cardinals smaller than it?

Posted by: Jamie Vicary on March 29, 2008 6:33 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

A while ago, Bruce said:

Consider the monoidal category of finite sets under cartesian product. Normally we wouldn’t bat an eyelid if someone were to just write each set as a natural number n, and ignore the associator (which can be taken to be the identity).

I reckon we can also make a category of finite-dimensional vector spaces strict and skeletal… can somebody back me up on this? I think this is normally called Mat(kk), with natural numbers for objects and kk-matrices for morphisms.

Posted by: Jamie Vicary on April 23, 2008 2:52 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

Jamie wrote:

I reckon we can also make a category of finite-dimensional vector spaces strict and skeletal… can somebody back me up on this?

Depressingly, I’ve never thought about this either. It’s a very important question.

If the trick you used to make (FinSet,×,1)(\Fin\Set, \times, 1) strict and skeletal really works (I haven’t had time to check), the same sort of trick should probably work for (FinVect,,k)(\Fin\Vect, \otimes, k).

I think this is normally called Mat(k), with natural numbers for objects and kk-matrices for morphisms.

Yeah. But the key issue here, which I’ve never seen discussed, is how we identify the tensor product of an n×nn \times n matrix and an m×mm \times m matrix with an nm×nmn m \times n m. Presumably we want to use your isomorphism of finite ordinals n×mnmn \times m \cong n m, where n×mn \times m is ordered lexicographically.

In fancy jargon, this amounts to taking advantage of the monoidal ‘free vector space’ functor F:FinSetFinVectF: \Fin\Set \to \Fin\Vect, sending nn to k nk^n.

Posted by: John Baez on April 25, 2008 3:38 AM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

how we identify the tensor product of an n×n matrix and an m×m matrix with an nm×nm. Presumably we want to use your isomorphism of finite ordinals n×m≅nm, where n×m is ordered lexicographically

Isn’t this the Kronecker product of the two matrices? I know we don’t teach it that often anymore to undergrads, but I figured you’d seen it. And the strictness result for ordinals makes the strictness work here.

Posted by: John Armstrong on April 25, 2008 6:32 AM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

John Armstrong:

Isn’t this the Kronecker product of the two matrices? I know we don’t teach it that often anymore to undergrads, but I figured you’d seen it.

Yes, but I’d never paid much attention to the specific lexicographic ordering of the index sets n×kn \times k and m×m \times \ell that show up when you take a tensor product of an n×mn \times m matrix and k×k \times \ell matrix. You see, I don’t usually think of the indices of a matrix as taking values in linearly ordered sets — though of course they do when you actually write down a matrix as a rectangular grid of numbers. After all, for most purposes the order is irrelevant! But now it turns out that to make FinVectFinVect a strict monoidal skeletal category, the order matters! So, what once seemed naive now turns out to be ultra-sophisticated.

Posted by: John Baez on April 25, 2008 2:02 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

Thanks John\,\otimes\,John! That’s how I felt it should work out too.

Posted by: Jamie Vicary on April 25, 2008 8:23 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

I reckon we can also make a category of finite-dimensional vector spaces strict and skeletal…

I guess there’s an ‘indirect’ proof of this as well. Firstly we observe that there can only be one associator on the ordinary category of vector spaces… the usual one. That’s because an associator is natural, so it is completely determined by its component a ,,a_{\mathbb{C}, \mathbb{C}, \mathbb{C}}, where it can only be the map

(1)(λ 1λ 2)λ 3λ 1(λ 2λ 3) (\lambda_1 \otimes \lambda_2) \otimes \lambda_3 \mapsto \lambda_1 \otimes (\lambda_2 \otimes \lambda_3)

because the pentagon equation has the form

(2)cubicina=quadraticina cubic in a = quadratic in a

and so it only has one solution… the trivial one (this argument holds water, right? In general recall that there are only finitely many possible associators on any fusion category… this is Ocneanu rigidity.)

Secondly, it is easy to make VectVect skeletal… we just choose the full subcategory Vect 0Vect_0 having objects n\mathbb{C}^n. We pull-back the tensor-product and associator from Vect\Vect to make Vect 0\Vect_0 a monoidal category (this is the ‘indirect’ step because sneakily we’re making an ‘uncardinal’ number of choices in order to construct an explicit equivalence of categories VectVect 0\Vect \cong \Vect_0, which we need in order to pull-back this data).

So here is our candidate strict monoidal category, (Vect 0,,a)(\Vect_0, \otimes, a). It must indeed be strict, because if it wasn’t we’d have a contradiction: it would mean there would be two solutions to the pentagon equations (because we always have the trivial associator on a strict category which is equipped with a tensor product \otimes).

Posted by: Bruce Bartlett on April 28, 2008 3:20 AM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

Hi Bruce, that’s interesting. I don’t get why all the associativities must be trivial just because α ,,\alpha _{\mathbb{C},\mathbb{C},\mathbb{C}} is, though. I agree that this must be 11, which tells us that for f:Af:\mathbb{C} \to A, g:Bg:\mathbb{C} \to B and h:Ch:\mathbb{C} \to C we have α A,B,C((fg)h)=f(gh)\alpha_{A,B,C} \circ ((f \otimes g) \otimes h) = f \otimes (g \otimes h). I agree that this defines α A,B,C\alpha _{A,B,C} — but how can we also conclude that it’s somehow trivial? Surely the morphisms f(gh)f\otimes (g \otimes h) and (fg)h(f \otimes g) \otimes h could be dramatically different.

Also, it seems to me that this would all be just the same for infinite-dimensional vector spaces — but presumably that can’t be made strict and skeletal.

Posted by: Jamie Vicary on April 28, 2008 1:13 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

Bruce wrote:

(this argument holds water, right?)

The first stage of your argument argument seems to hold water. You’re using some special features of VectVect to show that VectVect with its usual tensor product can have only one associator satisfying naturality and the pentagon identity: namely, the usual associator.

The second stage of your argument doesn’t seem to use anything special about VectVect. You note that, just like any monoidal category VectVect is monoidally equivalent to a skeletal monoidal category Vect 0Vect_0. It’s easy to prove this result if we use the axiom of choice, just by choosing any skeleton

Vect 0VectVect_0 \hookrightarrow Vect

and showing there’s a functor going the other way

VectVect 0 Vect \to Vect_0

which gives an equivalence of categories

VectVect 0 Vect \simeq \Vect_0

Then, using this, we can transport the tensor product on VectVect over to Vect 0Vect_0. Then, we can show that different choices of associator for Vect 0Vect_0 correspond in a 1-1 way with different choices of the associator for VectVect.

Combining these two stages of your argument, we can conclude that the skeletal category Vect 0Vect_0, equipped with the tensor product coming from VectVect as above, admits only one associator satisfying the pentagon identity.

But then, in the third stage of your argument, you seem to magically conclude that this associator must be the identity!

I don’t see that. It seems to me that we still need Jamie’s explicit construction to get the associator on Vect 0Vect_0 to be the identity.

Here’s how you magically jump to your final conclusion:

we always have the trivial associator on a strict category which is equipped with a tensor product \otimes

I don’t know what this means. First, I don’t know what a ‘strict category’ is. Second, if you mean to say ‘strict monoidal category’, that’s a category that has a trivial associator — and yes, such a category always admits a trivial associator. But…

Oh, whoops — I bet you meant to say ‘skeletal category’. Hmm, is that true? You’re saying that given a monoidal category, and picking a skeletal subcategory and equipping it with a tensor product functor as above, we can always choose the identity

1:(x 1x 2)x 3x 1(x 2x 3) 1 : (x_1 \otimes x_2) \otimes x_3 \to x_1 \otimes (x_2 \otimes x_3)

Is that right? It’s certainly well-defined because both sides are isomorphic (since we started with a monoidal category) hence equal (since now we’re in a skeleton). It’s natural. And, it satisfies the pentagon.

Hmm, so maybe this argument is right. But I still feel there should be a flaw, since there’s only one point where you used any special feature about VectVect, right near the beginning… and I don’t see why SetSet lacks this special feature! So, shouldn’t your argument prove that (Set,×,1)(Set, \times, 1) admits a strict skeletal version, even though our betters have told us otherwise?

If it’s true that FinSetFinSet is monoidally equivalent to a skeletal strict monoidal category, but SetSet is not, there should be something about your argument that breaks down in the latter case. But right now it seems to work equally well in both cases!

Posted by: John Baez on April 28, 2008 7:24 AM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

Oh, whoops — I bet you meant to say ‘skeletal category’. Hmm, is that true?

Yes, that’s what I meant to say - sorry.

So, shouldn’t your argument prove that (Set,×,1)(Set, \times ,1) admits a strict skeletal version, even though our betters have told us otherwise?

Firstly let me say that I am much more comfortable in the linear setting of VectVect, because there I understand how natural transformations work, and how many components you have to specify before they are uniquely determined.

I believe the reason my argument won’t hold for (Set,×,1)(Set, \times, 1) is because it seems to me that naturality is not enough to ensure that the associator is uniquely determined by its value at a {1},{1},{1}a_{\{1\}, \{1\}, \{1\}}…. different associators could have the same value there and on finite sets, but ‘differ at infinity’ somehow.

Posted by: Bruce Bartlett on April 28, 2008 11:40 AM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

Bruce said:

I believe the reason my argument won’t hold for (Set,×\times,1) is because it seems to me that naturality is not enough to ensure that the associator is uniquely determined by its value at a 1×1×11 \times 1 \times 1. different associators could have the same value there and on finite sets, but ‘differ at infinity’ somehow.

I think it would still work for a category of infinite sets. The associator α 1,1,1\alpha _{1,1,1} is uniquely determined because 1×1×11 \times 1 \times 1 is terminal, and for a,b,ca, b, c morphisms out of 1 giving elements of sets AA, BB and CC, we have α A,B,C((a×b)×c)=a×(b×c)\alpha _{A,B,C} \circ ((a \times b) \times c) = a \times (b \times c). Functions on sets are completely determined by their behaviour on points, so I think this does determine α A,B,C\alpha _{A,B,C}.

Posted by: Jamie Vicary on April 28, 2008 1:19 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

Mmmm, you’re right. Now I am confused. I’ve never been able to quite get to the bottom of this.

Posted by: Bruce Bartlett on April 28, 2008 5:34 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

Bruce wrote:

Firstly let me say that I am much more comfortable in the linear setting of Vect, because there I understand how natural transformations work, and how many components you have to specify before they are uniquely determined.

Ah, so you’re one of those quantum physicists who thinks that no structure short of a vector space is worth studying — mere sets are beneath contempt.

I used to be a bit like that, until Jim Dolan talked me out of it. Even though I’d studied axiomatic set theory as a student, I felt much happier with the structured setting of linear algebra. Actually, being an analyst, I preferred a Banach space or Hilbert space to a mere vector space. I’ve become much more accepting of various and sundry contexts in my later years…

If you really feel uncomfortable with sets and functions, call them ‘vector spaces equipped with a basis’, and ‘linear transformations that map basis elements to basis elements’. This gives a faithful and essentially surjective (but not full!) embedding of Set\Set into Vect\Vect, which is symmetric monoidal — it sends ×\times to \otimes. So, if you can make Vect\Vect into a skeletal strict monoidal category, you should be able to do the same for Set\Set, unless the non-fullness is the killer — that is, the fact that Set\Set lacks some of the morphisms of Vect\Vect. But, if you’ve gotten the associator in Vect\Vect to be an identity morphism, I don’t see how that could be the problem.

(Mind you, the idea of treating sets as vector spaces equipped with extra structure is sort of hilarious, but it does work.)

Or maybe it’s infinity that turns you off! In fact, maybe by Vect\Vect you secretly mean FinVect\Fin\Vect — the category of finite-dimensional vector spaces. But, I don’t see where your argument used finite-dimensionality.

I believe the reason my argument won’t hold for (Set,×,1)(Set,\times,1) is because it seems to me that naturality is not enough to ensure that the associator is uniquely determined by its value at a 1,1,1a_{{1},{1},{1}} different associators could have the same value there and on finite sets, but ‘differ at infinity’ somehow.

Okay, so you’re blaming the infinite, rather than the moral deficiencies of sets as compared with vector spaces.

But, I don’t see how this is supposed to work. The 1-element set is a ‘generator’ for Set\Set, just as the 1-dimensional vector space is a generator for Vect\Vect. This is just an overeducated way of saying that two morphisms f,g:STf, g : S \to T must agree if their composites with all possible morphisms s:1Ss: 1 \to S agree. And this is just an overeducated way of saying that a function is determined by its value on points.

So, if I want to completely know an associator

a S,T,U:(S×T)×US×(T×U) a_{S,T,U} : (S \times T) \times U \to S \times (T \times U)

it suffices to know its composite with all possible morphisms

(s×t)×u:(1×1)×1(S×T)×U(s \times t) \times u :(1 \times 1) \times 1 \to (S \times T) \times U

But, since the associator is natural, we can draw a naturality square containing a S,T,Ua_{S,T,U} and (s×t)×u(s \times t) \times u as two of its sides, and a 1,1,1a_{1,1,1} and s×(t×u)s \times (t \times u) as its other two sides.

And so, if I’m not falling prey to some delusion, we know a S,T,Ua_{S,T,U} as soon as we know a 1,1,1a_{1,1,1}.

Of course we also need to know (s×t)×u(s \times t) \times u and s×(t×u)s \times (t\times u). But there’s no mystery about these, is there? (Jamie has his doubts.) I’m imagining we’ve fixed the tensor product in SetSet, both on objects and on morphisms, and we’re asking if more than one associator is possible. And, your argument seems to be saying no, because the associator is determined by a 1,1,1a_{1,1,1}, where we have no choice.

So, your argument seems to show that (Set,×,1)(Set, \times , 1) is equivalent to a strict skeletal monoidal category, which other people have told us is false.

So, somebody somewhere is making some mistake. Quite possibly me.

We’re completely confused! Whee! We must be doing research!

Posted by: John Baez on April 28, 2008 5:54 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

And so, if I’m not falling prey to some delusion,

I guess it must be me who has fallen prey to a delusion… indeed, the very delusion which Maclane warned us against in the first place!

That was the point at which I claimed that “if you have a skeletal category equipped with a tensor product functor, then you always have the identity associator”. The trouble is that while the identity associator will always solve the pentagon equations, it need not be natural. In general if you “pull back” an associator to an equivalent skeletal subcategory by making a gazillion choices, I guess you will have no control over the relationship between

(1)(f×g)×h:A×B×CA ×B ×C (f \times g) \times h : A \times B \times C \rightarrow A^' \times B^' \times C^'

and

(2)f×(g×h):A×B×CA ×B ×C . f \times (g \times h) : A \times B \times C \rightarrow A^' \times B^' \times C^'.

That’s what Jamie had issues with anyway, and John had qualms with it too. So there is no paradox - my argument was bogus.

But I’m still confused by all things associator-y. Especially the interplay between finite and infinite sets. I think I should absorb more carefully Jamie’s numbering system.

Posted by: Bruce Bartlett on April 28, 2008 7:00 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

I’m glad it’s not just me that gets confused about this! :) I went to a great workshop in Barbados last month, organised by Prakash Panangaden. One of the highlights was a long argument I had with Peter Selinger and Eric Paquette, who were kind enough to take the time to persuade me that you really can’t just turn a blind eye to this stuff and hope it doesn’t affect your calculations. As a result, I have a lot more interest in these strictness/skeletality problems than I once did, which lead to me deciding to bear my ignorance here in the first place.

Going back to what we’re all talking about, I think it’s certainly true that, if the monoidal unit is generating, a given monoidal product will have a unique associator. I didn’t realise this before! But there’s no reason to think that it should be trivial, even if α I,I,I\alpha _{I,I,I} is the identity. And especially in the cartesian case, it’s a bit misleading to say that the associator is unique, because it’s only unique after you’ve picked your favourite elements from the isomorphism classes (A×B)×C(A \times B) \times C and A×(B×C)A \times (B \times C) for each choice of AA, BB and CC (and choosing these also means choosing the relevant projectors.) I don’t think any of these choices necessarily get that much easier to make, even if the category is skeletal! For example, there will still be a lot of flexibility choosing the projectors.

Posted by: Jamie Vicary on April 28, 2008 10:04 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

Jamie wrote:

As a result, I have a lot more interest in these strictness/skeletality problems than I once did, which lead to me deciding to bear my ignorance here in the first place.

Bear it or bare it? When I can’t bear my ignorance here, I bare my ignorance here: lay it open for the world to see, by asking questions. But maybe you mean ‘bear’ as in ‘carry’.

Going back to what we’re all talking about, I think it’s certainly true that, if the monoidal unit is generating, a given monoidal product will have a unique associator. I didn’t realise this before!

Neither did I. I hope it’s true! If it’s true, it’s a real stroke of cleverness on Bruce’s part.

I think it’s true, as long as we realize that by ‘monoidal product’ we mean not just the tensor product of objects, but also of morphisms. We need to know the tensor product of the morphisms x:IXx : I \to X, y:IYy: I \to Y and z:IZz: I \to Z for us to know enough sides of this naturality square:

(II)I a I,I,I I(II) (xy)z x(yz) (XY)Z a X,Y,Z X(YZ) \begin{aligned} (I \otimes I) \otimes I &\stackrel{a_{I,I,I}}{\to} &I \otimes (I \otimes I) \\ (x \otimes y) \otimes z \downarrow & & \downarrow x \otimes (y \otimes z)\\ (X \otimes Y) \otimes Z &\stackrel{a_{X,Y,Z}}{\to} &X \otimes (Y \otimes Z) \end{aligned}

to determine the associator a X,Y,Za_{X,Y,Z} in the case when II is generating.

Posted by: John Baez on April 29, 2008 3:26 AM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

John said:

(Mind you, the idea of treating sets as vector spaces equipped with extra structure is sort of hilarious, but it does work.)

Now that Bob Coecke, Dusko Pavlovic and I are on the verge of getting the proof of this into print, it’s a good time to remind everybody of one particular way to choose this extra structure: given a finite-dimensional Hilbert space HH, choosing a basis corresponds to choosing a ‘special commutative \dagger-Frobenius monoid’ on the Hilbert space. ‘Special’ means that the comultiplication m :HHHm ^\dagger : H \to H \otimes H is an isometry, so mm =id Hm \circ m ^\dagger = \mathrm{id} _H. You can drop this, but then you lose uniqueness — there are lots of non-special commutative \dagger-Frobenius monoids that give rise to the same basis set.

This is indeed hilarious, and leads to such fun things as the free Hilbert space functor John was talking about being isomorphic to the forgetful functor that forgets the \dagger-Frobenius monoid information.

It lets you do lots of other really interesting things, too. For example, you can write down this equation:

(1)FinSetHilb 2Cob \mathbf{FinSet} \simeq \mathbf{Hilb} ^{\mathbf{2Cob}}

You’ve got classical logic, quantum logic and geometry, all in the same place! (On the right-hand side, that functor category just contains \dagger-functors.)

I’m finishing up a paper of my own that generalises this stuff a little bit… so I’m really just trying to whip up a bit of enthusiasm for the topic in advance :).

Posted by: Jamie Vicary on April 28, 2008 10:23 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

I erroneously said that

(1)FinSetHilb 2Cob. \mathbf{FinSet} \simeq \mathbf{Hilb^{2Cob}}.

This is wrong: morphisms on the right-hand side are natural transformations between \dagger-preserving functors, and these must themselves admit a dagger; but FinSet\mathbf{FinSet} certainly doesn’t admit a dagger.

The correct equation is

(2)FinSet 0Hilb 2Cob \mathbf{FinSet_0} \simeq \mathbf{Hilb^{2Cob}}

where FinSet 0\mathbf{FinSet_0} is the groupoid of finite sets and bijections. This equation seems less pretty to me than the wrong one above… but that’s probably just because I don’t know what to do with it.

Posted by: Jamie Vicary on May 20, 2008 2:46 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

Every monoidal functor F:ABF:\mathbf{A}\to \mathbf{B} can be factorized in the following way:

AEIm plFMB,\mathbf{A}\overset{E}\longrightarrow\mathrm{Im}_{\mathrm{pl}}F\overset{M}\longrightarrow \mathbf{B},

where EE is a monoidal functor which is an identity on objects and MM is a full and faithful monoidal functor.

The objects of the full image of FF, Im plF\mathrm{Im}_{\mathrm{pl}}F, are the objects of A\mathbf{A} and its arrows are the arrows of B\mathbf{B} :

(Im plF)(A,A ):=𝔹(FA,FA ).(\mathrm{Im}_{\mathrm{pl}}F)(A,A^'):=\mathbb{B}(F A,F A^').

The composition and identities are those of B\mathbf{B}. The tensor product is defined on object as in A\mathbf{A}; the tensor product of b:A 1A 2b:A_1\to A_2 and b :A 1 A 2 b^':A^'_1\to A^'_2 (i.e. b:FA 1FA 2b:F A_1\to F A_2 and b :FA 1 FA 2 b^':F A^'_1\to F A^'_2 in B\mathbf{B}) is defined as the following composite:

F(A 1A 1 )φFA 1FA 1 bbFA 2FA 2 φF(A 2A 2 ),F(A_1\otimes A^'_1)\overset{\varphi}\longrightarrow F A_1\otimes F A^'_1\overset{b\otimes b'}\longrightarrow F A_2\otimes F A^'_2\overset{\varphi}\longrightarrow F(A_2\otimes A^'_2),

where φ\varphi is the natural transformation of the monoidal structure of FF. The unit of the tensor product is the unit of A\mathbf{A} and the associativity, right unit and left unit natural transformations are defined as the image by FF of the corresponding transformations in A\mathbf{A}.

The monoidal functor EE sends an object AA to AA and an arrow a:AA a:A\to A^' to Fa:AA F a:A\to A^'. The natural transformation of monoidal functor is the identity. The monoidal functor MM sends an object AA to FAF A and an arrow b:AA b:A\to A^' to bb itself. The natural transformations of monoidal functor are those of FF.

Now, if FF is a surjective (up to isomorphism) monoidal functor, then MM is a monoidal equivalence since it is full, faithful and surjective. If moreover the domain A\mathbf{A} is a monoid seen as a discrete monoidal category, the full image of FF is a strict monoidal category : the associativity and left and right unit natural transformations are the image by FF of those of A\mathbf{A}, which are identities since A\mathbf{A} is a monoid. So, in this situation, B\mathbf{B} is monoidally equivalent to a strict monoidal category whose objects are the elements of the monoid A\mathbf{A}.

We can now apply this result to the monoidal functor []:FinSet[-]:\mathbb{N}\to \mathrm{FinSet} (both equipped with the product), which sends a natural number nn to the set [n]:={k<n}[n]:=\{k \lt n\}. The structure of monoidal functor on [][-] is given by φ m,n:[m]×[n][mn]:(j,k)jn+k.\varphi_{m,n}:[m]\times[n]\to[m n]:(j,k)\mapsto j n+k. It is easy to check that φ\varphi satisfies the hexagon condition of monoidal functor. The inverse of φ m,n\varphi_{m,n} is given by Euclidean division.

So the full image of [][-] is a strict monoidal category monoidally equivalent to (FinSet,×,1)(\mathrm{FinSet},\times,1) whose objects are the natural numbers. In fact, the tensor product on this full image is given on objects by the product of natural numbers, and the tensor product of two functions f:[m][m]f:[m]\to[m'] and f :[n][n ]f^':[n]\to[n^'] is, thanks to the second equation above, the function [mn][m n ][m n]\to[m^'n^'] which sends a number ll to f(j)n+g(k)f(j)n'+g(k), where jj and kk are the unique numbers such that l=jn+kl=j n+k.

For finite dimensional vector spaces, we can take the full image of the functor []FinSetLFinVect,\mathbb{N}\overset{[-]}\longrightarrow\mathrm{FinSet}\overset{L}\longrightarrow\mathrm{FinVect}, where LL is the free vector space functor, which is surjective (and monoidal, I suppose).

Posted by: Mathieu Dupont on April 28, 2008 9:43 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

Thanks for this Mathieu. This is a very slick and elegant way to come up with a strict skeletal monoidal category equivalent to (FinSet,×,a)(FinSet, \times, a). It is essentially Jamie’s numbering system, put in a nice way. I think what’s nice is that it cleanly separates what’s “difficult” in the problem from what is “easy”. It seems to me that this argument will help analyse any situation where you want to study the various ways in which a fusion ring can be “categorified”, I guess.

Posted by: Bruce Bartlett on April 29, 2008 6:52 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

Yes, it’s the second numbering system he gives in his comment. And at first sight, the tensor product of matrices given by this construction (for the functor FinVect:nK n\mathbb{N}\to\mathrm{FinVect}:n\mapsto K^n, with φ j,k:K mK nK mn\varphi_{j,k}:K^m\otimes K^n\to K^{mn} which maps e ie je_i\otimes e_j to e in+je_{in+j}) is the Kronecker product already mentionned.

Posted by: Mathieu Dupont on April 30, 2008 7:46 AM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

Thanks John, that’s a very useful perspective. This connection to 2-groups sounds fascinating — once I’ve finished a paper I’m working on (and finished my thesis!) I’ll take a good look at it.

Given this connection to algebraic topology, for any monoidal category, there must be a topological way to ask the question ‘can this monoidal category be made simultaneously strict and skeletal?’ Does the 2-group example you mentioned extend?

Posted by: Jamie Vicary on March 29, 2008 1:52 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

Jamie wrote:

there must be a topological way

I don’t know if there is. The study of nn-groupoids is the same as homotopy theory, so I can look at a 2-group, think of it as a space, and use that to help me study whether the 2-group can be made simultaneously skeletal and strict. I don’t know how to do that for a monoidal category.

This is actually what ‘directed algebraic topology’ is about, or should be about — finding generalized ‘spaces’ that correspond to nn-categories, the way ordinary spaces correspond to nn-groupoids.

But anyway, one can also just take a monoidal category and study directly whether it can be made both skeletal and strict, as we’re now doing for SetSet.

Posted by: John Baez on March 30, 2008 4:39 AM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

John wrote:

This is actually what ‘directed algebraic topology’ is about, or should be about — finding generalized ‘spaces’ that correspond to nn-categories, the way ordinary spaces correspond to nn-groupoids.

Is this an entirely different notion of ‘generalised space’ to that which non-commutative geometers are looking for?

Posted by: Jamie Vicary on March 30, 2008 10:25 AM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

Jamie wrote:

Is this an entirely different notion of ‘generalised space’ to that which non-commutative geometers are looking for?

I never like to say anything is ‘entirely’ different from anything else, since ultimately I want all concepts to combine in some sort of cosmic implosion — the mathematical ‘Big Crunch’ that Greg Egan describes in his story Glory:

The Big Crunch was her nickname for the mythical result that the Niah had aspired to reach: a unification of every field of mathematics that they considered significant.

But so far, the people in directed topology are studying sets equipped with structure that allows for ‘paths’ that don’t have ‘inverses’ — one-way roads, as it were. The most principled approach I’ve seen is that of Marco Grandis. Personally I want a way to build a kind of ‘directed space’ from any \infty-category, which would allow for one-way roads but also one-way roads between roads, etc.

Meanwhile, the noncommutative geometers are studying associative but noncommutative algebras and treating them as ‘spaces’ in a kind of metaphorical or analogical way.

The only connection I see is rather limited: noncommutative geometers sometimes use noncommutative algebras as a stand-in for topological groupoids.

Topological groupoids and \infty-categories are both special cases of topological \infty-categories… I think we’d have to go up to that level to unify all this stuff.

Posted by: John Baez on March 30, 2008 11:30 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

By the way, we have talked about directed homotopy theory and Grandis’ work on it a (tiny) bit here.

Posted by: Urs Schreiber on March 31, 2008 7:37 AM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

The reason that I ask is that there’s an exciting conjecture that could be made, linking ‘commutative quantum nn-algebras’ (i.e. commutative C*-algebras, symmetric 2-H*-algebras and so on) and nn-groupoids for all nn. It’s then natural to wonder whether the extension to noncommutative algebras on the one side might mirror an extension to non-groupoidal nn-categories on the other.

… ultimately I want all concepts to combine in some sort of cosmic implosion — the mathematical ‘Big Crunch’

Well, to me that’s what’s so exciting about a lot of the things that we talk about on this blog — for example, your recent paper with Mike Stay is certainly very Crunchy.

Posted by: Jamie Vicary on March 31, 2008 10:42 AM | Permalink | Reply to this

Crunchy Math/Physics/Computer in the Ideocosm; Re: Classical vs Quantum Computation (Week 2)

“… ultimately I want all concepts to combine in some sort of cosmic implosion — the mathematical ‘Big Crunch’”

Does this suggest, as a goal of the Math/Physics/Computer Science eneterprise, that there is an Big Bang Initial Meta-Object Concept from which infinitely many concepts (almost all concepts?) derive, and then a Big Crunch Terminal Meta-Object Concept to which infinitely many concepts (almost all concepts?) contribute? Some meta-meta…-meta diagram that commutes?

Or are there multiple ways in and out of a Semantic Web that usefully embraces Math/Physics/Computer Science?

This gets to the Topology and the Directed Homotopy of the space of all possible ideas – the “ideocosm”, to use Fritz Zwicky’s term.

See:
What Ideonomy Can Do

Posted by: Jonathan Vos Post on March 31, 2008 6:07 PM | Permalink | Reply to this

Re: Crunchy Math/Physics/Computer in the Ideocosm; Re: Classical vs Quantum Computation (Week 2)

Conc. “Ideonomy”:
I guess Gunkel had the questionable idea of adapting a bad joke of Stanislav Lem (the “linguistic prognostics” of “Prof. Trottelreiner (engl. ca. “Prof Purefool”)” in “The futurological Congress”)

Posted by: Thomas Riepe on March 31, 2008 6:42 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

Jamie almost wrote:

The reason that I ask is that there’s an exciting conjecture that could be made, linking ‘commutative quantum nn-algebras’ (i.e. commutative C*-algebras, symmetric 2-C*-algebras and so on) and nn-groupoids for all nn.

Right: the categorified Gelfan’d–Naimark hypothesis, setting up a duality between compact Hausdorff nn-groupoids XX and symmetric (n+1)(n+1)-C*-algebras AA: Ahom(X,nHilb) A \simeq hom(X,n Hilb) XSpec(A) X \simeq Spec(A) or something like that.

(The n=0n = 0 case is the usual Gelfan’d–Naimark theorem; already for n=1n = 1 I only know how to handle a limited special case of this hypothesis!)

It’s then natural to wonder whether the extension to noncommutative algebras on the one side might mirror an extension to non-groupoidal nn-categories on the other.

Is it? I don’t see why. It’s probably good to ponder some n=1n = 1 examples.

… ultimately I want all concepts to combine in some sort of cosmic implosion — the mathematical ‘Big Crunch’

Well, to me that’s what’s so exciting about a lot of the things that we talk about on this blog — for example, your recent paper with Mike Stay is certainly very Crunchy.

Thanks! That’s a nice-sounding adjective.

It’s interesting that mathematicians seem generally less grandiose than physicists when it comes to Dreams of a Final Theory. Perhaps it’s just more obvious that math is an infinite endeavor. But anyone who believes in god, or even in the depth of nature, should be skeptical of claims that we’ll figure out all the fundamental laws of physics anytime soon. I wouldn’t be surprised if they go on forever too.

Posted by: John Baez on March 31, 2008 8:30 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

John corrected me to:

The reason that I ask is that there’s an exciting conjecture that could be made, linking ‘commutative quantum nn-algebras’ (i.e. commutative C*-algebras, symmetric 2-C*-algebras and so on) and nn-groupoids for all nn.

Hmm… I’m pretty sure I haven’t seen a definition of a 2-C*-algebra before. Do you not think 2-H*-algebras will be good enough for the hypothesis? Or is 2-C*-algebra the same thing as a 2-H*-algebra? I don’t see how the difference between H*-algebras and C*-algebras categorifies!

It’s then natural to wonder whether the extension to noncommutative algebras on the one side might mirror an extension to non-groupoidal nn-categories on the other.

Is it? I don’t see why. It’s probably good to ponder some n=1n=1 examples.

Well, if there is any sort of extension along these lines, I’m not saying it’s easy to find. We fall at the first hurdle if we naively try and look at the unitary representations of general nn-categories in nnHilb, because ‘unitary’ doesn’t mean anything. So it’s difficult to say outright that the generalisation doesn’t work, because it can’t even be posed.

All I know is that people study sophisticated generalised spaces that have non-commutative ‘algebras of functions’ on them in an attempt to formulate a non-commutative spectral theorem, and it doesn’t seem impossible to me a priori that these could have something to do with ‘1-way topological spaces’.

Posted by: Jamie Vicary on March 31, 2008 10:19 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

Will the final thing to disappear in the mathematical Big Crunch be the gulf between the Two Cultures?

Posted by: David Corfield on April 29, 2008 4:57 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

David wrote:

Will the final thing to disappear in the mathematical Big Crunch be the gulf between the Two Cultures?

That might even persist after the Crunch! There will always be lots of tricky problems for the problem-solvers to chew on, so I can imagine this science fiction scenario: the theory-builders unify all the beautiful abstract concepts they know and decide mathematics is done, but the problem solvers disagree and keep on working. The theory-builders would say the problem-solvers had been reduced to playing with shallow puzzles, while the problem-solvers would say the theory-builders had become trapped in a deadly edifice of incomprehensible abstraction.

In terms of astrophysics analogies, this would resemble the Big Crunch less than a black hole that swallowed up some but not all mathematicians.

It would make a fun story, but I hope it doesn’t actually happen — though some might argue it’s already well underway.

Posted by: John Baez on April 30, 2008 8:34 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

‘Theory Building’ and ‘Problem Solving’ were used more to designate two kinds of theory. The wonder is whether the theories from either side will unite. Minhyong gave a good illustration of the difference

(1) The theorem about primes in arithmetic progressions.

(2) The theorem about arithmetic progressions in primes.

and an interesting sketch of a solution.

Posted by: David Corfield on May 1, 2008 10:34 AM | Permalink | Reply to this

Theory-Commutator; Re: Classical vs Quantum Computation (Week 2)

Some lobe of my brain asked me about the commutator in theory-space:

[primes, arithmetic progressions]_Theory

=

“theorem about primes in arithmetic progressions” - “theorem about arithmetic progressions in primes”

and recalls that I’d hinted at this in
A133234 a(n) is least semiprime (not already in list) such that no 3-term subset forms an arithmetic progression

Again, the “theory commutator” is scratching my persistent itch about the topology of the ideocosm (space of all possible ideas, to use the term coined by Fritz Zwicky).

Posted by: Jonathan Vos Post on May 1, 2008 5:14 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

My characterization includes the counit law, but not the coassociative law - instead, it requires that !A and ΔA are monoidal natural transformations.

I think that I was assuming that they were natural already, on the grounds that you can’t do any diagrammatic reasoning otherwise. (You can’t slide something independent —off to the side— up and down past them if they’re not monoidally natural.)

I guess coassociativity follows somehow…

I guess…

Posted by: Toby Bartels on October 27, 2006 8:10 AM | Permalink | Reply to this
Read the post Classical vs Quantum Computation (Week 3)
Weblog: The n-Category Café
Excerpt: Guest lecture by James Dolan: Holodeck strategies and cartesian closed categories.
Tracked: October 20, 2006 3:12 AM

Re: Classical vs Quantum Computation (Week 2)

Mike Stay raised the following puzzle about the theme of this lecture:

In a cartesian category with coproducts, the Hom functor is product-preserving functor from C op×CC^{op} \times C to SetSet:

Hom(A+B,C)Hom(A,C)×Hom(B,C) Hom(A + B,C) \cong Hom(A,C) \times Hom(B,C) Hom(A,B×C)Hom(A,B)×Hom(A,C) Hom(A,B \times C) \cong Hom(A,B) \times Hom(A,C)

So we can view it as a model of the theory C op×CC^{op} \times C.

This isn’t always true for a mere monoidal category, since both (Vect,)(Vect, \oplus) and (Vect,)(Vect, \otimes) are monoidal categories but have different sized Hom sets.

Is there something similar that always holds?

I’ve thought more about the question of whether the ‘elements’ functor

el:CSet el: C \to Set

given by

el(c)=Hom(I,c) el(c) = Hom(I, c)

is a model of the monoidal category CC, where II is the unit object. If CC is cartesian, this functor is product-preserving, so it does indeed give a model of CC in SetSet. If CC is just monoidal… well, think about it!

I’ve never thought about HomHom as a model of C op×CC^{op} \times C. I bet someone reading this has, though.

Posted by: John Baez on January 28, 2007 7:32 PM | Permalink | Reply to this

Re: Classical vs Quantum Computation (Week 2)

This may be heading off in a direction different to the one where Mike and/or John wanted to go, but there is a way of seeing Hom as a lax model of a certain kind. Jim Dolan and I were thinking about this stuff a while back in connection with the theory of buildings (see below).

If VV is a monoidal category, there is a jazzed-up defnition of VV-enriched category, as “nothing but” a set (discrete category) X together with a functor d:X×XVd: X \times X \to V and a lax monoidal structure on the functor Set d:Set VSet X×XSet^d: Set^V \to Set^{X \times X} where the monoidal product on the domain is Day convolution, and the monoidal product on the codomain is given by composition of endospans on XX.

By restriction along the Yoneda embedding, this gives a lax monoidal functor V opSet X×XV^{op} \to Set^{X \times X} which we could think of as a lax endospan model of V opV^{op}.

Cranking up the abstraction level a notch or two, we can think of a VV-enrichment of a category XX as a lax morphism of (pseudo)monoids V opX op×XV^{op} \to X^{op} \times X in the compact bicategory of categories and bimodules (or profunctors) between them. (In a compact bicategory, X *XX^* \otimes X automatically carries a monoid structure, where X *X^* is the dual of XX.)

If you want a strong model rather than a lax model of V opV^{op}, i.e., where Set dSet^d is a strong monoidal functor, that’s also interesting to contemplate. A special case of that is where XX admits VV-tensors, i.e., where each covariant hom-functor d(x,):XVd(x, -): X \to V has a VV-enriched left adjoint: V(v,d(x,y))d(vx,y).V(v, d(x, y)) \cong d(v \cdot x, y). (Proving strong monoidality in this case is a fun little exercise in the calculus of bimodules.)

Jim and I were using this stuff to give a slicked-up definition of Tits buildings, from a generalized metric space point of view. I’ll have to be a little cryptic here: given a Coxeter diagram DD, there’s an associated monoidal poset W W_{\infty} which Jim calls the “Murphy monoid”. It’s presented much like the Coxeter group, except that the generators are idempotents instead of involutions, and the partial order is the smallest one respecting the monoid structure such that the identity is maximal. Then a DD-building is “nothing but” a “strong W W_{\infty}-enrichment” of a set FF (of “flags”), 2 d:2 W 2 F×F2^d: 2^{W_{\infty}} \to 2^{F \times F} which moreover preserves the homs adjoint to the tensors in these monoidal categories. (Thus we replace Set by 2, with its usual nontrivial order.)

Posted by: Todd Trimble on January 29, 2007 8:37 PM | Permalink | Reply to this
Read the post Classical vs Quantum Computation (Week 1)
Weblog: The n-Category Café
Excerpt: Computation, the lambda calculus and cartesian closed categories: an overview.
Tracked: January 31, 2007 4:30 AM
Read the post Calculations Inside Semisimple Categories
Weblog: The n-Category Café
Excerpt: Bruce Bartlett on computations in semisimple categories.
Tracked: May 18, 2007 12:27 PM

Categorified C*-algebras and H*-algebras

I’m getting sick of the highly nested threading above, so I’ll reply to Jamie’s comment about 2-C*-algebras here. Jamie wrote:

Hmm… I’m pretty sure I haven’t seen a definition of a 2-C*-algebra before.

Neither have I.

I know what C*-algebras and H*-algebras are, I know what C*-categories and H*-categories are, and I know what 2-H*-algebras are. Some of the definitions are conveniently listed in a post by Urs. I’ve never tried defining 2-C*-algebras, but someone should!

To understand 2-C*-algebras we really should understand infinite-dimensional 2-Hilbert spaces. I defined finite-dimensional 2-Hilbert spaces a while ago, but I’m still just gradually working my way towards understanding the infinite-dimensional ones. The higher Hilbert spaces discussed in my paper with Baratin, Freidel and Wise are not the final correct notion of 2-Hilbert space, but they’re close.

Do you not think 2-H*-algebras will be good enough for the hypothesis?

No, not for the full-fledged version of the Gelfan’d–Naimark Hypothesis mentioned above.

We can see this already one notch down. A finite-dimensional H*-algebra is almost the same thing as a finite-dimensional C*-algebra — there are functors going back and forth between H*-Alg and C*-Alg, and they almost form an equivalence.

(The only difference is that we don’t require 1=1\| 1 \| = 1 in an H*-algebra, while we do in a C*-algebra. This leads to some subtle issues that would be fun to explore elsewhere… I believe Bruce Bartlett has thought about these a bit! But, they’re not the main point here.)

On the other hand, infinite-dimensional C*-algebras are far more general than infinite-dimensional H*-algebras.

So, there’s a nice Gelfan’d–Naimark theorem for commutative C*-algebras, saying any of these is the algebra of continuous complex functions on a compact Hausdorff space, and conversely.

But, this isn’t true for commutative H*-algebras.

However, we can say any finite-dimensional commutative H*-algebra is the algebra of complex functions on a finite measure space, and conversely. This is a ‘baby’ version of the Gelfan’d–Naimark theorem.

(Measure space? Well, this is where the subtle parenthetical remark above rears its ugly head.)

There is also a theorem of Gelfan’d–Naimark type that applies to arbitrary commutative H*-algebras — but it’s still sort of a ‘baby’ version the one for commutative C*-algebras.

Given all this, we’d naturally expect the Gelfan’d–Naimark theorem for symmetric 2-H*-algebras to be just a baby version of the version for 2-C*-algebras (whatever those turn out to be).

And as you know, I proved this baby version in HDA2.

Or is a 2-C*-algebra the same thing as a 2-H*-algebra?

We surely don’t want that.

I don’t see how the difference between H*-algebras and C*-algebras categorifies!

Neither do I, completely, but the difference between H*-categories and C*-categories is very instructive.

(Unfortunately, the word “C*-category” seems to be ungooglable — try papers by Michael Müger and others if you want to see the definition.)

Posted by: John Baez on April 3, 2008 8:49 PM | Permalink | Reply to this

Re: Categorified C*-algebras and H*-algebras

The higher Hilbert spaces discussed in my paper with with Baratin, Freidel and Wise are not the final correct notion of 2-Hilbert space

Ah, the 2-rep article. Didn’t know you had made it available.

By the way, i have tought of the following concept of ω\omega-representation of ω\omega-groups:

I had talked about representations of L L_\infty-algebras a bit before, inspired by the idea that we define any rep by its action Lie \infty-algebroid: it’s as follows:

for VV a chain complex thought of as an \infty-vector space and for gg a (finite dimensional) L L_\infty-algebra I say that an action of gg on VV is defined through the action Lie \infty-algebroid whose CE algebra, in turn, is required to sit in the sequence V *CE(g,V)CE(g) \wedge^\bullet V^* \leftarrow CE(g,V) \leftarrow CE(g) Where the item on the left is the free graded symmetric dgca obtained from V *V^* and where the left arrow is a surjection and the right one an injection.

This is to be thought of as the linearized and dual version to the action groupoid sequence VV//GBG. V \to V//G \to \mathbf{B} G \,.

Anyway, one nice thing about such a definition is that the method for integrating L L_\infty-algebras to Lie ω\omega-groups extendes seamlessly also to the representation:

we simply hit the sequence above with the functor S:DGCAsSmoothSpacesS : DGCAs \to SmoothSpaces to obtain

S( V *)S(CE(g,V))S(CE(g)) S(\wedge^\bullet V^* ) \to S(CE(g,V)) \to S(CE(g)) and then apply Π ω:SmoothSpacesLieωGroupoids \Pi_\omega : SmoothSpaces \to Lie \omega-Groupoids Π ω(S( V *))Π ω(S(CE(g,V)))Π ω(S(CE(g))). \Pi_\omega(S(\wedge^\bullet V^* )) \to \Pi_\omega(S(CE(g,V))) \to \Pi_\omega(S(CE(g))) \,. The item on the right is Π ω(S(CE(g)))=BG \Pi_\omega(S(CE(g))) = \mathbf{B}G for GG the “simply connected” ω\omega-group integrating gg. Π ω(S(CE(g,V))) \Pi_\omega(S(CE(g,V))) plays the role of the action groupoid of GG on the ω\omega-category Π ω(S( V *))\Pi_\omega(S(\wedge^\bullet V^*)).

So that’s the “representation space” here. It comes to us as a bit of a hybrid between a Baez-Crans \infty-vector space (i.e. an ω\omega-category internal to vector spaces) and something else.

Whatever it is, it has an action of the Lie ω\omega-group on t such that differentially it reproduces the action of an L L_\infty-algebra on a Baez-Crans \infty-vector space.

Posted by: Urs Schreiber on April 3, 2008 9:36 PM | Permalink | Reply to this

Re: Categorified C*-algebras and H*-algebras

Urs wrote:

Ah, the 2-rep article. Didn’t know you had made it available.

I haven’t, really. It’s not done, and it still has a bunch of mistakes in it. I just thought Jamie might like a peek.

However, my coauthors want to finish this up really soon! So, when I go to Shanghai on Monday my main job will be to finish that and also the paper with Alex Hoffnung on smooth spaces. There’s nothing more fun than going to exotic places and staring at a computer all day.

Posted by: John Baez on April 4, 2008 12:17 AM | Permalink | Reply to this

Re: Categorified C*-algebras and H*-algebras

The formulation of C *C^*-algebras that Bas Spitters and Chris Heunen consider seems to be well suited for internalization. I don’t think they have tried to internalize it in nCatn Cat, but since it works so well for what they do, maybe it would be worth considering this.

Posted by: Urs Schreiber on April 3, 2008 9:42 PM | Permalink | Reply to this

Re: Categorified C*-algebras and H*-algebras

Thanks John. I only have time for a quick reply at the moment since (sensibly) I am being hassled to go to bed.

I thought that the only problem with infinite-dimensional 2-Hilbert spaces was that the category of them would fail to have all duals — because having duals for an infinite-dimensional 2-Hilbert space means we have to have an infinite-dimensional Hilbert space as a scalar, and having a dual for that means that we have to have an infinite complex number.

I guess that this isn’t the problem you’ve got in mind, though, since this doesn’t stop you constructing individual infinite-dimensional 2-Hilbert spaces, just a nice 2-category of them.

Posted by: Jamie Vicary on April 3, 2008 10:50 PM | Permalink | Reply to this

Re: Categorified C*-algebras and H*-algebras

Hi John,

Thanks for giving us another sneak preview of the paper on 2-reps! I’m a bit confused: am I right to say that in this paper you are studying strict representations, with weak intertwiners for morphisms, and modifications for 2-intertwiners? That seems strange.

Posted by: Bruce Bartlett on April 4, 2008 10:16 AM | Permalink | Reply to this

Re: Categorified C*-algebras and H*-algebras

It may be stupid, but it’s not strange: there’s been a whole lot of work on the category of

[strict 2-categories, strict 2-functors]

since this can be given an internal hom

hom(C,D) = [strict 2-functors from C to D, weak natural transformations between these]

and adjoint to this internal hom there is a tensor product called the ‘Gray’ tensor product of 2-categories, which is pretty interesting.

Crane, Sheppeard and Yetter studied representations of 2-groups on higher Hilbert spaces in this context, and our paper is an elaboration of their work. In fact our paper began life as the introduction to a longer paper which studies a 4d state sum model based on representations of the Poincaré 2-group. But the introduction grew so long that it fell off and grew into a paper of it own! I then decided I was too tired to write the original state sum paper — especially since Baratin and Freidel did most of the really hard computations. But, I decided to help finish off this one.

You’re right: someone should study fully weak representations of 2-groups on these higher Hilbert spaces. But it probably ain’t gonna be me.

Posted by: John Baez on April 4, 2008 8:02 PM | Permalink | Reply to this

Re: Categorified C*-algebras and H*-algebras

Unfortunately, the word “C*-category” seems to be ungooglable

Yeps! Grrr…. this kind of thing has caused me so much trouble. “*-categories”, “H*-algebra”, “*-anything”, and you’re in the soup.

Posted by: Bruce Bartlett on April 4, 2008 10:21 AM | Permalink | Reply to this

Re: Categorified C*-algebras and H*-algebras

I think that’s more from the lack of relevant hits than from a fault in Google’s search engine. The search “c* algebra” (with quotes) turns up only relevant hits on the first page. Also, “c star algebra” turns up a ton of hits, too. Are there sites you expected to see in the search that didn’t turn up?

Posted by: Mike Stay on April 4, 2008 5:40 PM | Permalink | Reply to this

Re: Categorified C*-algebras and H*-algebras

Also, if you get a bunch of irrelevant hits (like “five-star category” of hotels) then add a term you’re pretty sure will be connected only with that context. The search

“star category” functor

gives a bunch of relevant hits.

Posted by: Mike Stay on April 4, 2008 5:45 PM | Permalink | Reply to this

Re: Categorified C*-algebras and H*-algebras

Finally, if you use Google Scholar, you’re more likely to get hits for mathematical usage. Searching for

“c category” functor

gave at least ten hits in the first three pages for C *C^* categories.

Posted by: Mike Stay on April 4, 2008 5:55 PM | Permalink | Reply to this

Re: Categorified C*-algebras and H*-algebras

I think that’s more from the lack of relevant hits than from a fault in Google’s search engine.

I disagree. I don’t know of a way, in Google, to include the asterisk as part of the text without Google thinking it’s a wildcard. I regard that as a fault in its search engine.

Your comments are helpful, thanks, but they will fail for searches like “category with a *-structure”, which as far as I can see only returns one mathematical hit in the first three pages, and that hit is a false one anyway, I think.

Posted by: Bruce Bartlett on April 4, 2008 7:06 PM | Permalink | Reply to this

Re: Categorified C*-algebras and H*-algebras

Bruce wrote:

I don’t know of a way, in Google, to include the asterisk as part of the text without Google thinking it’s a wildcard. I regard that as a fault in its search engine.

Oh, a wildcard! I see. I wondered why searching under “C*-category” mainly turned up stuff on pregnancy, with a little bioterrorism thrown in, and even some category theory — but nothing about C*-categories.

Posted by: John Baez on April 4, 2008 7:32 PM | Permalink | Reply to this

Re: Categorified C*-algebras and H*-algebras

I regard that as a fault in its search engine.

Yeah, it would be nice to be able to say “include punctuation in my search.” That is possible on http://www.google.com/codesearch, where you can use regular expressions to search over your codebase. I assume that something similar must be possible for .ps or .pdf files.

I’ll ping the scholar guys and see what they think about the possibility. Any other typographic stuff you’d like to be able to search on?

Posted by: Mike Stay on April 4, 2008 9:43 PM | Permalink | Reply to this

Re: Categorified C*-algebras and H*-algebras

Your comments are helpful, thanks, but they will fail for searches like “category with a *-structure”,

Given that Google doesn’t index punctuation except in code search, get rid of it in your queries (since you don’t want to use it as a wildcard). The web search doesn’t turn up anything relevant. Do you know of a web document in which that phrase appears that should have been in the search results? Search quality people would be interested.

A Google Scholar search for

“category with a structure”

turns up John’s paper “Quantum Algebra and Topology”

…Definition 2. An H*-category is a Hilb-category with a ∗-structure that defines an antinatural transformation from hom(x, y) to hom(y, x)…

It looks like the phrase “antinatural transformation” might be useful to narrow down searches that are too broad.

Posted by: Mike Stay on April 4, 2008 9:55 PM | Permalink | Reply to this

Re: Categorified C*-algebras and H*-algebras

Search quality people would be interested.

By the way: I noticed that about three weeks ago there must have occured a moderately major change in the Google algorithm. In any case, since then typing “n-category cafe” into Google produces a remarkably weird collection of links – not featuring the only sensible search result, the blog’s index page, anywhere. (At least an entry of the blog appears near the top. The top result itself is an empty page!)

It didn’t use to be that way. The blog’s index page used to be the first hit even for “n-category”. That of course wasn’t optimal either, as clearly the Wiki entry on n-categories deserves to be there at top.

I am guessing that the new behaviour might be related to the special characters in the blog’s title. Better search results (though still strange) are obtained by typing some html ot UTML special character code into the search request box.

Posted by: Urs Schreiber on April 4, 2008 11:22 PM | Permalink | Reply to this

Re: Categorified C*-algebras and H*-algebras

Mike Stay wrote:

It looks like the phrase “antinatural transformation” might be useful to narrow down searches that are too broad.

I think I invented that term in HDA2 — so yeah, that narrows things down quite a bit.

There’s a large literature on C*-categories and \dagger-categories, all difficult to search for thanks to those stars and daggers, none of which mentions ‘antinatural transformations’.

Posted by: John Baez on April 4, 2008 10:33 PM | Permalink | Reply to this

Re: Categorified C*-algebras and H*-algebras

OK, Google doesn’t index punctuation, but it does have a small list of exceptional terms, like C++ and C#, and I now know how to add more. So RIGHT NOW is your chance to get all your favorite typographical horrors added to Google’s index. Post below any terms you’d like to be able to search for.

Posted by: Mike Stay on April 5, 2008 5:05 PM | Permalink | Reply to this

Post a New Comment