mystification and categorification

mystification and categorification

[Stephen Schanuel]

    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

Re: mystification and categorification

[David Yetter]

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.

Re: mystification and categorification

[Vaughan Pratt]

>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

Re: mystification and categorification

[Mike Oliver]

Vaughan Pratt wrote:

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

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.

Re: mystification and categorification

[Steve Vickers]

Vaughan Pratt wrote:

>(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
>

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.

Re: mystification and categorification

[Tom Leinster]

Steve Schanuel wrote:
> 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?)

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

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.

>     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'.

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

Re: mystification and categorification

[Pawel Sobocinski]

On 7 Mar 2004, at 19:43, Tom Leinster wrote:

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

 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.

Quillen model structure of category of toposes/locales?

[Vidhyanath Rao]

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

More Topos questions ala "Conceptual Mathematics"

[Galchin Vasili]

Hello,

1) In the very last chapter (Session 33 "2: Toposes and logic" of "Conceptual Mathematics"  where the authors cover topoi, they define  '=>' for the internal Heyting algebra of Omega:

"Another logical operation is 'implication', which is denoted '=>'. This is also a map Omega x Omega->Omega, defined as the classifying map of the subobject S 'hook' Omega x Omega determined by the all those <alpha, beta> in Omega x Omega such that alpha "subset of" beta."

Starting from "subobject S 'hook" ......" I got totally lost. I am frustrated because I know this is crucial to understanding why Omega is an internal Heyting algebra, so any help would be appreciated. (I am assuming that alpha and beta are subojects of Omega???).

2) In the same Session 33 on pg 350 is a set "rules of logic". These are exactly the axioms for a Heyting algebra, yes?



Regards, Bill Halchin

Re: More Topos questions ala "Conceptual Mathematics"

[Stephen Schanuel]

    Probably it's easiest to try to define implication yourself, and then
you'll see that it is just what 'Conceptual Mathematics' says -- but if you
need more help:

    'Implication' is supposed to be a binary operation on Omega, i.e. a map
from OmegaxOmega to Omega. How can we go about specifying such a map?

    Well, a map from any object X to Omega amounts (by the universal
property) to a subobject of X, so we're looking for a subobject of
OmegaxOmega, i.e. a monomorphism with codomain X=OmegaxOmega. Now how can we
go about specifying a nonomorphism with a given codomain X? Perhaps the
simplest way is to specify two maps with domain X and common codomainY; then
the equalizer of these will do.

    See if you can think of two maps from OmegaxOmega to Omega whose
equalizer seems to capture the intuitive notion of 'implication'. It might
help to start with a simple case, the category of sets, where Omega is just
the two-element set with elements called T (true) and F (false). (If you
have ever seen 'truth tables', you will see that what you are looking for is
also called the 'truth table for implication', but if you haven't seen
these, please ignore this remark.) If you succeed in specifying the pair of
maps, you will have learned much more than you can by reading further; but
if after trying you are still stuck, then read on.

    The desired two maps from OmegaxOmega to Omega are:
(1) projection on the first factor, and
(2) conjunction, which was defined in the paragraph just preceding the one
you're stuck on.

    I hope you managed to find these maps, but even if you didn't, you can
now have fun by looking at the maps conjunction, imlication, negation, etc,
in irreflexive graphs (and other simple toposes) and comparing these with
those in sets; you'll learn why Boolean algebra, so familiar in sets, needs
to be replaced by Heyting algebra in more general toposes.

    Good luck in your studies!

Yours,
Steve Schanuel
----- Original Message -----
From: "Galchin Vasili" <vngalchin@yahoo.com>
To: <categories@mta.ca>
Sent: Wednesday, February 19, 2003 7:16 PM
Subject: categories: More Topos questions ala "Conceptual Mathematics"


>
> Hello,
>
> 1) In the very last chapter (Session 33 "2: Toposes and logic" of
"Conceptual Mathematics"  where the authors cover topoi, they define  '=>'
for the internal Heyting algebra of Omega:
>
> "Another logical operation is 'implication', which is denoted '=>'. This
is also a map Omega x Omega->Omega, defined as the classifying map of the
subobject S 'hook' Omega x Omega determined by the all those <alpha, beta>
in Omega x Omega such that alpha "subset of" beta."
>
> Starting from "subobject S 'hook" ......" I got totally lost. I am
frustrated because I know this is crucial to understanding why Omega is an
internal Heyting algebra, so any help would be appreciated. (I am assuming
that alpha and beta are subojects of Omega???).
>
> 2) In the same Session 33 on pg 350 is a set "rules of logic". These are
exactly the axioms for a Heyting algebra, yes?
>
>
>
> Regards, Bill Halchin
>
>
>
>

Re: More Topos questions ala "Conceptual Mathematics"

[Vaughan Pratt]

>From: Stephen Schanuel
>you'll learn why Boolean algebra, so familiar in sets, needs
>to be replaced by Heyting algebra in more general toposes.

I would expand this beyond Heyting algebras to quantales, residuated monoids,
etc.  See http://boole.stanford.edu/pub/seqconc.pdf for an example of a
situation, namely event structures as a model catering simultaneously to
concerns of branching time and "true" concurrency, that has traditionally
been handled in a Boolean way.  That paper extends event structures to three-
and four-valued logics of behavior.

This particular extension (expansion, augmentation) doesn't generalize the
two-valued Boolean logic of event structures to Heyting algebras.  There are
exactly two three-element idempotent commutative quantales.
Obviously the three-element Heyting algebra is one of them, and this HA
does find application in drawing a distinction between accidental and
causal temporal precedence, a topic Haim Gaifman looked into around 1988.

The other, which isn't a Heyting algebra, is at the core of the notion of
transition as the intermediate state between "ready" and "done," more on
this in the above-cited paper.

This is not to say that there is no topos-theoretic approach to this
extension.  In particular the above paper briefly mentions the presheaf
category Set^FinBip where FinBip is the category of finite bipointed sets,
as a notion of cubical set.  Cubical sets certainly provide one algebraically
attractive model of true concurrency that works roughly the same way as
the one based on this 3-element quantale---both of them entail cubical
structure---but I've been finding the latter a more elementary and natural
tool for working with cubes, at least for my purposes---homologists may
find limitations that I don't seem to run into.  An advantage of Set^FinBip
is that it accommodates cyclic structures (iterative concurrent automata),
whereas the one based on 3' as I've been calling this 3-element quantale
works with acyclic cubical sets, calling for iteration to be unfolded, much
as formal languages "are" unfolded grammars.

(Come to think of it, I don't know anything about the subobject classifier of
Set^FinBip.  If someone has a succinct description of it I'd be very grateful.)

The main point here is that there *is* a logic of behavior that is
close to but not quite intuitionistic, at least not in the strict Heyting
algebra sense.  Furthermore it is not a question of just finding the smallest
Heyting algebra in which the above quantale embeds, since there isn't one that
preserves the ordered monoid structure: a Heyting algebra must have its monoid
unit at the top, which 3' as "the other three-element quantale" doesn't.  So
whatever relationship obtains between the subobject classifier of Set^FinBip
and 3', it's not an ordered-monoid embedding of the latter in the former.

See http://boole.stanford.edu/pub/seqconc.pdf for more details.

Vaughan

re: More Topos questions ala "Conceptual Mathematics"

[Galchin Vasili]

Hello,

   I have been reading up on the Curry-Howard
isomorphism. In the last chapter of "Conceptual
Mathematics" Lawvevre and Schanuel say that the
logical connectives are completely analogous to
categorical operations x, map object and +. Is this an
oblique reference to the Curry-Howard isomorphism?

Regards, Bill Halchin

--- Stephen Schanuel <schanuel@adelphia.net> wrote:
>     Probably it's easiest to try to define
> implication yourself, and then
> you'll see that it is just what 'Conceptual
> Mathematics' says -- but if you
> need more help:
>
>     'Implication' is supposed to be a binary
> operation on Omega, i.e. a map
> from OmegaxOmega to Omega. How can we go about
> specifying such a map?
>
>     Well, a map from any object X to Omega amounts
> (by the universal
> property) to a subobject of X, so we're looking for
> a subobject of
> OmegaxOmega, i.e. a monomorphism with codomain
> X=OmegaxOmega. Now how can we
> go about specifying a nonomorphism with a given
> codomain X? Perhaps the
> simplest way is to specify two maps with domain X
> and common codomainY; then
> the equalizer of these will do.
>
>     See if you can think of two maps from
> OmegaxOmega to Omega whose
> equalizer seems to capture the intuitive notion of
> 'implication'. It might
> help to start with a simple case, the category of
> sets, where Omega is just
> the two-element set with elements called T (true)
> and F (false). (If you
> have ever seen 'truth tables', you will see that
> what you are looking for is
> also called the 'truth table for implication', but
> if you haven't seen
> these, please ignore this remark.) If you succeed in
> specifying the pair of
> maps, you will have learned much more than you can
> by reading further; but
> if after trying you are still stuck, then read on.
>
>     The desired two maps from OmegaxOmega to Omega
> are:
> (1) projection on the first factor, and
> (2) conjunction, which was defined in the paragraph
> just preceding the one
> you're stuck on.
>
>     I hope you managed to find these maps, but even
> if you didn't, you can
> now have fun by looking at the maps conjunction,
> imlication, negation, etc,
> in irreflexive graphs (and other simple toposes) and
> comparing these with
> those in sets; you'll learn why Boolean algebra, so
> familiar in sets, needs
> to be replaced by Heyting algebra in more general
> toposes.
>
>     Good luck in your studies!
>
> Yours,
> Steve Schanuel
> ----- Original Message -----
> From: "Galchin Vasili" <vngalchin@yahoo.com>
> To: <categories@mta.ca>
> Sent: Wednesday, February 19, 2003 7:16 PM
> Subject: categories: More Topos questions ala
> "Conceptual Mathematics"
>
>
> >
> > Hello,
> >
> > 1) In the very last chapter (Session 33 "2:
> Toposes and logic" of
> "Conceptual Mathematics"  where the authors cover
> topoi, they define  '=>'
> for the internal Heyting algebra of Omega:
> >
> > "Another logical operation is 'implication', which
> is denoted '=>'. This
> is also a map Omega x Omega->Omega, defined as the
> classifying map of the
> subobject S 'hook' Omega x Omega determined by the
> all those <alpha, beta>
> in Omega x Omega such that alpha "subset of" beta."
> >
> > Starting from "subobject S 'hook" ......" I got
> totally lost. I am
> frustrated because I know this is crucial to
> understanding why Omega is an
> internal Heyting algebra, so any help would be
> appreciated. (I am assuming
> that alpha and beta are subojects of Omega???).
> >
> > 2) In the same Session 33 on pg 350 is a set
> "rules of logic". These are
> exactly the axioms for a Heyting algebra, yes?
> >
> >
> >
> > Regards, Bill Halchin
> >
> >
> >
> >
>
>


__________________________________
Do you Yahoo!?
Yahoo! Calendar - Free online calendar with sync to Outlook(TM).
http://calendar.yahoo.com