From MAILER-DAEMON Wed Aug 19 13:47:29 2009
Date: 19 Aug 2009 13:47:29 -0300
From: Mail System Internal Data
Subject: DON'T DELETE THIS MESSAGE -- FOLDER INTERNAL DATA
Message-ID: <1250700449@mta.ca>
X-IMAP: 1243871509 0000000124
Status: RO
This text is part of the internal format of your mail folder, and is not
a real message. It is created automatically by the mail system software.
If deleted, important folder data will be lost, and it will be re-created
with the data reset to initial values.
From rrosebru@mta.ca Mon Jun 1 12:48:22 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Mon, 01 Jun 2009 12:48:22 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MB9kI-0004RD-AF
for categories-list@mta.ca; Mon, 01 Jun 2009 12:48:18 -0300
MIME-Version: 1.0
Date: Mon, 01 Jun 2009 16:15:43 +0300
From: Panagis Karazeris
To:
Subject: categories: preprint announcement
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Sender: categories@mta.ca
Precedence: bulk
Reply-To: Panagis Karazeris
Message-Id:
Status: RO
X-Status:
X-Keywords:
X-UID: 1
Dear all,
I would like to announce that the following preprint is available as
http://arxiv.org/abs/0905.4883
as well as from my webpage
www.math.upatras.gr/~pkarazer
Final Coalgebras in Accessible Categories,
by Panagis Karazeris, Apostolos Matzaris and Jiri Velebil
Abstract:
We give conditions on a finitary endofunctor of a finitely accessible
category to admit a final coalgebra. Our conditions always apply to the
case of a finitary endofunctor of a locally finitely presentable (l.f.p.)
category and they bring an explicit construction of the final coalgebra i=
n
this case. On the other hand, there are interesting examples of final
coalgebras beyond the realm of l.f.p. categories to which our results
apply. We rely on ideas developed by Tom Leinster for the study of
self-similar objects in topology.=20
Best regards,
Panagis Karazeris
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Wed Jun 3 11:47:36 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Wed, 03 Jun 2009 11:47:36 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MBrkF-0006y5-Ju
for categories-list@mta.ca; Wed, 03 Jun 2009 11:47:11 -0300
From: Hasse Riemann
To: Category mailing list
Subject: categories: Famous unsolved problems in ordinary category theory
Date: Tue, 2 Jun 2009 16:31:32 +0000
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
Sender: categories@mta.ca
Precedence: bulk
Reply-To: Hasse Riemann
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 2
=20
Hello categorists
=20
I don't know what to make of the silence to my question.
This is the easiest question i have. I can't believe it is so difficult.
It is not like i am asking you to solve the problems.
=20
There must be some important open problems in ordinary category theory.
There are plenty of them in the theory of algebras and
in representation theory=2C so there should be more of them in category the=
ory.
=20
Especially if you broaden the boundaries a bit of what ordinary category th=
eory is.
Take for instance:
model categories=2C
categorical logic=2C
categorical quantization=2C
topos theory-locales-sheaves.
But i had originally pure category theory in mind.
=20
Best regards
Rafael Borowiecki
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Wed Jun 3 11:47:37 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Wed, 03 Jun 2009 11:47:37 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MBrjM-0006rM-Cl
for categories-list@mta.ca; Wed, 03 Jun 2009 11:46:16 -0300
Date: Tue, 2 Jun 2009 11:38:55 +0100 (BST)
From: Dusko Pavlovic
To: Till Mossakowski , categories@mta.ca
Subject: categories: Re: patenting colimits?
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed
Sender: categories@mta.ca
Precedence: bulk
Reply-To: Dusko Pavlovic
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 3
thanks. our tools can be just as freely downloaded, eg
http://www.kestrel.edu/home/projects/pda/
-- dusko
On Tue, 2 Jun 2009, Till Mossakowski wrote:
> Dusko,
>
> let me just notice that we are maintaining a *free software* tool
> that actually is built upon categorical ideas (using Goguen's
> and Burstall's institutions) and that computes colimits
> (there is a menu Edit -> Proofs -> Compute Colimit
>
> http://www.dfki.de/sks/hets
>
> It is published under a free license, so you can freely download
> the binaries, the source, modify the source, and republish your
> improvements under the license.
>
> Best,
> Till
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Wed Jun 3 11:47:37 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Wed, 03 Jun 2009 11:47:37 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MBriJ-0006lD-UV
for categories-list@mta.ca; Wed, 03 Jun 2009 11:45:11 -0300
Date: Tue, 02 Jun 2009 10:51:22 +0200
From: Till Mossakowski
MIME-Version: 1.0
To: Dusko Pavlovic , categories@mta.ca
Subject: categories: Re: patenting colimits?
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Sender: categories@mta.ca
Precedence: bulk
Reply-To: Till Mossakowski
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 4
Dusko,
let me just notice that we are maintaining a *free software* tool
that actually is built upon categorical ideas (using Goguen's
and Burstall's institutions) and that computes colimits
(there is a menu Edit -> Proofs -> Compute Colimit
http://www.dfki.de/sks/hets
It is published under a free license, so you can freely download
the binaries, the source, modify the source, and republish your
improvements under the license.
Best,
Till
Dusko Pavlovic schrieb:
> [sorry, i just noticed this]
>
> On May 26, 2009, at 8:29 PM, Zinovy Diskin wrote:
>
>> impressive examples, such as the extremely successful Eclipse project
>> http://www.eclipse.org, (btw, Eclipse is partly based on categorical
>> ideas that engineers developed/reinvented from scratch).
>
> i designed two tools which people who built them built on top of
> eclipse, and i must admint that i managed to completely miss those
> categorical ideas. eclipse is very handy, but some simple class
> hierarchies often become unrecognizable in its straitjacket. i am
> probably not the only one who would be curious to learn more about
> category theory behind eclipse :)
>
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Wed Jun 3 11:48:59 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Wed, 03 Jun 2009 11:48:59 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MBrlu-0007A8-Lz
for categories-list@mta.ca; Wed, 03 Jun 2009 11:48:54 -0300
MIME-Version: 1.0
Date: Wed, 3 Jun 2009 13:10:21 +0200
Subject: categories: Decidability of the theory of a monad
From: Andrej Bauer
To: categories list
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit
Sender: categories@mta.ca
Precedence: bulk
Reply-To: Andrej Bauer
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 5
Consider the theory of a monad, i.e., the axioms are those of a
category and a monad given as a triple: an operation T on objects, for
each object A a morphism eta_A : A -> T A, and an operation lift_{A,B}
which maps morphisms f : A -> T B to lift f : T A -> T B. Concretely,
the axioms are (where lift f is written f* and composition is
juxtaposition):
id f = f
f id = f
(f g) h = f (g h)
eta* = id
f* eta = f
(f* g)* = f* g*
Presumably, the equational theory (with partial operations) of such a
triple is decidable. Is this known? If we ignore the types and
partiality, we can attempt to turn the above equations into a
confluent terminating rewrite system using the Knuth-Bendix algorithm,
but it gets stuck (on various orderings I tried).
A more categorical way of asking the same question is: what is a
concrete description of the free "monad on a category" (is this the
same as "free monad" on "free category"?).
With kind regards,
Andrej
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Wed Jun 3 11:49:31 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Wed, 03 Jun 2009 11:49:31 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MBrmR-0007E1-Oq
for categories-list@mta.ca; Wed, 03 Jun 2009 11:49:27 -0300
Date: Wed, 3 Jun 2009 15:41:54 +0100 (BST)
From: Bob Coecke
To: categories@mta.ca
Subject: categories: 3 year Lectureship at Oxford in Categories/Quantum
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed
Sender: categories@mta.ca
Precedence: bulk
Reply-To: Bob Coecke
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 6
Oxford University Computing Laboratory has a vacancy for a fixed-term 3
year Departmental Lectureship starting October 1st and ending September
30th 2012. The successful candidate will be expected to lecture two
courses per year, namely:
* Categories, Proofs and Processes
http://web.comlab.ox.ac.uk/teaching/courses/20082009/catsproofsprocs/
* Quantum Computer Science
http://web.comlab.ox.ac.uk/teaching/courses/20082009/quantum/
Each of these courses involves twenty hours of lecturing per year.
He will carry out research, including supervision, in a group under
joint direction of Samson Abramsky and Bob Coecke:
http://web.comlab.ox.ac.uk/activities/quantum/
More details are available form:
http://www.comlab.ox.ac.uk/news/documents/CatsQCSLectureship-fps.pdf
and you can contact Samson Abramsky and Bob
Coecke .
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Thu Jun 4 21:09:33 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Thu, 04 Jun 2009 21:09:33 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MCMzl-0006Up-7L
for categories-list@mta.ca; Thu, 04 Jun 2009 21:09:17 -0300
MIME-Version: 1.0
Date: Thu, 4 Jun 2009 00:08:28 +0200
Subject: categories: Re: Decidability of the theory of a monad
From: Andrej Bauer
To: categories list
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit
Sender: categories@mta.ca
Precedence: bulk
Reply-To: Andrej Bauer
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 7
I thank eveyone who answered my question so quickly. For reference I
post a summary of the answers.
Bill Lawvere answered that "the theory of a monad is just that of
ordinal addition of 1 on the augmented simplicial category Delta
considered as a (non-commutative) monoidal category wrt ordinal
addition." A relevant reference in this regard is his "Ordinal Sums
and Equational Doctrines" which was part of the Zurich Triples Book,
available online as TAC Reprints 18.
Similarly, Jaap van Oosten pointed out that the free "monad on a
category" on one generator is the simplicial category \Delta (nonempty
finite ordinals and monotone functions).
It follows from these observations that the theory of a monad is decidable.
Todd Wilson kindly pointed me to a thesis by Wolfgang Gehrke, see
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.7087 ,
which contains a complete set of rewrite rules (page 40, Proposition
20) for the theory of a monad:
id f ==> f
f id ==> f
(f g) h ==> f (g h)
eta* ==> id
f* eta ==> f
f* g* ==> (f* g)*
f* (eta g) ==> f g
f* (g* h) ==> (f* g)* h
The last two rules are extra, compared to the original equations. So
the next time you wonder whether an equation holds of a general monad,
just use the above rewrite rules on both sides of the equation.
With kind regards,
Andrej
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Thu Jun 4 21:09:33 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Thu, 04 Jun 2009 21:09:33 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MCMzA-0006S7-Tt
for categories-list@mta.ca; Thu, 04 Jun 2009 21:08:40 -0300
From: "Ronnie Brown"
To: "Hasse Riemann" ,
Subject: categories: Re: Famous unsolved problems in ordinary category theory
Date: Wed, 3 Jun 2009 21:30:17 +0100
MIME-Version: 1.0
Content-Type: text/plain;format=flowed;charset="iso-8859-1";reply-type=original
Content-Transfer-Encoding: 7bit
Sender: categories@mta.ca
Precedence: bulk
Reply-To: "Ronnie Brown"
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 8
In reply to Hasse Riemann's question (see below):
I remember being asked this kind of question at a Topology conference in
Baku in 1987. It is worth discussing the background to this, as someone who
has never gone for a `famous problem', but found myself trying to develop
some mathematics to express some basic intuitions.
Saul Ulam remarked to me in 1964 at my first international conference
(Syracuse, Sicily) that a young person may feel the most ambitious thing to
do is to tackle a famous problem; but this may distract that person from
developing the mathematics most appropriate to them. It was interesting that
this remark came from someone as good as Ulam!
G.-C. Rota writes in `Indiscrete thoughts' (1997):
What can you prove with exterior algebra that you cannot prove without it?"
Whenever you hear this question raised about some new piece of mathematics,
be assured that you are likely to be in the presence of something important.
In my time, I have heard it repeated for random variables, Laurent Schwartz'
theory of distributions, ideles and Grothendieck's schemes, to mention only
a few. A proper retort might be: "You are right. There is nothing in
yesterday's mathematics that could not also be proved without it. Exterior
algebra is not meant to prove old facts, it is meant to disclose a new
world. Disclosing new worlds is as worthwhile a mathematical enterprise as
proving old conjectures. "
It is like the old military question: do you make a frontal attack; or find
a way of rendering the obstacle obsolete?
I was early seduced (see my first two papers) by the idea of looking for
questions satisfying 3 criteria:
1) no-one had previously asked it;
2) the question was technically easy to answer;
3) the answer was important.
Usually it has been 2) which failed!
Of course you do not find such questions where everyone is looking! It could
be interesting to investigate how such questions arise, perhaps by pushing a
point of view as far as it will go, or seeing a new analogy.
"If at first, the idea is not absurd, then there is no hope for it." Albert
Einstein
It could be interesting to investigate historically:
if (let us suppose) category theory has advanced without a fund of famous
open problems, how then has it advanced?
One aim of mathematics is understanding, making difficult things easy,
seeing why something is true. Thus improved exposition is an important part
of the progress of mathematics (even if this is ignored by Research
Assessment Exercises). R. Bott said to me (1958) that Grothendieck was
prepared to work very hard to make something tautological. By contrast, a
famous algebraic topologist replied to a question of mine about his graduate
text by asking: `Is the function not continuous?' He never gave me a proof!
And I never found it! (Actually the function was not well defined, but that
I could fix!)
Grothendieck wrote to me in 1982: `The introduction of the cipher 0 or the
group concept was general nonsense too, and mathematics was more or less
stagnating for thousands of years because nobody was around to take such
childish steps ...'. See also
http://www.bangor.ac.uk/~mas010/Grothendieck-speculation.html
The point I am trying to make is that the question on `open problems' raises
issues on the nature of, on professionalism in, and so on the methodology
of, mathematics. It is a good question to start with.
Hope that helps.
Ronnie Brown
----- Original Message -----
From: "Hasse Riemann"
To: "Category mailing list"
Sent: Tuesday, June 02, 2009 5:31 PM
Subject: categories: Famous unsolved problems in ordinary category theory
Hello categorists
I don't know what to make of the silence to my question.
This is the easiest question i have. I can't believe it is so difficult.
It is not like i am asking you to solve the problems.
There must be some important open problems in ordinary category theory.
There are plenty of them in the theory of algebras and
in representation theory, so there should be more of them in category
theory.
Especially if you broaden the boundaries a bit of what ordinary category
theory is.
Take for instance:
model categories,
categorical logic,
categorical quantization,
topos theory-locales-sheaves.
But i had originally pure category theory in mind.
Best regards
Rafael Borowiecki
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
--------------------------------------------------------------------------------
No virus found in this incoming message.
Checked by AVG - www.avg.com
Version: 8.5.339 / Virus Database: 270.12.51/2151 - Release Date: 06/02/09
17:53:00
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Thu Jun 4 21:09:33 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Thu, 04 Jun 2009 21:09:33 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MCMxT-0006Ni-9H
for categories-list@mta.ca; Thu, 04 Jun 2009 21:06:55 -0300
MIME-Version: 1.0
Date: Wed, 3 Jun 2009 11:45:09 -0500
Subject: categories: Re: Famous unsolved problems in ordinary category theory
From: Michael Shulman
To: Hasse Riemann ,
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Sender: categories@mta.ca
Precedence: bulk
Reply-To: Michael Shulman
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 9
Probably people are going to jump on me for saying this, but it seems to
me that category theory is different from much of mathematics in that
often the difficulty is in the definitions rather than the theorems, and
in the questions rather than the answers. Thus, there are probably many
unsolved problems in category theory, but we don't know what they are
yet, because figuring out what they are is the main aspect of them
that is unsolved. (-:
Mike
On Tue, Jun 2, 2009 at 11:31 AM, Hasse Riemann wrote:
>
>
>
> Hello categorists
>
> I don't know what to make of the silence to my question.
> This is the easiest question i have. I can't believe it is so difficult.
> It is not like i am asking you to solve the problems.
>
> There must be some important open problems in ordinary category theory.
> There are plenty of them in the theory of algebras and
> in representation theory, so there should be more of them in category theory.
>
> Especially if you broaden the boundaries a bit of what ordinary category theory is.
> Take for instance:
> model categories,
> categorical logic,
> categorical quantization,
> topos theory-locales-sheaves.
> But i had originally pure category theory in mind.
>
> Best regards
> Rafael Borowiecki
>
>
> [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
>
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Thu Jun 4 21:10:14 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Thu, 04 Jun 2009 21:10:14 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MCN0d-0006YW-2I
for categories-list@mta.ca; Thu, 04 Jun 2009 21:10:11 -0300
Date: Thu, 04 Jun 2009 08:29:11 +1000
Subject: categories: Re: Decidability of the theory of a monad
From: Steve Lack
To: Andrej Bauer ,
Mime-version: 1.0
Content-type: text/plain; charset="US-ASCII"
Content-transfer-encoding: 7bit
Sender: categories@mta.ca
Precedence: bulk
Reply-To: Steve Lack
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 10
Dear Andrej,
The free monad on a category has a well-known simple concrete description.
Let Ordf be the category of finite ordinals and order-preserving maps.
-->
0 --> 1 <-- 2 ...
-->
(This is sometimes called the algebraicist's simplicial category - it
contains the topologist's simplicial category as the full subcategory of
non-empty finite ordinals. Ordf is simply called Delta in Categories for the
Working Mathematician.) Ordinal sum makes Ordf into a strict monoidal
category. The object 1 is a monoid in this monoidal category, and in fact
is the "free monoid in a monoidal category", in the sense that for any
strict monoidal category C, there is a bijection between monoids in C and
strict monoidal functors from Ordf to C. (There is also a non-strict version
of this fact.)
The free "category with a monad" on a category A is the Ordf x A, with monad
having endofunctor part (n,a) |-> (n+1,a), with the obvious multiplication.
More generally, the monoidal category Ordf can be regarded as a one-object
2-category mnd, and 2-functors mnd-->K for a 2-category K, are in bijection
with monads in K. Freely adding a monad to an object of K can be seen as
left Kan extension along the unique 2-functor 1-->mnd.
Regards,
Steve Lack.
On 3/06/09 9:10 PM, "Andrej Bauer" wrote:
> Consider the theory of a monad, i.e., the axioms are those of a
> category and a monad given as a triple: an operation T on objects, for
> each object A a morphism eta_A : A -> T A, and an operation lift_{A,B}
> which maps morphisms f : A -> T B to lift f : T A -> T B. Concretely,
> the axioms are (where lift f is written f* and composition is
> juxtaposition):
>
> id f = f
> f id = f
> (f g) h = f (g h)
> eta* = id
> f* eta = f
> (f* g)* = f* g*
>
> Presumably, the equational theory (with partial operations) of such a
> triple is decidable. Is this known? If we ignore the types and
> partiality, we can attempt to turn the above equations into a
> confluent terminating rewrite system using the Knuth-Bendix algorithm,
> but it gets stuck (on various orderings I tried).
>
> A more categorical way of asking the same question is: what is a
> concrete description of the free "monad on a category" (is this the
> same as "free monad" on "free category"?).
>
> With kind regards,
>
> Andrej
>
>
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Thu Jun 4 21:11:34 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Thu, 04 Jun 2009 21:11:34 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MCN1u-0006eI-DI
for categories-list@mta.ca; Thu, 04 Jun 2009 21:11:30 -0300
Date: Thu, 04 Jun 2009 11:52:16 +0200
From: Sergey Goncharov
MIME-Version: 1.0
To: categories@mta.ca
Subject: categories: Re: Decidability of the theory of a monad
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: quoted-printable
Sender: categories@mta.ca
Precedence: bulk
Reply-To: Sergey Goncharov
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 11
Hi!
not touching the partiality issue the answer to the question about=20
decidability is positive. Decidability follows from the results, proved=20
in our paper "Kleene Monads: Handling Iteration in a Framework of=20
Generic Effects", accepted for the upcoming CALCO conference. The paper=20
should be soon available on my homepage:=20
http://www.informatik.uni-bremen.de/~sergey/papers_e.htm
It does contain a confluent and strongly normalising rewrite system but=20
the proof details will show up (hopefully) only in the journal version.=20
The proofs are also included into my PhD thesis, which is under=20
development and thus still unpublished but in case of interest I can=20
make available some parts of it containing the proofs under discussion.
Best regards,
--------------------------------------
Sergey Goncharov
Junior Researcher
DFKI Bremen=09
Safe and Secure Cognitive Systems
Cartesium, Enrique-Schmidt-Str. 5
D-28359 Bremen
phone: +49-421-218-64276
Fax: +49-421-218-9864276
mail: Sergey.Goncharov@dfki.de
www.dfki.de/sks/staff/sergey
--------------------------------------
-------------------------------------------------------------
Deutsches Forschungszentrum f=C3=BCr K=C3=BCnstliche Intelligenz GmbH
Firmensitz: Trippstadter Strasse 122, D-67663 Kaiserslautern
Gesch=C3=A4ftsf=C3=BChrung:
Prof. Dr. Dr. h.c. mult. Wolfgang Wahlster (Vorsitzender)
Dr. Walter Olthoff
Vorsitzender des Aufsichtsrats:
Prof. Dr. h.c. Hans A. Aukes
Amtsgericht Kaiserslautern, HRB 2313
-------------------------------------------------------------
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Thu Jun 4 21:12:12 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Thu, 04 Jun 2009 21:12:12 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MCN2W-0006hQ-88
for categories-list@mta.ca; Thu, 04 Jun 2009 21:12:08 -0300
Date: Thu, 04 Jun 2009 11:59:12 +0100
From: Steve Vickers
MIME-Version: 1.0
To: Andrej Bauer ,
Subject: categories: Re: Decidability of the theory of a monad
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit
Sender: categories@mta.ca
Precedence: bulk
Reply-To: Steve Vickers
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 12
Dear Andrej,
It seems to me that the monad-on-a-category freely generated by one
object should be the simplicial category Delta, following from the facts
that Delta contains the universal monoid and a monad on C is a monoid in
C^C - see Mac Lane Cats for Working Mathematician Section VII.5, VII.6.
The object n of Delta will correspond to T^n(X) where T is the (functor
for the) monad and X the generating object. If I've got that right then
I would presume it's already known and proved carefully somewhere.
After that, the monad-on-a-category freely generated by a category C
would seem to be CxDelta. (Object (X,n) represents T^n(X), morphism
(f,s): (X,m) -> (Y,n) corresponds to T^m(f);s(Y): T^m(X) -> T^m(Y) ->
T^n(Y) and using naturality of T to deduce that s(Y);T^n(g) =
T^m(g);s(Z) so the f's can always be shunted to the left.) Again, if
I've got that right then it wouldn't surprise me to find it's already known.
This would suggest that C |-> CxDelta is a monad on Cat. Then a monad on
C is a structure morphism CxDelta -> C, i.e. Delta -> C^C with
appropriate properties, which looks like a monoid in C^C, which we knew
already.
I don't know Knuth-Bendix well enough to understand the issues there.
But since you mention various orderings, that reminds me of Freyd's
trick in "essentially algebraic" presentations of these cartesian
theories. (Amongst theories of partial operators, it is the cartesian
theories that have good universal algebraic properties.) That involves
ordering the operators so that, for each one, its domain of definition
is defined by equations involving "earlier" operators. (Ultimately that
comes down to total operators, for which no equations are needed.) Then
the equations s = t are understood in the sense "if s and t are both
defined, then they are equal". I don't know if that can be accommodated
in Knuth-Bendix as it stands. In particular, I don't know how amenable
K-B is to incorporating conditional rewrites. Conditional equations seem
inevitable in cartesian theories; the essentially algebraic formulation
reduces them to definedness explicitly conditional on equations, and
equations implicitly conditional on definedness. You might want to look
at my paper with Palmgren, which unifies them by identifying definedness
with self-equality.
You ask whether a free "monad on a category" is the same as a "free
monad" on "free category". Of course, in using the word "free" one ought
to be careful what kind of structure these are free over, but generally
speaking if the forgetful functors compose then so will their left
adjoints, the free functors.
Best wishes,
Steve.
Andrej Bauer wrote:
> Consider the theory of a monad, i.e., the axioms are those of a
> category and a monad given as a triple: an operation T on objects, for
> each object A a morphism eta_A : A -> T A, and an operation lift_{A,B}
> which maps morphisms f : A -> T B to lift f : T A -> T B. Concretely,
> the axioms are (where lift f is written f* and composition is
> juxtaposition):
>
> id f = f
> f id = f
> (f g) h = f (g h)
> eta* = id
> f* eta = f
> (f* g)* = f* g*
>
> Presumably, the equational theory (with partial operations) of such a
> triple is decidable. Is this known? If we ignore the types and
> partiality, we can attempt to turn the above equations into a
> confluent terminating rewrite system using the Knuth-Bendix algorithm,
> but it gets stuck (on various orderings I tried).
>
> A more categorical way of asking the same question is: what is a
> concrete description of the free "monad on a category" (is this the
> same as "free monad" on "free category"?).
>
> With kind regards,
>
> Andrej
>
>
> [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Fri Jun 5 14:04:59 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Fri, 05 Jun 2009 14:04:59 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MCcqB-0007Xq-T1
for categories-list@mta.ca; Fri, 05 Jun 2009 14:04:27 -0300
Date: Thu, 4 Jun 2009 21:53:10 -0400
From: tholen@mathstat.yorku.ca
To: Michael Shulman , categories@mta.ca,
Subject: categories: Re: Famous unsolved problems in ordinary category theory
MIME-Version: 1.0
Content-Type: text/plain;charset=ISO-8859-1; format="flowed"
Content-Disposition: inline
Content-Transfer-Encoding: 7bit
Sender: categories@mta.ca
Precedence: bulk
Reply-To: tholen@mathstat.yorku.ca
Message-Id:
Status: RO
X-Status:
X-Keywords:
X-UID: 13
Finding the "right" questions and notions is certainly a prominent
theme in category theory, perhaps more prominently than in other
fields. Still, just like in other fields, solving open problems was
always part of the agenda. For example, half a century ago people asked
whether every "standard construction" (=monad) is induced by an
adjunction, and it took a few years to have two interesting answers.
And there is ceratinly a string of examples leading all the way to
today.
I don't know whether there are any >famous< unsolved problems in
ordinary category theory, but there are certainly non-trivial
questions. Here is one that we formulated in an article with Reinhard
B"orger (Can. J. Math 42 (1990) 213-229) two decades ago:
A category A is total (Street-Walters) if its Yoneda embedding A --->
Set^{A^{op}} has a left adjoint. Then
1. A has small colimits, and
2. any functor A-->B that preserves all existing colimits of A has a
right adjoint.
Do properties 1 and 2 imply totality for A?
I must admit that, after formulating the question we never considered
it again, so there may well be a known or quick answer. So don't hold
back please, especially since I plan to incorporate several questions
of this type in my CT09 talk.
Walter.
Quoting Michael Shulman :
> Probably people are going to jump on me for saying this, but it seems to
> me that category theory is different from much of mathematics in that
> often the difficulty is in the definitions rather than the theorems, and
> in the questions rather than the answers. Thus, there are probably many
> unsolved problems in category theory, but we don't know what they are
> yet, because figuring out what they are is the main aspect of them
> that is unsolved. (-:
>
> Mike
>
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Fri Jun 5 14:04:59 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Fri, 05 Jun 2009 14:04:59 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MCcpH-0007Tv-Vc
for categories-list@mta.ca; Fri, 05 Jun 2009 14:03:32 -0300
From: Hasse Riemann
To: Category mailing list
Subject: categories: unsolved problems
Date: Fri, 5 Jun 2009 01:25:12 +0000
MIME-Version: 1.0
Content-Type: text/plain; charset="windows-1256"
Content-Transfer-Encoding: quoted-printable
Sender: categories@mta.ca
Precedence: bulk
Reply-To: Hasse Riemann
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 14
=20
Hello categorists
=20
To those who have replied on my question and others.
=20
First i want to thank for the suggestions of problems.
=20
Since i am new here some people assume that i seek a problem to solve so =
i can quickly become famous.
I am in fact much more interested in the structure and foundation of math=
ematics than solving
math problems. I just felt i should know these problems since they are fa=
mous, but almost none came to mind.
=20
A reason for this is that the proofs i have seen have mostly been "not wa=
ter tight", they miss some things (mostly in the logic).
And, they are not spelled out in full but are very "cut down" in their ar=
guments. This makes them too time
consuming to follow. I don't want to read a proof to recreate half of it =
but to understand why something is true.
=20
"A mathematical theory is not to be considered complete until you have ma=
de it so clear that you can explain it to the first man whom you meet on =
the street" -David Hilbert
=20
I argue that the same is true for proofs. Something to think about next t=
ime you write a proof.
=20
In Dyson Freemans terminology i am a bird and not a frog. As a bird i mus=
t say that it is sad that about 90% of mathematicians are frogs. This giv=
e an inbalance in mathematics.
=20
To answer Michael Shulman:
Yes, there is something different about category theory. It is at the top=
of mathematics. A perfect place for a bird :)
=20
Now to my question.
=20
After some intensive work and help from people on the mailing list i have=
found
some problems that are interesting in ordinary category theory :)
=20
You just have to learn to see them. Some won't be stated even as problems=
to solve.
=20
To illustrate my point:
How many categories of n objects are there up to categorical equivalence =
for n a natural number?
If it can not be given directly, can it be expressed by other counting fu=
nctions?
Maby the pattern is easier than that for groups.
=20
A simplified version of the problem is to count only finite categories wi=
th at most 1 morphism between any objects.
This suggests the NC(r,s)-problem:
What is the number of categories with r objects and at most s morphisms (=
in one direction) between any two objects.
=20
Specialized versions of these are to count model categories, toposes (def=
ined as categories and not as 2-categories),...
Correct me if it is not so, but i don't know of any theorem that model ca=
tegories or toposes must be infinite.
=20
Another example first stated by John Baez that i call the no-go quantizat=
ion conjecture:
There is no functor from the symplectic category (symplectic manifolds an=
d symplectomorphisms) to the Hilbert category (Hilbert spaces and unitary=
operators) that preserves positivity. I.e. a one-parameter group of symp=
lectic transformations generated by a positive Hamiltonian is mapped to a=
one-parameter group of unitary operators with a positive generator.
=20
That maby helps to find the problems. Not that i am trying to popularize =
them.
If you know some you can still e-mail them to me.
=20
Now from the question to the mysterious Hasse Riemann!
=20
It seems that people wonder about me so here i go.
This is written from a 15 year old gymnasium account from the time of the=
beginning of internet.
Bernhard Riemann was my hero then because of riemannian geometry and riem=
ann surfaces.
Actually i have still not managed to replace Riemann!
Hasse is just a name that i think fits me more than Rafael.
Since everyone i e-mail knows me by this pseudo i have decided not to cha=
nge it.
=20
It took me 20 years of studying mathematics to find category theory.
It is a long time but it was hardly wasted time.
I actually went into category theory 3 times before (not so deep), but no=
t until this fourth time
i understood what category theory really is and that it is precisely what=
i was looking for :)
,and hence decided to stay here for a long while.
The first year in category theory went with a blazing speed.
Now, a half year after that i have more questions than facts.
I happen to be seated in Stockholm. It is not a bad place but there are n=
o category theorists in Sweden!
Hence i'm counting on you people.
=20
Best regards
Rafael Borowiecki
=20
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Fri Jun 5 14:05:06 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Fri, 05 Jun 2009 14:05:06 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MCcql-0007an-Kt
for categories-list@mta.ca; Fri, 05 Jun 2009 14:05:03 -0300
From: Hasse Riemann
To: Category mailing list
Subject: categories: Re: Famous unsolved problems in ordinary category theory
Date: Fri, 5 Jun 2009 02:42:52 +0000
MIME-Version: 1.0
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
Sender: categories@mta.ca
Precedence: bulk
Reply-To: Hasse Riemann
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 15
=20
Dear Ronnie
=20
This is what stuck with me from the e-mail
=20
> One aim of mathematics is understanding=2C making difficult things easy=
=2C
> seeing why something is true. Thus improved exposition is an important pa=
rt
> of the progress of mathematics (even if this is ignored by Research
> Assessment Exercises).=20
=20
Indeed they don't teach you this at the university=2C but somehow i always =
knew it.
It was obvious from the start=2C then i had to resist everyone trying to te=
ll me otherwise.
I am glad that there are other who see this as well.
=20
> Grothendieck wrote to me in 1982: `The introduction of the cipher 0 or th=
e
> group concept was general nonsense too=2C and mathematics was more or les=
s
> stagnating for thousands of years because nobody was around to take such
> childish steps ...'.
=20
I like this quote since i like structuralizing mathematics.
Something to think about if you want to take the next step.
Fill in the void with a precise mathematical void.
=20
Best regards
Rafael Borowiecki
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Fri Jun 5 14:06:13 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Fri, 05 Jun 2009 14:06:13 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MCcrp-0007gs-DY
for categories-list@mta.ca; Fri, 05 Jun 2009 14:06:09 -0300
Date: Thu, 4 Jun 2009 22:54:45 -0400
From: John Iskra
MIME-Version: 1.0
To: Ronnie Brown
Subject: categories: Re: Famous unsolved problems in ordinary category theory
Content-Type: text/plain; charset="ISO-8859-1"; format=flowed
Content-Transfer-Encoding: 7bit
Sender: categories@mta.ca
Precedence: bulk
Reply-To: John Iskra
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 16
One of my favorite quotes:
The question you raise ``how can such a formulation lead to
computations'' doesn't bother me in the least! Throughout my whole life
as a mathematician, the possibility of making explicit, elegant
computations has always come out by itself, as a byproduct of a thorough
conceptual understanding of what was going on. Thus I never bothered
about whether what would come out would be suitable for this or that,
but just tried to understand -- and it always turned out that
understanding was all that mattered.
A. Grothendieck
Raoul Bott reinforced this in a talk I had the privilige to hear back in
98. He said that mathematics, done well, never required the placing of
your oar in the water (he probably put it better than that...). The
idea I think is that if you continually ask and answer the questions
that occur to you, and, thus, gain understanding, then you will
inevitably make progress. And that is what matters, really. So often
the person credited with solving a 'famous' problem only takes the final
step in a hard journey of a thousand miles made by a thousand others.
Glory and fame - such as it is in the world of mathematics - are nice,
but they are not, in the end, mathematics. I think it is of high
importance to avoid confusing them.
John Iskra
Ronnie Brown wrote:
> In reply to Hasse Riemann's question (see below):
>
> I remember being asked this kind of question at a Topology conference in
> Baku in 1987. It is worth discussing the background to this, as someone who
> has never gone for a `famous problem', but found myself trying to develop
> some mathematics to express some basic intuitions.
>
> Saul Ulam remarked to me in 1964 at my first international conference
> (Syracuse, Sicily) that a young person may feel the most ambitious thing to
> do is to tackle a famous problem; but this may distract that person from
> developing the mathematics most appropriate to them. It was interesting that
> this remark came from someone as good as Ulam!
>
...
>
>
>
>
>
>
>
> ----- Original Message -----
> From: "Hasse Riemann"
> To: "Category mailing list"
> Sent: Tuesday, June 02, 2009 5:31 PM
> Subject: categories: Famous unsolved problems in ordinary category theory
>
>
>
>
>
> Hello categorists
>
> I don't know what to make of the silence to my question.
> This is the easiest question i have. I can't believe it is so difficult.
> It is not like i am asking you to solve the problems.
>
> There must be some important open problems in ordinary category theory.
> There are plenty of them in the theory of algebras and
> in representation theory, so there should be more of them in category
> theory.
>
> Especially if you broaden the boundaries a bit of what ordinary category
> theory is.
> Take for instance:
> model categories,
> categorical logic,
> categorical quantization,
> topos theory-locales-sheaves.
> But i had originally pure category theory in mind.
>
> Best regards
> Rafael Borowiecki
>
>
> [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
>
>
> --------------------------------------------------------------------------------
>
>
>
> No virus found in this incoming message.
> Checked by AVG - www.avg.com
> Version: 8.5.339 / Virus Database: 270.12.51/2151 - Release Date: 06/02/09
> 17:53:00
>
>
>
> [For admin and other information see: http://www.mta.ca/~cat-dist/ ]
> .
>
>
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Fri Jun 5 14:06:49 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Fri, 05 Jun 2009 14:06:49 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MCcsQ-0007kj-A1
for categories-list@mta.ca; Fri, 05 Jun 2009 14:06:46 -0300
MIME-Version: 1.0
Date: Thu, 4 Jun 2009 21:10:14 -0700
Subject: categories: Famous unsolved problems in ordinary category theory
From: John Baez
To: categories
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit
Sender: categories@mta.ca
Precedence: bulk
Reply-To: John Baez
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 17
Rafael Borowiecki wrote:
> I don't know what to make of the silence to my question.
> This is the easiest question i have. I can't believe it is so difficult.
> It is not like i am asking you to solve the problems.
>
> There must be some important open problems in ordinary category theory.
I think the reason for the silence is that category theory is a bit
different than other branches of mathematics. Other branches of mathematics
get very excited about patterns that may exist, but may not. So when
mathematicians hear the phrase "famous unsolved problems", that's the sort
of thing that comes to mind: for example, Goldbach's conjecture, the twin
prime conjecture, the Riemann hypothesis or the Hodge conjecture.
On the other hand, category theorists tend to get excited about taking
already partially understood patterns in mathematics and making them very
clear. So, the most important open problems often aren't of the form "Is
this statement true or false?" Instead, they tend to be a bit more
open-ended, like "Develop a workable theory of n-categories." So, they
don't have names.
I've tried to encourage people to work on n-categories by emphasizing five
"hypotheses": the homotopy hypothesis, the stabilization hypothesis, the
cobordism hypothesis, the tangle hypothesis, and the generalized tangle
hypothesis. I didn't want to call them "conjectures", because they're a bit
open-ended. But they're precise enough that someone can claim to have
proved one, and people can probably agree on whether this has occurred. For
example, Jacob Lurie claims to have proved the cobordism hypothesis:
http://arxiv.org/abs/0905.0465
http://lab54.ma.utexas.edu:8080/video/lurie.html
and when he provides the full details, people should be able to decide if he
has.
Best,
jb
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Fri Jun 5 14:08:44 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Fri, 05 Jun 2009 14:08:44 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MCcuF-0000CY-HN
for categories-list@mta.ca; Fri, 05 Jun 2009 14:08:39 -0300
Mime-Version: 1.0 (Apple Message framework v624)
Content-Type: text/plain; charset=US-ASCII; format=flowed
Content-Transfer-Encoding: 7bit
From: Paul Taylor
Subject: categories: Famous unsolved problems in ordinary category theory
Date: Fri, 5 Jun 2009 09:41:32 +0100
To: Categories list
Sender: categories@mta.ca
Precedence: bulk
Reply-To: Paul Taylor
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 18
Rafael Borowiecki, under the alias Hasse Riemann, asked,
> Are there any famous unsolved problems in category theory?
Ronnie Brown's posting in response to this is a classic, and
deserves to be printed out and pinned up in every graduate
student's office! I particularly like the military analogy
with the choice between a frontal assault and making the
obstacle obsolete. The following point is especially important:
> I was early seduced (see my first two papers) by the idea of
> looking for questions satisfying 3 criteria:
> 1) no-one had previously asked it;
> 2) the question was technically easy to answer;
> 3) the answer was important.
> **** Usually it has been 2) which failed! ****
I sent (a version of) the following reply to "categories" when
Rafael first asked the question, but then asked Bob to withdraw
it as I thought I could write it better. I put off doing so
because other topics were under discussion, but by his posting
Ronnie has obliged me to send it, since otherwise I would just
be a chicken.
So here goes:
Do I hear taunts of "do you have a Fields Medal?"?
These are a bit like those of "do you have a girlfriend?".
Well, no, I admit it. I don't. I have a boyfriend (Richard), and
some of you have met him. If you bear with me, you will see that
this is not a completely frivolous answer, even though it is a
personal one.
My point is that there are analogies between being a gay man and
being a conceptual--constructive mathematician:
- They both involve long periods of self-doubt and pretence in the
face of real and perceived discrimation. This is very much still
real in the mathematical case, as evidenced by that fact that
categorists and consructivists are largely to be found in
computer science departments, excluded from mathematics in case
they might corrupt the youth.
- The result of this is a significantly delayed adolescence --
I have met gay men going through adolescence in the 50s or 70s.
- Finally, there is pride in being who you are, and the recognition
of "Honi soit qui mal y pense" -- that it is the people who think
ill of it that have the problem. In the words of a song from
"La Cage aux Folles" that is known as the "sweet potato song",
"I yam what I yam!".
Before I came out as a categorist, I pretended to be interested
in difficult puzzles, I was in the British team in the
International Mathematical Olympiad in 1979, but didn't do very
well. I started a magazine called QARCH, whose total output
in 30 years amounts to less than one of my papers now.
I was taught as an undergraduate by the Hungarian analyst and
graph theorist Bela Bollobas. He set problems for first year
students problems that took three weeks to solve, if at all.
(Bela is a mathematician of considerable stature -- so great that
it took me five years to notice that he is 10cm shorter than me --
and I remember him with great affection, in case he gets to read this.)
However, I hope that Bela (along with Andrej Bauer, Imre Leader and
Dorette Pronk, who help organise IMO things in Slovenia, Britain and
Canada nowadays), will forgive me if I say that there is something
fundamentally unsatisfying about IMO problems. Once you have the
solution, that is it. They are like crosswords or jigsaws or sudoku.
After that I had my delayed adolescence (with an unsuitable
boyfriend). I studied continuous posets instead of algebraic
ones and categories instead of posets, just to show that I could.
Somebody should have told me to get a proper job as a programmer,
but they didn't have the guts to say it to me. (If graduate
students ask me for advice nowadays, I do tell them to get proper
jobs, and not surprisingly they (mis)interpret this personally.)
Long after this, the first paper on Abstract Stone Duality was
published on my 40th birthday, more or less. According to
G H Hardy's depressing "Mathematician's Apology", and to the rules
for getting a Fields Medal, I was officially finished as a
mathematician. But it is pretty clear that I have been doing
my best mathematics during my fifth decade. On the other hand,
all of those gratuitously difficult problems had gone into the mix.
Before I return to the question. please refer to number 6 in
en.wikipedia.org/wiki/Hilbert's_problems
which asks for the axiomatisation of physics. Even in this most
famous collection of gratuitously difficult problems, we find a
conceptual question.
The first of Hilbert's problems is called the "continuum hypothesis",
but is about smashing the continuum into dust. Elsewhere, he
said "no-one shall expell us from Cantor's Paradise", but I regard
it as a dystopia. I dream of some eventual escape, returning to the
Euclidean paradise. There we would actually talk about lines,
circles, compact subsets or whatever, instead of families of subsets
or arcane algebra (or, indeed, category theory). I am looking for
a language for mathematics that would look like "set theory" (as
mathematicians, not set theorists, perceive it) but would yields
computable continua instead of dust.
More categorically, I believe that there is some notion of category
that is very similar to an elementary topos, but in which all
morphisms are continuous (in particular Scott continuous with
respect to an intrinsic order).
I also believe that these ideas are applicable to other subjects.
When I have made the appropriate tools, I hope to be able to understand
algebraic geometry, which was a complete mystery to me as a student.
I am in princple capable of doing this, BECAUSE I am a categorist,
by following the analogy between frames and rings.
One version of this problem that I still cannot solve is a question
that Eugenio Moggi asked me in April 1993, although I forget the
exact words. We wanted a class of monos (I said they should be
the equalisers targetted at power of Sigma) that was closed under
composition and application of the Sigma^2 functor (ie taking the
exponential Sigma^(-) twice).
Another is how to embed the category of locales in a CCC WITHOUT
using illegitimate presheaves (Vickers and Townsend) or the axiom
of collection (Heckmann). When I wrote the original version of
this posting a couple of weeks back, I thought I could solve this
one. I am still hopeful, but it turns out to be a powerful question,
cf Ronnie's (2) above.
Notice that I give the principal formulation of the question in
vague language, not as a Diophantine equation. The more specific
the question, the more likely it is to have been the WRONG one.
Asking an impertinent question is the best way of getting a
pertinent answer.
This still involves very difficult problems and hundreds of journal
pages of formal proofs. But for me the problems serve the concepts
rather than the other way round. This is the essence of what it is
to be a conceptual mathematician. Ronnie Brown has told you a
different story of his own, but with the same message. Many
other experienced categorists (including the ones in higher
dimensions, which Rafael excluded from his original question,
for some reason) would do likewise.
What about Fields Medals? People will get them, using my work,
two or three generations down the line.
Paul Taylor
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Fri Jun 5 14:09:22 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Fri, 05 Jun 2009 14:09:22 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MCcur-0000HW-0l
for categories-list@mta.ca; Fri, 05 Jun 2009 14:09:17 -0300
From: Thorsten Altenkirch
To: categories List
Content-Type: text/plain; charset=US-ASCII; format=flowed; delsp=yes
Content-Transfer-Encoding: 7bit
Mime-Version: 1.0 (Apple Message framework v930.3)
Subject: categories: Re: Decidability of the theory of a monad
Date: Fri, 5 Jun 2009 09:58:21 +0100
Sender: categories@mta.ca
Precedence: bulk
Reply-To: Thorsten Altenkirch
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 19
Hi,
Sam Lindley and Ian Stark proved that Moggi's computational
Metalanguage (\lambda_ML) is decidable - this is simply typed lambda
calculus with a monad. If I am not mistaken your theory can be
faithfully encoded in \lambda_ML.
Actually, isn't it the case that the continuation monad is actually
the free monad. Hence, using this result decidability of \lambda_ML
should follow from the decidability of simply typed lambda calculus.
Cheers,
Thorsten
http://www.springerlink.com/content/y44yn0fg76dthfnn/
On 3 Jun 2009, at 12:10, Andrej Bauer wrote:
> Consider the theory of a monad, i.e., the axioms are those of a
> category and a monad given as a triple: an operation T on objects, for
> each object A a morphism eta_A : A -> T A, and an operation lift_{A,B}
> which maps morphisms f : A -> T B to lift f : T A -> T B. Concretely,
> the axioms are (where lift f is written f* and composition is
> juxtaposition):
>
> id f = f
> f id = f
> (f g) h = f (g h)
> eta* = id
> f* eta = f
> (f* g)* = f* g*
>
> Presumably, the equational theory (with partial operations) of such a
> triple is decidable. Is this known? If we ignore the types and
> partiality, we can attempt to turn the above equations into a
> confluent terminating rewrite system using the Knuth-Bendix algorithm,
> but it gets stuck (on various orderings I tried).
>
> A more categorical way of asking the same question is: what is a
> concrete description of the free "monad on a category" (is this the
> same as "free monad" on "free category"?).
>
> With kind regards,
>
> Andrej
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Fri Jun 5 14:10:30 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Fri, 05 Jun 2009 14:10:30 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MCcvw-0000P3-WA
for categories-list@mta.ca; Fri, 05 Jun 2009 14:10:25 -0300
From: "Ronnie Brown"
To: "John Iskra" ,
Subject: categories: Re: Famous unsolved problems in ordinary category theory
Date: Fri, 5 Jun 2009 12:07:17 +0100
MIME-Version: 1.0
Content-Type: text/plain;format=flowed;charset="iso-8859-1";reply-type=original
Content-Transfer-Encoding: 7bit
Sender: categories@mta.ca
Precedence: bulk
Reply-To: "Ronnie Brown"
Message-Id:
Status: RO
X-Status:
X-Keywords:
X-UID: 20
John,
Glad you liked it! Thanks for the references to Raoul Bott.
Mind you there was a serious point:
how to turn abstract mathematics into machine computation?
I have discussed this often with Larry Lambe.
Ronnie
----- Original Message -----
From: "John Iskra"
To: "Ronnie Brown"
Cc: "Hasse Riemann" ;
Sent: Friday, June 05, 2009 3:54 AM
Subject: Re: categories: Re: Famous unsolved problems in ordinary category
theory
> One of my favorite quotes:
>
> The question you raise ``how can such a formulation lead to
> computations'' doesn't bother me in the least! Throughout my whole life
> as a mathematician, the possibility of making explicit, elegant
> computations has always come out by itself, as a byproduct of a thorough
> conceptual understanding of what was going on. Thus I never bothered
> about whether what would come out would be suitable for this or that,
> but just tried to understand -- and it always turned out that
> understanding was all that mattered.
>
> A. Grothendieck
>
>
> Raoul Bott reinforced this in a talk I had the privilige to hear back in
> 98. He said that mathematics, done well, never required the placing of
> your oar in the water (he probably put it better than that...). The
> idea I think is that if you continually ask and answer the questions
> that occur to you, and, thus, gain understanding, then you will
> inevitably make progress. And that is what matters, really. So often
> the person credited with solving a 'famous' problem only takes the final
> step in a hard journey of a thousand miles made by a thousand others.
>
> Glory and fame - such as it is in the world of mathematics - are nice,
> but they are not, in the end, mathematics. I think it is of high
> importance to avoid confusing them.
>
> John Iskra
>
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Fri Jun 5 14:11:02 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Fri, 05 Jun 2009 14:11:02 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MCcwV-0000SF-4y
for categories-list@mta.ca; Fri, 05 Jun 2009 14:10:59 -0300
From: Thomas Streicher
Date: Fri, 5 Jun 2009 16:17:01 +0200
To: Hasse Riemann , categories@mta.ca
Subject: categories: Re: Famous unsolved problems in ordinary category theory
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Sender: categories@mta.ca
Precedence: bulk
Reply-To: Thomas Streicher
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 21
Dear Rafael,
here is a list of problems from categorical logic that I find difficult
to solve and don't know the answer yet. Certainly they are more on the logical
side but categories are involved in all of them. I don't claim that these
problems are generally important for category theory but they simply do bother
me. I write this mail to show that there are technically hard problems and
with the salient hope that someone may come up with an answer. Nevertheless
I am aware that the subsequent list of problems might easly get a prize for
the "best collection of most misleading problems".
(1) In their booklet "Algebraic Set Theory" Joyal and Moerdijk defined
for every strongly inaccessible cardinal \kappa a class of
\kappa-small maps inside the effective topos.
Does there exist a "generic" \kappa-small map such that all other maps
can be obtained as pullbacks from this generic one?
In their book the authors show the existence of a weakly generic one
but this doesn't imply the existence of a generic one and I suspect
there is none.
(2) Does there exist a model for Martin-L\"of's Intensional Type Theory
which validates Church's Thesis?
This question is due to M.Maietti and G.Sambin. Notice that type theory
validates the axiom of choice and, accordingly, the statement is much
stronger than saying that for every function from N to N there exists a
code for an algorithm computing this function.
(3) In my habilitation thesis
(www.mathematik.tu-darmstadt.de/~streicher/HabilStreicher.pdf)
I showed that the sconing of the effective topos (i.e. glueing
Gamma : Eff -> Set) gives rise to a model of INTENSIONAL Martin-Loef
type theory faithfully reflecting most of the weakness compared to
EXTENSIONAL type theory.
Martin Hofmann and I showed that the groupoid model refutes
the principle UIP saying that all elements of identity types are equal.
This has recently generalised to \omega-groupoids by M.Warren and there
is recently some activity of constructing models based on abstract
homotopy.
Can one construct a categorical model model serving both purposes?
This is an issue since the groupoid model and related ones constructed
more recently have the defect that all types over N are fairly extensional
and thus don't do the job which sconing of the effective topos does.
(4) Is the realizability model for the polymorphic lambda calculus
parametric in the sense of Reynolds?
It needn't be realizability over natural numbers.
Would be interesting already for some pca!
Thomas
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Fri Jun 5 14:45:57 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Fri, 05 Jun 2009 14:45:57 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MCdTr-0003ua-VI
for categories-list@mta.ca; Fri, 05 Jun 2009 14:45:28 -0300
From: "Ronnie Brown"
To:
Subject: categories: Nonabelian algebraic topology: full draft
Date: Fri, 5 Jun 2009 17:39:39 +0100
MIME-Version: 1.0
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
Sender: categories@mta.ca
Precedence: bulk
Reply-To: "Ronnie Brown"
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 22
This is to announce that a full hyperref pdf of the current version of =
this book is available from=20
www.bangor.ac.uk/r.brown/nonab-a-t-.html
(4.2MB, xx+496 pp)=20
Comments welcome; we are aware of minor faults but hope this version =
will be useful as a big step towards the final version, and even =
stimulate further work!=20
Ronnie Brown
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Sat Jun 6 18:49:13 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Sat, 06 Jun 2009 18:49:13 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MD3jd-00032x-2d
for categories-list@mta.ca; Sat, 06 Jun 2009 18:47:29 -0300
From: "Ronnie Brown"
To: ,
Subject: categories: Draft of book- apologies
Date: Fri, 5 Jun 2009 22:13:34 +0100
MIME-Version: 1.0
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
Sender: categories@mta.ca
Precedence: bulk
Reply-To: "Ronnie Brown"
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 23
It has been pointed out that I got the url wrong! It should be=20
www.bangor.ac.uk/r.brown/nonab-a-t.html
I grow old! I grow old!=20
I wear the bottoms of my trousers rolled.=20
Ronnie Brown=20
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Sat Jun 6 18:49:13 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Sat, 06 Jun 2009 18:49:13 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MD3ip-00030l-1A
for categories-list@mta.ca; Sat, 06 Jun 2009 18:46:39 -0300
Date: Fri, 05 Jun 2009 16:36:23 -0400
To: categories@mta.ca
From: "Ellis D. Cooper"
Subject: categories: Fundamental Theorem of Category Theory?
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"; format=flowed
Sender: categories@mta.ca
Precedence: bulk
Reply-To: "Ellis D. Cooper"
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 24
Dear category theory community,
There are Fundamental Theorems of Arithmetic, Algebra, Calculus, and
indeed, many more.
My question is, What would be candidates for the Fundamental Theorem
of Category Theory?
Yoneda Lemma comes to my mind. What do you think?
Best,
Ellis D. Cooper
Ellis D. Cooper, Ph.D.
978-546-5228 (LAND)
978-853-4894 (CELL)
XTALV1@NETROPOLIS.NET
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Sat Jun 6 18:49:13 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Sat, 06 Jun 2009 18:49:13 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MD3kI-00034A-Rf
for categories-list@mta.ca; Sat, 06 Jun 2009 18:48:11 -0300
Date: Fri, 05 Jun 2009 16:36:59 -0600
From: Robin Cockett
MIME-Version: 1.0
To: Hasse Riemann ,
Subject: categories: Re: Famous unsolved problems in ordinary category theory
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Sender: categories@mta.ca
Precedence: bulk
Reply-To: Robin Cockett
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 25
A student asked them twice
"Aren't problems just so nice?
They get stuck in your hair
And the last one's just so rare .."
"Like lice." said they with a grin
"Our hair is all gone and thin ...
And Categories we espouse
Rather than such vermin house!"
-very anon
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Sat Jun 6 18:49:40 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Sat, 06 Jun 2009 18:49:40 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MD3lg-00038y-SH
for categories-list@mta.ca; Sat, 06 Jun 2009 18:49:36 -0300
From: Hasse Riemann
To: ,
Subject: categories: Famous unsolved problems in ordinary category theory
Date: Sat, 6 Jun 2009 01:35:11 +0000
MIME-Version: 1.0
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
Sender: categories@mta.ca
Precedence: bulk
Reply-To: Hasse Riemann
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 26
=20
Hi Paul
=20
I still think you are getting me wrong=2C as did Ronnie. But never mind=2C =
i am used to it
since i don't follow the mainstream science ways to specialize=2C solve pro=
blems=2C publish=2C repeat.
Yet the problems interest will pass very soon. I now know 19 ordinary categ=
ory problems (if you explain
this one) vs. at least 23 in higher category theory. This explains why i re=
stricted to ordinary categories.=20
=20
>From the good side i should be thankful that you and Ronnie trie to direct =
me towards "true mathematics"=2C
but i have already found my "true mathematics". A big part of the process t=
o get there was precisely to
ask own quastions and finding the answers to them. But some people just got=
irritated when i asked them
questions (in their field!) they didn't have the answer to.
=20
> Another is how to embed the category of locales in a CCC WITHOUT
> using illegitimate presheaves (Vickers and Townsend) or the axiom
> of collection (Heckmann).=20
=20
I don't follow to the end here.
Why should presheaves be illegitimate?
Then=2C i suppose the axiom of collection is valid at least in the CCC.
But what is so bad about the axiom of collection in this case?
Do the embedding get bad?
=20
Best regards
Rafael Borowiecki
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Sat Jun 6 18:50:14 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Sat, 06 Jun 2009 18:50:14 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MD3mF-0003B6-GY
for categories-list@mta.ca; Sat, 06 Jun 2009 18:50:11 -0300
From: Hasse Riemann
To: Category mailing list
Subject: categories: Timeline of category theory and related mathematics
Date: Sat, 6 Jun 2009 02:31:23 +0000
MIME-Version: 1.0
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
Sender: categories@mta.ca
Precedence: bulk
Reply-To: Hasse Riemann
Message-Id:
Status: RO
X-Status:
X-Keywords:
X-UID: 27
=20
Hello categorists
=20
As a small project many months ago i started http://en.wikipedia.org/wiki/T=
imeline_of_category_theory_and_related_mathematics.
Not only because there was none but to write a little piece of what i have =
learned so others can benefit from it. In fact i often look in it for detai=
ls. Since i am not a real expert in category theory (which is huge!) yet=2C=
could you see if there are errors=2C inaccuracies=2C bad explanation or wo=
rding etc.? It is so sad when you get wrong facts from wikipedia. Just edit=
=2C no e-mails needed.
Additions are just as good :)
=20
At the time there was no nLab. If there was i would maby have written it th=
ere. If you want
and there is a need to i could start transfering the timeline to nLab. I th=
ink you like more
to edit nLab than wikipedia.
=20
Best Regards
Rafael Borowiecki
=20
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Sat Jun 6 18:51:02 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Sat, 06 Jun 2009 18:51:02 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MD3mz-0003En-Qi
for categories-list@mta.ca; Sat, 06 Jun 2009 18:50:57 -0300
From: "Bhupinder Singh Anand"
To: "'Ronnie Brown'" ,
Subject: categories: Re: Famous unsolved problems in ordinary category theory
Date: Sat, 6 Jun 2009 09:29:46 +0530
MIME-Version: 1.0
Content-Type: text/plain;charset="us-ascii"
Content-Transfer-Encoding: 7bit
Sender: categories@mta.ca
Precedence: bulk
Reply-To: "Bhupinder Singh Anand"
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 28
On Friday, June 05, 2009 4:37 PM, Ronnie Brown wrote in
categories@mta.ca:
RB>> Mind you there was a serious point: how to turn abstract
mathematics into machine computation? <
Envelope-to: categories-list@mta.ca
Delivery-date: Sat, 06 Jun 2009 18:52:27 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MD3oK-0003Ku-6B
for categories-list@mta.ca; Sat, 06 Jun 2009 18:52:20 -0300
Date: Sat, 6 Jun 2009 11:18:12 +0200 (CEST)
Subject: categories: Re: Famous unsolved problems in ordinary category theory
From: soloviev@irit.fr
To: "Thomas Streicher" , categories@mta.ca
MIME-Version: 1.0
Content-Type: text/plain;charset=utf-8
Content-Transfer-Encoding: quoted-printable
Sender: categories@mta.ca
Precedence: bulk
Reply-To: soloviev@irit.fr
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 29
Dear All -
Here a question related to categorical logic (or categorical proof theory=
)
of a very different type. I would like to put it here because it is an
illustration of another part of the field and also because it is
technically difficult and interesting.
It is well known that certain systems of propositional logic have a
natural structure of free category for certain classes of categories with
structure. For example, we have a structure of free Symmetric Monoidal
Closed Category on the Intuitionistic Multiplicative Linear Logic. In thi=
s
structure formulas are objects and equivalence classes of derivations of
the sequents A -> B are morphisms.
Free SMCC (in presence of "tensor unit" I) is not "fully coherent": there
are non-commutative diagrams. For example, one has the Mac Lane's example
A*** -> B***
(called "triple dual diagram"). In terms of IMLL there exist two
non-equivalent derivations of
((A-oI)-oI)-o I -> ((A-oI)-oI)-o I
w.r.t. the equivalence of free SMCC on the derivations of IMLL. One
derivation is identity, another derivation is obtained in obvious way
using the derivability of ((A-oI)-oI)-o I -> A-o I. Let us denote these
derivations 1 and f respectively. (For the sequent ((A-oI)-oI)-o I ->
((A-oI)-oI)-o I every derivation is equivalent to 1 or to f.)
The "triple dual conjecture" says that if we declare f\equiv 1 then all
the derivations with the same final sequent in IMLL will become
equivalent. I.e. the stronger categorical structure than SMCC (obtained b=
y
adding this new axiom for equivalence/ commutativity of diagrams) will be
"fully coherent".
If it is true we would have an interesting new variety of categories
(subvariety of SMCCs) in the sense of Universal Algebra.
Proof-theoretically, the study of this conjecture requires to study the
equivalence relations on derivations of IMLL between the relation of free
SMCC and the relation that identifies all derivations with the same
final sequent.
In my paper
S. Soloviev. On the conditions of full coherence in closed categories.
Journal of Pure and Applied Algebra, 69:301-329, 1990.
it was shown that
- if the "triple dual diagram" is commutative w.r.t. some equivalence
relation ~ (containing the relation of free SMCC)
- and the following additional condition holds:
[a-oI/a] h ~ [a-oI/a] g =3D> h~g
for any two derivations of the same sequent,
then all the derivations of the same sequent in IMLL become equivalent.
The additional condition is a) difficult to verify b) has the form
different form the equational form ("commutativity of a diagram") require=
d
from the point of view of Universal Algebra approach. All the attempts to
prove "pure" triple dual conjecture (by myself and others) did not yet
succeed.
One may mention that it is known that some intermediate equivalence
relations between the relation of free SMCC and the "total" relation of
derivations do exist:
L. Mehats, S. Soloviev. Coherence in SMCCs and equivalences on deriva-
tions in IMLL with unit. Annals of Pure and Applied Logic, v.147, 3, p.
127-179, august 2007.
but all known intermediate relations are contained in the relation
generated by commutativity of triple dual diagram.
My ph.d. student
Antoine El Khoury has checked also that the commutativity of triple
dual diagram (equivalence of 1 and f) implies equivalence of derivations
of the balanced sequents with 1, 2 or 3 variables (commutativity
of corresponding diagrams in SMCC).
Remark. Obviosly, the commutativity of triple dual diagram implies
A*** isomorphe to A*.
Best regards to all
Sergei Soloviev
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Sun Jun 7 19:12:58 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Sun, 07 Jun 2009 19:12:58 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MDQZh-0004lq-TQ
for categories-list@mta.ca; Sun, 07 Jun 2009 19:10:45 -0300
Date: Sat, 6 Jun 2009 19:37:55 -0400 (EDT)
From: Andrew Salch
To: categories@mta.ca
Subject: categories: categories fibered in small categories
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed
Sender: categories@mta.ca
Precedence: bulk
Reply-To: Andrew Salch
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 31
I have a question for the categories list: it is well-known (and proven
e.g. in Hollander's PhD thesis) that categories fibered in groupoids over
a small category C are equivalent to lax presheaves of groupoids on C. I
would like to use the generalization of this result in which the word
"groupoids" is replaced throughout by "small categories." It is not hard
to write out how this proof goes, but I suspect there is some vast
generalization of this, e.g. with the word "groupoids" replaced by
"quasicategories" or something of that nature, which somebody has already
proven, and in that case I would prefer to cite the more general result.
Does anyone know if something like this is already in the literature?
Thanks,
Andrew S.
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Sun Jun 7 19:12:58 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Sun, 07 Jun 2009 19:12:58 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MDQZB-0004kQ-75
for categories-list@mta.ca; Sun, 07 Jun 2009 19:10:13 -0300
Date: Sat, 6 Jun 2009 23:22:52 +0100
From: Miles Gould
To: categories@mta.ca
Subject: categories: Re:Fundamental Theorem of Category Theory?
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Sender: categories@mta.ca
Precedence: bulk
Reply-To: Miles Gould
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 32
On Fri, Jun 05, 2009 at 04:36:23PM -0400, Ellis D. Cooper wrote:
> There are Fundamental Theorems of Arithmetic, Algebra, Calculus, and
> indeed, many more.
>
> My question is, What would be candidates for the Fundamental Theorem
> of Category Theory?
My suggestion would be the theorem that left adjoints preserve colimits,
and right adjoints preserve limits.
This may not be the deepest theorem in category theory, but
(a) it's pretty darn deep,
(b) it describes a beautiful connection between two fundamental notions
in the subject,
(c) it admits a huge variety of applications in "ordinary" mathematics.
I've occasionally referred to this theorem as the Fundamental Theorem of
Category Theory by way of emphasizing its importance while teaching, but
I've always immediately clarified that it's only me who uses this term :-)
Miles
--
Sometimes it's best to do nothing, if it's the right sort of nothing.
-- The Doctor
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Sun Jun 7 19:12:59 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Sun, 07 Jun 2009 19:12:59 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MDQbD-0004ps-IO
for categories-list@mta.ca; Sun, 07 Jun 2009 19:12:19 -0300
Mime-Version: 1.0 (Apple Message framework v753.1)
Content-Type: multipart/alternative; boundary=Apple-Mail-1--257933298
To: categories
Subject: categories: Categorical problems
From: Ross Street
Date: Sun, 7 Jun 2009 11:13:58 +1000
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;charset=US-ASCII;delsp=yes;format=flowed
Sender: categories@mta.ca
Precedence: bulk
Reply-To: Ross Street
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 33
Walter Tholen's recent message reminded me of a conjecture. Perhaps
we have been too shy about stating our conjectures because, even
among mathematicians, they may have seemed too technical.
I seem to remember Peter Freyd saying once that the problem in
category theory of proving sets were small (to find adjoints to
functors for example) was analogous to finding numerical bounds in
mathematical analysis. Surely by now, there are as many people who
understand what a sheaf is as understand what the Riemann Hypothesis
asserts (for example, local to global versus analytic continuation).
So here is a problem I came up with in the 1970s. As with Fermat's
Last Theorem, I don't particularly remember having any application
for it. However, similar solved problems were used by Rosebrugh-Wood
to characterize the category of sets in terms of adjoint strings
involving the Yoneda embedding. By locally small I mean having homs
in a chosen category Set of small sets.
Problem. Suppose A is a locally small site whose category E of Set-
valued sheaves is also locally small. Is E a topos?
== Ross
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Sun Jun 7 19:12:59 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Sun, 07 Jun 2009 19:12:59 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MDQaM-0004nO-La
for categories-list@mta.ca; Sun, 07 Jun 2009 19:11:26 -0300
Date: Sat, 06 Jun 2009 21:09:25 -0400
From: "Fred E.J. Linton"
To: "Ellis D. Cooper" ,
Subject: categories: Re: Fundamental Theorem of Category Theory?
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
Sender: categories@mta.ca
Precedence: bulk
Reply-To: "Fred E.J. Linton"
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 34
On Sat, 06 Jun 2009 05:51:38 PM EDT, "Ellis D. Cooper"
asked:
> There are Fundamental Theorems of Arithmetic, Algebra, Calculus, and
> indeed, many more.
> =
> My question is, What would be candidates for the Fundamental Theorem
> of Category Theory?
> =
> Yoneda Lemma comes to my mind. What do you think?
Perhaps that, yes; or, perhaps, the characterization of representable
functors.
Cheers, -- Fred
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Sun Jun 7 19:13:11 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Sun, 07 Jun 2009 19:13:11 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MDQbz-0004sl-Sm
for categories-list@mta.ca; Sun, 07 Jun 2009 19:13:07 -0300
Subject: categories: Re: preprint announcement
From: Vincenzo Ciancia
To: Panagis Karazeris , categories@mta.ca
Content-Type: text/plain; charset="UTF-8"
Date: Sun, 07 Jun 2009 21:15:11 +0200
Mime-Version: 1.0
Sender: categories@mta.ca
Precedence: bulk
Reply-To: Vincenzo Ciancia
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 35
Il giorno lun, 01/06/2009 alle 16.15 +0300, Panagis Karazeris ha
scritto:
> Dear all,
>=20
> I would like to announce that the following preprint is available as
>=20
> http://arxiv.org/abs/0905.4883
>=20
> as well as from my webpage
>=20
> www.math.upatras.gr/~pkarazer
>=20
> Final Coalgebras in Accessible Categories,
> by Panagis Karazeris, Apostolos Matzaris and Jiri Velebil
>=20
> Abstract:
> We give conditions on a finitary endofunctor of a finitely accessible
> category to admit a final coalgebra. Our conditions always apply to the
> case of a finitary endofunctor of a locally finitely presentable (l.f.p=
.)
> category and they bring an explicit construction of the final coalgebra=
in
> this case. On the other hand, there are interesting examples of final
> coalgebras beyond the realm of l.f.p. categories to which our results
> apply. We rely on ideas developed by Tom Leinster for the study of
> self-similar objects in topology.=20
>=20
> Best regards,
> Panagis Karazeris
>=20
I do not see the following paper in the references; would it be worth to
provide a comparison?
http://www.sciencedirect.com/science?_ob=3DArticleURL&_udi=3DB75H1-4G7MXP=
F-4&_user=3D144492&_rdoc=3D1&_fmt=3D&_orig=3Dsearch&_sort=3Dd&view=3Dc&_a=
cct=3DC000012038&_version=3D1&_urlVersion=3D0&_userid=3D144492&md5=3D5760=
58372d432ade83f476c43b8b466a
Terminal sequences for accessible endofunctors=20
James Worrell
Abstract:
We consider the behaviour of the terminal sequence of an accessible
endofunctor T on a locally presentable category K. The preservation of
monics by T is sufficient to imply convergence, necessarily to a
terminal coalgebra. We can say much more if K is Set, and =CE=BA is =CF=89=
. In
that case it is well known that we do not necessarily get convergence at
=CF=89, however we show that to ensure convergence we don't need to go to=
a
higher cardinal, just to the next limit ordinal, =CF=89 + =CF=89.
For an =CF=89-accessible endofunctor T on Set the construction of the
terminal coalgebra can thus be seen as a two stage construction, with
each stage being finitary. The first stage obtains the Cauchy completion
of the initial T-algebra as the =CF=89-th object in the terminal sequence=
A=CF=89.
In the second stage this object is pruned to get the final coalgebra A=CF=
=89
+=CF=89. We give an example where A=CF=89 is the solution of the correspo=
nding
domain equation in the category of complete ultra-metric spaces.
Thanks
Vincenzo
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Mon Jun 8 11:36:10 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Mon, 08 Jun 2009 11:36:10 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MDfvp-00025W-NZ
for categories-list@mta.ca; Mon, 08 Jun 2009 11:34:37 -0300
Mime-Version: 1.0 (Apple Message framework v753.1)
To: categories
Subject: categories: Categorical problems
From: Ross Street
Date: Sun, 7 Jun 2009 11:13:58 +1000
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;charset=US-ASCII;delsp=yes;format=flowed
Sender: categories@mta.ca
Precedence: bulk
Reply-To: Ross Street
Message-Id:
Status: RO
X-Status:
X-Keywords:
X-UID: 36
[From moderator: Resent with apologies to those who received an empty
message body...]
Walter Tholen's recent message reminded me of a conjecture. Perhaps
we have been too shy about stating our conjectures because, even
among mathematicians, they may have seemed too technical.
I seem to remember Peter Freyd saying once that the problem in
category theory of proving sets were small (to find adjoints to
functors for example) was analogous to finding numerical bounds in
mathematical analysis. Surely by now, there are as many people who
understand what a sheaf is as understand what the Riemann Hypothesis
asserts (for example, local to global versus analytic continuation).
So here is a problem I came up with in the 1970s. As with Fermat's
Last Theorem, I don't particularly remember having any application
for it. However, similar solved problems were used by Rosebrugh-Wood
to characterize the category of sets in terms of adjoint strings
involving the Yoneda embedding. By locally small I mean having homs
in a chosen category Set of small sets.
Problem. Suppose A is a locally small site whose category E of Set-
valued sheaves is also locally small. Is E a topos?
== Ross
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Mon Jun 8 14:14:04 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Mon, 08 Jun 2009 14:14:04 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MDiOt-0007bT-VL
for categories-list@mta.ca; Mon, 08 Jun 2009 14:12:48 -0300
From: Hasse Riemann
To: Category mailing list
Subject: categories: =?windows-1256?Q?Famous_uns?= =?windows-1256?Q?olved_prob?= =?windows-1256?Q?lems_in_or?= =?windows-1256?Q?dinary_cat?= =?windows-1256?Q?egory_theo?= =?windows-1256?Q?ry=FE?=
Date: Mon, 8 Jun 2009 01:34:10 +0000
Content-Type: text/plain; charset="windows-1256"
MIME-Version: 1.0
Content-Transfer-Encoding: quoted-printable
Sender: categories@mta.ca
Precedence: bulk
Reply-To: Hasse Riemann
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 37
=20
Hi categorists
=20
OK, here is the beuty of collecting and spreading problems that many seem=
to miss.
It just took me a few days to change my mood from the depressing answers
not to look for problems. Again i am much more for structuring of mathema=
tics.
=20
Usually you only get to know what is proved and not what is unproved.
Problems complete this by letting you know what to not to look for.
They also answer your questions even if it is by saying unkown or a conje=
cture.
Then, on the other hand, they are good research projects so they should b=
e widely known.
Just maby someone undertakest them and happens to find the solution.
But often he must first see the problem.
=20
The problems Ross Street put forward are so beautiful i have decided to p=
ost 2 problems
i have learned from him, unedited.
=20
1)
Fermat's Last Theorem is about the category of finite sets. Is there a ca=
tegorical proof?
Can we characterize those categories C in which x^n + y^n isomorphic to z=
^n has only trivial
solutions for n> 2?
=20
2)
The category of finite sets is a concrete form of the set N of natural nu=
mbers.
What are concrete forms of Z, Q, R and C?
If anyone know some problems of these sort below let me know.
=20
* characterization problems
* inherit properties problems
* every category/functor/... of type A is a category/functor/... of type =
B
=20
=20
I also foregot to mention before that i know and more than like Grothendi=
ecks philosophy
of dissolving problems by developing a proper framework for rhem.
=20
Best regards
Rafael Borowiecki
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Mon Jun 8 14:14:04 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Mon, 08 Jun 2009 14:14:04 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MDiPi-0007iO-Nq
for categories-list@mta.ca; Mon, 08 Jun 2009 14:13:38 -0300
MIME-Version: 1.0
Date: Mon, 8 Jun 2009 07:13:41 +0200
Subject: categories: Re: categories fibered in small categories
From: Urs Schreiber
To: Andrew Salch , categories@mta.ca
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Sender: categories@mta.ca
Precedence: bulk
Reply-To: Urs Schreiber
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 38
On Sun, Jun 7, 2009 at 1:37 AM, Andrew Salch wrote:
> it is well-known (and proven
> e.g. in Hollander's PhD thesis) that categories
> fibered in groupoids over a small category C
> are equivalent to lax presheaves of groupoids on C.
[...]
>I suspect there is some vast generalization of
> this, e.g. with the word "groupoids" replaced by
> "quasicategories" or something of that nature,
> which somebody has already proven, and in that
> case I would prefer to cite the more general result.
> Does anyone know if something like this is already
> in the literature?
Yes, see section 3.3.2 of Jacob Lurie's "Higher Topos Theory" for the
statement for "quasicategory valued presheaves".
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Mon Jun 8 14:14:35 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Mon, 08 Jun 2009 14:14:35 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MDiQa-0007nH-S4
for categories-list@mta.ca; Mon, 08 Jun 2009 14:14:32 -0300
From: "Ronnie Brown"
To: "Miles Gould" ,
Subject: categories: Re:Fundamental Theorem of Category Theory?
Date: Mon, 8 Jun 2009 10:06:12 +0100
MIME-Version: 1.0
Content-Type: text/plain;format=flowed;charset="iso-8859-1";reply-type=original
Content-Transfer-Encoding: 7bit
Sender: categories@mta.ca
Precedence: bulk
Reply-To: "Ronnie Brown"
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 39
Limits, colimits, and adjoints:
I go along with this: it is the result of general category theory that I
have used most in studying colimits of forms of multiple groupoids, for
homotopical applications. It really does come under `categories for the
working mathematician'.
I have also been attracted in the same vein by fibrations and cofibrations
of categories: see a recent paper in TAC.
I well remember a remark of Henry Whitehead in response to a visiting
lecturer saying: `The proof is trivial.' JHCW: `It is the snobbishness of
the young to suppose that a theorem is trivial because the proof is
trivial.' (There was and is no answer to that!) (His example was
Schroder-Bernstein.)
The leads to the interesting question of what makes a theorem nontrivial?
Good discussion topic for the young (at heart).
Ronnie Brown
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Mon Jun 8 14:15:18 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Mon, 08 Jun 2009 14:15:18 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MDiRG-000043-Tl
for categories-list@mta.ca; Mon, 08 Jun 2009 14:15:14 -0300
From: vxc@Cs.Nott.AC.UK
To: categories@mta.ca
Subject: categories: PhD position in Nottingham
Date: 08 Jun 2009 10:08:16 +0100
Mime-Version: 1.0
Content-Type: text/plain; format=flowed; charset=ISO-8859-1
Sender: categories@mta.ca
Precedence: bulk
Reply-To: vxc@Cs.Nott.AC.UK
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 40
PhD position in Type Theory at Nottingham
-----------------------------------------
A new PhD position is available in the Functional Programming Laboratory at
the University of Nottingham. The topic of research for the project is
"Programming and Reasoning with Infinite Structures": it consists in the
theoretical study and development of software tools for coinductive types
and structured corecursion.
The candidate must be a UK resident with an excellent degree in Computer
Science or Mathematics at MSc (preferred) or BSc level (first class or
equivalent). The applicant should have a good background in mathematical
logic, theoretical computer science or functional programming. (S)he should
be interested doing research in type theory, constructive mathematics,
category theory and foundations of formal reasoning.
We offer: PhD place with living expenses (standard UK level) for 3 years.
The grants also provide laptops and travel expenses for conference and
workshop visits. Nottingham University provides a vibrant research
environment in the Functional Programming Laboratory.
Deadline for applications: 20 June 2009.
Send a cover letter and your CV to Venanzio Capretta (vxc@cs.nott.ac.uk).
Please contact me for any additional information that you need.
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Mon Jun 8 14:16:18 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Mon, 08 Jun 2009 14:16:18 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from )
id 1MDiSE-0000BC-9G
for categories-list@mta.ca; Mon, 08 Jun 2009 14:16:14 -0300
Date: Mon, 8 Jun 2009 07:44:40 -0400
From: tholen@mathstat.yorku.ca
To: Miles Gould , categories@mta.ca
Subject: categories: Re: Fundamental Theorem of Category Theory?
MIME-Version: 1.0
Content-Type: text/plain;charset=ISO-8859-1;format="flowed"
Content-Disposition: inline
Content-Transfer-Encoding: 7bit
Sender: categories@mta.ca
Precedence: bulk
Reply-To: tholen@mathstat.yorku.ca
Message-Id:
Status: O
X-Status:
X-Keywords:
X-UID: 41
You could make your choice more comprehensive: Freyd's General and
Special Adjoint Functor Theorems give a more complete picture of the
fundamental relationship between limit preservation and adjointness.
Regards, Walter.
Quoting Miles Gould :
> On Fri, Jun 05, 2009 at 04:36:23PM -0400, Ellis D. Cooper wrote:
>> There are Fundamental Theorems of Arithmetic, Algebra, Calculus, and
>> indeed, many more.
>>
>> My question is, What would be candidates for the Fundamental Theorem
>> of Category Theory?
>
> My suggestion would be the theorem that left adjoints preserve colimits,
> and right adjoints preserve limits.
>
...
[For admin and other information see: http://www.mta.ca/~cat-dist/ ]
From rrosebru@mta.ca Tue Jun 9 07:54:24 2009 -0300
Return-path:
Envelope-to: categories-list@mta.ca
Delivery-date: Tue, 09 Jun 2009 07:54:24 -0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelope-from