Classical vs Quantum Computation (Week 2)

October 17, 2006

Classical vs Quantum Computation (Week 2)

Posted by John Baez

$MathML-enabled post (click for more details).$

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.

$MathML-enabled post (click for more details).$

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

82 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(X, Y) → 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(X, Y) 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)

$MathML-enabled post (click for more details).$

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}$ and $!_{A}$ make any object $A$ in a cartesian category into a comonoid - just like a monoid, but upside down, with $Δ_{A}$ as comultiplication and $!_{A}$ as counit.

I’m not sure these are all we need to reason with $Δ$ and $!$ diagrammatically. I have a characterization of cartesian categories in terms of $Δ$ 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}$ and $Δ_{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(X, Y) → 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(X, Y) 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)

$MathML-enabled post (click for more details).$

Doesn’t $Δ$ 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)

$MathML-enabled post (click for more details).$

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

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.

More interestingly: for every symmetric monoidal category $ℂ$ , there is a symmetric monoidal category $Comon (ℂ)$ of commutative comonoids in $ℂ$ . (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 $Comon$ 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)

$MathML-enabled post (click for more details).$

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 $Δ$ 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} : A \otimes I \to I \otimes A \to A$

be equal to $ρ_{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)

$MathML-enabled post (click for more details).$

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  $a$  for the associator and  $g$  for the symmetry
(or braiding), if one assumes the mediating isomorphism 
 $Φ$  between
 $(A \otimes A) \otimes (B \otimes B)$ 
and
 $(A \otimes B) \otimes (A \otimes B)$ 
to be (fasten your seat belt):

 $(A \otimes A) \otimes (B \otimes B)$ 
       |
       |  $a^{- 1}$ 
       |
       v
 $A \otimes (A \otimes (B \otimes B))$ 
       |
       |  $id \otimes a$ 
       |
       v
 $A \otimes ((A \otimes B) \otimes B)$ 
       |
       |  $id \otimes (g \otimes id)$ 
       |
       v
 $A \otimes ((B \otimes A) \otimes B)$ 
       |
       |  $id \otimes a^{- 1}$ 
       |
       v
 $A \otimes (B \otimes (A \otimes B))$ 
       |
       |  $a$ 
       |
       v
 $(A \otimes B) \otimes (A \otimes B)$ ,

then unicity of the pairing  $< f, g > = (f \otimes g) o Δ$ 
follows from the fact that  $Δ$  is monoidal.
There are two points to check here: (1)  $Φ$  makes 
our functor monoidal and (2) unicity follows.
We haven’t checked (1) yet but here is the argument 
for (2) (shortened):

 $Δ$  being monoidal, the following commutes:
           $Δ \otimes Δ$ 
 $A \otimes B$  —————————–>  $(A \otimes A) \otimes (B \otimes B)$ 
 ||                     |
 ||                     |  $Φ$ 
 ||        $Δ$             v
 $A \otimes B$  —————————–>  $(A \otimes B) \otimes (A \otimes B)$ 

Then, unicity seems to follow from the fact that  $< π, π' > = id$ . 
If so, we just have to prove that the 
following is the identity (writing  $e$  for the eraser, 
 $r$  for the right unitor,  $l$  for the left unitor):

       $A \otimes B$ 
       |
       |  $Δ$ 
       v
 $(A \otimes B) \otimes (A \otimes B)$ 
       |
       |  $(id \otimes e) \otimes (e \otimes id)$ 
       |
       v
 $(A \otimes I) \otimes (I \otimes B)$ 
       |
       |  $r \otimes l$ 
       |
       v
      $A \otimes B$ 

Using the previous diagram, this amounts to showing that

     $A \otimes B$ 
     |
     |  $Δ \otimes Δ$ 
     v
 $(A \otimes A) \otimes (B \otimes B)$ 
     |
     |  $Φ$ 
     v
 $(A \otimes B) \otimes (A \otimes B)$ 
     |
     |  $(id \otimes e) \otimes (e \otimes id)$ 
     |
     v
 $(A \otimes I) \otimes (I \otimes B)$ 
     |
     |  $r \otimes l$ 
     |
     v
     $A \otimes B$ 

is the identity.  But by the coherence laws of symmetric 
monoidal categories, and without touching the  $Δ$ ’s,
this reduces to

    $A \otimes B$ 
     |
     |  $Δ \otimes Δ$ 
     |
     v
 $(A \otimes A) \otimes (B \otimes B)$ 
     |
     |  $(id \otimes e) \otimes (e \otimes id)$ 
     |
     v
 $(A \otimes I) \otimes (I \otimes B)$ 
     |
     |  $r \otimes l$ 
     |
     v
    $A \otimes B$ 

which is the tensor of the hypotheses on  $Δ$  
and  $e$ , 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 $a$ and the unitors $l$ and $r$ - 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 $a$ , $l$ and $r$ 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 $a$ , $l$ and $r$ 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) \otimes Φ (y) \to Φ (x \otimes y)$ be invertible in his definition of a monoidal functor $Φ$ . 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) \otimes Φ (y) \to Φ (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)

$MathML-enabled post (click for more details).$

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 = (Δ \otimes Δ); Φ; ((id \otimes e) \otimes (e \otimes id)); (r \otimes l)$ is the identity, where $Φ$ is the symmetry, surrounded by uses of associativity.

Now, we have a symmetric monoidal equivalence

$C \overset{F}{\to} D \overset{G}{\to} C,$

where $C$ is our original cat and $D$ is its strict equivalent.

This should mean that, when transporting the considered $f$ to $D$ through $F$ yields the identity, which by naturality of the iso between 1 and $G \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)

$MathML-enabled post (click for more details).$

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 $B$ in ${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:

John Baez and Aaron Lauda, Higher-dimensional algebra V: 2-groups, Theory and Applications of Categories 12 (2004), 423-491. Section 8.3: Classifying 2-groups using group cohomology.

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)

$MathML-enabled post (click for more details).$

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)

$MathML-enabled post (click for more details).$

Jamie wrote:

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

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

So it isn’t that $D$ ’s not strict — it’s that $D$ ’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)

$MathML-enabled post (click for more details).$

Tom wrote:

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

OK, but this seems easy to fix up — can’t you just redefine the tensor product on $D$ 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)

$MathML-enabled post (click for more details).$

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)

$MathML-enabled post (click for more details).$

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)

$MathML-enabled post (click for more details).$

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

$(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} : (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 $X$ is equivalent to a skeletal subcategory $\tilde{X}$ , we need to pick a representative for each isomorphism class of objects in $X$ . These representatives will be the objects in $\tilde{X}$ .

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

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

$f_{x} : x \to \tilde{x}$

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

$X ≃ \tilde{X}$

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

So, even if $X$ is a strict monoidal category, these isomorphisms $a_{x}$ will show up in the associator for $\tilde{X}$ . And that’s why $\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)

$MathML-enabled post (click for more details).$

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 $n$ , 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)

$MathML-enabled post (click for more details).$

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}$ for some finite natural number $N$ . Given two finite sets $A$ and $B$ , I decided to give their product the following ordering, which seemed pretty natural:

(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}), \dots}

So first we list the elements of $A$ and $B$ 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 \times (B \times C)$ will have a different ordering to $(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 \times B$ , where $A$ is of size $∣ A ∣$ and $B$ is of size $∣ B ∣$ :

(2)

\begin{aligned} A \times B = { & (a_{1}, b_{1}), (a_{1}, b_{2}), \dots, (a_{1}, b_{∣ B ∣}), \\ (a_{2}, b_{1}), (a_{2}, b_{2}), \dots, (a_{2}, b_{∣ B ∣}), \\ \dots, \\ (a_{∣ A ∣}, b_{1}), \dots, (a_{∣ A ∣}, b_{∣ B ∣})} \end{aligned}

So first we cycle through the elements of $B$ , then we choose the next element of $A$ and cycle through $B$ again, and so on until the end. Using this choice we don’t need associators, because $A \times (B \times C)$ comes out identical to $(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})$ 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 \times (B \times C)$ and $(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)

$MathML-enabled post (click for more details).$

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 \times (B \times C)$ and $(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) \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)

underline n = {1, 2, 3, \dots, n} .

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

(2)

ℵ_{0} = {1, 2, 3, \dots}

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)

$MathML-enabled post (click for more details).$

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) \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)

$MathML-enabled post (click for more details).$

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, \dots, n - 1}$

than the infinite ones.

(However I like the ordinals I just wrote down better than your sets $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 $Set$ . 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} : 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 $Set$ skeletal and strict, but he came up with a trick that does the job for $FinSet$ and fails for $Set$ , 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)

$MathML-enabled post (click for more details).$

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)

$MathML-enabled post (click for more details).$

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}$ , letting 2 be ${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 $Set$ comes along with a very nice skeleton, $Card$ .

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 $Numbers$ to be a certain skeletal strict monoidal category that’s equivalent, as a monoidal category, to $FinSet$ . I would be very happy if the italicized phrase characterizes $Numbers$ 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 $FinSet$ are isomorphic as strict monoidal categories.

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

Then, starting from this strict monoidal category $Numbers$ , 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)

$MathML-enabled post (click for more details).$

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, \dots, n} \to {1,2, \dots, 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} : pqr \to 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)

$MathML-enabled post (click for more details).$

Bruce said:

Suppose we consider the monoidal category (Numbers $, \times, 1$ ). Objects are positive natural numbers, morphisms are functions $f : {1,2, \dots, n} \Rightarrow {1,2, \dots, 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)

$MathML-enabled post (click for more details).$

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

(1)

(1,1), (1,2), \dots, (1, n), (2,1), (2,2), \dots (2, n), \dots, (m,1), (m,2), \dots (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, \dots, n}$ for every finite set $X$ - 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)

$MathML-enabled post (click for more details).$

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)

$MathML-enabled post (click for more details).$

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( $k$ ), with natural numbers for objects and $k$ -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)

$MathML-enabled post (click for more details).$

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 $(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 $(Fin Vect, \otimes, k)$ .

I think this is normally called Mat(k), with natural numbers for objects and $k$ -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 \times n$ matrix and an $m \times m$ matrix with an $n m \times n m$ . Presumably we want to use your isomorphism of finite ordinals $n \times m ≅ n m$ , where $n \times m$ is ordered lexicographically.

In fancy jargon, this amounts to taking advantage of the monoidal ‘free vector space’ functor $F : Fin Set \to Fin Vect$ , sending $n$ to $k^{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)

$MathML-enabled post (click for more details).$

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 \times k$ and $m \times ℓ$ that show up when you take a tensor product of an $n \times m$ matrix and $k \times ℓ$ 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 $FinVect$ 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)

$MathML-enabled post (click for more details).$

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)

$MathML-enabled post (click for more details).$

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_{ℂ, ℂ, ℂ}$ , where it can only be the map

(1)

(λ_{1} \otimes λ_{2}) \otimes λ_{3} \mapsto λ_{1} \otimes (λ_{2} \otimes λ_{3})

because the pentagon equation has the form

(2)

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 $Vect$ skeletal… we just choose the full subcategory ${Vect}_{0}$ having objects $ℂ^{n}$ . We pull-back the tensor-product and associator from $Vect$ to make ${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 $Vect ≅ {Vect}_{0}$ , which we need in order to pull-back this data).

So here is our candidate strict monoidal category, $({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)

$MathML-enabled post (click for more details).$

Hi Bruce, that’s interesting. I don’t get why all the associativities must be trivial just because $α_{ℂ, ℂ, ℂ}$ is, though. I agree that this must be $1$ , which tells us that for $f : ℂ \to A$ , $g : ℂ \to B$ and $h : ℂ \to C$ we have $α_{A, B, C} \circ ((f \otimes g) \otimes h) = f \otimes (g \otimes h)$ . I agree that this defines $α_{A, B, C}$ — but how can we also conclude that it’s somehow trivial? Surely the morphisms $f \otimes (g \otimes h)$ and $(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)

$MathML-enabled post (click for more details).$

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 $Vect$ to show that $Vect$ 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 $Vect$ . You note that, just like any monoidal category $Vect$ is monoidally equivalent to a skeletal monoidal category ${Vect}_{0}$ . It’s easy to prove this result if we use the axiom of choice, just by choosing any skeleton

${Vect}_{0} ↪ Vect$

and showing there’s a functor going the other way

$Vect \to {Vect}_{0}$

which gives an equivalence of categories

$Vect ≃ {Vect}_{0}$

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

Combining these two stages of your argument, we can conclude that the skeletal category ${Vect}_{0}$ , equipped with the tensor product coming from $Vect$ 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}_{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_{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 thi

The n-Category Café

Skip to the Main Content

October 17, 2006