Subject: categories: Re: mystification and categorification

From: David Yetter <[email-masked]>
Date: Fri, 5 Mar 2004 10:55:26 -0600

Categorification is a bit like quantization:  it isn't a construction so much
as a desideratum for a relationship between one thing and another (in the
case of categorification an (n+1)-categorical structure and an n-categorical
structure; in the case of quantization a quantum mechanical system and
a classical mechanical system).

Categorification wants to find a higher-dimensional categorical structure
corresponding to a lower-dimensional one by weakening equations to
natural isomorphisms and imposing new, sensible, coherence conditions.
In general, for the original purpose for which it was proposed--constructions
of TQFT's and models of quantum gravity--one wants the highest categorical
level to have a linear structure (hence Baez wanting tensor product
and a sum it distributes over, rather than cartesian product and coproduct).
Specific lower-dimensional categories with structure are 'categorified' by
finding a higher-dimensional category with the new structure which 'lies over'
the lower dimensional one in the way an additive monoidal category lies
over its Grothendieck rig.

For instance any (k-linear) monoidal category with monoid of isomorphism
classes M is a categorification of M, and more generally (k-linear) monoidal
categories are a categorification of monoids.

A simple example shows why it is not a construction:  commutative monoids
(as rather special categories with one object) admit two different
categorifications:  symmetric monoidal categories and braided monoidal
categories (each regarded as a kind of bicategory with one object).
There is a good argument for regarding braided monoidal categories
as the 'correct' categorification:  the Eckmann-Hilton theorem ('a group
in GROUPS is an abelian group'  or, really as the proof shows, 'a monoid
in MONOIDS is a commutative monoid') 'categorifies' to: A monoidal category
in MONCAT is a braided monoidal category.

---

From: Vaughan Pratt <[email-masked]>
Date: Fri, 05 Mar 2004 22:49:56 -0800

>While I'm airing my confusions, can anyone tell me what
>'categorification' means? I don't know any such process; the simplest
>exanple, 'categorifying' natural numbers to get finite sets, seems to me
>rather 'remembering the finite sets and maps which gave rise to natural
>numbers by the abstraction of passing to isomorphism classes'.

A fair question.  I attended John's Coimbra lectures on this stuff in 1999
but a lot of it leaked out afterwards.  If I had to guess I'd say he was
categorifying the free monoid on one generator to make it a monoidal category,
but then how did the monoid end up as coproduct and the generator as the
final object?  One suspects some free association there---John, how *do*
you make that connection?

With regard to categorification in general, sets seem to play a central
role in at least one development of category theory.  The homobjects of
"ordinary" categories are homsets.  (In that sense I guess "ordinary" must
entail "locally small.")  2-categories are what you get if instead you let
them be homcats, suitably elaborated.

Going in the other direction, if you take homsets to be vacuous, not
in the sense that they are empty but rather that they are all the same,
then you get sets.  One more step in that direction makes everything look
the same, which may have something to do with the Maharishi Yogi hiring
category theorists for the math dept. of his university in Fairfield, Iowa.
(When I spoke last with the MY's "Minister of World Health," an MD who like
Ross Street was a classmate of mine but eight years earlier starting in 1957,
the entire conversation seemed to be largely a skirting of the minefield
of the sameness of everything, which may subconsciously have been behind my
obscure reply to Peter Freyd's posting a while back about unique existence
going back to Descartes, where I tried to one-up him by claiming it went
*much* further back.)

Categorification isn't the only way to get to 2-categories, which can be
understood instead in terms of the interchange law as a two-dimensional
associativity principle.  However John has got a lot of mileage out of
the categorification approach, which one can't begrudge in an era where
mileage and minutes are as integral to a balanced life as one's checkbook.
(Q: How many minutes in a month?  A: Depends on your plan.)

>Since in the category of sets, any nasty old infinite set satisfies
>the golden equation and many others, I have taken the liberty of
>interpreting  'nice' to mean at least 'satisfying no unexpected
>equations'.

Quite right.  I would add to this "and satisfying the expected equations."
The "nasty sets" of which Steve speaks fail to satisy such expected
equations as 2^2^X ~ X.  (The power set of a set is a Boolean algebra,
for heaven's sake.  Why on earth forget that structure prior to taking the
second exponentiation?  Set theorists seem to think that they can simply
forget structure without paying for it, but in the real world it costs
kT/2 joules per element of X to forget that structure.  If set theorists
aren't willing to pay real-world prices in their modeling, why should we
taxpayers pay them real-world salaries?  Large cardinals are a figment of
their overactive imaginations, and the solution to consistency concerns is
not to go there.)

Vaughan Pratt

---

From: "Stephen Schanuel" <[email-masked]>
Date: Thu, 4 Mar 2004 00:44:46 -0500

I was unable to understand John Baez' golden object problem, nor his
description of the solutions. He refuses to tell us what 'nice' means,
but let me at least propose that to be 'tolerable' a solution must be an
object in a category, and John doesn't tell us what category is involved
in either of the solutions; at least I couldn't find a specification of
the objects, nor the maps, so I found the descriptions 'intolerable', in
the technical sense defined above. He is very generous, allowing one to
use a category with both plus and times as extra monoidal structures.
(Does anyone know an example of interest in which the plus is not
coproduct?) This freedom is unnecessary; a little algebra plus Robbie
Gates' theorem provides a solution G to  G^2=G+1 which satisfies no
additional equations, in an extensive category (with coproduct as plus,
cartesian product as times).
    Briefly, here it is. A primitive fifth root of unity z is a root of
the polynomial 1+X+X^2+X^3+X^4, hence satisfies 1+z+z^2+z^3+z^4+z=z,
which is of the 'fixed point' form p(z)=z with p in N[X] and p(0) not
0. Gates' theorem then says that the free distributive category
containing an object Z and an isomorphism from p(Z) to Z is extensive,
and its Burnside rig B (of isomorphism classes of objects) is, as one
would hope, N[X]/(p(X)=X); that is, Z satisfies no unexpected
equations. Since the degree of p is greater than 1, an easy general
theorem tells us (from the joint injectivity of the Euler and dimension
homomorphisms) that two polynomials agree at the object Z if and only if
either they are the same polynomial or both are non-constant and they
agree at the number z.Now the 'algebra':  the golden number is 1+z+z^4.
So G=1+Z+Z^4 satisfies G^2=G+1, as desired. It satisfies no
unexpected equations, because the relation X^2=X+1 reduces any
polynomial in N[X] to a linear polynomial, and these reduced forms have
distinct Euler characteristics, i.e. differ at z. Thus the homomorphism
from N[X]/(X^2=X+1) to B (sending X to G) is injective, and that's all
I wanted.
    Since in the category of sets, any nasty old infinite set satisfies
the golden equation and many others, I have taken the liberty of
interpreting  'nice' to mean at least 'satisfying no unexpected
equations'. One could ask for more; the construction above has produced
a distributive, but not extensive, category whose Burnside rig is
N[X]/(X^2=X+1), the full subcategory with objects polynomials in G.
(If it were extensive, it would be closed under taking summands, but
every object in the larger category is a summand of G.) I don't know
whether there is an extensive category with N[X]/(X^2=X+1) as its full
Burnside rig; perhaps one or both of the examples John mentioned would
do, if I knew what they were.
    While I'm airing my confusions, can anyone tell me what
'categorification' means? I don't know any such process; the simplest
exanple, 'categorifying' natural numbers to get finite sets, seems to me
rather 'remembering the finite sets and maps which gave rise to natural
numbers by the abstraction of passing to isomorphism classes'.
   Finally, a note to John: While you're trying to give your audience
some feeling for the virtues of n-categories, couldn't you give them a
little help with n=1, by being a little more precise about objects and
maps?
   Greetings to all, and thanks for your patience while I got this stuff
off my chest,
   Steve Schanuel

---

From: Tom Leinster <[email-masked]>
Date: 07 Mar 2004 19:43:05 +0000

Steve Schanuel wrote:
> a category with both plus and times as extra monoidal structures.
> coproduct?)

Here are two examples that I've come across previously of rig categories
in which the plus is not coproduct:

(i) the category of finite sets and bijections, with + and x inherited
from the category of sets;

(ii) discrete rig categories, which are of course the same thing as
rigs.

> This freedom is unnecessary; a little algebra plus Robbie

If you *do* allow yourself the freedom to use any rig category then an
even simpler solution exists, also satisfying no additional equations:
just take the rig freely generated by an element G satisfying G^2 = G +
1 and regard it as a discrete rig category.

> interpreting  'nice' to mean at least 'satisfying no unexpected

I'd interpret "nice" differently.  (Apart from anything else, the
trivial example in my previous paragraph would otherwise make the golden
object problem uninteresting.)  "Nice" as I understand it is not a
precise term - at least, I don't know how to make it precise.  Maybe I
can explain my interpretation by analogy with the equation T = 1 + T^2.
A nice solution T would be the set of finite, binary, planar trees
together with the usual isomorphism T -~-> 1 + T^2; a nasty solution
would be a random infinite set T with a random isomorphism to 1 + T^2.
(Both these solutions are in the rig category Set with its standard +
and x.)  I regard the first solution as nice because I can see some
combinatorial content to it (and maybe, at the back of my mind, because
it has a constructive feel), and the second as nasty because I can't.
I'm not certain what I think of the solution given by the set of
not-necessarily-finite binary planar trees (nice?), or by the set of
binary planar trees of cardinality at most aleph_5 (probably nasty).

Maybe the finding of a "nice" solution is similar in spirit to the
finding of a "concrete interpretation" of a combinatorial identity.  As
an extremely simple example, consider the identity saying that each
entry in Pascal's triangle is the sum of the two above it,

   (n+1 choose r) = (n choose r-1) + (n choose r).

This is a doddle to prove, but all the same you'd be missing something
if you didn't know the standard "concrete interpretation": choosing r
objects out of n+1 objects amounts to EITHER choosing the first one and
then choosing r-1 of the remaining n OR ... .  Even if the challenge of
finding a "nice solution" or "concrete interpretation" isn't made
precise, I think there is a shared sense of what would count as an
answer, and finding an answer is in general not straightforward.

Best wishes,
Tom

---

From: Mike Oliver <[email-masked]>
Date: Sun, 07 Mar 2004 15:04:04 -0600

> their overactive imaginations, and the solution to consistency concerns is

I will answer you in a Popperian key:  Large cardinals are falsifiable,
and are not yet falsified.  They may in fact be figments of our imaginations,
but then why do they keep on *working*?  Could be just a coincidence -- but
so could all other observation; that way lies the nullification of science
in general.

It's an illusion, by the way, to think that you can be rid of concerns about
consistency by dumping large cardinals, that you can thus achieve a priori
justification for apodictic certainty.  That doesn't exist even for the
natural numbers; Ed Nelson is quite right on this point.

As to the question of taxpayer funding, I will not attempt to justify
it (I'm a libertarian in politics), but will merely note that many
taxpayers probably feel that way about *all* pure mathematics.

---

From: Steve Vickers <[email-masked]>
Date: Mon, 08 Mar 2004 10:20:23 +0000

Vaughan Pratt wrote:

>(The power set of a set is a Boolean algebra,

Dear Vaughan,

I like it!

But there's still the question of just what structure the power set has.
Constructively it's not a Boolean algebra in general, though it is a frame.

And is it even a set? You can in fact only say that by removing the
structure, which is exactly what you told the set-theorists not to do.
And in this instance it's arguable. Topos theorists say it is a set,
predicative type theorists say it isn't.

Part of the structure of the power "set" is topological - the Scott
topology, with the inclusion order as its specialization order. But to
formalize it as topological space, point-set + topological structure,
you again have to forget structure in order to get a point-set. Taking
this seriously generally brings you to point-free topology in some form
or other.

Steve Vickers.

---

From: Pawel Sobocinski <[email-masked]>
Date: Tue, 9 Mar 2004 10:54:02 +0000

> binary planar trees of cardinality at most aleph_5 (probably nasty).

 From a computer science point of view, both the first "nice" solution
(finite binary trees) and the second "nice?" solution (possibly
non-finite
binary trees) are canonical, in the sense that the first is the carrier
of the
initial algebra for the endofunctor 1+X^2 on Set,  while the second is
the
carrier of its final coalgebra.

All the best,
Pawel.

---

From: "Vidhyanath Rao" <[email-masked]>
Date: Fri, 12 Mar 2004 08:50:46 -0500

I would like some references to model structures on the category of
toposes/locales (thinking of them as generalized spaces), perhaps even
the category of internal toposes of a given (boolean?) topos. What I
know of is about model structures on the category of simplicial objects
in a topos.

Along the same lines, does it make sense to ask about ``internally
simplicial objects'' in a topos with an NNO (i.e., do such toposes have an
internal category that looks like the category of internally ``finite sets
with linear order and order preserving maps'')?

Nath Rao