From MAILERDAEMON Wed Nov 8 14:26:00 2006
Date: 08 Nov 2006 14:26:00 0400
From: Mail System Internal Data
Subject: DON'T DELETE THIS MESSAGE  FOLDER INTERNAL DATA
MessageID: <1163010360@mta.ca>
XIMAP: 1159800537 0000000050
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 recreated
with the data reset to initial values.
From rrosebru@mta.ca Mon Oct 2 11:47:01 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Mon, 02 Oct 2006 11:47:01 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GUOpE00050ZVi
for categorieslist@mta.ca; Mon, 02 Oct 2006 11:31:21 0300
MimeVersion: 1.0
MessageId:
Date: Mon, 2 Oct 2006 15:38:21 +0200
To: categories@mta.ca
From: giovanni sambin
Subject: categories: grants for foreign PhD students in Padua
ContentType: text/plain; charset="usascii"
Sender: catdist@mta.ca
Precedence: bulk
Status: RO
XStatus:
XKeywords:
XUID: 1
The University of Padua (Italy) is offering 10 grants for study in one
of the PhD programs, beginning January 2007.
The grants are for all doctorate programs, and they are reserved to
nonItalian citizens. More information (in Italian and English) on the
grants and on the university can be found at the website:
http://www.unipd.it/studenti/Dopo_laurea/dottorati_ricerca/bandi_dottorato_grad/bandidottoratograduatorie.htm
Please note that the deadline is October 25, and that the application
must reach the office by that date.
The doctorate school on Mathematical Sciences includes a curriculum in
logic. Before sending the official application, any prospective applicant is suggested to get in contact with:
Bruno Chiarellotto, director of the school
bruno.chiarellotto@unipd.it
or directly with
Giovanni Sambin, professor of logic
giovanni.sambin@unipd.it
In fact, the application must include a research objective.
Some information on research in logic in Padua can be found at www.math.unipd.it/~logic and www.math.unipd.it/~sambin
G. Sambin
From rrosebru@mta.ca Wed Oct 4 15:40:35 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Wed, 04 Oct 2006 15:40:35 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GVBX700073JEH
for categorieslist@mta.ca; Wed, 04 Oct 2006 15:31:53 0300
Date: Tue, 3 Oct 2006 10:58:59 +0100 (BST)
From: S B Cooper
To: categories@mta.ca
Subject: categories: CiE 2007  Preliminary Announcement
MIMEVersion: 1.0
ContentType: TEXT/PLAIN; charset=USASCII; format=flowed
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: RO
XStatus:
XKeywords:
XUID: 2
**********************************************************************
PRELIMINARY ANNOUNCEMENT
CiE 2007
http://www.mat.unisi.it/newsito/cie07.html
Computability in Europe 2007: Computation and Logic in the Real World
Department of Mathematics and Computer Science "Roberto Magari"
University of Siena
Siena, 1823 June 2007
IMPORTANT DATES:
Submission of papers: Jan. 12, 2007
Notification of authors: Feb. 16, 2007
Deadline for final revisions: Mar. 9, 2007
The Third Conference CiE 2007, organised by CiE (Computability in
Europe) will take place at the University of Siena, June 1823 2007.
CiE is a European network of mathematicians, logicians, computer scientists,
philosophers, theoretical physicists and others interested in new developments
in computability and in their underlying significance for the real world.
CiE 2007 will address various aspects of the ways computability and
theoretical computer science enable scientists and philosophers to deal
with mathematical and real world issues, ranging through problems
related to logic, mathematics, physical processes, real computation and
learning theory. At the same time it will focus on different ways in
which computability emerges from the real world, and how this affects
our way of thinking about everyday computational issues.
CiE 2007 will be colocated with the annual CCA (Computability and Complexity
in Analysis) Conference (Siena, College Santa Chiara, June 1618, 2007):
http://ccanet.de/cca2007/
CiE 2007 conference topics include, but not exclusively 
* Admissible sets
* Analog computation
* Artificial intelligence
* Automata theory
* Classical computability and degree structures
* Complexity classes
* Computability theoretic aspects of programs
* Computable analysis and real computation
* Computable structures and models
* Computational and proof complexity
* Computational learning and complexity
* Concurrency and distributed computation
* Constructive mathematics
* Cryptographic complexity
* Decidability of theories
* Derandomization
* DNA computing
* Domain theory and computability
* Dynamical systems and computational models
* Effective descriptive set theory
* Finite model theory
* Formal aspects of program analysis
* Formal methods
* Foundations of computer science
* Games
* Generalized recursion theory
* History of computation
* Hybrid systems
* Higher type computability
* Hypercomputational models
* Infinite time Turing machines
* Kolmogorov complexity
* Lambda and combinatory calculi
* Lsystems and membrane computation
* Mathematical models of emergence
* Molecular computation
* Neural nets and connectionist models
* Philosophy of science and computation
* Physics and computability
* Probabilistic systems
* Process algebra
* Programming language semantics
* Proof mining
* Proof theory and computability
* Quantum computing and complexity
* Randomness
* Reducibilities and relative computation
* Relativistic computation
* Reverse mathematics
* Swarm intelligence
* Type systems and type theory
* Uncertain Reasoning
* Weak systems of arithmetic and applications
We particularly welcome submissions in emergent areas, such as bioinformatics
and natural computation, where they have a basic connection with computability.
Contributed papers will be selected from submissions received by the
PROGRAM COMMITTEE consisting of:
M. Agrawal (Kanpur) M. Arslanov (Kazan)
G. Ausiello (Roma) A. Bauer (Ljubljana)
A. Beckmann (Swansea) U. Berger (Swansea)
A. Cantini (Firenze) B. Cooper (Leeds, cochair)
L. Crosilla (Firenze) J. Diaz (Barcelona)
C. Dimitracopoulos (Athens) F. Ferreira (Lisbon)
S. Goncharov (Novosibirsk) P. Gruenwald (Amsterdam)
D. Harel (Rehovot) A. Hodges (Oxford)
J. Kempe (Paris) G. Longo (Paris)
B. Loewe (Amsterdam) J. Makowsky (Haifa)
E. Mayordomo (Zaragoza) W. Merkle (Heidelberg)
F. Montagna (Siena) D. Normann (Oslo)
T. Pheidas (Heraklion) G. Rozenberg (Leiden)
G. Sambin (Padova) H. Schwichtenberg (Muenchen)
W. Sieg (Carnegie Mellon) A. Sorbi (Siena, cochair)
I. Soskov (Sofia) P. van Emde Boas (Amsterdam).
The PROGRAMME COMMITTEE cordially invites all researchers (European and
nonEuropean) in computability related areas to submit their papers (in
PDFformat, max 10 pages) for presentation at CiE 2007. We particularly invite
papers that build bridges between different parts of the research community.
The CONFERENCE PROCEEDINGS will be published by LNCS, Springer Verlag. There
will also be journal special issues, collecting invited contributions related
to the conference.
The conference is sponsored by EATCS, ASL, EACSL, and AILA (Italian Association
of Logic and Applications).
**********************************************************************
From rrosebru@mta.ca Wed Oct 4 15:40:35 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Wed, 04 Oct 2006 15:40:35 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GVBXl00078SRD
for categorieslist@mta.ca; Wed, 04 Oct 2006 15:32:33 0300
Date: Tue, 03 Oct 2006 14:27:32 +0100
From: Alexander Kurz
MIMEVersion: 1.0
To: categories@mta.ca
Subject: categories: PhD Studentship available
ContentType: text/plain; charset=ISO88591
ContentTransferEncoding: 7bit
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: O
XStatus:
XKeywords:
XUID: 3

Please distribute to potential candidates

The Department of Computer Science of the University of Leicester offers
a PhD studentship (GTA). The GTA scheme involves some teaching and runs
for 4 years. Unfortunately, the university waives the fees only for EU
nationals.
The PhD student will join Nick Bezhanishvili and myself in our current
work on "Coalgebras, Modal Logic, and Stone Duality". Colleagues in
Leicester working on related topics include Roy Crole, Reiko Heckel,
Vincent Schmitt, Emilio Tuosto, and FerJan de Vries. Moreover, there
will be close collaboration with the logic groups at the University of
Amsterdam (in particular with the VICIproject directed by Yde Venema at
ILLC) and at the University of Oxford (Hilary Priestley, Alexandru Baltag).
For more information on the topic see
http://www.cs.le.ac.uk/people/akurz/
The official announcement and application form is available at (Ref
S2995)
http://www.le.ac.uk/personnel/supportjobs/index.html
The applications should be submitted no later than 20 October 2006.
If you have any questions please send me an email.
Best wishes,
Alexander
From rrosebru@mta.ca Wed Oct 4 15:40:35 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Wed, 04 Oct 2006 15:40:35 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GVBYA0007AyKG
for categorieslist@mta.ca; Wed, 04 Oct 2006 15:32:58 0300
To: categories@mta.ca
Subject: categories: TLCA '07  Preliminary Call for Papers
Date: Wed, 04 Oct 2006 10:25:22 +0900
From: Hasegawa Masahito
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: RO
XStatus:
XKeywords:
XUID: 4
Preliminary Call for Papers
Eight International Conference on
Typed Lambda Calculi and Applications (TLCA '07)
Paris, June 2628, 2007
Part of RDP 07 (http://www.lsv.enscachan.fr/rdp07/)
The TLCA series of conferences serves as a forum for presenting
original research results that are broadly relevant to the theory
and applications of typed calculi. The following list of topics
is nonexhaustive:
* Prooftheory: Natural deduction and sequent calculi, cut
elimination and normalisation, linear logic and proof nets,
typetheoretic aspects of computational complexity
* Semantics: Denotational semantics, game semantics,
realisability, categorical models
* Implementation: Abstract machines, parallel execution, optimal
reduction, type systems for program optimisation
* Types: Subtypes, dependent types, type inference, polymorphism,
types in theorem proving
* Programming: Foundational aspects of functional and
objectoriented programming, proof search and logic programming,
connections between and combinations of functional and logic
programming, type checking
The programme of TLCA will consist of three invited talks and about
25 papers selected from original contributions. Accepted papers will
be published as a volume of Springer Lecture Notes in Computer Science
series (http://www.springer.de/comp/lncs/index.html).
Submissions: The submitted papers should describe original work and
should allow the Programme Committee to assess the merits of the
contribution: in particular references and comparisons with related
work should be included.
Submission of material already published or submitted to other
conferences with published proceedings is not allowed.
Papers should not exceed 15 pages in Springer LNCS format
(http://www.springer.de/comp/lncs/authors.html).
Instructions for submissions will appear soon.
Program Committee
* Chantal Berline (CNRS, France)
* Peter Dybjer (Chalmers, Sweden)
* Healfdene Goguen (Google, USA)
* Robert Harper (Carnegie Mellon University, USA)
* Olivier Laurent (CNRS, France)
* Simone Martini (University of Bologna, Italy)
* Simona Ronchi Della Rocca (University of Torino, Italy), chair
* Peter Selinger (University of Dalhousie, Canada)
* Paula Severi (University of Leicester, UK)
* Kazushige Terui (University of Sokendai, Japan)
* Pawel Urzyczyn (University of Warsaw, Poland)
Important Dates
December 22 Title and abstract due
January 2 Deadline for submission
March 1015 Author review period
March 25 Notification of acceptancerejection
April 20 Deadline for the final version
Steering Committe
Samson Abramsky, Oxford, chair
Henk Barendregt, Nijmegen
Mariangiola DezaniCiancaglini, Turin
Roger Hindley, Swansea
Martin Hofmann, Munich
Pawel Urzyczyn, Warsaw
Publicity Chair
Masahito Hasegawa
From rrosebru@mta.ca Thu Oct 5 16:21:27 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Thu, 05 Oct 2006 16:21:27 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GVYej0001uH6H
for categorieslist@mta.ca; Thu, 05 Oct 2006 16:13:17 0300
To: LiCS 2006 List
From: Kreutzer + Schweikardt
Subject: categories: LICS 2007  Call for Workshop Proposals
Date: Thu, 5 Oct 2006 19:57:38 +0200 (CEST)
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: RO
XStatus:
XKeywords:
XUID: 5
LICS 2007 Call for Workshop Proposals
The TwentySecond IEEE Symposium on Logic in Computer Science (LICS 2007)
will be held in Wroclaw, Poland, July 1014, 2007. It will be colocated
with two other meetings: the International Colloquium on Automata,
Languages, and Programming (ICALP'07) July 913, 2007, and also the
European Logic Colloquium (ELC 2007), July 1419. Workshops are planned
for July 8, 9 and July 15 (possibly the afternoon of 14th).
LICS workshops have traditionally been an important and exciting part of
the program. They introduce either newest research in traditional areas of
the LICS community, recent interdisciplinary and applied areas of general
theory, or emerging directions that already have some substantial overlap
with LICS community interests. Researchers and practitioners are invited to
submit proposals for workshops on topics relating logic  broadly construed  to
computer science or related fields. Typically, LICS workshops feature a
mix of invited speakers and contributed presentations. LICS workshops do not
produce formal proceedings. However, in the past there have been special issues of
journals based in part on certain LICS workshops.
Proposals should include:
 A short scientific summary and justification of the proposed topic.
This should include a discussion of the particular benefits of the
topic to the LICS community.
 A discussion of the proposed format and agenda.
 Procedures for selecting participants and papers.
 Expected number of participants. (This is important!)
 Potential invited speakers.
 Plans for dissemination (for example, special issues of journals).
 For workshops of potential interest to ICALP participants, whether
the workshop should be considered as a possible joint LICS/ICALP
workshop.
 Tell us the timeframe you would prefer: 1 day, 1.5 or 2 days, either
before LICS (July 8,9) or after LICS (July 15). Alas, some overlap
with either ICALP or ELC is inevitable.
Proposals are due Nov. 15, 2006, and should be submitted electronically to:
Philip Scott
Workshops Chair, LICS 2007
phil@site.uottawa.ca
Workshops will be chosen by a committee that consists of the LICS
General Chair, LICS Workshop Chair, LICS 2007 PC Chair, and LICS 2007
Conference Chair. In the case of potential joint workshops, these will
be discussed with colleagues from ICALP. A decision will be made by
the end of November.
From rrosebru@mta.ca Sat Oct 7 09:41:34 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Sat, 07 Oct 2006 09:41:34 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GWBLQ0004qvMU
for categorieslist@mta.ca; Sat, 07 Oct 2006 09:31:56 0300
MimeVersion: 1.0 (Apple Message framework v606)
ContentTransferEncoding: 7bit
ContentType: text/plain; charset=USASCII; format=flowed
To: categories@mta.ca
From: PierreLouis Curien
Subject: categories: Position preannouncement in Paris 7 (REMINDER, qualification deadline 16/10/06)
Date: Sat, 7 Oct 2006 11:16:56 +0200
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: O
XStatus:
XKeywords:
XUID: 6
**** REMINDER ****
Deadline for the "qualification procedure is 16 October, strictly.
********************************
POSITION PREANNOUNCEMENT
A position of Maitre de Conferences (permanent position, more or less
equivalent to "associate professor", or "lecturer")
** in mathematics**
is likely to be opened next year at Paris 7 University.
The hired candidate will work in the laboratory PPS (Preuves,
Programmes et Systemes), which spreads its interests on both sides of
the correspondence between proofs and programs, covering work on
language design and implementation, rewriting, semantics (and game
semantics in particular), categories, linear logic, realizability,
probabilistic and topological methods, etc... See www.pps.jussieu.fr.
The position will be opened around February 2007, with decisions taken
around May 2007, and job starting in September 2007.
But there is a preliminary phase called ** qualification **, through
which all candidates to academic positions in France have to go.
This procedure consists of an evaluation of both research and teaching
experience of candidates in view of their potential application to a
position in a French university. The first phase of this (rather light)
procedure is opened on September 11, 2006, and
*** closes on October 16, 2006 ***
and is entirely electronical
(http://www.education.gouv.fr/personnel/enseignant_superieur/
enseignant_chercheur/calendrier_qualification.htm). The section of
qualification should be preferably number 25 (mathe'matiques), but
candidates interested in multiple applications in France, including in
CS departments, may also apply for qualification in section 27
(informatique) simultaneously.
This approaching first deadline is the main reason for the present
early announcement.
A certain fluency in French is required for the position. The teaching
will be in the mathematics department, so some experience in teaching
mathematics (rather than computer science) is welcome Teaching is in
French.
I invite potential candidates to contact me, and I also encourage
colleagues to point me to interesting potential candidates fitting the
criteria.
Best regards,
Pierre=Louis Curien
curien@pps.jussieu.fr
From rrosebru@mta.ca Mon Oct 9 09:49:31 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Mon, 09 Oct 2006 09:49:31 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GWuQU0002KX0S
for categorieslist@mta.ca; Mon, 09 Oct 2006 09:40:10 0300
Date: Mon, 9 Oct 2006 11:14:34 +0100 (BST)
From: Richard Garner
To: categories@mta.ca
Subject: categories: Reflexive coequalizers
MIMEVersion: 1.0
ContentType: TEXT/PLAIN; charset=USASCII; format=flowed
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: O
XStatus:
XKeywords:
XUID: 7
Dear categorists,
I have a proof that the indiscrete category functor
Set > Cat preserves reflexive coequalizers which,
although straightfoward, uses the explicit
description of colimits in Cat. Is this necessary,
or can I deduce the result from general
principles?
[Also, I'm sure this result must appear somewhere
but I can't find a reference for it. If anyone
knows of one, I'd be grateful.]
Many thanks,
Richard
From rrosebru@mta.ca Mon Oct 9 21:26:34 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Mon, 09 Oct 2006 21:26:34 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GX5Pl0005JvRR
for categorieslist@mta.ca; Mon, 09 Oct 2006 21:24:09 0300
Date: Mon, 09 Oct 2006 11:36:46 +0100
To: categories@mta.ca
From: Jorge Picado
Subject: categories: CT2007  first announcement
MimeVersion: 1.0
ContentType: text/plain; charset="iso88591"; format=flowed
ContentTransferEncoding: quotedprintable
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: RO
XStatus:
XKeywords:
XUID: 8
CT2007
INTERNATIONAL CATEGORY THEORY CONFERENCE
Hotel Tivoli Almansor, Carvoeiro (Algarve), Portugal
1723 June 2007
In the tradition of previous meetings held in White Point (2006), Vancouver=
=20
(2004), Como (2000), Coimbra (1999), Vancouver (1997), Halifax (1995),=20
Tours (1994), Isle of Thorns (1992), Montreal (1991) and Como (1990), a=20
Conference on Category Theory will be held in Hotel Tivoli Almansor=20
(http://www.algarvetivolialmansor.com/), Carvoeiro, a village near the sea=
=20
in the region of Algarve (south of Portugal), from June 17 until June 23,=20
2007. We will take this occasion to celebrate the 70th birthday of F.=20
William Lawvere.
The arrival day is Sunday June 17. The scientific programme will begin=20
Monday morning, June 18, and will finish before lunch on Saturday June 23.=
=20
The programme will consist of conferences delivered by invited speakers and=
=20
contributed talks.
Scientific Committee:
Samson Abramsky (Oxford, UK)
Jir=ED Ad=E1mek (Braunschweig, Germany)
Francis Borceux (Louvain, Belgium)
George Janelidze (Cape Town, South Africa)
Steven Lack (Sydney, Australia)
Michael Makkai (Montreal, Canada)
Manuela Sobral (Coimbra, Portugal)
Ross Street (Sydney, Australia)
Walter Tholen (Toronto, Canada)
Updated information will be provided in the conference web page=20
http://www.mat.uc.pt/~categ/ct2007/
The Organizing Committee,
Diana Rodelo, University of Algarve (drodelo@ualg.pt)
Manuela Sobral, University of Coimbra (sobral@mat.uc.pt)
Maria Manuel Clementino, University of Coimbra (mmc@mat.uc.pt)
Jorge Picado, University of Coimbra (picado@mat.uc.pt)
Lurdes Sousa, IPViseu (sousa@infante.ipv.pt)
Maria Jo=E3o Ferreira, University of Coimbra (mjrf@mat.uc.pt)
Gon=E7alo Gutierres, University of Coimbra (ggutc@mat.uc.pt)
From rrosebru@mta.ca Mon Oct 9 21:26:34 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Mon, 09 Oct 2006 21:26:34 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GX5OG0005DQ2D
for categorieslist@mta.ca; Mon, 09 Oct 2006 21:22:36 0300
Date: Mon, 9 Oct 2006 14:37:24 +0100 (BST)
From: "Prof. Peter Johnstone"
To: categories@mta.ca
Subject: categories: Re: Reflexive coequalizers
InReplyTo:
MessageID:
References:
MIMEVersion: 1.0
ContentType: TEXT/PLAIN; charset=USASCII
Sender: catdist@mta.ca
Precedence: bulk
Status: O
XStatus:
XKeywords:
XUID: 9
On Mon, 9 Oct 2006, Richard Garner wrote:
>
> Dear categorists,
>
> I have a proof that the indiscrete category functor
> Set > Cat preserves reflexive coequalizers which,
> although straightfoward, uses the explicit
> description of colimits in Cat. Is this necessary,
> or can I deduce the result from general
> principles?
>
It certainly follows from the fact that reflexive coequalizers
commute with finite products in Set (or in any cartesian closed
category). This is a result that some people attribute to me,
since the first place it was explicitly written down seems to
have been my PhD thesis, though I'm sure it was known well
before that.
Peter Johnstone
From rrosebru@mta.ca Mon Oct 9 21:26:34 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Mon, 09 Oct 2006 21:26:34 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GX5RV0005QjVd
for categorieslist@mta.ca; Mon, 09 Oct 2006 21:25:58 0300
Date: Mon, 9 Oct 2006 16:47:42 +0200 (CEST)
From: Jiri Adamek
To: categories@mta.ca
Subject: categories: Re: Reflexive coequalizers
MIMEVersion: 1.0
ContentType: TEXT/PLAIN; charset=USASCII
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: O
XStatus:
XKeywords:
XUID: 10
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
On Mon, 9 Oct 2006, Richard Garner wrote:
>
> I have a proof that the indiscrete category functor
> Set > Cat preserves reflexive coequalizers which,
> although straightfoward, uses the explicit
> description of colimits in Cat. Is this necessary,
> or can I deduce the result from general
> principles?
>
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
This is a nice example of an algebraically exact functor:
for varieties Alg T, where T is an algebraic theory (and
Alg T is the category of all finiteproduct preserving
functors in [T, Set]), all theory morphisms F: T > S
induce functors Alg F: Alg S > Alg T given by precomposing
with F; they are called algebraically exact. These are precisely
the right adjoints between varieties which preserve sifted
colimits and reflexive coequalizers are special sifted colimits.
This all is a part of the duality between varieties and algebraic
theories (described by F.W.Lawvere, J. Rosicky and myself, Algebra
Universalis 49 (2003), 145).
Consider the "obvious" algebraic theory S of Set, the dual of
finite sets, and the "obvious" theory C of Cat, the dual of
finitely presentable cats. The functor F: C > S which forgets
morphisms induces the indiscrete category functor as Alg F.
From rrosebru@mta.ca Mon Oct 9 21:28:46 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Mon, 09 Oct 2006 21:28:46 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GX5U20005bmMk
for categorieslist@mta.ca; Mon, 09 Oct 2006 21:28:34 0300
From: "George Janelidze"
To:
Subject: categories: Re: Reflexive coequalizers
Date: Mon, 9 Oct 2006 20:40:20 +0200
MIMEVersion: 1.0
ContentType: text/plain;charset="iso88591"
ContentTransferEncoding: 7bit
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: O
XStatus:
XKeywords:
XUID: 11
Dear Richard,
If we were asking the same question about the category SimplSet of
simplicial sets instead of Cat, the answer would be obvious since:
(*) The functor Set > Set sending X to X^n preserves reflexive
coequalizers for each natural n. This (very simple) fact should be
considered as well known since it is involved in one of several wellknown
proofs of monadicity of varieties of universal algebras over Set.
(**) Since SimplSet is a Setvalued functor category, all colimits in it
reduce to colimits in Set.
For those who are familiar with the standard adjunction between SimplSet and
Cat, the result for SimplSet will immediately imply the result for Cat
(since the fundamental category functor being the left adjoint in that
adjunction preserves all colimits and obviously sends "indiscrete simplicial
sets" to indiscrete categories).
One could also use various (not too much) truncated simplicial sets instead
of the simplicial sets of course (e.g. what I once called "precategories").
I mean, I do not remember any reference, but I would not need the explicit
description of colimits in Cat.
George Janelidze
 Original Message 
From: "Richard Garner"
To:
Sent: Monday, October 09, 2006 12:14 PM
Subject: categories: Reflexive coequalizers
>
> Dear categorists,
>
> I have a proof that the indiscrete category functor
> Set > Cat preserves reflexive coequalizers which,
> although straightfoward, uses the explicit
> description of colimits in Cat. Is this necessary,
> or can I deduce the result from general
> principles?
>
> [Also, I'm sure this result must appear somewhere
> but I can't find a reference for it. If anyone
> knows of one, I'd be grateful.]
>
> Many thanks,
>
> Richard
>
>
>
From rrosebru@mta.ca Mon Oct 9 21:30:11 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Mon, 09 Oct 2006 21:30:11 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GX5VP0005iZIV
for categorieslist@mta.ca; Mon, 09 Oct 2006 21:29:59 0300
Date: Mon, 9 Oct 2006 21:09:46 +0100 (BST)
From: Richard Garner
To: categories@mta.ca
Subject: categories: Re: Reflexive coequalizers
MIMEVersion: 1.0
ContentType: TEXT/PLAIN; charset=USASCII; format=flowed
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: O
XStatus:
XKeywords:
XUID: 12
Ah yes, I see now. I had observed that the
underlying diagram of indiscrete graphs was still a
coequalizer  which unfortunately is to truncate
one's simplicial sets a little too much! Many
thanks for the enlightenment.
Richard
On 09 October 2006 20:40 George Janelidze wrote:
> Dear Richard,
>
> If we were asking the same question about the category SimplSet of
> simplicial sets instead of Cat, the answer would be obvious since:
>
> (*) The functor Set > Set sending X to X^n preserves reflexive
> coequalizers for each natural n. This (very simple) fact should be
> considered as well known since it is involved in one of several wellknown
> proofs of monadicity of varieties of universal algebras over Set.
>
> (**) Since SimplSet is a Setvalued functor category, all colimits in it
> reduce to colimits in Set.
>
> For those who are familiar with the standard adjunction between SimplSet and
> Cat, the result for SimplSet will immediately imply the result for Cat
> (since the fundamental category functor being the left adjoint in that
> adjunction preserves all colimits and obviously sends "indiscrete simplicial
> sets" to indiscrete categories).
>
> One could also use various (not too much) truncated simplicial sets instead
> of the simplicial sets of course (e.g. what I once called "precategories").
>
> I mean, I do not remember any reference, but I would not need the explicit
> description of colimits in Cat.
>
> George Janelidze
>
>  Original Message 
> From: "Richard Garner"
> To:
> Sent: Monday, October 09, 2006 12:14 PM
> Subject: categories: Reflexive coequalizers
>
>
>>
>> Dear categorists,
>>
>> I have a proof that the indiscrete category functor
>> Set > Cat preserves reflexive coequalizers which,
>> although straightfoward, uses the explicit
>> description of colimits in Cat. Is this necessary,
>> or can I deduce the result from general
>> principles?
>>
>> [Also, I'm sure this result must appear somewhere
>> but I can't find a reference for it. If anyone
>> knows of one, I'd be grateful.]
>>
>> Many thanks,
>>
>> Richard
>>
>>
>>
>
>
From rrosebru@mta.ca Tue Oct 10 22:08:33 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Tue, 10 Oct 2006 22:08:33 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GXSPr0005gjUh
for categorieslist@mta.ca; Tue, 10 Oct 2006 21:57:48 0300
Subject: categories: Paper: The Euler characteristic of a category
From: Tom Leinster
To: categories@mta.ca
ContentType: text/plain
Date: Tue, 10 Oct 2006 10:36:18 +0100
MimeVersion: 1.0
ContentTransferEncoding: 7bit
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: O
XStatus:
XKeywords:
XUID: 13
The following paper is available. It is the full version of the talk I
gave at CT06.
"The Euler characteristic of a category"
The Euler characteristic of a finite category is defined and shown to be
compatible with Euler characteristics of other types of object,
including orbifolds. A formula is proved for the cardinality of a
colimit of sets, generalizing the classical inclusionexclusion formula.
Both rest on a generalization of MobiusRota inversion from posets to
categories.
http://arxiv.org/abs/math.CT/0610260
Best wishes,
Tom

Tom Leinster
From rrosebru@mta.ca Tue Oct 10 22:08:33 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Tue, 10 Oct 2006 22:08:33 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GXSRh0005rBV7
for categorieslist@mta.ca; Tue, 10 Oct 2006 21:59:41 0300
Date: Tue, 10 Oct 2006 13:48:06 0700
From: Ashish Tiwari
To: tiwari@csl.sri.com
Subject: categories: RTA'07: First Call for Papers
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: O
XStatus:
XKeywords:
XUID: 14
************************************
* *
* RTA'07 FIRST CALL FOR PAPERS *
* *
************************************
http://www.lsv.enscachan.fr/rdp07/rta.html
June 2628, 2007
Paris, France
The 18th International Conference on Rewriting Techniques and Applications
(RTA'07) is organized as part of the Federated Conference on Rewriting,
Deduction, and Programming (RDP'07), which comprises, in addition to RTA'07=
,
the conference on Typed Lambda Calculi and Applications (TLCA'07) and eight
workshops (HOR, PATE, RULE, SecReT, UNIF, WFLP, WRS, and WST).
IMPORTANT DATES:
Jan 26, 2007: Deadline for electronic submission of title and abstract
Jan 31, 2007: Deadline for electronic submission of papers
Apr 02, 2007: Notification of acceptance of papers
Apr 23, 2007: Deadline for final versions of accepted papers
RTA is the major forum for the presentation of research on all aspects of
rewriting. Typical areas of interest include (but are not limited to):
* Applications: case studies; rulebased (functional and logic) programmin=
g;
symbolic and algebraic computation; theorem proving; system synthesis an=
d
verification; analysis of cryptographic protocols; proof checking; reaso=
ning
about programming languages and logics; program transformation;
* Foundations: matching and unification; narrowing; completion techniques;
strategies; constraint solving; explicit substitutions; tree automata;
termination; combination;
* Frameworks: string, term, graph, and proof rewriting; lambdacalculus an=
d
higherorder rewriting; proof nets; constrained rewriting/deduction;
categorical and infinitary rewriting; integration of decision procedures=
;
* Implementation: compilation techniques; parallel execution; rewrite tool=
s;
termination checking;
* Semantics: equational logic; rewriting logic; rewriting models of progra=
ms.
BEST PAPER AWARD: An award is given to the best paper or papers as decided =
by
the program committee.
RTA'07 PROGRAM COMMITTEE CHAIR:
* Franz Baader (Dresden, Germany)
RTA'07 PROGRAM COMMITTEE:
* Alessandro Armando (Genova, Italy)
* Franz Baader (Dresden, Germany)
* Roberto Di Cosmo (Paris, France)
* J=FCrgen Giesl (Aachen, Germany)
* Deepak Kapur (Albuquerque, USA)
* H=E9l=E8ne Kirchner (Nancy, France)
* Barbara K=F6nig (Duisburg, Germany)
* Salvador Lucas (Valencia, Spain)
* Narciso Mart=EDOliet (Madrid, Spain)
* Tobias Nipkow (Munich, Germany)
* Femke van Raamsdonk (Amsterdam, The Netherlands)
* Aaron Stump (St. Louis, USA)
* Sophie Tison (Lille, France)
* Ralf Treinen (Cachan, France)
RTA'07 CONFERENCE CHAIRS:
* Ralf Treinen (Cachan, France)
* Xavier Urbain (Paris, France)
RTA PUBLICITY CHAIR:
* Ashish Tiwari (Menlo Park, USA)
RTA'07 SUBMISSIONS:
Submissions must be original and not submitted for publication elsewhere.
Submission categories include regular research papers and system descriptio=
ns.
Problem sets and submissions describing interesting applications of rewriti=
ng
techniques are also welcome. The page limit for submissions is 15 pages in
Springer LNCS style (10 pages for system descriptions). The submission Web
page will be made available beginning of December. As usual, the proceeding=
s
of RTA'07 will be published in the Springer LNCS series.
Please consult the RTA'07 conference Web page for further information:
http://www.lsv.enscachan.fr/rdp07/rta.html
From rrosebru@mta.ca Wed Oct 11 14:06:24 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Wed, 11 Oct 2006 14:06:24 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GXhQG0004pL8k
for categorieslist@mta.ca; Wed, 11 Oct 2006 13:59:12 0300
Date: Wed, 11 Oct 2006 13:02:09 0400 (EDT)
From: Richard Blute
To: categories@mta.ca
Subject: categories: Octoberfest schedule
MIMEVersion: 1.0
ContentType: TEXT/PLAIN; charset=USASCII
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: O
XStatus:
XKeywords:
XUID: 15
Hi everyone,
Here is the schedule for Octoberfest 06.
Abstracts will appear on the website
shortly, which can be found at
http://www.site.uottawa.ca/~phil/lfc/
cheers
Rick Blute
Saturday, October 21st
8:459:15 Registration and Welcome
9:159:45 Robin Cockett (Calgary)
9:5010:20 Pieter Hofstra (Calgary)
10:2010:50 Break
10:5011:20 Derek Wise (UC Riverside)
11:2511:55 Eric Paquette (UQAM)
12:0012:30 Benoit Valiron (Dalhousie)
12:302:00 Lunch
2:003:00 Plenary SpeakerBen Steinberg (Carleton)
3:003:30 Break
3:304:00 Jonathan Scott (Ottawa)
4:054:35 PaulEugene Parent (Ottawa)
4:405:20 Nick Gurski (Yale)
5:255:55 Gabor Lukacs (Manitoba)
Sunday, October 22nd
9:009:30 Bob Rosebrugh (Mount Allison)
9:3510:05 Marta Bunge (McGill)
10:1010:40 Brian Redmond (Ottawa)
10:4011:10 Break
11:1011:40 Michael Winter (Brock)
11:4512:15 Fred Linton (Wesleyan)
12:2012:50 Jim Lambek (McGill)
Titles (abstracts will appear on website)
++++++
Robin CockettSeely categories revisited
Pieter HofstraModels of more than the lambda calculus
Derek WiseVolumetric Field Theory
Eric PaquetteThe classical world from quantum theory
Benoit ValironOn a fully abstract model for a quantum linear lambda calculus
Ben SteinbergOrdered 2complexes and inverse semigroups
Jonathan ScottOperads and iterated loop spaces
PaulEugene ParentTowards an adjoint to a ConnesMoscovici construction
Nick GurskiEckmanHilton arguments in dimensions 1 and 2
Gabor LukacsDuality theory of locally precompact groups
Bob RosebrughImplementing database design categorically (System demonstration)
Marta BungeLocally quasiconnected toposes
Brian RedmondSoft linear logic
Michael WinterCardinality in allegories
Fred LintonOn Algebras over the Banach unit disc monad
Jim LambekTowards a Feynman category for the standard model.

From rrosebru@mta.ca Fri Oct 13 12:48:11 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Fri, 13 Oct 2006 12:48:11 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GYP8U0005vtGi
for categorieslist@mta.ca; Fri, 13 Oct 2006 12:39:46 0300
Date: Thu, 12 Oct 2006 22:25:04 0500 (CDT)
From: "Francisco Marmolejo (314)"
To: categories@mta.ca
Subject: categories: Leopoldo Roman
MIMEVersion: 1.0
ContentType: TEXT/PLAIN; charset=ISO88591
ContentTransferEncoding: quotedprintable
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: RO
XStatus:
XKeywords:
XUID: 16
Dear Category theorists,
It is with great sadness that I must tell you of Leopoldo Roman's untimely
death. I do not have any details at the moment, all I know is that this
happened earlier today (Wednesday). Leopoldo was the first to seriously
talk to me about Category Theory, and he was the one that sent me in the
direction of Dalhousie University; I will thank him for ever for both.
Francisco Marmolejo
From rrosebru@mta.ca Sun Oct 15 09:51:29 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Sun, 15 Oct 2006 09:51:29 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GZ5KI00012t50
for categorieslist@mta.ca; Sun, 15 Oct 2006 09:42:46 0300
Date: Sun, 15 Oct 2006 09:38:19 0300 (ADT)
From: Bob Rosebrugh
To: categories
Subject: categories: Power outage in Buffalo
MIMEVersion: 1.0
ContentType: TEXT/PLAIN; charset=USASCII
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: RO
XStatus:
XKeywords:
XUID: 18
Dear Colleagues,
Bill Lawvere has asked me to let you know that he will be unable to
respond to email for up to eight days due to a power outage.
As some of you know, Buffalo experienced an unseasonable and severe snow
storm Thursday night while leaves were still on trees. The resulting
damage to electrical service will take several days to repair. Telephones
are working and all are reported safe, if not warm.
Best wishes, Bob Rosebrugh
From rrosebru@mta.ca Sun Oct 15 21:07:08 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Sun, 15 Oct 2006 21:07:08 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GZFwd0004oNSd
for categorieslist@mta.ca; Sun, 15 Oct 2006 21:03:03 0300
Date: Sun, 15 Oct 2006 14:23:37 0400 (EDT)
From: Michael Barr
To: Categories list
Subject: categories: Available on my ftp site
MIMEVersion: 1.0
ContentType: TEXT/PLAIN; charset=USASCII
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: O
XStatus:
XKeywords:
XUID: 19
I have redone my ftp site to a certain extent. Available now are the
latest version of TTT (a small number of corrections, plus one place where
some incomprehensible equations were replaced by equivalent diagrams) and
a couple of my older papers that I found on Jstor. I really do not
understand the copyright issues on the latter. Clearly Jstor deserves
something (but they earned a fee when I downloaded them). In the olden
days (say 25 years ago and older) the publishers did not ask for any
copyright form signed, but just registered a copyright. They act as if I
have no rights, but I believe that without a piece of paper, they cannot
really stop me. I have not signed over my rights since before 1995
(including two papers in 1995 in JPAA, where I gave them only a
righttoprint). So there is a ten or 15 year period where I really did
sign over the copyright. So be warned. Incidentally, Charles and I have
full rights to TTT and this is posted with Charles's permission.
My ftp site is
ftp.math.mcgill.ca/pub/barr/pdffiles
Michael
From rrosebru@mta.ca Mon Oct 16 12:18:56 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Mon, 16 Oct 2006 12:18:56 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GZU7M0004ZNFN
for categorieslist@mta.ca; Mon, 16 Oct 2006 12:11:04 0300
From: "Erzsebet CsuhajVarju"
To:
Subject: categories: FCT 2007  First Announcement
Date: Mon, 16 Oct 2006 14:20:10 +0200
MIMEVersion: 1.0
ContentType: text/plain; charset="iso88592"
ContentTransferEncoding: quotedprintable
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: O
XStatus:
XKeywords:
XUID: 20
__________________________________________________________
FIRST ANNOUNCEMENT
____________________________________________________________
=20
CALL FOR PAPERS
FCT 2007
16th International Symposium on Fundamentals of Computation Theory
Budapest, Hungary
August 2730, 2007
URL: http://www.conferences.hu/fct2007
Email: fct2007@conferences.hu
ORGANIZING INSTITUTIONS:
Computer and Automation Research Institute, Hungarian Academy of =
Sciences
Department of Computer Science, University of Szeged
The Symposium on Fundamentals of Computation Theory was established in
1977 for researchers interested in all aspects of theoretical computer
science, in particular in algorithms, complexity, formal and logical
methods. It is a biennial series of conferences previously held in =
Poznan
(1977), WendischRietz (1979), Szeged (1981), Borgholm (1983), Cottbus
(1985), Kazan (1987), Szeged (1989), GosenBerlin (1991), Szeged =
(1993),
Dresden (1995), Krak=F3w (1997), Iasi (1999), Riga (2001), Malm=F6 =
(2003), and
L=FCbeck (2005).
TOPICS:
Authors are invited to submit papers presenting original unpublished
research in all areas of theoretical computer science.
Topics of interest include (but not limited to):
automata and formal languages
design and analysis of algorithms
computational and structural complexity
semantics
logic, algebra and categories in computer science
circuits and networks
learning theory
specification and verification
parallel and distributed systems
concurrency theory
cryptography and cryptographic protocols
approximation and randomized algorithms
computational geometry
quantum computation and information
bioinspired computation
INVITED SPEAKERS:=20
Ahmed Bouajjani (Paris, France)
Oscar H. Ibarra (Santa Barbara, CA, USA)
L=E1szl=F3 Lov=E1sz (Budapest, Hungary)
Philip Scott (Ottawa, Canada)
STEERING COMMITTEE:
Bogdan Chlebus (Warsaw/Denver, Poland/USA)
Zolt=E1n =C9sik (Szeged, Hungary)
Marek Karpinski (Bonn, Germany)  chair
Andrzej Lingas (Lund, Sweden)
Miklos Santha (Paris, France)
Eli Upfal (Providence, RI, USA)
Ingo Wegener (Dortmund, Germany)
PROGRAMME COMMITTEE:
Jiri Adamek (Braunschweig, Germany)
Giorgio Ausiello (Rome, Italy)
Jean Berstel (MarnelaVall=E9e, France)
Flavio Corradini (Camerino, Italy)
Erzs=E9bet CsuhajVarj=FA (Budapest, Hungary)  cochair
Zolt=E1n =C9sik (Szeged, Hungary)  cochair
Jozef Gruska (Brno, Czech Republic)
Masahito Hasegawa (Kyoto, Japan)
Juraj Hromkovic (Zurich, Switzerland)
Anna Ingolfsdottir (Reykjavik, Iceland)
Masami Ito (Kyoto, Japan)
Frederic Magniez (Paris, France)
Catuscia Palamidessi (Palaiseau, France)
Gheorghe Paun (Bucharest/Seville, Romania/Spain)
JeanEric Pin (Paris, France)
R. Ramanujam (Chennai, India)
Alexander Rabinovich (TelAviv, Israel)
Grzegorz Rozenberg (Leiden, The Netherlands)
Wojciech Rytter (Warsaw, Poland)
Arto Salomaa (Turku, Finland)
David A. Schmidt (Manhattan, KS, USA)
Alex Simpson (Edinburgh, UK)
Michael Sipser (Cambridge, MA, USA)
Colin Stirling (Edinburgh, UK)
Howard Straubing (Boston, MA, USA)
Gy=F6rgy Tur=E1n (Chicago, IL, USA)
Thomas Wilke (Kiel, Germany)
SUBMISSION:
Authors are invited to submit a draft of a full paper with at most 12
pages in LNCS style.
The paper should provide sufficient detail to allow the Programme =
Committee
to evaluate its validity, quality, and relevance. If appropriate, then
detailed proofs can be attached as an appendix. Simultaneous submission =
to
other conferences with published proceedings is not allowed.
Only electronic submissions are accepted, PLEASE FOLLOW the =
INSTRUCTIONS
on the CONFERENCE WEB SITE: http://www.conferences.hu/fct2007
IMPORTANT DATES:
Deadline for submissions: March 5, 2007
Notification to the authors: April 20, 2007
Final version : May 20, 2007
Symposium: August 2730, 2007
PROCEEDINGS:
We anticipate that the proceedings will be published in the Lecture =
Notes
in Computer Science series of Springer Verlag, and that
a special issue of Theoretical Computer Science will be devoted to
selected papers presented at the conference.
PLEASE CONTACT:
Programme:
Dr. Erzs=E9bet CsuhajVarj=FA
Computer and Automation Research Institute
Hungarian Academy of Sciences
H1111, Budapest
Kende u.1317, Hungary
Email: csuhaj@sztaki.hu
LOCAL ARRANGEMENTS:
Mrs. Mariann Kindl
Computer and Automation Research Institute
Hungarian Academy of Sciences
H1111 Kende u.1317, Hungary
Phone: +3612796188
Fax: +3613869378
Email: fct2007@conferences.hu
From rrosebru@mta.ca Tue Oct 17 08:25:37 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Tue, 17 Oct 2006 08:25:37 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GZn0N0007M34o
for categorieslist@mta.ca; Tue, 17 Oct 2006 08:21:07 0300
To: categories@mta.ca
Subject: categories: Lawveremetrics and Banach spaces
From: Paul Taylor
Date: Tue, 17 Oct 2006 11:19:21 +0100
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: O
XStatus:
XKeywords:
XUID: 21
There is a widely cited paper by Bill Lawvere called "Metric spaces,
generalised logic and closed catgeories" in which he shows how metric
spaces are examples of enriched categories. The enriching structure
consists of the nonnegative reals, with "greater than" as the morphisms
and addition as the tensor product. Using this one can generalise
the notion of metric space by substituting other structures in place of R.
An obvious question is  what happens when we follow through this idea
for Banach spaces? What becomes of the $\ell_p$ spaces and of dual spaces?
Do families of seminorms naturally fit into this pattern?
Paul Taylor
From rrosebru@mta.ca Tue Oct 17 20:13:34 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Tue, 17 Oct 2006 20:13:34 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GZy1O0006guE0
for categorieslist@mta.ca; Tue, 17 Oct 2006 20:06:54 0300
Date: Tue, 17 Oct 2006 10:46:47 0400 (EDT)
From: Michael Barr
To: categories@mta.ca
Subject: categories: Re: Lawveremetrics and Banach spaces
MIMEVersion: 1.0
ContentType: TEXT/PLAIN; charset=USASCII
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: O
XStatus:
XKeywords:
XUID: 22
I would like to remind the categorical community that Lawvere's paper is
now generally available as a TAC Reprints #1.
On Tue, 17 Oct 2006, Paul Taylor wrote:
> There is a widely cited paper by Bill Lawvere called "Metric spaces,
> generalised logic and closed catgeories" in which he shows how metric
> spaces are examples of enriched categories. The enriching structure
> consists of the nonnegative reals, with "greater than" as the morphisms
> and addition as the tensor product. Using this one can generalise
> the notion of metric space by substituting other structures in place of R.
>
> An obvious question is  what happens when we follow through this idea
> for Banach spaces? What becomes of the $\ell_p$ spaces and of dual spaces?
> Do families of seminorms naturally fit into this pattern?
>
> Paul Taylor
>
>
>
From rrosebru@mta.ca Wed Oct 18 19:30:52 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Wed, 18 Oct 2006 19:30:52 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GaJrf0002HmS5
for categorieslist@mta.ca; Wed, 18 Oct 2006 19:26:19 0300
Date: Tue, 17 Oct 2006 11:17:03 +0330
From: "darush aghababayee.dehkordi"
Subject: categories: from darush.aghababayeedehkordi
MIMEVersion: 1.0
To: categories
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: RO
XStatus:
XKeywords:
XUID: 23
in Rmodule category congugate of aR module as same as opposit of this
Rmodule
but i dont see general definition of conjugation of a category
conjugatify of an rmodule is dulify of rmodule
(this example exist in homologybook of sunders maclane)
darush.aghababayeedehkordi
From rrosebru@mta.ca Wed Oct 18 19:30:52 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Wed, 18 Oct 2006 19:30:52 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GaJtQ0002Pt57
for categorieslist@mta.ca; Wed, 18 Oct 2006 19:28:08 0300
Date: Wed, 18 Oct 2006 11:17:41 +0200
From: metere@mat.unimi.it
To: categories@mta.ca
Subject: categories: Milan Workshop in categorical algebra: Third announcement
MIMEVersion: 1.0
ContentType: text/plain; charset=ISO88591
ContentTransferEncoding: 8bit
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: O
XStatus:
XKeywords:
XUID: 24
********************************************
* INTERNAL ACTIONS and INTERNAL STRUCTURES *
* *
* WORKSHOP in CATEGORICAL ALGEBRA *
* *
********************************************
Third announcement: Important Notice and Schedule.
Dear Colleagues, the Workshop will be held at the Department
of Mathematics, via Saldini 50, Milano.
IMPORTANT NOTICE.
If you have registered using the webform, and you did not
receive ANY confirmation Email, maybe your registration have been lost
in the internet. So, if this is the case, please send us an
Email to "milanworkshop.06@gmail.com".
Here is a preliminary program.
Thursday 26th October 2006
9:00  9.45 > registration
9:45  10:30 > Marino Gran
"Internal groupoids and crossed modules" (Ia)
10:45  11:15 > coffee break
11:15  12:15 > Marino Gran (Ib)
13:00  14:30 > Lunch
14:30  15:00 > Communications
15:15  16:00 > Dominique Bourn
"Split extension classifier, actions representation
and associated classification properties" (Ia)
16:15  16:45 > coffee break
16:45  17:45 > Dominique Bourn (Ib)
18.00  18:30 > Communications
Friday 27th October
9:30  10:15 > Marino Gran (IIa)
10:30  11:00 > coffee break
11:00  12:00 > Marino Gran (IIb)
13:00  14:30 > Lunch
14:30  15:00 > Communications
15:15  16:00 > Dominique Bourn (IIa)
16:15  16:45 > coffee break
16:45  17:45 > Dominique Bourn (IIb)
18.00  18:30 > Communications
Saturday 28th October
9:30  10:15 > Enrico Vitale
"Schreier theory and obstruction theory via categorical groups" (a)
10:30  11:00 > coffee break
11:00  12:00 > Enrico Vitale (b)
The web pages
http://users.mat.unimi.it/users/mantovani/workshopMi06.htm
contain the abstracts of the lectures.
Best regards,
Stefano Kasangian
Sandra Mantovani
Beppe Metere

From rrosebru@mta.ca Mon Oct 23 09:09:24 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Mon, 23 Oct 2006 09:09:24 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GbyUm0003axFj
for categorieslist@mta.ca; Mon, 23 Oct 2006 09:01:32 0300
Date: Sun, 22 Oct 2006 18:26:06 0700
From: John Baez
To: categories
Subject: categories: cartesian closed categories and holodeck games
MimeVersion: 1.0
ContentType: text/plain; charset=usascii
ContentDisposition: inline
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: O
XStatus:
XKeywords:
XUID: 26
Dear Categorists 
This contains a popularization of Dolan and Trimble's work on
game theory and the free cartesian closed category on one object.
It also has links to more detais.
Best,
jb
....................................................................
Also available as http://math.ucr.edu/home/baez/week240.html
October 22, 2006
This Week's Finds in Mathematical Physics (Week 240)
John Baez
[stuff deleted]
In my seminar this year, we're focusing on two topics: quantization
and cohomology, and classical versus quantum computation. I'm
trying out something new: not only are the notes available on the
web, there's also a blog entry for each class, where you can ask
questions, make comments and correct my mistakes!
4) John Baez, Fall 2006 seminars: Quantization and cohomology, and
Classical versus quantum computation. Notes by Derek Wise, homeworks
and blog entries available at http://math.ucr.edu/home/baez/qgfall2006/
I hope more people blend teaching with blogging. It's not too much
work if someone with legible handwriting takes notes and the lectures
can actually be followed from the notes. You can use blogging to
interactively teach people scattered all over the planet!
This week, James Dolan gave a talk on something he's been working on for a
long time: games and cartesian closed categories. Lately he's been
making a lot of progress with Todd Trimble. Let me introduce you to
what they did, because it's really cool.
Let's play a game. I have a set X in my pocket, and I'm not telling
you what it is. Can you pick an element of X in a systematic way?
No, of course not: you don't have enough information. X could even
be empty, in which case you're clearly doomed! But even if it's nonempty,
if you don't know anything about it, you can't pick an element in a
systematic way.
So, you lose.
Okay, let's play another game. Can you pick an element of
X^X
in a systematic way? Here A^B means the set of functions from B to A.
So, I'm asking if you can pick a function from X to itself in a systematic
way.
Yes! You can pick the identity function! This sends each element
of X to itself:
x > x
You don't need to know anything about X to describe this function.
X can even be empty.
So, you win.
Are there any other ways to win? No.
Now let's play another game. Can you pick an element of
X^(X^X)
in a systematic way?
An element in here takes functions from X to itself and turns them into
elements of X. When X is the set of real numbers, people call this sort
of thing a "functional", so let's use that term. A functional eats
functions and spits out elements.
You can scratch your head for a while trying to dream up a systematic
way to pick a functional for any set X. But, there's no way.
So, you lose.
Let's play another game. Can you pick an element of
(X^X)^(X^X)
in a systematic way?
An element in here eats functions and spits out functions. When X is
the set of real numbers, people often call this sort of thing an
"operator", so let's use that term.
Given an unknown set X, can you pick an operator in a systematic
way? Sure! You can pick the identity operator. This operator
eats any function from X to itself and spits out the same function.
We can write any function from X to itself as
x > y,
where y is something depending on x. So, we can write the identity
operator as
(x > y) > (x > y)
Anyway: you win.
Are there any other ways to win? Yes! There's an operator that
takes any function and spits out the identity function:
(x > y) > (z > z)
This is a bit funnylooking, but I hope you get what it means: you
put in any function x > y, and out pops the identity function z > z.
This arrow notation is very powerful. It's usually called the
"lambda calculus", since when Church invented it in the 1930s, he
wrote it using the Greek letter lambda instead of an arrow: instead of
x > y
he wrote
lambda x.y
But this just makes things more confusing, so let's not do it.
Are there more ways to win this game? Yes! There's also an operator
that takes any function f from X to itself and "squares" it  in other
words, does it twice. If we write the result as f^2, this operator is
f > f^2
But, we can express this operator without using any special symbol
for squaring. If we write our function f as
(x > y)
and apply it to some element z, we get
(x > y)(z)
So, if we apply f^2 to z, we get
(x > y)((x > y)(z))
So, the function f^2 does this:
z > (x > y)((x > y)(z))
and our squaring operator f > f^2 does this:
(x > y) > (z > (x > y)((x > y)(z)))
This looks pretty complicated. But, it shows that our systematic
way of choosing an element of
(X^X)^(X^X)
can still be expressed using just the lambda calculus.
Now that you know "squaring" is a way to win this particular game,
you'll immediately guess a bunch of other ways: "cubing", and so on.
It turns out all the winning strategies are of this form! We can
list them all using the lambda calculus:
(x > y) > (z > z)
(x > y) > (z > (x > y)(z))
(x > y) > (z > (x > y)((x > y)(z)))
(x > y) > (z > (x > y)((x > y)((x > y)(z))))
etc. Note that the second one is just a longer name for the
identity operator. The longer name makes the pattern clear.
The moral of this game is that all systematic methods for picking
an element of (X^X)^(X^X) for an unknown set X can be written
using the lambda calculus. So, from now on, we'll take this
as our *definition* of a "systematic way".
Now let's play another game. Can you pick an element of
X^(X^(X^X))
in a systematic way?
An element in here eats functionals and spits out elements of X.
So, it's called a "functionalal" on X. At least that's what Jim
calls it.
If I have an unknown set in my pocket, can you pick a functionalal
on this set in a systematic way?
Yes! You just need to pick a recipe that takes functionals on X
and turns them into elements of X. Here's one recipe: take any
functional and evaluate it on the *identity* function, getting
an element of x.
In lambda calculus notation, this recipe looks like this:
((x > y) > z) > ((x > y) > z)(w > w)
Can you think of other ways to win this game? I hope so: there are
infinitely many! Jim and Todd figured out a systematic way to list
them all.
Now let's play another game. Can you pick an element of
X^(X^(X^(X^X)))
in a systematic way? Such a thing eats functionalals and spits out
elements of X, so it's called a "functionalalal".
So, can you find a functionalalal on an unknown set in some systematic
way?
The answer is no: you lose.
How about picking an element of
((X^X)^(X^X))^((X^X)^(X^X))
in a systematic way? Such a thing eats operators and spits out operators,
so it's called an "operatorator".
The answer is yes: there are lots of ways to win this game. The real
challenge is listing them! This is the sort of question Dolan and
Trimble's work answers: for any game of this sort, it lets you list
all the ways to win.
In fact, instead of moving on to functionalators, operatorals,
operatoralatorals, and so on, let me just tell you trick for instantly
deciding which of all these games you can win.
You just take your game, like this:
((X^X)^(X^X))^((X^X)^(X^X))
and evaluate it by setting X = 0. If you get 0, there's no way to
win. If you get 1, there's at least one way to win.
To use this trick, you need to know that
0^0 = 1
This is something they don't teach in school! In analysis, X^Y
can approach anything between 0 and 1 when X and Y approach 0. So,
teachers like to say 0^0 is undefined. But X^X approaches 1 when X > 0.
More importantly, in set theory, A^B stands for the set of functions
from B to A, and the number of elements in this set is
A^B = A^B
When A and B are empty, there's just one function from B to A, namely
the identity. So, for our purposes we should define 0^0 = 1.
Consider the case of functionals, which are elements of X^(X^X).
If we evaluate this at X = 0 we get
0^(0^0) = 0^1 = 0
So, there are no functionals when X is the empty set. So, you can't
pick a functional on a unknown set in a systematic way. That's why
you lose when your game evaluates to 0. It's more interesting to
prove that for games evaluating to 1, there's a way to win.
But we'd really like to understand *all* the ways to win. And for this,
Dolan and Trimble needed the theory of holodeck games.
In Star Trek, the "holodeck" is a virtual reality environment where
you can play various games. On the holodeck, if you regret a move
you made, you can back up to any earlier point in the game and make
a new move.
Actually I'm deviating from the technical specifications of the
holodeck on Star Trek, as explained here:
6) Wikipedia, Holodeck, http://en.wikipedia.org/wiki/Holodeck
So, if you're a Star Trek purist, it's better to imagine a video game
where you can save your game at any state of play, and go back to these
saved games whenever you want. And, you have to imagine being so paranoid
that you *always* save your game before making a move. This allows games
to go on forever, so we only say you have a winning strategy if you can win
in a finite number of moves, no matter what the other player does.
To make this completely precise, we consider twoplayer games where the
players take turns making moves. When a player can't make a move,
they lose. Any such game can be written as a "game tree", like this:
 \/
\  /
\/
In this example, the first player has three choices for her first move.
If she picks the middle branch, the second player has one choice for his
first move. Then the first player has one choice for her second move.
Then the second player has no choice for his second move  so he loses.
So, in this particular example the second player has no winning strategy.
A cool thing about such a game is that we can take its game tree and
turn it into an expression built from some variable X using products
and exponentials. To do this, just put an X at each vertex of the tree
except the root:
X X X
 \/
X X X
\  /
X X X
\/
Then blow on the tree with a strong westerly wind, so strong that the
branches blow away and only the X's are left:
X XX
X X X
X X X
This is just a way of writing an expression built from X using products and
exponentials:
X^X X^(X^X) X^(X^(XX))
Conversely, any such expression can be turned back into a tree, at least
after we simplify it using these rules:
(AB)^C = A^C B^C
(A^B)^C = A^(BC)
For example, consider the set of operators:
(X^X)^(X^X)
If we simplify this, we get
X^(X X^X)
or
X
X X
X
giving the tree
X
/
X X
\ /
X

or in other words
/
\ /

And here's a cool fact: if you take any expression built from X
using products and exponentials, and evaluate it at X = 0, you can
tell which player has a winning strategy for the game described by
the corresponding tree! If you get 1, the second player has a winning
strategy; if you get 0, they don't.
It's pretty easy to prove: try it.
But if you've been paying attention, you'll have noticed something weird.
I've told you TWO ways to get a game from any expression built from X
using products and exponentials. First, the game of systematically
picking an element of the resulting set. Second, the game we get by
turning this expression into a game tree, like I just did.
For *both* these games, you can decide if there's a winning
strategy by evaluating the expression at X = 0.
But are they the same game? No! One is the holodeck version of the other!
Let's look at the familiar example of operators:
(X^X)^(X^X) = X^(X X^X)
This evaluates to 1 at X = 0. So, if we turn it into a tree
/
\ /

we get a game where the second player has a winning strategy.
This game is not very exciting, but it becomes more exciting if you
call it "The Lady or the Tiger". In this game, the first player
has only one first move: he takes the second player to a room
with two doors, corresponding to the two branches of the above tree.
Then it's the second player's turn.
If he opens the left door, a beautiful lady pops out and they instantly
get married and live happily ever after. If he opens the right door,
the first player opens a tiger cage. Then the tiger jumps out and eats
the second player.
In this game, the second player has just ONE winning strategy:
on his first move he should choose the left door.
Next look at the game of defining an element of
(X^X)^(X^X) = X^(X X^X)
using the lambda calculus. We've seen there are INFINITELY MANY
strategies for winning this:
(x > y) > (z > z)
(x > y) > (z > (x > y)(z))
(x > y) > (z > (x > y)((x > y)(z)))
(x > y) > (z > (x > y)((x > y)((x > y)(z))))
and so on. These correspond to 2ndplayer winning strategies
for the *holodeck version* of The Lady or the Tiger.
What are these strategies?
One is just to play the game and win by choosing the left door.
Another is to choose the right door  and then, just when the
tiger is about to eat you, back up and choose the left door!
Another is to choose the right door  and then, just when the
tiger is about to eat you, back up and choose... the right door!
Whoops! Then, when the tiger is about to devour you again, back
up again, and this time choose the left door.
And so on: for each n, there's a strategy where you choose the
right door n times before wising up and choosing the left door.
Now, if you want a really nice math project, ponder the pattern
relating all these strategies to the corresponding lambda calculus
expressions:
(x > y) > (z > z)
(x > y) > (z > (x > y)(z))
(x > y) > (z > (x > y)((x > y)(z)))
(x > y) > (z > (x > y)((x > y)((x > y)(z))))
etc.
Then, figure out how to prove Dolan and Trimble's "Fundamental Theorem".
This sets up a 11 correspondence between winning secondperson
strategies for the holodeck verson of any 2person game, say:
 \/
\  /
\/
and ways of using the lambda calculus to define elements of the
corresponding set:
X^X X^(X^X) X^(X^(XX))
If you get stuck, first try these notes from Dolan's talk, and
then Trimble's more rigorous, technical treatment:
7) James Dolan, Holodeck strategies and cartesian closed categories,
lecture at UCR, notes by John Baez, Oct. 19, 2006, available at
http://math.ucr.edu/home/baez/qgfall2006/f06week03b.pdf
8) Todd Trimble, Holodeck games and CCCs, available at
http://math.ucr.edu/home/baez/trimble/holodeck.html
Dolan's talk also explains some other fun stuff, like how to multiply
and exponentiate games. So, if you read these notes, you'll learn how
to play
chess x go
and
chess^{go}
at least after chess and go have been "improved" so games never last
forever and the last player able to make a move wins.
But, if you're planning to study this stuff, I'd better admit now
that Dolan and Trimble formalize the concept of "systematically
picking an element of an unknown set" with the help of cartesian
closed categories.
A category is "cartesian" if it has finite products  or in other words,
binary products and a terminal object. It's "cartesian closed" if it
also has exponentials. All these terms are carefully defined in the
week 2 and week 3 notes of my classical versus quantum computation course,
so let me just illustrate them with an example: the category of sets.
Here the product A x B of two sets A and B is their usual Cartesian
product. The exponential A^B is the set of functions from B to A.
Any 1element set is a terminal object.
What Dolan and Trimble really study is the "free cartesian closed
category on one object x", which I like to call CCC[x]. Any object
in CCC[x] is built from the object x by means of binary products,
exponentials and the terminal object. For example, we have objects
like this:
x^1 1^(x^x) (x x)^(x 1 x^(x^x))
where I've omitted the times symbols for products.
However, every object is isomorphic to one in "tree form". For example,
the above object is isomorphic to
x x^(x x^(x^x)) x^(x x^(x^x))
which we can draw as a tree:
x x
 /
x x x x
\ /
x x x
\/
Dolan and Trimble consider the set of elements of any object in CCC[x],
where an "element" is a morphism from the terminal object, e.g.
f: 1 > x x^(x x^(x^x)) x^(x x^(x^x))
And, they show these elements are in 11 correspondence with secondplayer
winning strategies for the holodeck version of the game whose tree is
constructed as above.
If we pick any set X, the universal property of CCC[x] gives a functor
F: CCC[x] > Set
This maps elements of any object in CCC[x] to elements of the corresponding
object in Set:
F(f): 1 > X X^(X X^(X^X)) X^(X X^(X^X))
So, the element f gives a "systematic way of picking elements" of
any set built from any arbitrary set X using finite products and
exponentials. There might be *other* things that deserve to be
called "systematic ways of picking elements", but while that's an
interesting question, it's not really the point here.
By the way, in a cartesian closed category, there's a 11 correspondence
between morphisms
f: B > A
and elements
f: 1 > A^B
So, Dolan and Trimble's work really gives a complete description of
objects and morphisms in the free cartesian closed category on one object!
They also can describe *composition* in terms of games, and maybe Jim
will talk about this next Tuesday. So, they have a complete description
of CCC[x] in terms of games.
Now let me give you some references on cartesian closed categories, the
lambda calculus, categorical semantics, and games. It's an interesting
network of subjects.
Categorical semantics was born in Lawvere's celebrated 1963 thesis on
algebraic theories:
9) F. William Lawvere, Functorial Semantics of Algebraic Theories,
Dissertation, Columbia University, 1963. Also available at
available at http://www.tac.mta.ca/tac/reprints/articles/5/tr5abs.html
Semantics deals with theories and their models. Dual to the concept of
semantics is the concept of "syntax", which deals with proofs. In the
case of algebraic theories, the syntax was studied before Lawvere in
the subject called "universal algebra":
10) Stanley Burris and H.P. Sankappanavar, A Course in Universal
Algebra, available at http://www.math.uwaterloo.ca/~snburris/htdocs/ualg.html
Lawvere modernized universal algebra by realizing that an algebraic
theory is just a cartesian category, and a model is a productpreserving
functor from this theory into Set or some other cartesian category 
hence his thesis title, "Functorial Semantics". I explained this in
much more detail back in "week200".
The relevance of all this to computer science becomes visible when we
note that a proof in universal algebra can be seen as a rudimentary form
of computation. The "input" of the computation is a set of assumptions,
while the "output" is the equation to be proved.
Treating proofs as computations may seem strained, but it becomes less
so when we move to richer formalisms which allow for more complex logical
reasoning. One of bestknown of these is the lambda calculus, invented
by Church and Kleene in the 1930s as a model of computation. Any function
computable by the lambda calculus is also computable by a Turing machine,
and according to the ChurchTuring thesis these are all the functions
computable by any sort of systematic process. Moreover, computations in
the lambda calculus can actually be seen as proofs.
The usefulness of this way of thinking was brought out in Landin's
classic paper:
11) P. Landin, A correspondence between ALGOL 60 and Church's
lambdanotation, Comm. ACM 8 (1965), 89101, 158165.
This began a long and fruitful line of research  see for example this:
12) H. Barendregt, The Lambda Calculus, its Syntax and Semantics,
NorthHolland, 1984.
The power of the lambda calculus is evident in the textbook developed for
MIT's introductory course in computer science, which is available online:
13) H. Abelson, G. J. Sussman and J. Sussman, Structure
and Interpretation of Computer Programs, available at
http://wwwmitpress.mit.edu/sicp/
It cites pioneers like Haskell Curry, and it even has a big "lambda"
on the cover!
Students call it "the wizard book", because the cover also features a
picture of a wizard. It's used at over 100 colleges and universities,
and it has spawned a semimythical secret society called The Knights
of the Lambda Calculus, whose selfreferential emblem celebrates the
ability of the lambda calculus to do recursion.
In 1980, Lambek made a great discovery:
14) Joachim Lambek, From lambda calculus to Cartesian closed categories,
in To H. B. Curry: Essays on Combinatory Logic, Lambda Calculus
and Formalism, eds. J. P. Seldin and J. Hindley, Academic Press, 1980,
pp. 376402.
He showed that just as algebraic theories can be regarded as cartesian
categories, theories formulated in the lambda calculus can be regarded
as cartesian closed categories (or CCCs, for short).
Lambek's discovery introduced a semantics for the lambda calculus,
since it lets us to speak of "models" of theories formulated
in the lambda calculus, just as we could for algebraic theories. In
computer programming, the importance of a model is that it gives a
picture of what a program actually accomplishes. A model in the
category of Sets, for example, sends any program to an actual function
between sets.
There's no way to list all the interesting references to CCCs and the
lambdacalculus, but here are some online places to get going on them,
starting out easy and working up to the harder ones:
15) Wikipedia, Lambda calculus, available at
http://en.wikipedia.org/wiki/Lambda_calculus
16) Mark ChuCarroll, Lambda calculus, available at
http://goodmath.blogspot.com/2006/06/lamdacalculusindex.html
Mark ChuCarroll, Category theory, available at
http://scienceblogs.com/goodmath/goodmath/category_theory/
17) Peter Selinger, Lecture notes on the lambda calculus, available
at http://www.mscs.dal.ca/~selinger/papers.html#lambdanotes
18) Phil Scott, Some aspects of categories in computer science,
available at http://www.site.uottawa.ca/~phil/papers/handbook.ps
and here's a classic:
19) Joachim Lambek and Phil Scott, Introduction to Higher Order
Categorical Logic, volume 7 of Cambridge Studies in Advanced Mathematics,
Cambridge U. Press, 1986.
Dolan and Trimble are not the first to study the relation between games
and categories. In the 1970s, Conway invented a wonderful theory of
games and surreal numbers:
20) John H. Conway, On Numbers and Games, Academic Press, New York, 1976.
Second edition: A. K. Peters, Wellesley, Massachusetts, 2001.
21) Elwyn Berlekamp, John H. Conway, Richard Guy, Winning Ways, vols. 12,
Aadmic Press, New York, 1982. Second edition, vols. 14, A. K. Peters,
Wellelsey, Massachusetts, 20012004.
22) Dierk Schleicher and Michael Stoll, An introduction to Conway's games
and numbers, available as math.CO/0410026.
In 1977, Joyal modified Conway's work a bit and related it explicitly
to category theory:
23) Andre Joyal, Remarques sur la theorie des jeux a deux personnes,
Gazette des Sciences Mathematiques du Quebec, Vol I no 4 (1977), 4652.
For an online version in English, try:
24) Andre Joyal, trans. Robin Houston, Remarks on the theory of
twoperson games, 2003. Available at
http://www.ma.man.ac.uk/~rhouston/Joyalgames.ps
I don't know the subsequent history very well  I'm no expert on any
of this stuff!  but by 1990 Martin Hyland was giving lectures on
Conway games and linear logic, and I think this triggered a lot of
work on "game semantics" for logic, where propositions are interpreted
as games and proofs are winning strategies:
25) Samson Abramsky and Radha Jagadeesan, Games and full completeness
for multiplicative linear logic, Journal of Symbolic Logic, 59 (1994),
543  574. Also available at http://citeseer.ist.psu.edu/564168.html
26) Martin Hyland and C.H. L. Ong, Fair games and full completeness
for multiplicative linear logic without the MIXrule, available at
http://citeseer.ist.psu.edu/hyland93fair.html
For a good introduction to all this work, try these:
27) Robin Houston, Categories of Games, M.Sc. thesis, U. Manchester, 2003.
Available at http://www.cs.man.ac.uk/~houstorx/msc.pdf
Robin Houston, Mathematics of Games, continuation report, U. Manchester,
2004. Available at http://www.cs.man.ac.uk/~houstorx/continuation.pdf
Finally, for more on categories, intuitionistic logic, and linear logic,
see "week227".

Previous issues of "This Week's Finds" and other expository articles on
mathematics and physics, as well as some of my research papers, can be
obtained at
http://math.ucr.edu/home/baez/
For a table of contents of all the issues of This Week's Finds, try
http://math.ucr.edu/home/baez/twfcontents.html
A simple jumpingoff point to the old issues is available at
http://math.ucr.edu/home/baez/twfshort.html
If you just want the latest issue, go to
http://math.ucr.edu/home/baez/this.week.html
From rrosebru@mta.ca Mon Oct 23 21:00:50 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Mon, 23 Oct 2006 21:00:50 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1Gc9fO00021wR4
for categorieslist@mta.ca; Mon, 23 Oct 2006 20:57:14 0300
Date: Mon, 23 Oct 2006 13:59:25 0700
From: John Baez
To: categories
Subject: categories: cartesian closed categories and holodeck games
MimeVersion: 1.0
ContentType: text/plain; charset=usascii
ContentDisposition: inline
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: O
XStatus:
XKeywords:
XUID: 27
Dominic Hughes writes:
> This "backtracking game" characterisation has been known since around
> '93'94, in the work of Hyland and Ong ....
Thanks for filling me in on the history! I apologize to everyone whose
work I slighted in "week240". I've tried to update the web version to
more accurately say who did what first:
http://math.ucr.edu/home/baez/week240.html
People may also be interested in joining the discussion here:
http://golem.ph.utexas.edu/category/2006/10/classical_vs_quantum_computati_3.html#comments
Best,
jb
From rrosebru@mta.ca Mon Oct 23 21:00:50 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Mon, 23 Oct 2006 21:00:50 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1Gc9gH000278HK
for categorieslist@mta.ca; Mon, 23 Oct 2006 20:58:09 0300
Date: Mon, 23 Oct 2006 13:53:52 +0100
From: Monika Seisenberger
MIMEVersion: 1.0
To: CALCO 2007
Subject: categories: 1cfc: CALCOjnr (Conference on Algebra and Coalgebra in Computer Science), Bergen, Norway
ContentType: text/plain; charset=usascii; format=flowed
ContentTransferEncoding: 7bit
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: O
XStatus:
XKeywords:
XUID: 28
[Apologies for multiple copies]
!!! PLEASE FORWARD TO PHD STUDENTS AND YOUNG RESEARCHERS !!!
**
* 1st call for contributions *
* *
* CALCOjnr 2007 *
* *
* CALCOjnr: CALCO Young Researchers Workshop *
* August 20, 2007, Bergen, Norway *
* *
* *
* part of *
* 2nd Conference on Algebra and Coalgebra in Computer Science *
* August 2024, 2007, Bergen, Norway *
* *
**
* Abstract submission: April 10, 2007 *
* Author notification: April 30, 2007 *
* Final abstract due: May 16, 2007 *
* Full paper submission: September 30, 2007 *
**
* http://www.ii.uib.no/calco07/ *
**
CALCO 2007 will be preceded by the CALCO Young Researchers Workshop,
CALCOjnr, dedicated to presentations by PhD students and young
researchers at the beginning of their careers.
CALCO brings together researchers and practitioners to exchange new
results related to foundational aspects and both traditional and emerging
uses of algebras and coalgebras in computer science. The study of algebra
and coalgebra relates to the data, process and structural aspects of
software systems.
This is a highlevel, biannual conference formed by joining the forces
and reputations of CMCS (the International Workshop on Coalgebraic Methods
in Computer Science), and WADT (the Workshop on Algebraic Development
Techniques). The first, and very successful, CALCO conference took place
2005 in Swansea, Wales.
The second event will take place 2007 in Bergen, Norway.
The CALCO Young Researchers Workshop, CALCOjnr, is a CALCO satellite
workshop dedicated to presentations by PhD students and by those who have
completed their doctoral studies within the past few years. Attendance at
the workshop is open to all  it is anticipated that many CALCO conference
participants will want to attend the CALCOjnr workshop (and vice versa).
CALCOjnr presentations will be selected according to originality,
significance, and general interest, on the basis of submitted 2page
abstracts, by the organisers. A booklet with the abstracts of the accepted
presentations will be available at the workshop.
After the workshop, the author(s) of each presentation will be invited
to submit a full 1015 page paper on the same topic. They will also be
asked to write (anonymous) reviews of papers submitted by other authors
on related topics. Additional reviewing and the final selection of papers
will be carried out by the CALCOjnr PC.
The volume of selected papers from the workshop will be published as a
Department of informatics, University of Bergen, technical report, and
it will also be made available in an open access database searchable from
http://oaister.umdl.umich.edu/o/oaister/. Authors will retain copyright,
and are also encouraged to disseminate the results reported at CALCOjnr
by subsequent publication elsewhere.
Topics of Interest

The CALCO Young Researchers Workshop will invite submissions on the same
topics as the CALCO conference: reporting results of theoretical work
on the mathematics of algebras and coalgebras, the way these results
can support methods and techniques for software development, as well as
experience with the transition of resulting technologies into industrial
practice. In particular, the workshop will encourage submissions included
or related to the topics listed below.
* Abstract models and logics
 Automata and languages,
 Categorical semantics,
 Modal logics,
 Relational systems,
 Graph transformation,
 Term rewriting,
 Adhesive categories
* Specialised models and calculi
 Hybrid, probabilistic, and timed systems,
 Calculi and models of concurrent, distributed,
mobile, and contextaware computing,
 General systems theory and computational models
(chemical, biological, etc)
* Algebraic and coalgebraic semantics
 Abstract data types,
 Inductive and coinductive methods,
 Reengineering techniques (program transformation),
 Semantics of conceptual modelling methods and techniques,
 Semantics of programming languages
* System specification and verification
 Algebraic and coalgebraic specification,
 Formal testing and quality assurance,
 Validation and verification,
 Generative programming and modeldriven development,
 Models, correctness and (re)configuration of
hardware/middleware/architectures,
 Process algebra
Important Dates (all dates in 2007)

10 April Firm deadline for 2page abstract submission
30 April Notification of abstract selection decision
16 May Final version of abstract due
Early registration ends
20 August CALCO Young Researchers Workshop
2124 August CALCO conference technical program
30 September Firm deadline for 1015 page paper submission
15 November Notification of paper selection decision
30 November Final version of paper due
Program Committee

* Magne Haveraaen, University of Bergen, Norway
http://www.ii.uib.no/~magne/
* John Power, University of Edinburgh, UK
http://www.inf.ed.ac.uk/people/staff/John_Power.html
* Monika Seisenberger, University of Wales Swansea, UK
http://www.cs.swan.ac.uk/~csmona/
 http://www.ii.uib.no/calco07/
From rrosebru@mta.ca Mon Oct 23 21:00:50 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Mon, 23 Oct 2006 21:00:50 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1Gc9ec0001y13h
for categorieslist@mta.ca; Mon, 23 Oct 2006 20:56:26 0300
Date: Mon, 23 Oct 2006 10:39:12 0700 (PDT)
From: Dominic Hughes
To: categories
Subject: categories: Re: cartesian closed categories and holodeck games
MessageID:
MIMEVersion: 1.0
ContentType: TEXT/PLAIN; charset=USASCII
Sender: catdist@mta.ca
Precedence: bulk
Status: O
XStatus:
XKeywords:
XUID: 29
This "backtracking game" characterisation has been known since around
'93'94, in the work of Hyland and Ong:
M. Hyland and L. Ong. On full abstraction for PCF. Information and
Computation, Volume 163, pp. 285408, December 2000. [Under review for
6 years!]
ftp://ftp.comlab.ox.ac.uk/pub/Documents/techpapers/Luke.Ong/pcf.ps.gz
(PCF is an extension of typed lambda calculus.) My D.Phil. thesis
extended the lambda calculus (free CCC) characterisation to secondorder,
published in:
Games and Definability for System F. Logic in Computer Science, 1997
http://boole.stanford.edu/~dominic/papers/
To characterise the free CCC on an *arbitrary* set {Z,Y,X,...} of
generators (rather than a single generator, as you discuss), one simply
adds the following Copycat Condition:
(*) Whenever first player plays an occurrence of X, the second player
must play an occurrence of X.
[Try it: see how X > Y > X has just one winning strategy.] Although the
LICS'97 paper cited above appears to be the first place the Copycat
Condition appears in print, I like to think it was already understood at
the time by people working in the area. Technically speaking, winning
strategies correspond to etaexpanded betanormal forms. See pages 57 of
my thesis for an informal description of the correspondence.
It sounds like you've reached the point of trying to figure out how
composition should work. Proving associativity is fiddly. Hyland and Ong
give a very elegant treatment, via a larger CCC of games in which *both*
players can backtrack. The free CCC subcategory is carved out as the
socalled *innocent* strategies. This composition is almost identical to
that presented by Coquand in:
A semantics of evidence for classical arithmetic. Thierry Coquand.
Proceedings of the CLICS workshop, Aarhus, 1992.
Dominic
PS A gametheoretic characterisation with an entirely different flavour
(winning strategies less "obviously" corresponding to etalong betanormal
forms) is:
Abramsky, S., Jagadeesan, R. and Malacaria, P., Full Abstraction for
PCF. Info. & Comp. 163 (2000), 409470.
http://web.comlab.ox.ac.uk/oucl/work/samson.abramsky/pcf.pdf
[Announced concurrently with HylandOng, around '93'94.]
On Sun, 22 Oct 2006, John Baez wrote:
> Dear Categorists 
>
> This contains a popularization of Dolan and Trimble's work on
> game theory and the free cartesian closed category on one object.
> It also has links to more detais.
>
> Best,
> jb
>
> ....................................................................
>
> Also available as http://math.ucr.edu/home/baez/week240.html
>
From rrosebru@mta.ca Mon Oct 23 22:23:09 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Mon, 23 Oct 2006 22:23:09 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GcAx80001HCNF
for categorieslist@mta.ca; Mon, 23 Oct 2006 22:19:38 0300
Date: Fri, 20 Oct 2006 16:14:09 +0100
From: Miles Gould
To: categories@mta.ca
Subject: categories: Decomposability of monads
MimeVersion: 1.0
ContentType: text/plain; charset=usascii
ContentDisposition: inline
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: RO
XStatus:
XKeywords:
XUID: 30
Dear categorists,
The free ring monad (on, say, Set) may be decomposed into the free
monoid monad and the free abelian group monad, connected by a
distributive law. Is it known which monads can be decomposed into
"simpler" ones (whatever that means), connected by distributive laws?
I'm particularly interested in the case of monads describing algebraic
theories.
Thanks,
Miles

Amazing! You type random strings of letters, and it does what you want!
 Rhiannon Mogridge, on vi
From rrosebru@mta.ca Tue Oct 24 09:35:08 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Tue, 24 Oct 2006 09:35:08 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GcLMO00026cQL
for categorieslist@mta.ca; Tue, 24 Oct 2006 09:26:24 0300
Date: Mon, 23 Oct 2006 23:24:23 0700
From: John Baez
To: categories
Subject: categories: Re: cartesian closed categories and holodeck games
MimeVersion: 1.0
ContentType: text/plain; charset=usascii
ContentDisposition: inline
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: O
XStatus:
XKeywords:
XUID: 31
On Mon, Oct 23, 2006 at 11:15:04PM 0700, Vaughan Pratt wrote:
> In your Week 240 post to categories, you said
>
> > The moral of this game is that all systematic methods for picking
> > an element of (X^X)^(X^X) for an unknown set X can be written
> > using the lambda calculus.
> What is unsystematic about the contagiousfixpoint functional? This is the
> functional that maps those functions that have any fixpoints to the identity
> function (the function that makes every element a fixpoint) and functions
> without fixpoints to themselves (thus preserving the absence of fixpoints).
Whoops. I got carried away there. Later I admitted that by "systematic
method" I just meant "definable using the lambda calculus". I'll have to
fix this. Thanks!
Best,
jb
From rrosebru@mta.ca Tue Oct 24 09:35:09 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Tue, 24 Oct 2006 09:35:09 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GcLLh00022LOa
for categorieslist@mta.ca; Tue, 24 Oct 2006 09:25:42 0300
To: categories
Subject: categories: Re: cartesian closed categories and holodeck games
Date: Mon, 23 Oct 2006 23:15:04 0700
From: Vaughan Pratt
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: O
XStatus:
XKeywords:
XUID: 32
Hi, John,
In your Week 240 post to categories, you said
> The moral of this game is that all systematic methods for picking
> an element of (X^X)^(X^X) for an unknown set X can be written
> using the lambda calculus.
What is unsystematic about the contagiousfixpoint functional? This is the
functional that maps those functions that have any fixpoints to the identity
function (the function that makes every element a fixpoint) and functions
without fixpoints to themselves (thus preserving the absence of fixpoints).
It's a perfectly good functional that is equally well defined for all sets
X, its statement in no way depends on X, and conceptually the concept of
contagious fixpoints is even intuitively natural, but how do you write it
using the lambda calculus?
Many more examples in this vein at JPAA 128, 3392 (Pare and Roman, Dinatural
numbers, 1998). The above is the case K = {0} of Freyd's (proper) class
of examples.
Vaughan
From rrosebru@mta.ca Tue Oct 24 21:44:53 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Tue, 24 Oct 2006 21:44:53 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GcWpI0002G5Va
for categorieslist@mta.ca; Tue, 24 Oct 2006 21:41:01 0300
Date: Tue, 24 Oct 2006 19:58:57 +0200
ContentType: text/plain; charset=USASCII; format=flowed
Subject: categories: laws and equations
From: Enrico Vitale
To: categories@mta.ca
ContentTransferEncoding: 7bit
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: O
XStatus:
XKeywords:
XUID: 33
Dear Colleagues,
Recently, Bill Lawvere proposed parallel pairs of morphisms
in an algebraic theory as the categorical concept of "equational
law". We have just observed that this is, for many sorted theories,
the first definition that makes sense! For example, the following
variant
of Birkhoff's Variety Theorem holds for manysorted algebras:
a full subcategory is equationally presentable (in Bill's sense)
iff it is closed under products, subobjects, regular quotients and
directed unions. If equation is "traditionally" understood as
a pair of terms (elements of a free algebra of the given signature)
of the same sort, then Birkhoff's theorem is not true:
Example. Consider algebras on two sorts (say, a,b) with no
operations  that is, consider the category Set x Set.
Take the full subcategory V of all objects (A,B) such
that either A is empty or B has at most 1 element. This is an
HSP subcategory of Set x Set, but there does not exist any
equation that only works with one of the sorts such
that all the objects of V satisfy it. But in the theory which is a free
completion of the discrete category {a,b} under finite products
the parallel pair of projections
p_2, p_3: a x b x b > b
specifies V.
If, on the other hand, equations are understood as pairs of terms
together with a manysorted set of variables (encoding the universal
quantification), the following example demonstrates that
we are beyond the realm of finitary logic:
Example. Consider algebras on infinitely many sorts with
no operations. The full subcategory of all objects which are
either subobjects of the terminal object, or have all but finitely
many sorts empty, is an HSP class. But it is not closed under
directed unions, and thus cannot be described in finitary logic.
Best regards
Jiri Adamek and Enrico Vitale
From rrosebru@mta.ca Thu Oct 26 10:34:33 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Thu, 26 Oct 2006 10:34:33 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1Gd5EZ0007Eu6s
for categorieslist@mta.ca; Thu, 26 Oct 2006 10:25:23 0300
Date: Thu, 26 Oct 2006 10:56:40 +0200
From: Andrej Bauer
MIMEVersion: 1.0
To: categories@mta.ca
Subject: categories: Characterization of integers as a commutative ring with unit
ContentType: text/plain; charset=ISO88592; format=flowed
ContentTransferEncoding: 7bit
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: RO
XStatus:
XKeywords:
XUID: 34
For the purposes of defining the data structure of integers in a
Coqlike system, I am looking for an _algebraic_ characterization of
integers Z as a commutative ring with unit. (The oneelement ring is a
ring.)
Some possible characterizations which I don't much like:
1) Z is the free group generated by one generator. I want the ring
structure, not the group structure.
2) Z is the free ring generated by the semiring of natural numbers. This
just translates the problem to characterization of the semiring of
natural numbers.
3) Z is the initial nontrivial ring. This is no good because
"nontrivial" is an inequality "0 =/= 1" rather than an equality.
4) Let R be the free commutative ring with unit generated by X. Then Z
is the image of the homomorphism R > R which maps X to 0. This is just
ugly and there must be something better.
I feel like I am missing something obvious. Surely Z appears as a
prominent member of the category of commutative rings with unit, does it
not?
Best regards,
Andrej
From rrosebru@mta.ca Thu Oct 26 21:39:04 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Thu, 26 Oct 2006 21:39:04 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GdFg20002qY4p
for categorieslist@mta.ca; Thu, 26 Oct 2006 21:34:26 0300
Date: Thu, 26 Oct 2006 11:21:55 0400
From: Fred E.J.Linton
To: categories@mta.ca
Subject: categories: Re: Characterization of integers as a commutative ring with unit
MimeVersion: 1.0
ContentType: text/plain; charset=ISO88591
ContentTransferEncoding: quotedprintable
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: O
XStatus:
XKeywords:
XUID: 35
What is not to like about Z being the initial ringwithunit? No need to
impose 0 {/ne} 1  it follows.
Cheers,
 Fred.
From rrosebru@mta.ca Thu Oct 26 21:39:05 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Thu, 26 Oct 2006 21:39:05 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GdFhE0002wcTa
for categorieslist@mta.ca; Thu, 26 Oct 2006 21:35:41 0300
Date: Thu, 26 Oct 2006 22:26:17 +0200
From: Andrej Bauer
MIMEVersion: 1.0
To: categories@mta.ca
Subject: categories: Re: Characterization of integers as a commutative ring with unit
ContentType: text/plain; charset=ISO88592; format=flowed
ContentTransferEncoding: 7bit
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: O
XStatus:
XKeywords:
XUID: 36
I would like to thank all 11 people who pointed out that Z _is_ the
initial unital ring. I forgot to take into account that homomorphisms of
unital rings map 1 to 1, so the trivial ring is not initial (and Z is).
Thank you for being kind even though I asked a trivial questions.
Andrej
From rrosebru@mta.ca Thu Oct 26 21:39:05 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Thu, 26 Oct 2006 21:39:05 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GdFef0002lZJl
for categorieslist@mta.ca; Thu, 26 Oct 2006 21:33:01 0300
MimeVersion: 1.0 (Apple Message framework v752.2)
ContentType: text/plain; charset=USASCII; delsp=yes; format=flowed
To: categories@mta.ca
ContentTransferEncoding: 7bit
From: Steve Vickers
Subject: categories: Re: Characterization of integers as a commutative ring with unit
Date: Thu, 26 Oct 2006 15:48:52 +0100
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: O
XStatus:
XKeywords:
XUID: 37
Dear Andrej,
Z is the initial ring with unit. (Doesn't matter whether you require
commutativity.)
It's not clear to me why you felt the need to say "nontrivial" in (3).
Regards,
Steve.
On 26 Oct 2006, at 09:56, Andrej Bauer wrote:
> For the purposes of defining the data structure of integers in a
> Coqlike system, I am looking for an _algebraic_ characterization of
> integers Z as a commutative ring with unit. (The oneelement ring is a
> ring.)
>
> Some possible characterizations which I don't much like:
>
> 1) Z is the free group generated by one generator. I want the ring
> structure, not the group structure.
>
> 2) Z is the free ring generated by the semiring of natural numbers.
> This
> just translates the problem to characterization of the semiring of
> natural numbers.
>
> 3) Z is the initial nontrivial ring. This is no good because
> "nontrivial" is an inequality "0 =/= 1" rather than an equality.
>
> 4) Let R be the free commutative ring with unit generated by X. Then Z
> is the image of the homomorphism R > R which maps X to 0. This is
> just
> ugly and there must be something better.
>
> I feel like I am missing something obvious. Surely Z appears as a
> prominent member of the category of commutative rings with unit,
> does it
> not?
>
> Best regards,
>
> Andrej
>
>
From rrosebru@mta.ca Thu Oct 26 21:39:38 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Thu, 26 Oct 2006 21:39:38 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GdFkJ0003CXJe
for categorieslist@mta.ca; Thu, 26 Oct 2006 21:38:51 0300
MIMEVersion: 1.0
ContentType: text/plain; charset="iso88591"
ContentTransferEncoding: quotedprintable
Subject: categories: RE: Characterization of integers as a commutative ring with unit
Date: Fri, 27 Oct 2006 10:01:28 +1000
From: "Stephen Lack"
To:
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: RO
XStatus:
XKeywords:
XUID: 38
Dear Andrej,
I take it by unit you mean identity (1). Then in the category of =
commutative
rings with 1, you presumably want the 1 to be preserved. So Z is =
initial, and
the trivial ring is terminal.
On the category of commutative rings without 1 (i.e. not necessarily =
having a 1),
there is a monoidal structure, formed by tensoring the underlying =
abelian groups,
and equipping this with the usual multiplication. (This would be the =
coproduct
in the category of commutative rings with 1, but it is not the coproduct =
here.)
If you allow yourself to use this extra structure, then Z is =
characterized as
the unit object for the tensor product.
The category of commutative rings with 1, but homomorphisms not =
necessarily=20
preserving it, seems rather unnatural, but for what it's worth, the =
tensor=20
product of the previous paragraph restricts to this category, and so can =
be
used to characterize Z once again.
Regards,
Steve Lack.
Original Message
From: catdist@mta.ca on behalf of Andrej Bauer
Sent: Thu 10/26/2006 6:56 PM
To: categories@mta.ca
Subject: categories: Characterization of integers as a commutative ring =
with unit
=20
For the purposes of defining the data structure of integers in a
Coqlike system, I am looking for an _algebraic_ characterization of
integers Z as a commutative ring with unit. (The oneelement ring is a
ring.)
Some possible characterizations which I don't much like:
1) Z is the free group generated by one generator. I want the ring
structure, not the group structure.
2) Z is the free ring generated by the semiring of natural numbers. This
just translates the problem to characterization of the semiring of
natural numbers.
3) Z is the initial nontrivial ring. This is no good because
"nontrivial" is an inequality "0 =3D/=3D 1" rather than an equality.
4) Let R be the free commutative ring with unit generated by X. Then Z
is the image of the homomorphism R > R which maps X to 0. This is just
ugly and there must be something better.
I feel like I am missing something obvious. Surely Z appears as a
prominent member of the category of commutative rings with unit, does it
not?
Best regards,
Andrej
From rrosebru@mta.ca Fri Oct 27 09:39:37 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Fri, 27 Oct 2006 09:39:37 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GdQwe0004wlPW
for categorieslist@mta.ca; Fri, 27 Oct 2006 09:36:20 0300
From: "George Janelidze"
To:
Subject: categories: Re: Characterization of integers as a commutative ring with unit
Date: Fri, 27 Oct 2006 11:29:29 +0200
MIMEVersion: 1.0
ContentType: text/plain;charset="iso88591"
ContentTransferEncoding: 7bit
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: O
XStatus:
XKeywords:
XUID: 39
Dear Steve,
Thank you for your kind words. I have mentioned my paper with Aurelio only
because there are too many details that I could not describe in a brief
email message. But if it comes to "...I should have mentioned explicitly
your work with Aurelio...", I can say the same about myself: I should have
mentioned your (very important!) paper
[A. Carboni, S. Lack, and R. F. C. Walters, Introduction to extensive and
distributive categories, Journal of Pure and Applied Algebra 84, 1993,
145158]
and Bill Lawvere's original question about commutative rings and many other
things that Aurelio did mention in his CT1999 talk. (In any case, I hope you
do not assume that I know what "Coq" is, do you?)
Yours
George
 Original Message 
From: "Stephen Lack"
To: "George Janelidze" ;
Cc: "Andrej Bauer"
Sent: Friday, October 27, 2006 9:51 AM
Subject: RE: categories: RE: Characterization of integers as a commutative
ring with unit
Dear George,
I remember well your lovely talk and paper, and indeed I had this
in mind when I wrote. I shouldn't have used the words "extra structure"
(in fact I said this really because I don't know what "Coq" is) and I
should have mentioned explicitly your work with Aurelio.
Sorry.
Steve.
From rrosebru@mta.ca Fri Oct 27 09:39:37 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Fri, 27 Oct 2006 09:39:37 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GdQvr0004sOTX
for categorieslist@mta.ca; Fri, 27 Oct 2006 09:35:31 0300
Contentclass: urn:contentclasses:message
MIMEVersion: 1.0
ContentType: text/plain;charset="iso88591"
ContentTransferEncoding: quotedprintable
Subject: categories: RE: Characterization of integers as a commutative ring with unit
Date: Fri, 27 Oct 2006 17:51:43 +1000
From: "Stephen Lack"
To:
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: O
XStatus:
XKeywords:
XUID: 40
Dear George,
I remember well your lovely talk and paper, and indeed I had this
in mind when I wrote. I shouldn't have used the words "extra structure"
(in fact I said this really because I don't know what "Coq" is) and I=20
should have mentioned explicitly your work with Aurelio.
Sorry.
Steve.
Original Message
From: George Janelidze [mailto:janelg@telkomsa.net]
Sent: Fri 10/27/2006 5:23 PM
To: categories@mta.ca; Stephen Lack
Cc: Andrej Bauer
Subject: Re: categories: RE: Characterization of integers as a =
commutative ring with unit
=20
Dear Steve,
In your message of October 27 to Andrej Bauer you say:
"On the category of commutative rings without 1 (i.e. not necessarily =
having
a 1),
there is a monoidal structure, formed by tensoring the underlying =
abelian
groups,
and equipping this with the usual multiplication. (This would be the
coproduct
in the category of commutative rings with 1, but it is not the coproduct
here.)
If you allow yourself to use this extra structure, then Z is =
characterized
as
the unit object for the tensor product."
But no, this is not an extra structure, which, explained properly, has =
some
obvious and some nonobvious aspects  see [A. Carboni and G. Janelidze,
Smash product of pointed objects in lextensive categories, Journal of =
Pure
and Applied Algebra 183, 2003, 2743] (I also gave a talk about this =
called
"Abstract commutative algebra I: Associativity of tensor (=3Dcosmash)
products (12.12.2001)" on Australian Category Seminar).
In simple words: tensor product of commutative rings of A and B without =
1 is
nothing but their cosmash product (=3Dthe kernel of the canonical =
morphism
A+B > AxB), and therefore Z is the unit object of the smash product. =
This
observation itself might be infinitely old  simply because it is =
simple!
But the reason of the associativity of the smash product and the very
definition of associativity is a different story (e.g. the associativity
isomorphism itself is not an extra structure as it happens in a general
monoidal category).
Let me also point out that the cosmash product is to be investigated in =
any
semiabelian category. Note that:
In any semiabelian category the canonical morphism A+B > AxB is a
regular=3Dnormal epimorphism for each two objects A and B. Therefore the
cosmash product of A and B is not merely its kernel  IT IS THE MEASURE =
OF
NONADDITIVITY. And you can define an abelian category as a semiabelian
category with trivial cosmash products. In this sense the category CR =
of
commutative rings without 1 is "very nonabelian"  since instead of =
having
trivial cosmash products it has a unit object for the cosmash product
(this is like a monoid with zero versus a semigroup with zero and zero
multiplication). On the other hand this makes CR "almost abelian" since =
it
is one of the very few semiabelian categories where the cosmash =
product is
associative (it is not the case for groups, not for noncommutative =
rings,
etc.).
George Janelidze
From rrosebru@mta.ca Fri Oct 27 09:39:37 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Fri, 27 Oct 2006 09:39:37 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GdQv60004o1Gq
for categorieslist@mta.ca; Fri, 27 Oct 2006 09:34:44 0300
From: "George Janelidze"
To: ,
Subject: categories: Re: Characterization of integers as a commutative ring with unit
Date: Fri, 27 Oct 2006 09:23:35 +0200
MIMEVersion: 1.0
ContentType: text/plain;charset="iso88591"
ContentTransferEncoding: 7bit
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: O
XStatus:
XKeywords:
XUID: 41
Dear Steve,
In your message of October 27 to Andrej Bauer you say:
"On the category of commutative rings without 1 (i.e. not necessarily having
a 1),
there is a monoidal structure, formed by tensoring the underlying abelian
groups,
and equipping this with the usual multiplication. (This would be the
coproduct
in the category of commutative rings with 1, but it is not the coproduct
here.)
If you allow yourself to use this extra structure, then Z is characterized
as
the unit object for the tensor product."
But no, this is not an extra structure, which, explained properly, has some
obvious and some nonobvious aspects  see [A. Carboni and G. Janelidze,
Smash product of pointed objects in lextensive categories, Journal of Pure
and Applied Algebra 183, 2003, 2743] (I also gave a talk about this called
"Abstract commutative algebra I: Associativity of tensor (=cosmash)
products (12.12.2001)" on Australian Category Seminar).
In simple words: tensor product of commutative rings of A and B without 1 is
nothing but their cosmash product (=the kernel of the canonical morphism
A+B > AxB), and therefore Z is the unit object of the smash product. This
observation itself might be infinitely old  simply because it is simple!
But the reason of the associativity of the smash product and the very
definition of associativity is a different story (e.g. the associativity
isomorphism itself is not an extra structure as it happens in a general
monoidal category).
Let me also point out that the cosmash product is to be investigated in any
semiabelian category. Note that:
In any semiabelian category the canonical morphism A+B > AxB is a
regular=normal epimorphism for each two objects A and B. Therefore the
cosmash product of A and B is not merely its kernel  IT IS THE MEASURE OF
NONADDITIVITY. And you can define an abelian category as a semiabelian
category with trivial cosmash products. In this sense the category CR of
commutative rings without 1 is "very nonabelian"  since instead of having
trivial cosmash products it has a unit object for the cosmash product
(this is like a monoid with zero versus a semigroup with zero and zero
multiplication). On the other hand this makes CR "almost abelian" since it
is one of the very few semiabelian categories where the cosmash product is
associative (it is not the case for groups, not for noncommutative rings,
etc.).
George Janelidze
From rrosebru@mta.ca Fri Oct 27 09:39:37 2006 0300
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Fri, 27 Oct 2006 09:39:37 0300
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GdQuV0004kmPS
for categorieslist@mta.ca; Fri, 27 Oct 2006 09:34:07 0300
Date: Thu, 26 Oct 2006 21:09:40 0400 (EDT)
From: Josh NicholsBarrer
To: categories@mta.ca
Subject: categories: Re: Characterization of integers as a commutative ring with unit
MIMEVersion: 1.0
ContentType: TEXT/PLAIN; charset=USASCII
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: O
XStatus:
XKeywords:
XUID: 42
Hi Andrej,
Isn't Z the initial /ring/? 0 isn't initial, as 0=1 holds only in itself
(Spec Z is the terminal scheme, Spec 0 the empty scheme, so the initial
scheme).
Josh
On Thu, 26 Oct 2006, Andrej Bauer wrote:
> For the purposes of defining the data structure of integers in a
> Coqlike system, I am looking for an _algebraic_ characterization of
> integers Z as a commutative ring with unit. (The oneelement ring is a
> ring.)
>
> Some possible characterizations which I don't much like:
>
> 1) Z is the free group generated by one generator. I want the ring
> structure, not the group structure.
>
> 2) Z is the free ring generated by the semiring of natural numbers. This
> just translates the problem to characterization of the semiring of
> natural numbers.
>
> 3) Z is the initial nontrivial ring. This is no good because
> "nontrivial" is an inequality "0 =/= 1" rather than an equality.
>
> 4) Let R be the free commutative ring with unit generated by X. Then Z
> is the image of the homomorphism R > R which maps X to 0. This is just
> ugly and there must be something better.
>
> I feel like I am missing something obvious. Surely Z appears as a
> prominent member of the category of commutative rings with unit, does it
> not?
>
> Best regards,
>
> Andrej
>
>
From rrosebru@mta.ca Sun Oct 29 19:17:44 2006 0400
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Sun, 29 Oct 2006 19:17:44 0400
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GeJnS0003nS70
for categorieslist@mta.ca; Sun, 29 Oct 2006 19:10:30 0400
From: Peter Freyd
Date: Sun, 29 Oct 2006 09:57:15 0500
To: categories@mta.ca
Subject: categories: this week's nonsense
MIMEVersion: 1.0
ContentType: text/plain; charset=usascii
ContentTransferEncoding: 7bit
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: RO
XStatus:
XKeywords:
XUID: 43
The math advisers from CalTech had a little fun on Friday's episode of
"Numb3rs". The Mathematician and the Physicist are looking at a dead
person's notebook. They're dead serious.
MATHEMATICIAN: it's a categorybased approach to I don't know what,
but it's a forcasting system. Right?. It's very sophisticated.
PHYSICIST: [In awe at what he sees] Oh, no, no. no. This is more
than sophisticated. You know what this reminds me of? A topos
approach to Bach's music.
MATHEMATICIAN: I said: very sophisticated.
FBI AGENT: Yes  you did.
Be assured that neither the page we see from the notebook nor the
rest of the program had anything to do with categories, topoi or Bach.
From rrosebru@mta.ca Sun Oct 29 19:17:44 2006 0400
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Sun, 29 Oct 2006 19:17:44 0400
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GeJjR0003TBB6
for categorieslist@mta.ca; Sun, 29 Oct 2006 19:06:21 0400
Date: Sat, 28 Oct 2006 16:13:55 0400 (EDT)
From: F W Lawvere
To: categories@mta.ca
Subject: categories: Re: LawvereMetrics and Banach Spaces
MIMEVersion: 1.0
ContentType: TEXT/PLAIN; charset=USASCII
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: O
XStatus:
XKeywords:
XUID: 44
Dear colleagues,
Here are a few thoughts on the recent discussion of metric spaces:
The whole general theory of enriched categories should in
particular be focused on metric spaces and relatives.
For example, enriched functor categories have a uniform
definition, which in the case of metric spaces yields the sup metric. Of
course, this does involve subtracting distances (but not in the sense of
abelian groups, rather subtraction is the hom in the enriching category
itself.)
Dividing distances would be a dimensional mistake: the enriching
category should be visualized as a possible conception of actual physical
distance (not of numbers that might measure it), the addition and ordering
being independent of any choice of unit. The same idea applies to the
equivalent notion of nearness, as appropriate to the intrinsic measuring
of convex sets (n(x,y)n(y,z) less than or equal to n(x,z), often
complicated by using d = exp(n/u) where u is a unit). With either point
of view, there is no further definable operation on distance with respect
to which to "divide". But on monoidal functors instead, there is of course
the operation of composition.
Not only categorists are enlightened by lax monoidal functors and
such; subadditive functions are familiar to analysts. In their 1965 paper
Eilenberg and Kelly included a definite "laxity" in the definition of
monoidal (or closed) functor, since the goal was to induce good 2functors
between categories of enriched categories. For example, why should an
additive category ever be considered as an ordinary category?  because
the functor from abelian groups to sets is accompanied by a comparison
transformation between tensor product and cartesian product. In other
cases where the analogous comparison is an isomorphism, one might speak of
strict monoidal functors.
To deal with the fibered category of metric spaces whose morphisms
have general Lipschitz constants (not just less than or equal to 1), the
base monoid is conceived as acting by strict monoidal functors on
distances. In particular, the hom of Banach spaces is normed in THIS
monoid, not in the original one. The more general monoidal endofunctors
yield much more refined notions of Lipschitz (and more refined notions of
Hausdorff dimension) wherein they replace the special numbers as indices.
But indices occur in another way: The Orlicz family forms a more natural
parameterizable class of reflexive Banach spaces than the Lebesgue family.
Here we encounter the important fact that the adjoint of a monoidal
functor is not usually monoidal.
The square root function is monoidal, but squaring is not. This
suggests inverting the system of parameterizing the Lebesgue spaces (or
more generally), so that the parameter for Hilbert space is the square
root function, not 2. Since the origin of Hilbert space is in the
Pythagorean metric on the product of two metric spaces, it is suggested to
consider an infinite family of products.
The first product that occurs to a category theorist for the
category of enriched categories with given value category, is the tensor
product which extends the given tensor product in the value category.
This leads to the "sum" metric on the product of two metric spaces (this
functor's right adjoint is the sup metric on distancedecreasing functions
as mentioned above). Of course, there is also the cartesian product which
in our case leads to the "max" metric. Infinite versions of these two
products are a staple of analysis, but so are many intermediate products,
which, as suggested above, should be parameterized by the monoidal
endofunctors of the category of distancevalues.
Computational aspects might be approached in the following two
traditional ways, which could even be combined. Paul Taylor's ascending
reals seem to be related to the study of metric spaces in a topos, where
the object of semicontinuous or onesided Dedekind reals, the
infcompletion of the nonnegative rationals, is often the appropriate
recipient of norms for continuously varying Banach spaces (even though the
scalar multipliers remain the twosided continuous Dedekind reals). The
other, even older, idea was to replace closed sets by "located" sets which
are actually Lipschitz functions, that is, objects in the enriched functor
category that plays the role of the power set in generalized logic.
Bill Lawvere
************************************************************
F. William Lawvere
Mathematics Department, State University of New York
244 Mathematics Building, Buffalo, N.Y. 142602900 USA
Tel. 7166456284
HOMEPAGE: http://www.acsu.buffalo.edu/~wlawvere
************************************************************
From rrosebru@mta.ca Sun Oct 29 19:17:44 2006 0400
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Sun, 29 Oct 2006 19:17:44 0400
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GeJla0003fbVi
for categorieslist@mta.ca; Sun, 29 Oct 2006 19:08:35 0400
Date: Sat, 28 Oct 2006 22:58:44 0400 (EDT)
From: flinton@wesleyan.edu
To: categories@mta.ca
MIMEVersion: 1.0
ContentType: text/plain;charset=UTF8
ContentTransferEncoding: 8bit
Subject: categories: Re: cosmash product (was: categories: Re: Characterization...
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: RO
XStatus:
XKeywords:
XUID: 45
Remarking on George Janelidze's comment,
> ... tensor product of commutative rings of A and B without 1 is
> nothing but their cosmash product (=the kernel of the canonical
> morphism A+B > AxB), and therefore Z is the unit object of the smash
> product. This observation itself might be infinitely old  simply
> because it is simple!
Infinitely old the following isn't, but certainly the s.e.s.
tensor product > coproduct > product
made an appearance, for Boolean rngs (boolean algebras w/o unit),
in my 1963 Columbia dissertation. Here  that is, for Boolean
rngs  what's noteworthy is that the tensor product is the same,
whether one thinks "as abelian groups, with induced rng structure,"
"as Z_2modules, with induced rng structure," or "as the object
that represents 'bilinear maps,' i.e., functions on the cartesian
product that, for each choice of fixed member of either factor,
are homomorphisms on the other factor."
[That the third perspective is as valid as the first two comes about
because of the idempotence  xx=x  of multiplication in Boolean
rngs; it surely won't be valid for commutative rngs generally.]
On another point, viz., George's comment,
> ... cosmash product is associative ... not the case for groups ...
what exactly are the relations among grouptheoretic cosmash product,
grouptheoretic tensor product (in the spirit of Hassler Whitney's
study from circa 1938 (the very year I was born!)), and group
theoretic commutator constructions? [I recall that Whitney's
tensor product of two groups, though defined in terms of
representing "bilinear maps," worked out to coincide with
the usual tensor product of the groups' abelianizations.]
Cheers,
 Fred
From rrosebru@mta.ca Mon Oct 30 13:56:50 2006 0400
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Mon, 30 Oct 2006 13:56:50 0400
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1GebGQ0005QK9Y
for categorieslist@mta.ca; Mon, 30 Oct 2006 13:49:34 0400
Date: Mon, 30 Oct 2006 17:30:26 GMT
From: Jeremy.Gibbons@comlab.ox.ac.uk
To: categories@mta.ca
Subject: categories: University of Oxford: Lectureships in Software Engineering
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: O
XStatus:
XKeywords:
XUID: 46
UNIVERSITY OF OXFORD
Software Engineering Programme
Kellogg College
THREE UNIVERSITY LECTURERSHIPS IN SOFTWARE ENGINEERING
Applications are invited for three new University Lecturerships in Software
Engineering. The successful applicants will join the staff of the
University's Software Engineering Programme in teaching and researching the
application of scientific principles to the development of software
systems. The salary will be on a scale up to GBP50,589 per annum.
An advanced degree in a related subject, proven teaching ability, and a
strong research record  of international standing  are all essential
requirements. Applications are particularly welcome from those with
expertise in software and systems security, serviceoriented architectures,
or modeldriven development.
The appointments will be associated with fellowships at Kellogg College,
Oxford and the appointees will be members of the Governing Body of the
college. The closing date for applications is 27th November 2006.
For further information, including full details of the application
procedure and selection criteria, see http://www.softeng.ox.ac.uk/jobs/
From rrosebru@mta.ca Tue Oct 31 19:19:17 2006 0400
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Tue, 31 Oct 2006 19:19:17 0400
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1Gf2kp0000dPDB
for categorieslist@mta.ca; Tue, 31 Oct 2006 19:10:47 0400
Date: Tue, 31 Oct 2006 08:58:17 0500 (EST)
From: F W Lawvere
To: categories@mta.ca
Subject: categories: Amendment/Commentary
MIMEVersion: 1.0
ContentType: TEXT/PLAIN; charset=USASCII
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: RO
XStatus:
XKeywords:
XUID: 47
Re: Commentary of Adjointness in Foundations in TAC Reprints
Dear colleagues,
I have taken advantage of the useful possibility for
postpublication amendments to add two sentences to my commentary
for the TAC Reprint no. 16, Adjointness in Foundations.
Matias Menni has made several advances concerning the
connection between tractability of proof theory and classical logic
of the meta theory. His recent works contain important concepts and
precise versions which update the formulations given in my
commentary.
Thanks to Bob Rosebrugh and Mike Barr.
Bill Lawvere
************************************************************
F. William Lawvere
Mathematics Department, State University of New York
244 Mathematics Building, Buffalo, N.Y. 142602900 USA
Tel. 7166456284
HOMEPAGE: http://www.acsu.buffalo.edu/~wlawvere
************************************************************
From rrosebru@mta.ca Tue Oct 31 19:19:17 2006 0400
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Tue, 31 Oct 2006 19:19:17 0400
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1Gf2lD0000fLEG
for categorieslist@mta.ca; Tue, 31 Oct 2006 19:11:11 0400
Date: Tue, 31 Oct 2006 18:07:26 +0000 (GMT)
From: "Prof. Peter Johnstone"
To: Categories mailing list
Subject: categories: Artin glueing for quasitoposes
MIMEVersion: 1.0
ContentType: TEXT/PLAIN; charset=USASCII
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: O
XStatus:
XKeywords:
XUID: 48
Given a subobject of 1 in a topos, it's well known that one can
`split' the topos into complementary open and closed subtoposes,
and reconstruct the topos (up to equivalence) by applying Artin
glueing to these two subtoposes.
Hands up, all those of you who thought that the same thing works
for quasitoposes ... I thought so! It isn't true, as I have just
discovered.
Certainly, given a strong subobject U >> 1 in a quasitopos E,
one can construct the `closed complement' of the open subquasitopos
E/U, in exactly the same way as one does for a topos: let's denote it
by C(U). It's also true that one has a `fringe functor' from E/U to
C(U), and that one gets a comparison functor from E to the
quasitopos obtained by glueing along this functor (again, the glueing
construction works for quasitoposes just as it does for toposes).
But, for this comparison to be an equivalence, one needs to know
that the inverse image functors E > E/U and E > C(U) are (not
just jointly faithful, but) jointly isomorphismreflecting. And
that can fail: I have a counterexample in a slice of the quasitopos
of Frechet spaces (Elephant, A2.6.4(c).
Has anyone noticed this failure before? If so, has anyone actually
written it up?
Peter Johnstone
From rrosebru@mta.ca Tue Oct 31 19:19:17 2006 0400
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Tue, 31 Oct 2006 19:19:17 0400
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1Gf2jN0000VkBR
for categorieslist@mta.ca; Tue, 31 Oct 2006 19:09:17 0400
To: LiCS 2006 List
From: Kreutzer + Schweikardt
Subject: categories: LICS 2007 Call for Workshop Proposals
Date: Tue, 31 Oct 2006 13:30:23 +0100 (CET)
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: O
XStatus:
XKeywords:
XUID: 49
LICS 2007 CALL FOR WORKSHOP PROPOSALS
The TwentySecond IEEE Symposium on Logic in Computer Science (LICS 2007)
will be held in Wroclaw, Poland, July 1014, 2007. It will be colocated
with two other meetings: the International Colloquium on Automata,
Languages, and Programming (ICALP'07) July 913, 2007, and also the
European Logic Colloquium (ELC 2007), July 1419. Workshops are planned
for July 8, 9 and July 15 (possibly the afternoon of 14th).
Detailed information can be found on the LICS 2007 webpage at
http://www.informatik.huberlin.de/lics/lics07/
LICS workshops have traditionally been an important and exciting part of
the program. They introduce either newest research in traditional areas of
the LICS community, recent interdisciplinary and applied areas of general
theory, or emerging directions that already have some substantial overlap
with LICS community interests. Researchers and practitioners are invited to
submit proposals for workshops on topics relating logic  broadly construed 
to computer science or related fields. Typically, LICS workshops feature a
mix of invited speakers and contributed presentations. LICS workshops do not
produce formal proceedings. However, in the past there have been special
issues of journals based in part on certain LICS workshops.
Proposals should include:
 A short scientific summary and justification of the proposed topic.
This should include a discussion of the particular benefits of the
topic to the LICS community.
 A discussion of the proposed format and agenda.
 Procedures for selecting participants and papers.
 Expected number of participants. (This is important!)
 Potential invited speakers.
 Plans for dissemination (for example, special issues of journals).
 For workshops of potential interest to ICALP participants, whether
the workshop should be considered as a possible joint LICS/ICALP
workshop.
 Tell us the timeframe you would prefer: 1 day, 1.5 or 2 days, either
before LICS (July 8,9) or after LICS (July 15). Alas, some overlap
with either ICALP or ELC is inevitable.
Proposals are due Nov. 15, 2006, and should be submitted electronically to:
Philip Scott
Workshops Chair, LICS 2007
phil@site.uottawa.ca
Workshops will be chosen by a committee that consists of the LICS
General Chair, LICS Workshop Chair, LICS 2007 PC Chair, and LICS 2007
Conference Chair. In the case of potential joint workshops, these will
be discussed with colleagues from ICALP. A decision will be made by
the end of November.
From rrosebru@mta.ca Tue Oct 31 19:19:17 2006 0400
Returnpath:
Envelopeto: categorieslist@mta.ca
Deliverydate: Tue, 31 Oct 2006 19:19:17 0400
Received: from Majordom by mailserv.mta.ca with local (Exim 4.61)
(envelopefrom )
id 1Gf2m30000jwQe
for categorieslist@mta.ca; Tue, 31 Oct 2006 19:12:03 0400
Date: Tue, 31 Oct 2006 22:47:09 +0000 (GMT)
From: "Prof. Peter Johnstone"
To: Categories mailing list
Subject: categories: Re: Artin glueing for quasitoposes
MIMEVersion: 1.0
ContentType: TEXT/PLAIN; charset=USASCII
Sender: catdist@mta.ca
Precedence: bulk
MessageId:
Status: O
XStatus:
XKeywords:
XUID: 50
Here are the details of the counterexample mentioned in my earlier
email, for anyone who wants to see them.
Let E be the quasitopos of Frechet spaces (called subsequential
spaces in my paper "On a topological topos"): all you need to
know about this category is that it contains the category S of
sequential spaces as a full subcategory, closed under limits
(not under all colimits, but in fact all colimits that occur in
the following discussion are preserved). All the action takes place
inside S. Let N be the discrete space of natural numbers, and
N+ its onepoint compactification N \cup \{\infty\}. Let A be
the space obtained from the disjoint union of two copies of N+
by identifying the two copies of \infty, and let A' be the disjoint
union of N and N+. Clearly, there is a morphism A' \to A which
is bijective on points (hence, both monic and epic) but not an
isomorphism.
However, if we regard A and A' as spaces over N+ in the obvious
way, the morphism A' \to A becomes an isomorphism when we pull
it back along the inclusion N \to N+, and also when we form the
pushouts of
A x N > A(')
N+


v
N
since both such pushouts are isomorphic to N+. This says that,
if we work in the quasitopos E/N+, the morphism A' \to A is mapped to
an isomorphism in both the open subquasitopos E/N and its closed
"complement".
I should say that I came to consider this question as a result of
a seminar talk today by Pawel Sobocinski, which raised the question
of whether quasitoposes are quasiadhesive categories. This example
shows that the quasitopos of Frechet spaces is not quasiadhesive.
Peter Johnstone