From rrosebru@mta.ca Wed Nov 1 08:46:52 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eA1CFhT23111
for categories-list; Wed, 1 Nov 2000 08:15:43 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Reply-To: "s.j.vickers"
From: Steve Vickers
To: categories
Subject: categories: RE: Category Theory from RFC Walters' book
Date: Wed, 1 Nov 2000 10:04:16 -0000
Message-ID: <000201c043eb$18d5bc50$d40a6c89@open.ac.uk>
MIME-Version: 1.0
Content-Type: text/plain; charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
X-Priority: 3 (Normal)
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook 8.5, Build 4.71.2173.0
In-Reply-To:
Importance: Normal
X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 1
> Hello Category Theory community,
>
> I am rereading RFC Walters' "Categories and Computer Science".
> In chapter 1 Section 3 (starting on pg . 10), Walters discusses the
> the notion of generators and relations to generate categories. He
> gives several examples of this concept. E.g. "Example 15. Consider
> the category presented by one object A, one arrow e:A->A, and the
> one relation e.e.e.e = 1subA. From this, he deduces by hand the
> category has additional arrows e .e, e.e.e. I have two questions:
>
> 1) Walters shows that e.e.e = e is not "deducible". What kind of
> formal system/inference rule system is "at work" here that
> allows us to deduce
> formally any additional arrows and allows us to deduce
> arrow relations from the "axiom" relation, i.e. e.e.e.e = 1subA??
> Is this some kind of equational logic? Please specify in detail.
>
> 2) Given generators and relations are we guaranteed to get a category?
It is folklore that the method of generators and relations works for any
essentially algebraic theory with finitary operators, as well as for some
more general ones. "Algebraic" means defined by operators and equational
laws (could be many-sorted); "essentially" means that the operators may be
partial, with their domains of definition described by finite sets of
equations.
The way the method works is that from the presentation by generators and
relations one can derive a universal property of the desired algebra, so the
problem is whether an algebra does indeed exist with that property. If it
does, then it is unique up to isomorphism.
The theory of categories is essentially algebraic, so generators and
relations for a category do present a category.
I wish I knew of an introductory text describing the techniques at this
level of generality, but unfortunately I'm not aware of any - maybe somebody
can suggest one. Manes's book "Algebraic Theories" is quite good on the
algebraic case.
Here's a sketch of a formal system.
>>>>>>>>>>>>>>>>>>>>>>>>
Terms are of two sorts: object and arrow.
Term formation is by function symbols s, t, i and c, with the obvious
arities, for source, target, identity and composition. (Note at this level
that a term exists for the composite of any two arrows, regardless of
whether they are composable.)
Equality of terms is symmetric and transitive, but _not_ reflexive.
Rules include the following (x and y are objects, f and g are arrows).
f=g |- s(f)=s(g)
f=g |- t(f)=t(g)
x=y |- i(x)=i(y)
f1=f2, g1=g2, t(f1)=s(g1), t(f2)=s(g2) |- c(f1,g1)=c(f2,g2)
Also rules for the usual equational laws of category theory (associativity
etc.), and
|- u=u for each generator u (object or arrow)
|- r for each equational relation r
The category is then got by taking all terms z for which z=z, modulo
equality.
<<<<<<<<<<<<<<<<<<
Steve Vickers.
From rrosebru@mta.ca Wed Nov 1 08:48:15 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eA1CGF902490
for categories-list; Wed, 1 Nov 2000 08:16:15 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: Wed, 1 Nov 2000 12:05:43 +0100 (MET)
From:
Message-Id: <200011011105.MAA22504@schartriller.math.uu.nl>
To: categories@mta.ca
Subject: categories: Re: Category Theory from RFC Walters' book
X-Sun-Charset: US-ASCII
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 2
> Hello Category Theory community,
>
> I am rereading RFC Walters' "Categories and Computer Science".
> In chapter 1 Section 3 (starting on pg . 10), Walters discusses the
> the notion of generators and relations to generate categories. He
> gives several examples of this concept.
On "generators":
Given a graph (set of objects and set of (formal) arrows between objects),
the original objects together with the finite *paths* (f,g,h,...,k) in
this graph (as morphisms) constitute a category (called
the "free category on this graph"):
- identities are the empty paths;
- composition is concatenation of paths.
On "relations":
Given a category and a relation R on its arrows (i.e. a subset of A x A)
relating only arrows with the same domain and codomain, let R' be the
smallest congruence relation containing R.
[A congruence relation S is an equivalence relation (i.e. S is
reflexive, symmetric and transitive) that moreover
is closed under composition: aSb and cSd imply (a.c)S(b.d).]
[Check that the " *smallest* congruence relation containing R "
is a well-defined notion, as the class of congruence relations containing R
is closed under arbitrary intersections. So the intersection of those
congruence relations containing R is also a congruence relation
containing R, indeed the smallest one.]
Now the original objects together with the congruence classes [f] of R'
(as morphisms) constitute a category (called the quotient category):
- identities are the classes of the identities [1];
- the composite [f].[g] is by definition [f.g], which is well-defined.
There is a more explicit/constructive description of R' in terms of R.
Consider the following relation:
aR"b iff there exist n \geq 0 and an n-chain:
(n+1) morphisms a_0, a_1, ..., a_n such that
a = a_0;
a_n = b;
for all 0 \leq i < n there are morphisms u,v,c,d such that
a_i = u.c.v and a_{i+1} = u.d.v and either cRd or dRc
This clearly is a congruence relation containing R, whence R' \subseteq R".
The other way around, you show by induction on n that every n-chain is
between R'-congruent formulas. Hence R' = R".
There is much more to say about presentations in general, but I hope the
above details for categories answer your questions.
Let me briefly return to your specific example:
> E.g. "Example 15. Consider
> the category presented by one object A, one arrow e:A->A, and the
> one relation e.e.e.e = 1subA. From this, he deduces by hand the
> category has additional arrows e .e, e.e.e. I have two questions:
Observe that the free category on this graph (one object, one arrow)
has infinitely many arrows: (); (e); (e,e); (e,e,e); (e,e,e,e); ...
Let us denote them by e^0, e^1, e^2, e^3, e^4, ...
Recall that these arrows are actually the paths in the graph, and
that they are all different!
According to your example R = { (e^4,e^0) }.
Check that R' = R" = { (e^n,e^m) | n-m is a 4-fold }.
Check that there are only four congruence classes in the quotient
category: [e^0], [e^1], [e^2], [e^3].
An example of a composite: [e^2].[e^3] = [e^2.e^3] = [e^5] = [e^1].
> 1) Walters shows that e.e.e = e is not "deducible". What kind of
> formal system/inference rule system is "at work" here that
> allows us to deduce
> formally any additional arrows and allows us to deduce
> arrow relations from the "axiom" relation, i.e. e.e.e.e = 1subA??
> Is this some kind of equational logic? Please specify in detail.
You do not deduce additional arrows; the arrows are the original paths.
R' can be described by the following deductive system:
axioms: the instances of R and reflexivity;
rules: symmetry, transitivity, closure.
> 2) Given generators and relations are we guaranteed to get a category?
Yes, since we agreed upon considering the smallest congruence relation
containing your relations.
Regards,
Quintijn Puite
From rrosebru@mta.ca Wed Nov 1 15:15:46 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eA1IdTl06348
for categories-list; Wed, 1 Nov 2000 14:39:29 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Message-Id: <200011011252.eA1Cqmt08314@nmh.informatik.uni-bremen.de>
Date: Wed, 1 Nov 2000 13:52:48 +0100 (MET)
From: Till Mossakowski
Reply-To: Till Mossakowski
Subject: categories: Two one-sided inverse adjoints
To: categories@mta.ca
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
Content-MD5: h16nwYdh6UmA48uR87ylZQ==
X-Mailer: dtmail 1.3.0 @(#)CDE Version 1.4 SunOS 5.8 sun4u sparc
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 4
Consider the following situation:
R |- F |- L with F o R = id and F o L = id.
I have derived a number of results about this situation, but probably this
is already known in the literature? Under the name `Lawvere cylinders'?
Till Mossakowski
-----------------------------------------------------------------------------
Till Mossakowski Phone +49-421-218-4683, monday: +49-4252-1859
Dept. of Computer Science Fax +49-421-218-3054
University of Bremen till@informatik.uni-bremen.de
P.O.Box 330440, D-28334 Bremen http://www.informatik.uni-bremen.de/~till
-----------------------------------------------------------------------------
From rrosebru@mta.ca Wed Nov 1 15:34:56 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eA1IoxO13724
for categories-list; Wed, 1 Nov 2000 14:50:59 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: Tue, 31 Oct 2000 15:14:38 +0530
Message-Id: <200010310944.PAA00756@cse.iitd.ernet.in>
X-Authentication-Warning: localhost.localdomain: sanjiva set sender to sanjiva@sanjiva.cse.iitd.ernet.in using -f
From: Sanjiva Prasad
To: categories@mta.ca
Subject: categories: FST TCS 2000 Call for Participation
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 6
*******************************************************************
* *
* Call for Participation *
* *
* Foundations of Software Technology *
* and *
* Theoretical Computer Science *
* (FST TCS 2000) *
* *
* India International Centre *
* New Delhi, India *
* 13--15 December July, 2000 *
* *
* REGISTER AT http://www.cse.iitd.ernet.in~/fsttcs20 *
* EARLY REGISTRATION DEADLINE IS November 15 *
* *
*******************************************************************
Invited Speakers:
Peter Buneman (U Penn)
Bernard Chazelle (Princeton)
E. Allen Emerson (U Texas, Austin)
Martin Groetschel (ZIB, Berlin)
Jose Meseguer (SRI)
Philip Wadler (Avaya Labs
Satellite Events:
Tutorial Workshop on Recent Advances in Programming Languages
December 11-12, 2000 at IIT Delhi, Hauz Khas
Workshop on Geometry
December 16-17, 2000 at IIT Delhi, Hauz Khas
FST TCS 2000 Preliminary Programme
13 December 2000
9:00-9:30 Opening
9:30-10:30 Invited Talk: E Allen Emerson
Model Checking: Theory into Practice
10:30-11:00 Tea
11:00-12:30 40. Fast On-line/Off-line 100. Model checking CTL
Algorithms for Optimal Properties of Pushdown Systems
Reinforcement of a Network Igor Walukiewicz
and its Connections with
Principal Partition
H. Narayanan, Sachin B. Patkar
59. On-Line Edge-Coloring 125. A Decidable Dense
with a Fixed Number of Colors Branching-time Temporal Logic
Lene Monrad Favrholdt, Salvatore La Torre and
Morten Nyhave Nielsen Margherita Napoli
15. On Approximability of the 126. Fair Equivalence Relations
Independent/Connected Edge Orna Kupferman, Nir Piterman,
Dominating Set Problems Moshe Vardi
Toshihiro Fujito
12:30-14:00 Lunch
14:00-15:00 Invited Talk: Philip Wadler
An Algebra for XML Query
15:00-15:30 Tea
15:30-17:00 8. Arithmetic Circuits and 113. Combining Semantics with
Polynomial Replacement Systems Non-Standard Interpreter
Pierre McKenzie, Heribert Hierarchies
Vollmer, Klaus W. Wagner Sergei Abramov, Robert Glueck
70. Depth-3 Arithmetic Circuits 112. Using Modes to Ensure
for S(2,n)(X) and Extensions of Subject Reduction for Typed
the Graham-Pollack Theorem Logic Programs with Subtyping
Jaikumar Radhakrishnan, Pranab Jan-Georg Smaus, Francois
Sen, Sundar Vishwanathan Fages, Pierre Deransart
130. The Weak Monadic Quantifier 23. Dynamically Ordered
Alternation Hierarchy of Probabilistic Choice Logic
Equational Graphs is Infinite Programming
Ly Olivier Marina De Vos, Dirk Vermeir
14 December 2000
9:00-10:00 Invited Talk: Bernard Chazelle
Irregularities of Distribution, Derandomization, and
Complexity Theory
10:10-11:10 147. Coordinatized Kernels and
Catalytic Reductions: Improved 12. A Complete Fragment of
FPT Algorithms for Max Leaf Higher-Order Duration
Spanning Tree and Other Problems $\mu$-Calculus
Michael R. Fellows, Catherine Dimitar P. Guelev
McCartin, Ulrike Stege, Frances
A. Rosamond
53. Planar Graph Blocking for 39. A Complete Axiomatisation
External Searching for Timed Automata
Surender Baswana, Sandeep Sen Huimin Lin and Wang Yi
11:10-11:30 Tea
11:30-12:30 124. Text Sparsification via 120. Semantic Theory for
Local Maxima Heterogeneous System Design
Pierluigi Cresceznzi, Alberto Rance Cleaveland, Gerald
Del Lungo, Roberto Grossi, Luettgen
Elena Lodi, Linda Palgi,
Gianluca Rossi
38. Approximate Swapped Matching 133. Formal Verification of the
A Amir, M Lewenstein, E. Porat Ricart-Agrawala Algorithm
Ekaterina Sedletsky, Amir
Pnueli, Mordechai Ben-Ari
12:30-14:00 Lunch
14:00-15:00 Invited Talk: Jose Meseguer
Rewriting Logic as a Metalogical Framework
15:00-15:30 Tea
15:30-17:00 96. On distribution-specific 117. A General Framework for
learning with membership queries Types in Graph Rewriting
versus pseudorandom generation Barbara Koenig
Johannes Köbler, Wolfang Lindner
69. $\Theta_2^p$-completeness: 146. The Ground Congruence for
A classical approach for new Chi Calculus
results Yuxi Fu, Zhenrong Yang
Joel Vogel, Holger Spakowski
110. Is the Standard Proof System 122. Inheritance in the Join
for SAT P-optimal? Calculus
Johannes Köbler, Jochen Messner Cedric Fournet, Cosimo Laneve,
Luc Maranget Didier Remy
15 December 2000
9:00-10:00 Invited Talk: Martin Grötschel
Frequency Assignment in Mobile Phone Systems
10:10-11:10 65. Approximation Algorithms 118. The Fine Structure of
for Bandwidth and Storage Game Lambda Models
Allocation Problems under Real Pietro Di Gianantonio,
Time Constraints Gianluca Franco
Stefano Leonardi, Alberto
Marchetti-Spaccamela,
Andrea Vitaletti
37. Dynamic Spectrum Allocation: 127. Strong Normalisation of
The Impotency of Duration Second Order Symmetric
Notification Lambda-calculus
Bala Kalyanasundaram, Kirk Pruhs Michel Parigot
11:10-11:30 Tea
11:30-12:30 94. Scheduling to minimize the 49. Keeping Track of the Latest
average completion time of Gossip in Shared Memory Systems
dedicated tasks Bharat Adsul, Aranyak Mehta,
Foto Afrati, Eviripidis Bampis, Milind Sohoni
Aleksei V. Fishin, Klaus Jansen
Claire Keyon
73. Hunting for Functionally 123. On Concurrent Knowledge
Analogous Genes and Logical Clock Abstractions
M. T. Hallett, J. Lagergren Ajay Kshemkalyani
12:30-14:00 Lunch
14:00-15:00 Invited Talk: Peter Buneman
Data Provenance: Some Basic Issues
15:00-15:30 Tea
15:30-16:30 20. Decidable Hierarchies of
Starfree Languages
Christian Glasser, Heinz Schmitz
58. Prefix languages of
Church-Rosser Languages
Jens R. Woinowski
16:30-17:00 Closing
Organization:
FST TCS 2000 is being organized by the Indian Institute of Technology,
Delhi under the aegis of the Indian Association for Research in
Computer Science (IARCS).
--
Sanjiva Prasad
Associate Professor
Department of Computer Science and Engineering sanjiva@cse.iitd.ernet.in
Indian Institute of Technology, Delhi (Off) +91 11 659 1294
Hauz Khas, New Delhi 110016 (Res) +91 11 659 1684
INDIA (Fax) +91 11 686 8765
http://www.cse.iitd.ernet.in/~sanjiva
From rrosebru@mta.ca Wed Nov 1 16:03:12 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eA1JTpu27022
for categories-list; Wed, 1 Nov 2000 15:29:51 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
To: categories
Date: Mon, 30 Oct 2000 14:50:22 -0500
From: Rick Jardine
Subject: categories: Conference on Algebraic Topological Methods in Computer Science
Message-ID:
MIME-Version: 1.0
Sender: cat-dist@mta.ca
Precedence: bulk
Status: RO
X-Status:
X-Keywords:
X-UID: 7
First Announcement:
Conference on Algebraic Topological Methods in Computer Science
Department of Mathematics
Stanford University
July 30 - August 3, 2001
The application of algebraic topological methods in areas related to
Computer Science is an emerging field that is of interest to both pure
and applied mathematical scientists. The aim of this conference is to
describe recent advances, and define the fundamental open problems
in the field through a mixture of expository and technical lectures. There
will be twenty lectures, on a variety of topics in the area.
The following is a preliminary list of invited speakers:
John Baez (Math, UC Riverside)
Marshall Bern (Xerox PARC)
Tamal Dey (CS, Ohio State)
Herbert Edelsbrunner (CS, Duke)
David Eppstein (CS, UC Irvine)
Michael Freedman (Microsoft)
Philippe Gaucher (CNRS, Strasbourg)
Eric Goubault (Commissariat a l'Energie Atomique, France)
Jean Goubault-Larrecq (ENS Cachan)
Marco Grandis (Dip. di Mat., Genova)
Jeremy Gunawardena (HP BRIMS)
Joel Hass (Math Dept, UC Davis)
Maurice Herlihy (CS, Brown)
Reinhard Laubenbacher (NMSU)
Laszlo Lovasz (Microsoft)
Vaughan Pratt (CS, Stanford)
Christian Reidys (Los Alamos National Lab)
Bernd Sturmfels (Math Dept, UC Berkeley)
Noson Yanofsky (CS, Brooklyn College)
All conference announcements and information will be available at the
web site:
http://www.math.uwo.ca/~jardine/at-cs.html
The organizers for this meeting are:
Gunnar Carlsson: gunnar@math.stanford.edu
Rick Jardine: jardine@uwo.ca
From rrosebru@mta.ca Thu Nov 2 10:32:29 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eA2DLcS00403
for categories-list; Thu, 2 Nov 2000 09:21:38 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Message-ID: <3A014237.B31FE524@bangor.ac.uk>
Date: Thu, 02 Nov 2000 10:30:15 +0000
From: Ronnie Brown
X-Mailer: Mozilla 4.75 [en] (Win98; U)
X-Accept-Language: en
MIME-Version: 1.0
To: categories@mta.ca
Subject: categories: Re: Category Theory from RFC Walters' book
References: <200011011244.eA1CiKt07396@nmh.informatik.uni-bremen.de>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 8
It could be useful to mention the paper
29 #1239 Higgins, Philip J., Algebras with a scheme of operators. Math. Nachr. 27
1963 115--132. (Reviewer: A. Heller) 18.10
which discusses partial algebras at an early date.
Ronnie Brown
Till Mossakowski wrote:
> >It is folklore that the method of generators and relations works for any
> >essentially algebraic theory with finitary operators, as well as for some
> >more general ones. "Algebraic" means defined by operators and equational
> >laws (could be many-sorted); "essentially" means that the operators may be
> >partial, with their domains of definition described by finite sets of
> >equations.
>
> >I wish I knew of an introductory text describing the techniques at this
> >level of generality, but unfortunately I'm not aware of any - maybe somebody
> >can suggest one. Manes's book "Algebraic Theories" is quite good on the
> >algebraic case.
>
> @BOOK{Reichel,
> AUTHOR = "Horst Reichel",
> TITLE ="Initial Computability, Algebraic Specifications and Partial Algebras",
> PUBLISHER = "Oxford Science Publications",
> YEAR = 1987}
>
> contains an elementary introduction to essentially algebraic theories;
> also, the theory of categories is used as an example.
>
> Till Mossakowski
>
> -----------------------------------------------------------------------------
> Till Mossakowski Phone +49-421-218-4683, monday: +49-4252-1859
> Dept. of Computer Science Fax +49-421-218-3054
> University of Bremen till@informatik.uni-bremen.de
> P.O.Box 330440, D-28334 Bremen http://www.informatik.uni-bremen.de/~till
> -----------------------------------------------------------------------------
--
Prof R. Brown,
School of Informatics, Mathematics Division,
University of Wales, Bangor
Dean St., Bangor,
Gwynedd LL57 1UT, United Kingdom
Tel. direct:+44 1248 382474|office: 382475
fax: +44 1248 361429
World Wide Web:
home page: http://www.bangor.ac.uk/~mas010/
(Links to survey articles:
Higher dimensional group theory
Groupoids and crossed objects in algebraic topology)
Symbolic Sculpture and Mathematics:
http://www.cpm.sees.bangor.ac.uk/sculmath/
Centre for the Popularisation of Mathematics
http://www.cpm.sees.bangor.ac.uk/
Raising Public Awareness of Mathematics
http://www.cpm.sees.bangor.ac.uk/rpamath/
From rrosebru@mta.ca Thu Nov 2 10:32:44 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eA2DKFB30689
for categories-list; Thu, 2 Nov 2000 09:20:15 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: Wed, 1 Nov 2000 21:22:24 -0500 (EST)
From: F W Lawvere
Reply-To: wlawvere@ACSU.Buffalo.EDU
To: categories@mta.ca
Subject: categories: Adjoint cylinders
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 9
I would be happy to learn the results which Till Mossakowski has found
concerning those situations involving an Adjoint Unity and Identity of
Opposites as I discussed in my "Unity and Identity of Opposites in
Calculus and Physics",in Applied Categorical Structures vol.4, 167-174,
1996.
Two parallel functors are adjointly opposite if they are full and
faithful and if there is a third functor left adjoint to one and right
adjoint to the other; the two subcategories are opposite as such but
identical if one neglects the inclusions.
A simple example which I recently noted is even vs odd. That is, taking
both the top category and the smaller category to be the poset of
natural numbers, let L(n)=2n but R(n)=2n+1. Then the required middle
functor exists; a surprising formula for it can be found by solving a
third-order linear difference equation.
I hope that Till Mossakowski's results may help to compute some other
number-theoretic functions that arise by confronting Hegel's Aufhebung
idea (or one mathematical version of it) with multi-dimensional
combinatorial topology. Consider the set of all such AUIO situations
within a fixed top category. This set of "levels" is obviously ordered by
any of the three equivalent conditions :
L1 belongs to L2, R1 belongs to R2, F2 depends on F1.
(Here "belongs" and "depends" just mean the existence of
factorizations, but in dual senses). However there is also the stronger
relation that
L1 might belong to R2;
for a given level, there may be a smallest higher level which is strongly
higher in that sense, and if so it may be called the Aufhebung of the
given level.
In case the given containing category is such that the set of all
levels is isomorphic to the natural numbers with infinity (the top) and
minus infinity (the initial object=L and terminal object=R), then the
Aufhebung exists, but the specific function depends on the category.
Mike Roy in his 1997 U. of Buffalo thesis studied the topos of ball
complexes, finding in particular that both Aufhebung and coAufhebung exist
and that they are both equal to the successor function on dimensions.
Still not calculated is that function for the topos of presheaves on the
category of nonempty finite sets. This category is important logically
because the presheaf represented by 2 is generic among all Boolean algebra
objects in all toposes defined over the same base topos of sets, and
topologically because of its close relation with classical simplicial
complexes. Here the levels or dimensions just correspond to those
subcategories of finite sets that are closed under retract. It is easy to
see that the Aufhebung of dimension 0 (the one point set) is dimension 1
(the two-point set and its retracts), but what is the general formula ?
************************************************************
F. William Lawvere
Mathematics Department, State University of New York
244 Mathematics Building, Buffalo, N.Y. 14260-2900 USA
Tel. 716-645-6284
HOMEPAGE: http://www.acsu.buffalo.edu/~wlawvere
************************************************************
From rrosebru@mta.ca Thu Nov 2 14:28:23 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eA2Hjx004470
for categories-list; Thu, 2 Nov 2000 13:45:59 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Message-ID: <3A019FB6.2454C847@brics.dk>
Date: Thu, 02 Nov 2000 18:09:10 +0100
From: Luigi Santocanale
X-Mailer: Mozilla 4.76 [en] (X11; U; SunOS 5.7 sun4u)
X-Accept-Language: en
MIME-Version: 1.0
To: "Categories@Mta. Ca"
Subject: categories: Re: coinduction: definable equationally?
References: <200010280923.CAA10190@coraki.Stanford.EDU>
Content-Type: text/plain; charset=iso-8859-1
Sender: cat-dist@mta.ca
Precedence: bulk
Status: RO
X-Status:
X-Keywords:
X-UID: 10
Vaughan Pratt wrote:
> We may now reword the original question in the light of the foregoing.
> To what variety can one similarly associate suitable operations fully
> defined equationally so as to include an equationally expressed principal
> of coinduction?
In the same way an induction principle is expressible by means of a
least fixed point, one could expect coinductive principles to be
expressible by means of greatest fixed points.
The following example will clarify what I have in mind.
Let G,H two graphs, then we can construct the graph G*H, where
(G*H)_0 = G_0 x H_0
and
(G*H)_1 = (G_1 x H_0) + (G_0 x H_1) .
Every transition of G*H is labeled: it is either a left transition or a
right transition. We obtain in this way two modal operators on the
subsets of G_0 x H_0, call them and . A bisimulation is a subset
B of G_0 x H_0 such that
B <= [r]B and B <= [l] ,
where the [] are the duals of <>. If G = H, then saying that G has no
proper quotient amounts to saying that the greatest bisimulation is
equal to the diagonal D. Therefore a principle of coinduction can be
expressed as follows:
\nu_z.([r]z \wedge [l]z) = D
where \nu_z.f(z) is the greatest fixed point of f(z). The example can be
generalized.
The following question arises: is the greatest postfixed point definable
equationally? The answer is yes, at least in several cases, as it is the
least prefixed point.
Consider a theory which contains the signature <0,+,.,\>. <0,+> satisfy
the semilattice axioms and, with respect to induced order, a.x is left
adjoint to a\x, for a fixed a. Let f(z) be any term of the theory, then
the following holds:
g(x) is the parameterized least prefixed point of f(z).x if and only if
the equations
f(g(x)).x = g(x)
g(x) <= g(x+y)
g(f(x)\x) <= x
hold.
It is an easy exercise to check this is true, using the fact that
f(x).(f(x)\x) <= x . If . has a right unit 1, then g(1) is the least
prefixed point of f(z). Similar results hold for the greatest postfixed
point if we can find an operation . with a parameterized right adjoint.
Algebraic models of the propositional $\mu$-calculus form a variety, as
the models of PDL do, and hopefully coinductive principles can be
expressed. One could also define something like a $\mu$-linear logic,
its models would form a variety.
Best regards,
Luigi
--
Luigi Santocanale,
BRICS
Department of Computer Science Telephone: +45 8942 3288
University of Aarhus Telefax: +45 8942 3255
Ny Munkegade, building 540 http://www.brics.dk/~luigis/
DK - 8000 Århus C, Denmark. mailto:luigis@brics.dk
From rrosebru@mta.ca Sun Nov 5 12:05:24 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eA5FOxU24439
for categories-list; Sun, 5 Nov 2000 11:24:59 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
X-Authentication-Warning: triples.math.mcgill.ca: barr owned process doing -bs
Date: Sun, 5 Nov 2000 08:37:48 -0500 (EST)
From: Michael Barr
X-Sender: barr@triples.math.mcgill.ca
To: Categories list
Subject: categories: preprint: Paper on derived functors
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 11
The files derfun.ps and derfun.pdf are now at ftp.math.mcgill.ca/pub/barr
for anonymous ftp. It does what I promised a few weeks ago: derived
functors in the absence of enough projectives.
From rrosebru@mta.ca Sun Nov 5 12:09:45 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eA5FNmU27759
for categories-list; Sun, 5 Nov 2000 11:23:48 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
X-Authentication-Warning: triples.math.mcgill.ca: barr owned process doing -bs
Date: Sun, 5 Nov 2000 05:23:28 -0500 (EST)
From: Michael Barr
X-Sender: barr@triples.math.mcgill.ca
To: Categories list
Subject: categories: Adjoint cylinders
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 12
In this discussion of adjoint cylinders, I haven't noticed anyone
pointing out that when L --| F --| R, then FL = Id (I use = for natural
equivalence here) iff FR = Id. Dusko told me earlier this year that it
was in his thesis, but I would not be surprised if it were older than
that. Here is a simple proof. Let eta: Id --> FL be the inner
adjunction of L --| F and epsilon: FR --> Id be the outer adjunction of
F --| R. Then if alpha F means apply F,the composites
alpha F Hom(eta-,F-)
Hom(L-,-) -------> Hom(FL-,F-) ------------> Hom(-,F-)
alpha F Hom(F-,epsilon-)
Hom(-,R-) -------> Hom(F-,FR-) ----------------> Hom(F-,-)
are isomorphisms. Then there is a commutative square (both composites
are Hom(eta-,epsilon -) o alpha F):
Hom(eta-,FR-) o alpha F
Hom(L-,R-) ------------------------> Hom(-,FR-)
| |
| |
| |
| |
Hom(FL-,epsilon-) o alpha F Hom(-,epsilon-)
| |
| |
| |
v Hom(eta,-) v
Hom(FL,-) -------------------------> Hom(-,-)
in which the upper and left hand maps are isomorphisms and it follows
that the bottom arrow is an isomorphism iff the right hand one is.
From rrosebru@mta.ca Sun Nov 5 19:47:44 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eA5NEUU04662
for categories-list; Sun, 5 Nov 2000 19:14:30 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Subject: categories: Re: Adjoint cylinders
Date: Sun, 5 Nov 2000 15:58:26 +0000 (GMT)
To: categories@mta.ca (Categories list)
In-Reply-To: from "Michael Barr" at Nov 05, 2000 05:23:28 AM
X-Mailer: ELM [version 2.5 PL2]
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Message-Id:
From: "Dr. P.T. Johnstone"
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 13
Mike Barr wrote:
> In this discussion of adjoint cylinders, I haven't noticed anyone
> pointing out that when L --| F --| R, then FL = Id (I use = for natural
> equivalence here) iff FR = Id. Dusko told me earlier this year that it
> was in his thesis, but I would not be surprised if it were older than
> that. Here is a simple proof....
Here is an even simpler one: FL is left adjoint to FR, by composability
of adjoints; the identity functor is left adjoint to itself.
Peter Johnstone
From rrosebru@mta.ca Sun Nov 5 19:47:48 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eA5NFoL07999
for categories-list; Sun, 5 Nov 2000 19:15:50 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
X-Received: from zent.mta.ca (zent.mta.ca [138.73.101.4])
by mailserv.mta.ca (8.11.1/8.11.1) with SMTP id eA5LpjF27088
for ; Sun, 5 Nov 2000 17:51:45 -0400 (AST)
X-Received: FROM callisto.acsu.buffalo.edu BY zent.mta.ca ; Sun Nov 05 17:55:36 2000 -0400
X-Received: (qmail 19946 invoked by uid 39883); 5 Nov 2000 21:51:44 -0000
Date: Sun, 5 Nov 2000 16:51:43 -0500 (EST)
From: F W Lawvere
Reply-To: wlawvere@ACSU.Buffalo.EDU
To: categories
Subject: categories: Adjoint cyclinders in Mitchell
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: cat-dist@mta.ca
Precedence: bulk
Status: RO
X-Status:
X-Keywords:
X-UID: 14
The fact that, given a string of three adjoints, the first is full and
faithful iff the third one is, can be found in Barry Mitchell's 1960 book.
************************************************************
F. William Lawvere
Mathematics Department, State University of New York
244 Mathematics Building, Buffalo, N.Y. 14260-2900 USA
Tel. 716-645-6284
HOMEPAGE: http://www.acsu.buffalo.edu/~wlawvere
************************************************************
From rrosebru@mta.ca Mon Nov 6 11:57:01 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eA6F7KJ15682
for categories-list; Mon, 6 Nov 2000 11:07:20 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: Mon, 6 Nov 2000 08:40:01 +0000 (GMT)
From: Dr Anne Heyworth
To: categories@mta.ca
Subject: categories: opinions wanted
In-Reply-To:
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 15
I had an idea and I'd like to know whether you like it and some advice on
making it work if you do.
There are quite a few interesting tales about category theorists around. I
think it will be a shame to lose this more human history as time passes
and us newer category theorists can't completely remember the stories....
So I'd like to set up a kind of archive - a sort of myths and legends of
the category theorists (but preferably more truth than myth!).
This is the plan so far (assuming you think this is not a terrible idea).
Format:
An email-style archive with tales/histories/mini-biographies submitted by
email in plain text and linked to from a page of titles (titles would
include rough dates, authors and characters - which would make it easily
searchable so you can easily read about your particular heroes!).
Procedure:
Email sent to me which would have to be accepted by every living character
in the story (for obvious reasons). Some procedure should be agreed for
the acceptance of stories about people no longer alive.
The best stories, I guess, will be those people write about themselves.
This is just an idea, I hope you will let me know whether you approve.
--Anne.
-----
Have you visited www.thehungersite.com
and www.therainforestsite.com today?
-----
From rrosebru@mta.ca Mon Nov 6 14:48:35 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eA6I2mg32691
for categories-list; Mon, 6 Nov 2000 14:02:48 -0400 (AST)
Message-Id: <200011061802.eA6I2mg32691@mailserv.mta.ca>
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: Mon, 6 Nov 2000 18:43:07 +0100 (MET)
From: Kristina Striegnitz
To: categories@mta.ca
Subject: categories: CFP: ESSLLI 01 Student Session
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Content-Transfer-Encoding: 8bit
X-MIME-Autoconverted: from QUOTED-PRINTABLE to 8bit by mailserv.mta.ca id eA6HsnF30908
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 20
!!! Concerns all students in Logic, Linguistics and Computer Science !!!
!!! Please circulate and post among students !!!
We apologize, if you receive this message more than once.
ESSLLI 2001 STUDENT SESSION
FIRST CALL FOR PAPERS
August 13-24 2001, Helsinki, Finland
Deadline: February 18, 2001
http://www.coli.uni-sb.de/~kris/esslli
We are pleased to announce the Student Session of the 13th European
Summer School in Logic, Language and Information (ESSLLI 2001)
organized by the University of Helsinki under the auspices of the
European Association for Logic, Language and Information
(FoLLI). ESSLLI 2001 will be held at the University of Helsinki in
August 2001. We invite submission of papers for presentation at the
ESSLLI 2001 Student Session and for appearance in the proceedings.
PURPOSE:
This sixth ESSLLI Student Session will provide, like the other
editions, an opportunity for ESSLLI participants who are students to
present their own work in progress and get feedback from senior
researchers and fellow-students. The ESSLLI Student Session
encourages submissions from students at any level, from undergraduates
(before completion of the Master Thesis) as well as postgraduates
(before completion of the PhD degree). Papers co-authored by
non-students will not be accepted. Papers may be accepted for full
presentation (30 minutes including 10 minutes of discussion) or for a
poster presentation. The accepted papers will be published in the
ESSLLI 2001 Student Session proceedings, which will be made available
during the summer school.
KLUWER BEST PAPER AWARD:
As in previous years, the best paper will be selected by the program
committee and will be offered a prize by Kluwer Academic Publishers
consisting in 1000 Dfl worth of books.
REQUIREMENTS:
The Student Session papers should describe original, unpublished work,
completed or in progress that demonstrates insight, creativity, and
promise. No previously published papers should be submitted. All
topics within the six ESSLLI subject areas (Logic, Language,
Computation, Logic & Language, Logic & Computation, Language &
Computation) are of interest.
FORMAT OF SUBMISSION:
Student authors should submit an anonymous extended abstract headed by
the paper title, not to exceed 5 pages in length exclusive of
references and send a separate identification page (see below). Note
that the length of the full papers will not be allowed to exceed 10
pages. Since reviewing will be blind, the body of the abstract should
omit author names and addresses. Furthermore, self-references that
reveal the author's identity (e.g., "We previously showed (Smith,
1991)... ") should be avoided. It is possible to use instead
references like "Smith (1991) previously showed...". For any
submission, a plain ASCII text version of the identification page
should be sent separately, using the following format:
Title: title of the submission
First author: firstname lastname
Address: address of the first author
......
Last author: firstname lastname
Address: address of the last author
Short summary: abstract (5 lines)
Subject area (one of): Logic | Language | Computation | Logic and
Language | Logic and Computation | Language and Computation
If necessary, the program committee may reassign papers to a more
appropriate subject area. The submission of the extended abstract
should be in one of the following formats: PostScript, PDF, RTF, or
plain text. But note that, in case of acceptance, the final version of
the paper has to be submitted in LaTeX format. Please, use A4 size
pages, 11pt or 12pt fonts, and standard margins. Submissions outside
the specified length and formatting requirements may be subject to
rejection without review.
The extended abstract and separate identification page must be sent by
e-mail to:
kris@coli.uni-sb.de by FEBRUARY 18, 2001
ESSLLI 2001 INFORMATION:
In order to present a paper at ESSLLI 2001 Student Session, at least
one student author of each accepted paper has to register as a
participant at ESSLLI 2001. The authors of accepted papers will be
eligible for reduced registration fees. For all information concerning
ESSLLI 2001, please consult the ESSLLI 2001 web site at
http://www.helsinki.fi/esslli.
IMPORTANT DATES:
Deadline for submission of abstracts: February 18, 2001.
Authors Notifications: April 17, 2001.
Final version due: May 18, 2001.
ESSLLI-2001 Student Session: August 13-24, 2001.
PROGRAM COMMITTEE:
Raffaella Bernardi, University of Utrecht (Logic & Language)
Patrick Blackburn, University of the Saarland (Logic & Language)
Gilles Dowek, INRIA (Computation)
Ruth Kempson, King`s College London (Language)
Carsten Lutz, University of Aachen (Logic & Computation)
Ani Nenkova, Columbia University (Logic)
Ilkka Niemelä, Helsinki University of Technology (Logic & Computation)
Malvina Nissim, University of Pavia (Language)
Susanne Salmon-Alt, Loria, Nancy (Language & Computation)
Jan Schwinghammer, University of the Saarland (Computation)
Kristina Striegnitz, University of the Saarland (Chair)
Yde Venema, University of Amsterdam (Logic)
Shuly Wintner, University of Haifa (Language & Computation)
For any question concerning the ESSLLI 2001 Student Session, please,
do not hesitate to contact me:
Kristina Striegnitz
Computational Linguistics, University of the Saarland, Germany
phone: +49 - 681 - 302 4503 email: kris@coli.uni-sb.de
From rrosebru@mta.ca Tue Nov 7 15:05:56 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eA7IMHl19617
for categories-list; Tue, 7 Nov 2000 14:22:17 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: Tue, 7 Nov 2000 10:31:33 +0000 (GMT)
From: Anne Heyworth
To: categories@mta.ca
Subject: categories: categorical myths and legends...
In-Reply-To:
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 21
Thanks very much for the positive responses.
I've started an archive using Bob's links to get the first two stories.
You can find the site at
http://www.mcs.le.ac.uk/~ah83/cat-myths
Comments/advice and submissions welcome.
--Anne.
From rrosebru@mta.ca Tue Nov 7 16:50:27 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eA7KIbF15742
for categories-list; Tue, 7 Nov 2000 16:18:37 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: Tue, 7 Nov 2000 14:45:23 -0500 (EST)
From: F W Lawvere
Reply-To: wlawvere@ACSU.Buffalo.EDU
To: categories@mta.ca
Subject: categories: DEVELOPMENT OF MATHEMATICS 1950-2000
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: cat-dist@mta.ca
Precedence: bulk
Status: RO
X-Status:
X-Keywords:
X-UID: 22
The book
DEVELOPMENT OF MATHEMATICS 1950-2000
edited by Jean-Paul Pier, and published by Birkhaeuser, recently
appeared. It has many good articles on the mathematics of the
stated period. Of course, the subjects were limited by space and
the choices made by the editorial board. In particular, categories,
homological algebra, etc. are not treated in separate articles.
My own paper
Comments on the Development of Topos Theory
pp 715 - 724
is rather compressed, due to space limitations. There are no doubt
many significant aspects which I was not able to include. The present
forum would perhaps be a good place to point those out.
Bill
************************************************************
F. William Lawvere
Mathematics Department, State University of New York
244 Mathematics Building, Buffalo, N.Y. 14260-2900 USA
Tel. 716-645-6284
HOMEPAGE: http://www.acsu.buffalo.edu/~wlawvere
************************************************************
From rrosebru@mta.ca Wed Nov 8 16:12:55 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eA8JIU216972
for categories-list; Wed, 8 Nov 2000 15:18:30 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: Wed, 8 Nov 2000 08:44:07 -0500 (EST)
From: F W Lawvere
Reply-To: wlawvere@ACSU.Buffalo.EDU
To: categories@mta.ca
Subject: categories: correction: DEVELOPMENT OF MATHEMATICS
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 23
My article
Comments on the Development of Topos Theory
is not AS compressed as my misprint suggested; it is on
pp 715 -734
of J.P. Pier's new book
DEVELOPMENT OF MATHEMATICS 1950 - 2000
Nonetheless, there are doubtless many aspects which are under-represented
in those pages. I hope that these aspects will be elaborated here on the
categories net.
************************************************************
F. William Lawvere
Mathematics Department, State University of New York
244 Mathematics Building, Buffalo, N.Y. 14260-2900 USA
Tel. 716-645-6284
HOMEPAGE: http://www.acsu.buffalo.edu/~wlawvere
************************************************************
From rrosebru@mta.ca Mon Nov 13 16:22:01 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eADJifd02692
for categories-list; Mon, 13 Nov 2000 15:44:42 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Message-ID: <3A102197.9A7FBE95@cs.keele.ac.uk>
Date: Mon, 13 Nov 2000 17:15:03 +0000
From: John Stell
Organization: Keele University
X-Mailer: Mozilla 4.08 [en] (WinNT; I)
MIME-Version: 1.0
To: categories@mta.ca
Subject: categories: Research Assistant Post
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 24
Post-Doctoral Research Assistant: Digital Topology and Geometry
Applications are invited for a Post Doctoral Research Assistant
at The University of Leeds to work on an EPSRC funded project
"Digital Topology and Geometry: An Axiomatic Approach, with Applications
to GIS and Spatial Reasoning". This is a joint project with Imperial
College,
London, where the Principal Investigator is Dr Mike Smyth.
The post will be based at the School of Computing, University of Leeds,
where there is a well-established research group in spatial reasoning.
There will be close collaboration with researchers at Imperial College,
and also with the Geographic Information Systems research group at
Keele University.
The post is available from 1st January 2001, but it may be possible to
agree
a slightly later starting date. The appointment is for a fixed term
of three years.
The principal aims of the project are
1. To develop an axiomatic theory of geometry that admits as models
discrete
spaces as well as classical continuos spaces such as Euclidean
spaces.
2. To produce topological and geometric structures which can be used as
the
basis of computational descriptions of natural phenomena.
Applications in
the areas of Geographic Information Systems (GIS) spatial reasoning
in
artificial inteligence (AI) will be investigated.
3. To extend digital topology as used in image analysis to a theory of
digital
geometry.
4. To design and implement algorithms within the developed digital
geometry
for tasks such as convex hull and Delauny triangulation.
The research assistant will work largely on the applications of the
geometric
theory including the development of algorithms and the evaluation of the
suitablility of the theory to problems in areas such as spatial
reasoning in AI,
GIS and image analysis. One phase of the project will focus on
applications to
multi-resolution spatial data: the description of geometric structure at
a variety
of levels of detail.
Candidates should have, or be about to complete a PhD in a relevant area
of
Computer Science, Mathematics, or Artificial Intelligence. Candidates
are not
expected to be familiar with all of the application areas mentioned
above, but
suitable research experience in one of the following areas would be
useful:
spatial reasoning, computational geometry, theory of image analysis,
computer
graphics, formal aspects of GIS. Applications are also welcome from
candidates whose main experience has been in a relevant area of topology
or geometry.
Details of the formal aplication procedure will be available
shortly, but anyone interested in this post should contact Dr John Stell
by email:
j.g.stell@cs.keele.ac.uk or by phone: 01782 584083.
From rrosebru@mta.ca Mon Nov 13 19:31:40 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eADNAaN19927
for categories-list; Mon, 13 Nov 2000 19:10:36 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
From: "Walter Tholen"
Message-Id: <1001113174128.ZM200386@pascal.math.yorku.ca>
Date: Mon, 13 Nov 2000 17:41:28 -0500
X-Mailer: Z-Mail (4.0.1 13Jan97)
To: categories@mta.ca
Subject: categories: papers available
Cc: tholen@pascal.math.yorku.ca
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 25
This is just to let you know that now ps-files of the following papers
(written during the past few months) are available via my home page at
http://www.math.yorku.ca/Who/Faculty/Tholen/research.html
Alternatively, I am happy to send hard copies upon request.
Regards, Walter.
J. Adamek, H. Herrlich, J. Rosicky, W. Tholen:
"On a generalized Small-Object Argument for the Injective Subcategory Problem"
J. Adamek, H. Herrlich, J. Rosicky, W. Tholen:
"Weak factorization systems and topological functors"
W. Tholen:
"Essential weak factorization systems"
M.M. Clementino, D. Hofmann, W. Tholen:
"The convergence approach to exponentiable maps"
G. Richter, W. Tholen:
"Perfect maps are exponentiable - categorically"
From rrosebru@mta.ca Tue Nov 14 10:26:01 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eAEDpCj23069
for categories-list; Tue, 14 Nov 2000 09:51:12 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
From: Etaps 2002
Date: Mon, 13 Nov 2000 19:54:23 +0100 (MET)
Message-Id: <200011131854.TAA12073@pierramenta.imag.fr>
Subject: categories: ETAPS 2002 - Call for Satellite Events
To: categories@mta.ca
Content-Type: text
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 26
(Apologies if you receive multiple copies of this announcement)
-----------------------------------------------------------------------
Call for Affiliated Workshops
ETAPS 2002
April 2002, Grenoble, France
http://www-etaps.imag.fr
-----------------------------------------------------------------------
ETAPS, the European Joint Conferences on Theory and Practice of
Software is a major international forum for academic and industrial
researchers working on topics relating to Software Science. After
ETAPS'98 in Lisbon, ETAPS'99 in Amsterdam, ETAPS 2000 in Berlin and
ETAPS 2001 in Genova, ETAPS 2002 will take place in Grenoble during
April 2002 (the precise dates will be communicated later).
ETAPS is a confederation of five main conferences: the International
Conference on Compiler Construction (CC), the European Symposium On
Programming (ESOP), Fundamental Approaches to Software Engineering
(FASE), Foundations of Software Science and Computation Structures
(FOSSACS) and Tools and Algorithms for the Construction and Analysis
of Systems (TACAS).
Workshops affiliated to ETAPS 2002 will be held before, after or
partly in parallel with the main conferences. Researchers and
practitioners wishing to organize a workshop affiliated to ETAPS 2002
are invited to submit, by electronic mail in ASCII or Postscript
format, proposals for workshops to the ETAPS 2002 Workshop Chair, by
December 1st, 2000. Such a proposal should be no longer than two pages
and should describe the topic of the workshop, the names and contact
information of the organizers, the estimated dates for paper
submissions, notification of acceptance and final versions (before
Ferbruary 15, 2002), the expected number of participants and duration,
the preferred period (pre- or post-ETAPS) and any other relevant
information (e.g., invited speakers, panels, publication policy, demo
sessions etc.).
The proposals will be evaluated by the ETAPS 2002 organizing committee
on the basis of their assessed benefit for prospective participants to
ETAPS 2002. Acceptance decisions will be made by December 15,
2000. The titles and brief information related to accepted workshop
proposals will be included in the conference program and advertised in
the call for participation. Workshop organizers will be responsible
for producing a Call for papers, Web site, reviewing and making
acceptance decisions on submitted papers and scheduling workshop
activities in consultation with the local organizers.
Any further information needed for preparing a workshop proposal can
be obtained by contacting the ETAPS 2002 Workshop Chair:
Rachid Echahed, Rachid.Echahed@imag.fr
Important dates :
December 1, 2000 : Workshop proposals
December 15, 2000 : Notification of acceptance
ETAPS 2002 Web site: http://www-etaps.imag.fr/
-------------
you received this e-mail via the individual
or collective address categories@mta.ca
From rrosebru@mta.ca Thu Nov 16 17:31:39 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eAGKknb28541
for categories-list; Thu, 16 Nov 2000 16:46:49 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: Thu, 16 Nov 2000 16:38:21 -0400 (AST)
From: Bob Rosebrugh
To: categories
Subject: categories: preprint: Factorization Systems and Distributive Laws
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: cat-dist@mta.ca
Precedence: bulk
Status: RO
X-Status:
X-Keywords:
X-UID: 27
The article whose abstract follows is available from
www.mta.ca/~rrosebru/
or in hard copy by request (pls include postal address).
Regards to all,
RJ Wood Bob Rosebrugh
------------------------------------------------------------------------
Factorization Systems and Distributive Laws
R. Rosebrugh and R. J. Wood
This article shows that the distributive laws of Beck in the bicategory of
sets and matrices determine strict factorization systems on their
composite monads ( = categories). Conversely, it is shown that strict
factorization systems on categories give rise to distributive laws.
Moreover, these processes are shown to be mutually inverse in a precise
sense. Further, an extension of the distributive law concept provides a
correspondence with the classical orthogonal factorization systems.
From rrosebru@mta.ca Fri Nov 17 20:59:11 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eAI06wl17110
for categories-list; Fri, 17 Nov 2000 20:06:58 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Message-ID: <3A15C1E4.8A84871C@kestrel.edu>
Date: Fri, 17 Nov 2000 15:40:20 -0800
From: Dusko Pavlovic
X-Mailer: Mozilla 4.5 [en] (X11; U; SunOS 5.5.1 sun4u)
X-Accept-Language: en
MIME-Version: 1.0
To: CATEGORIES mailing list
Subject: categories: catware?
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 28
hi.
i am wondering if there are any keen **software builders /
designers / developers** among the categorically minded?
there are several places that would be happy to have such
people, and
might be able to make them happy.
-- dusko
(needless to say, replies to me, preferably at
mailto:dusko@dusko.org,
rather than to the list.)
From rrosebru@mta.ca Thu Nov 23 14:28:46 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eANHd5H28124
for categories-list; Thu, 23 Nov 2000 13:39:05 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: 22 Nov 2000 08:57:20 -0000
Message-ID: <20001122085720.5917.qmail@dionysos.informatik.unibw-muenchen.de>
From: kahl@heraklit.informatik.UniBw-Muenchen.de
To: RelMiS@heraklit.informatik.UniBw-Muenchen.de
Subject: categories: RelMiS 2001 --- Call for Papers
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
X-MIME-Autoconverted: from 8bit to quoted-printable by gatesrv.rz.unibw-muenchen.de id JAA02656
Content-Transfer-Encoding: 8bit
X-MIME-Autoconverted: from quoted-printable to 8bit by mailserv.mta.ca id eAM96ct11147
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 29
Please accept my apologies if you receive multiple copies of this call.
-----------------------------------------------------------------------
RelMiS 2001 - Relational Methods in Software
============================================
7-8 April 2001, Genova, Italy
http://ist.unibw-muenchen.de/RelMiS/
A Satellite Event to ETAPS 2001
Motivation
==========
The role of the calculus of relations in algebra and logic is now well
understood and appreciated; relational methods should be part of the
``toolbox'' of everyone who uses mathematics, and relational methods can
also be of great value to everyone who develops or uses computer science.
For example, much of the work on special logics or ``laws'' for programs is
easily understood as an application of relational algebra. Also, every
relation on a state space can be used as a specification or description of a
program. This, in itself, is an advantage over some predicate based
formalism in which one can write ``specifications'' that are impossible to
satisfy.
Computer science, as a new application field for
relational methods, has both drawn from and contributed to previous
logico/mathematical work. Further integration of the two areas of research
would benefit both.
The purpose of this event is to provide (1) a tutorial introduction to
relational methods for computer scientists and software developers, and
(2) a workshop to discuss new results and future work.
7 April: Tutorial Day
=====================
There will be the following tutorial lectures:
* Gunther Schmidt: Basics of Relational Methods (9:30 - 11:00)
* David L. Parnas: The Tabular Method for Relational Documentation (11:30
- 13:00)
* Wolfram Kahl: Refinement and Development of Programs from Relational
Specifications (14:30 - 16:00)
* Rudolf Berghammer: Prototyping and Programming with Relations (16:30 -
18:00)
8 April:
Workshop ``Relational Methods in Software Development - Current Issues''
========================================================================
The second day of the RelMiS event will be an open workshop. Topics of the
workshop include, but are not limited to:
* Relational Specifications and Modelling:
methods and tools, tabular methods, abstract data types
* Relational Software Design and Development Techniques:
relational refinement, heuristic approaches for derivation, correctness
considerations, dynamic programming, greedy algorithms, catamorphisms,
paramorphisms, hylomorphisms and related topics
* Programming with Relations:
prototyping, testing, fault tolerance, information systems, information
coding
* Implementing relational algebra with mixed representation of relations
* Handling of Large Relations:
problems of scale, innovative representations, distributed
implementation
The number of papers will be kept small to allow extensive discussion.
Programme Committee
===================
Rudolf Berghammer (Kiel), Jules Desharnais (Québec), Wolfram Kahl (Munich),
David L. Parnas (Hamilton), Gunther Schmidt (Munich)
Submissions
===========
Submissions will be evaluated by the Program Committee for inclusion in the
proceedings, which will be published in the ENTCS series. Papers must
contain original contributions, be clearly written, and include appropriate
reference to and comparison with related work. Papers should be submitted
electronically as uuencoded PostScript files at the address
relmis@ist.unibw-muenchen.de. Preference will be given to papers that are no
shorter than 10 and no longer than 15 pages. A separate message should also
be sent, with a text-only one-page abstract and with mailing addresses (both
postal and electronic), telephone number and fax number of the corresponding
author.
Final versions will have to be submitted as LaTeX source and have to adhere
to the ENTCS style!
Important Dates
===============
Deadline for submission: 10 January 2001.
Notification of acceptance: 9 February 2001.
Final version due: 28 February 2001.
Workshop dates: 7-8 April 2001.
Organising Committee
====================
Wolfram Kahl
Federal Armed Forces University Munich, Germany
David L. Parnas
McMaster University, Hamilton, Ontario, Canada
Gunther Schmidt
Federal Armed Forces University Munich, Germany
Contact
=======
Contact Person: Wolfram Kahl
E-Mail: relmis@ist.unibw-muenchen.de
Workshop home page: URL: http://ist.unibw-muenchen.de/RelMiS/
From rrosebru@mta.ca Thu Nov 23 14:29:12 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eANHeeO25668
for categories-list; Thu, 23 Nov 2000 13:40:40 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Message-ID: <3A1CDA31.3FE90212@di.unipi.it>
Date: Thu, 23 Nov 2000 09:49:54 +0100
From: Andrea Corradini
Organization: Dipartimento di Informatica - Pisa
X-Mailer: Mozilla 4.72 [en] (X11; U; Linux 2.2.14-5.0 i686)
X-Accept-Language: en, it
MIME-Version: 1.0
To: categories@mta.ca
Subject: categories: CMCS 2001 - Call for Papers
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 30
============================================================
C A L L F O R P A P E R S
4th International Workshop on
Coalgebraic Methods in Computer Science (CMCS2001)
Genova, Italy
6-7 April 2001
A satellite workshop of ETAPS 2001
------------------------------------------------------------
Aims and Scope
During the last few years, it is becoming increasingly clear
that a great variety of state-based dynamical systems, like
transition systems, automata, process calculi and
class-based systems can be captured uniformly as
coalgebras. Coalgebra is developing into a field of its own
interest presenting a deep mathematical foundation, a
growing field of applications and interactions with various
other fields such as reactive and interactive system theory,
object oriented and concurrent programming, formal system
specification, modal logic, dynamical systems, control
systems, category theory, algebra, analysis, etc. The aim of
the workshop is to bring together researchers with a common
interest in the theory of coalgebras and its applications.
The topics of the workshop include, but are not limited to:
* the theory of coalgebras (including set theoretic and
categorical approaches);
* coalgebras as computational and semantical models (for
programming languages, dynamical systems, etc.);
* coalgebras in (functional, object-oriented, concurrent)
programming;
* coalgebras and data types;
* (coinductive) definition and proof principles for
coalgebras (with bisimulations or invariants);
* coalgebras and algebras;
* coalgebraic specification and verification;
* coalgebras and (modal) logic;
* coalgebra and control theory (notably of discrete event
and hybrid systems).
The workshop will provide an opportunity to present recent
and ongoing work, to meet colleagues, and to discuss new
ideas and future trends.
Previous workshops of the same series have been organized in
Lisbon, Amsterdam and Berlin. The proceedings appeared as
ENTCS Vols. 11,19 and 33.
------------------------------------------------------------
Location
CMCS2001 will be held in Genova on 6-7 April 2001, just
after ETAPS2001 (European Joint Conferences on Theory and
Practice of Software).
------------------------------------------------------------
Program Committee
Alexandru Baltag (Amsterdam), Andrea Corradini (Pisa), Bart
Jacobs (Nijmegen), Marina Lenisa (Udine), Ugo Montanari
(chair, Pisa), Larry Moss (Bloomington, IN), Ataru
T. Nakagawa (Tokyo), Dusko Pavlovic (Palo Alto), John Power
(Edinburgh), Horst Reichel (Dresden), Jan Rutten (Amsterdam).
------------------------------------------------------------
Submissions
Submissions will be evaluated by the Program Committee for
inclusion in the proceedings, which will be published in the
ENTCS series. Papers must contain original contributions, be
clearly written, and include appropriate reference to and
comparison with related work. Papers (of at most 15 pages)
should be submitted electronically as uuencoded PostScript
files at the address cmcs2001@di.unipi.it.
A separate message should also be sent, with a text-only
one-page abstract and with mailing addresses (both postal
and electronic), telephone number and fax number of the
corresponding author.
------------------------------------------------------------
Important Dates
Deadline for submission: 2 January 2001.
Notification of acceptance: 20 February 2001.
Final version due: 10 March 2001.
Workshop dates: 6-7 April 2001.
------------------------------------------------------------
Organizers
Andrea Corradini (Pisa), Marina Lenisa (Udine),
Ugo Montanari (Pisa).
------------------------------------------------------------
For more information:
http://www.di.unipi.it/~ugo/CMCS2001.html
mailto:cmcs2001@di.unipi.it
============================================================
From rrosebru@mta.ca Fri Nov 24 12:06:03 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eAOFXkJ00061
for categories-list; Fri, 24 Nov 2000 11:33:46 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Message-Id: <200011241013.eAOADct10088@mailserv.mta.ca>
From: gmh@marian.cs.nott.ac.uk
To: categories@mta.ca
Subject: categories: Four lectureships in Nottingham
Date: Fri, 24 Nov 2000 10:10:22 GMT
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 31
Dear all,
We are currently advertising four new lectureships in Nottingham.
There are no particular research areas specified for these positions,
but applications in the area of the Languages and Programming research
group (http://www.cs.nott.ac.uk/Research/lap/) would be most welcome.
Graham Hutton
----------------------------------------------------------------------
THE UNIVERSITY OF NOTTINGHAM
School of Computer Science and Information Technology
Four Lectureships
Applications are invited for the above posts in a rapidly-expanding
School based at one of the UK's strongest research-led universities.
The School was graded 4 in the 1996 Research Assessment Exercise and
is now building up its research strengths for a further improvement in
grade. These posts are part of a steady increase in the size of the
School accompanied by a move to new purpose-built accommodation in
September 1999. Although the successful candidates will have the
opportunity of teaching within their specialist area at undergraduate
and postgraduate level, there will also be a requirement to teach
general computer science and information technology modules outside of
any particular specialisation.
Candidates should already have a PhD in computer science, or another
closely related discipline, together with strong evidence of existing
research work and the potential for future research at Grade 5 level.
Outstanding candidates will be welcomed from any area of computer
science.
Salary will be within the range #18,731 - #30,967 per annum, depending
on qualifications and experience.
Informal enquiries may be addressed to Professor P H Ford, Head of
School, tel: +44 (0)115 951 4251 or Email:
Peter.Ford@Nottingham.ac.uk. Further information about the School is
available on the WWW at: http://www.cs.nott.ac.uk.
Further details and application forms are available from the Personnel
Office, Highfield House, The University of Nottingham, University
Park, Nottingham, NG7 2RD. Tel: +44 (0)115 951 5927. Fax: +44 (0)115
951 5205. Email: Carole.Matthews@Nottingham.ac.uk. Please quote
ref. LEG/537.
Closing date: 5 January 2001.
----------------------------------------------------------------------
From rrosebru@mta.ca Fri Nov 24 12:07:59 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eAOFWT409944
for categories-list; Fri, 24 Nov 2000 11:32:29 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: Fri, 24 Nov 2000 21:45:11 +0800 (GMT-8)
From: Gabriel Ciobanu
To: MCU 2001 Conference
cc: Yurii Rogozhin ,
Maurice Margenstern
Subject: categories: MCU'2001 - FINAL Call for Papers
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 32
(We apologize if you receive multiple copies of this Call for Papers)
Deadline for submission : December 15, 2000 !
----------------------------------------------
CALL FOR PAPERS CALL FOR PAPERS CALL FOR PAPERS CALL FOR PAPERS
International Conference
MACHINES ET CALCULS UNIVERSELS
MACHINES, COMPUTATIONS AND UNIVERSALITY
CHISINAU, MOLDOVA
Institute of Mathematics and Computer Science of the
Academy of Sciences of Moldova
23-30 MAY, 2001
TOPICS :
Digital Computations:
Turing machines, register machines, cellular automata,
other automata, tiling of the plane, polyominoes, snakes,
neural networks, molecular computations, word processing
(groups and monoids), other machines
Analog and Hybrid Computations:
BSS machines, infinite cellular automata, real machines,
quantum computing
In both cases:
frontiers between a decidable halting problem and an
undecidable one in the various computational settings
minimal universal codes:
size of such a code, namely, for Turing machines, register
machines, cellular automata, tilings, neural nets,
Post systems, ...
computation complexity of machines with a decidable halting
problem as well as universal machines
self-reproduction and other tasks
universality and decidability in the real field
PROGRAM COMMITTEE :
Erzsebet CSUHAJ-VARJU, Hungarian Academy of Sciences
Gabriel CIOBANU, A.I.Cuza University, Iasi, Romania
Serge GRIGORIEFF, University of Paris 7, France
Manfred KUDLEK, University of Hamburg, Germany
Maurice MARGENSTERN, GIFM, LITA, University of Metz, France, co-chair
Yuri MATIASEVICH, Euler Institute, Steklov Institute,
Saint-Petersburg, Russia
Liudmila PAVLOTSKAYA, Moscow, Russia
Yurii ROGOZHIN, Institute of Mathematics, Chisinau, Moldova, co-chair
Arto SALOMAA, Turku, Finland
Mephodii RATSA, Institute of Mathematics, Chisinau, Moldova
ORGANIZING COMMITTEE :
Maurice MARGENSTERN, GIFM, LITA, University of Metz, co-chair
Yurii ROGOZHIN, Institute of Mathematics and Computer Science,
Chisinau, co-chair
INVITED SPEAKERS :
Sergei ADIAN, Steklov Institute, Moscow, Russia (TBA)
Claudio BAIOCCHI, University of Roma, Italy
"Some small universal Turing machines"
Martin DAVIS, University of Berkeley, U.S.A.
"Between Logic and Computer Science"
Jozef GRUSKA, Mazaryk University, Brno, Czech Republica
"Potentials, puzzles and challenges of quantum entenglement"
Juhani KARHUMA"KI, Turku, Finland
"Combinatorial and computational problems on finite sets of words"
Giancarlo MAURI, University of Milano II, Milano, Italy
"Normal forms in P-systems", with C. FERRETTI and C. ZANDRON
Kenichi MORITA, University of Hiroshima, Japan
"A simple universal logic element and cellular automata for
reversible computations"
Maurice NIVAT, University of Paris VII, Paris, France (TBA)
Gheorghe PAUN, Insitute of Mathematics, Bucharest, Romania
"Universality Result in the Membrane Computing Area"
Ge'raud SE'NIZERGUES, University of Bordeaux I, Bordeaux, France
"Some applications of the equivalence algorithm for
deterministic push down automata"
Hava SIEGELMANN, Technion, Haifa, Israel
"Computability of Genetic Networks"
Klaus SUTNER, Pittsburgh, USA (TBA)
Boris TRAKHTENBROT, Tel Aviv, Israel (TBA)
Vladimir ZAKHAROV, Moscow, Russia
"The equivalence problem for computational models: decidable and
undecidable cases"
MCU'95 and MCU'98 gave rise to TCS special issues on "Universal
Machines and Computations" : 168-2 (1996) and 231-2 (2000). The interest
of computer scientists for the topics of the conference increased during
the last years. New domains have appeared, continuing the traditional
approaches in a natural way. This explains why a regular scientific
meeting on this topics must hold, at least each three years.
Initially the name of the conference was "MACHINES ET CALCULS UNIVERSELS"
(in French); the English translation was "Universal Machines and
Computations" and this was the title of the corresponding TCS issues. In
order to keep the same abbreviation, the new English name of the conference
is "MACHINES, COMPUTATIONS AND UNIVERSALITY".
CONFERENCE PROCEEDINGS
Besides invited lectures, about thirty contributions are planned. As a first
step, lectures and contributions will be published in a volume of Lecture Notes
in Computer Science devoted to the proceedings of the conference. Participants
will receive that volume at their arrival.
Contributions should be submitted as 12 page papers with an extra page
indicating the name of the author(s), his/her/their affiliation, e-mail and
addresses as well as the title of the contribution, a list of key-words and
a short abstract within 300 words. Submissions must conform to the usual
LNCS format, see http://www.springer.de/comp/lncs/authors.html.
Contributions will be submitted by e-mail as a NON ENCODED PostScript file
(any encoding will entail rejection of the submission). Accepted contributions
will possibly have to be corrected according to the remarks of the referee. In
any case, accepted contributions should be send in LATEX format, conform to
instructions to be found at the above URL.
Please, keep in mind the following dates :
Deadline for submission (extended) : December 15, 2000 *NEW*
Notification of acceptance or rejection : February 1, 2001
Deadline for corrected version of accepted papers :
February 15, 2001
TCS SPECIAL ISSUE
A special issue of Theoretical Computer Science devoted to "MCU'2001,
Machines, Computations and Universality", will be published on the topics of
the conference. A selection of the best works of the conference, among invited
lectures and accepted contributions will be published in this special issue.
It will be possible for a paper accepted for the Proceedings to be extended for
the special issue, provided that the selection process for the special issue
accepts again the paper.
GRANTS FOR STUDENTS :
If our grant applications are successful enough, a certain number of grants
will be presented to young postdoc researches or PhD students in order to
attend the sessions of the conference.
REGISTRATION FEES :
In order to attending the conference, send your registration form by surface
mail at the below indicated address, by FAX or by e-mail. Registration fees
amount to 300 US$ if paid before March 1st 2001 and to 350 US$ after that date.
In that latter case, they must be paid to the conference organization
account before May, 1st, 2001. ALL participants have to pay the registration
fees and please, take notice that the fees must be paid in EURO.
Please, note that registration fees will be received by the University of Metz
at an account that will later be indicated.
LANGUAGE OF THE CONFERENCE : English.
ACCOMMODATION
The accommodation will be provided by the local organisation committee.
Around one month before the conference, you will receive all indications on
the accommodation by the organizing committee.
COMMUNICATION :
-- by e-mail : mcu2001@antares.iut.univ-metz.fr
and, in case of problems : mcu2001@iut.univ-metz.fr
mcu2001@lita.univ-metz.fr
-- html site :
http://mcu2001.iut.univ-metz.fr/~mcu2001
http://www.math.md/mcu2001
-- fax : (33 3) 87 31 54 96
-- by surface mail :
Yurii ROGOZHIN
International Conference "Machines, Computations and Universality"
Institute of Mathematics and Computer Science,
Academy of Sciences of Moldova,
Academiei, 5
MD-2028 CHISINAU, MOLDOVA
Maurice MARGENSTERN
International Conference "Machines et calculs universels"
I.U.T. de Metz,
De'partement d'Informatique,
I^le du Saulcy,
F - 57045 METZ CEDEX
FRANCE
-----------------------------------------------------------------------
Organizing institutions :
Institute of Mathematics and Computer Science
of the Academy of Sciences of Moldova
LITA, University of Metz, France
First sponsors
Laboratoire d'Informatique The'orique et Applique'e,
(LITA), the University of Metz, Metz, France
---------------------- PLEASE, DISTRIBUTE WIDELY! ---------------------
Please forward this CFP to those colleagues of yours who may be interested.
From rrosebru@mta.ca Thu Nov 16 10:41:44 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eAGDhWI02268
for categories-list; Thu, 16 Nov 2000 09:43:32 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: Thu, 16 Nov 2000 09:48:03 +0100 (CET)
From: Tobias Schroeder
X-Sender: tschroed@pc12394
To: Category Mailing List
Subject: categories: subcategories of functor categories
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=ISO-8859-1
Content-Transfer-Encoding: 8bit
X-MIME-Autoconverted: from QUOTED-PRINTABLE to 8bit by mailserv.mta.ca id eAG8mBt30631
Sender: cat-dist@mta.ca
Precedence: bulk
Status: RO
X-Status:
X-Keywords:
X-UID: 34
Hi,
given a Set-endofunctor F:Set-->Set and a "type" L of limit
I'm searching for a "related" functor F_L:Set--->Set that
preserves that type of limit.
Example: As Vera Trnkova has proved around 1970 each
Set-endofunctor can turned into a functor that preserves
pullbacks of injective mappings just by modifying it
on the empty set and the empty mappings. - Now given
a functor that does not preserve pullbacks I'd like
to find a "related" one that does.
I'm not quite sure what "related" means. My
first idea was to consider the functor category
Fun(Set,Set) (not being abhorred by possible
size problems) and the subcategory Fun_L(Set,Set)
of Set-endofunctors that preserve limits
of type L. Then if Fun_L(Set,Set) were reflective
or coreflective in Fun(Set,Set) ...
but I think it is not.
So does anybody have an idea which type of
"relatedness" could be considered? Is
there some concept concerning these problem
in category theory?
Thank you very much
Tobias Schroeder
--------------------------------------------------------------
Tobias Schröder
FB Mathematik und Informatik
Philipps-Universität Marburg
WWW: http://www.mathematik.uni-marburg.de/~tschroed
email: tschroed@mathematik.uni-marburg.de
From rrosebru@mta.ca Mon Nov 27 12:17:50 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eARFdOm17079
for categories-list; Mon, 27 Nov 2000 11:39:24 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Message-ID: <002601c05875$786b74e0$ac4bd5c8@pitagoras>
From: "Simone Costa"
To: "Categories@Mta. Ca"
Subject: categories: Partial Constructions in Categories
Date: Mon, 27 Nov 2000 11:25:10 -0200
MIME-Version: 1.0
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
X-Priority: 3
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook Express 5.00.2314.1300
X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2314.1300
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 35
Dear friends,
I'm a M.S. student on Computer Science and I'm working with partial
constructions in categories.
I'm very interested in works describing the inheritance of limits, colimits,
products, etc, when dealing with partial categories. I've tried to find
papers on the subject but I had no success.
I would be very thankful for the help I could receive.
Thanks in advance.
S.Costa
From rrosebru@mta.ca Mon Nov 27 12:17:50 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eARFbZW16704
for categories-list; Mon, 27 Nov 2000 11:37:35 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: Sun, 26 Nov 2000 13:25:22 -0800
Message-Id: <200011262125.NAA22532@kamiak.eecs.wsu.edu>
From: "David B. Benson"
To: categories@mta.ca
Subject: categories: RFN (Request for Notation)
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 36
Dear Colleagues,
I am preparing notes for a sophomore (second year)
course, and I am finding several places wherein
I can find no standard notation. Your suggestions
will be most appreciated.
(1) Everybody knows that {(n,n+1) | n \in Z}
is the <> relation. What to call
the corresponding idea when the underlying
order is only a partial order?
I am currently using <> as in
phrases such as
``...the followers relation for the subsets
of the finite set {a, b, c}...''
in which ({a},{a,b}) is in the followers
relation, but {{a},{a,b,c}) is not, anymore
that (n,n+2) is in the successor relation.
Is there a better word than <>?
(2) I need a snappy name for an order pair in
a relation R. The books I have seem to just
say ``...the ordered pair (x,y) in relation R...''
The problem is that there are many uses of
ordered pairs, and this is a specific use,
a description of the fact that
x is R-related to y
by the fact that (x,y) \in R.
The word ``association'' will not do as this
has other meaning in computer science. I am
considered <> for an order pair in
a relation, but have the impression that this
word has been used for other purposes in the
literature.
(3) I badly need a good name for the sets
Nat_k = {n \in Nat | n < k }
These are widely used and I am surprised that
there is no satisfactory name in wide-spread use.
These are NOT the sets Z_k = Z mod k,
although the Nat_k form a system of distinct,
canonical representatives for the Z_k.
These are the set of array indices in computer
languages such as C and SML. In this use, the
Nat_k have nothing whatsoever to do with Z_k
and I certainly do not want to confuse the students!
Thank you in advance for any and all suggestions,
David
--
Professor David B. Benson (509) 335-2706
School of EE and Computer Science (EME 102A) (509) 335-3818 fax
PO Box 642752, Washington State University dbenson@eecs.wsu.edu
Pullman WA 99164-2752 U.S.A.
From rrosebru@mta.ca Mon Nov 27 12:17:53 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eARFUGs00428
for categories-list; Mon, 27 Nov 2000 11:30:16 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
From: Thomas Streicher
Message-Id: <200011241650.AA209814619@fb0448.mathematik.tu-darmstadt.de>
To: categories@mta.ca
Date: Fri, 24 Nov 2000 17:50:19 +0100 (MEZ)
Subject: categories: CFP APPSEM Workshop
X-Mailer: ELM [version 2.4ME+ PL47 (25)]
Mime-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Sender: cat-dist@mta.ca
Precedence: bulk
Status: RO
X-Status:
X-Keywords:
X-UID: 37
Call for Participation
FINAL APPSEM WORKSHOP
19.-22. March, 2001
Darmstadt, Germany
>From 19th to 22nd March the final workshop of the ESPRIT Working Group
Applied Semantics (APPSEM) will be organized by the Darmstadt site of APPSEM
at a place near Darmstadt. (Darmstadt itself is very close to Frankfurt
airport).
The intention of the workshop is to present the achievements of our working
group and to discuss new perspectives in particular of the application of
semantic methods to problems arising from applications.
There will be at least six invited lectures also by people who are not
formally members of the APPSEM Working Group.
Participation of interested people not formally belonging to APPSEM is
definitely encouraged.
More details (in particular concerning registration) can be found at
www.mathematik.tu-darmstadt.de/appsem2001
the workshop homepage which will be continuously updated.
The deadline for registration is 15/2/01.
Participation is guaranteed for APPSEM members who register before 15/1/01.
The costs for participation (including conference dinner) are 550 DM
(~ 250 EURO).
Hoping to see you in March,
Thomas Streicher
From rrosebru@mta.ca Mon Nov 27 12:19:29 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eARFkdd25228
for categories-list; Mon, 27 Nov 2000 11:46:39 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
X-Received: from zent.mta.ca (zent.mta.ca [138.73.101.4])
by mailserv.mta.ca (8.11.1/8.11.1) with SMTP id eARF7bt03246
for ; Mon, 27 Nov 2000 11:07:39 -0400 (AST)
X-Received: FROM agnostix.bangor.ac.uk BY zent.mta.ca ; Mon Nov 27 11:08:16 2000 -0400
X-Received: from hysterix.bangor.ac.uk (hysterix [147.143.2.6])
by agnostix.bangor.ac.uk (8.9.3+Sun/8.9.3) with ESMTP id PAA16309
for ; Mon, 27 Nov 2000 15:07:21 GMT
X-Received: from bangor.ac.uk (maths36 [147.143.10.34])
by hysterix.bangor.ac.uk (8.8.8/8.8.8) with ESMTP id PAA06932
for ; Mon, 27 Nov 2000 15:07:17 GMT
Message-ID: <3A2278A6.9053B3FA@bangor.ac.uk>
Date: Mon, 27 Nov 2000 15:07:18 +0000
From: Ronnie Brown
X-Mailer: Mozilla 4.75 [en] (Win98; U)
X-Accept-Language: en
MIME-Version: 1.0
To: categories@mta.ca
Subject: categories: Visit to Bangor of Eric Goubault
Content-Type: text/plain; charset=us-ascii
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 38
Dr E Goubault (ENS, Paris; Commission Energie Atomique) will visit
the School of Informatics, University of Wales, Bangor, UK, on Dec 19, 20
2000 and give two talks, the second of which will be more mathematical:
Tuesday, Dec 19, 4:00pm, Room 149
Geometric semantics for the analysis of concurrent and distributed
software
ABSTRACT: This talk will be focused on applications of geometrical ideas
and
modeling to computer scientific problems, among which: -
relationship with other models for concurrency (for instance
transition systems and Petri nets). - static analysis of
concurrent programs (mostly Java-like threads); in particular,
deadlocks, reachable states, scheduling properties (joint work
with Martin Raussen and Lisbeth Fajstrup), state-space reduction
techniques. - scheduling properties of distributed systems; in
particular serialisability conditions for databases (after Jeremy
Gunawardena and Martin Raussen), computability in fault-tolerant
systems (after Maurice Herlihy and Sergio Rajsbaum).
Wednesday, Dec 20th 11:15 pm, Room S5
Recent developments of "geometric concurrency theory"
ABSTRACT: In this talk, I will present some of the "geometrical theories"
used for modeling concurrent systems. Among these are: - the
(di-)topological approaches where the flow of concurrent
executions is modeled by a topological space of states plus local
partial orders on it. This is very much related to the "progress
graphs" of E. W. Dijkstra. I will also outline some links with
similar objects introduced in domain theory. Some of the algebraic
topology which is useful for describing interesting (scheduling)
properties of concurrent systems will be described (many results
from Martin Raussen and Lisbeth Fajstrup, Aalborg University). I
will also refer to recent work by Stefan Sokolowski, Gdansk
University. - the semi-cubical set approach which is in some way a
combinatorial counterpart of the topological approach. This is
very much related to ordinary transition systems semantics. This
was described first by Vaughan Pratt and Rob van Glabbeek,
Stanford University. - the omega-categorical approach (cubical
and/or globular of course) initiated also by Vaughan Pratt. Most
of this work has been developped by Philippe Gaucher, IRMA,
Strasbourg University.
I will add some recent developments (joint work with Philippe
Gaucher), and also some other "applications" of these ideas (in
Logics, joint work with Jean Goubault-Larrecq).
All are welcome. It is hoped the above schedule will allow good
time for discussion.
Enquiries to
Ronnie Brown r.brown@bangor.ac.uk
From rrosebru@mta.ca Mon Nov 27 12:19:30 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eARFcaf15409
for categories-list; Mon, 27 Nov 2000 11:38:36 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: Mon, 27 Nov 2000 10:40:13 +0100 (MET)
From: Jiri Velebil
X-Sender: velebil@newton.feld.cvut.cz
Reply-To: Jiri Velebil
To: categories@mta.ca
Subject: categories: preprint: `Iteration Monads'
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 39
The paper (for abstract, see below)
Aczel P., Adamek J., Velebil J.: Iteration Monads, preprint
is now available from
http://math.feld.cvut.cz/velebil/
Jiri Velebil
----------------------------------------------------------------
Abstract:
It has already been noticed by C. Elgot and his
collaborators that the algebra of (finite and infinite)
trees is completely iterative, i.e., every system of
ideal recursive equations has a unique solution.
We prove that this is a special case of a very general
coalgebraic phenomenon: suppose that an endofunctor
H of an abstract category A is ``iterative'',
i.e., that it has the property that for every object
X in A a final coalgebra for H(_)+X
exists. Then these final coalgebras, TX, form a
monad on A, called the iteration monad of H.
And every ideal equation e : X --> T(X+Y) has
a unique solution e^+: X --> TY.
We also present a more general view substituting
the category [A,A] of all endofunctors
of A by a monoidal category B: an object H in B
is called iterative if the endofunctor
H tensor (_)+I of B has a final coalgebra. This coalgebra
is, then, a monoid in B, called the iteration monoid
of H. And the assignment of an iteration monoid
to all objects forms a monoid in [B,B].
From rrosebru@mta.ca Mon Nov 27 15:15:06 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eARIalF00264
for categories-list; Mon, 27 Nov 2000 14:36:47 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
X-Authentication-Warning: vivien.it.uu.se: justin set sender to justin@DoCS.UU.SE using -f
Message-ID: <14882.36436.792098.783391@vivien.it.uu.se>
Date: Mon, 27 Nov 2000 17:39:48 +0100
From: Justin Pearson
To: categories@mta.ca
Subject: categories: Re: RFN (Request for Notation)
In-Reply-To: <200011262125.NAA22532@kamiak.eecs.wsu.edu>
References: <200011262125.NAA22532@kamiak.eecs.wsu.edu>
X-Mailer: VM 6.76 under Emacs 20.7.1
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 40
David B. Benson wrote:
> Dear Colleagues,
>
> I am preparing notes for a sophomore (second year)
> course, and I am finding several places wherein
> I can find no standard notation. Your suggestions
> will be most appreciated.
>
>
> (2) I need a snappy name for an order pair in
> a relation R. The books I have seem to just
> say ``...the ordered pair (x,y) in relation R...''
Depends what you want to talk about. If you want to talk about R as
simple a set then I would normally refer to an
element of R a tuple of R where the context tells you that
the tuple is of length two.
Regards
Justin
From rrosebru@mta.ca Tue Nov 28 16:28:38 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eASJcPQ08564
for categories-list; Tue, 28 Nov 2000 15:38:25 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: Tue, 28 Nov 2000 14:20:14 -0500 (EST)
From: Peter Freyd
Message-Id: <200011281920.eASJKEb16784@saul.cis.upenn.edu>
To: categories@mta.ca
Subject: categories: ridiculously abstract
Sender: cat-dist@mta.ca
Precedence: bulk
Status: RO
X-Status:
X-Keywords:
X-UID: 41
If you take a look at
http://slate.msn.com/diary/00-11-27/diary.asp?iMsg=1
you will find (in a column by Jim Holt) that "Category theory is a
ridiculously abstract framework that takes all the meaning out of
mathematics." At the end of the column is an invitation to make
comments. (Please don't!) Only one such comment seems to be about
category theory and it's this beauty:
Subject: category theory
From: John Rooney
Date: 28 Nov 2000 09:49
Category theory was not so bad when the Poles invented it. It was sort
of like reinventing the parts of speech or the distinction between
accident and substance. Later it was like subject and predicate, noun
and verb. The Dutch logicians have made it quite obscure. Here's to
better understanding of category theory and a less defeatist attitude.
(This almost makes sense if you substitute "categorial grammar" for
"category theory". But if you do that you then have to turn Jim
Lambek into a Pole.)
Here's the full Holt column. I'm certain that any attempt to counter
the statement about category theory -- given the mood of the piece
-- can only fail.
DIARY: Infiltrating the Mathematicians' Lair.
Jim Holt is a member of the Mathematical Sciences Research Institute
at the University of California, Berkeley, and a columnist for Lingua
Franca. His book on the history of the infinitesimal, Worlds Within
Worlds, will be published next fall.
Posted: Monday, Nov. 27, 2000, at 4:00 p.m. PT
Being at MSRI is a bit like going to heaven without all the bother and
expense of dying. I don't mean the sort of heaven where you wear
ermine and eat foie gras to the sound of trumpets. I mean the sort
where you spend your days languidly communing with beautiful,
timeless, abstract ideas: Platonic heaven.
MSRI stands for the Mathematical Sciences Research Institute. It is
the premier think tank in the world for pure mathematics. Even its
location is heavenly: It is housed in a Corbusian glass-and-wood
structure perched atop the loftiest of the hills above the University
of California at Berkeley, just below the ionosphere. From my office
window, I gaze down upon the skyscrapers of San Francisco, the isle of
Alcatraz, the Golden Gate Bridge, the Pacific Ocean. In a few minutes
I will leave my office, traverse some pristine white hallways, and
join a hundred of the most eminent mathematicians from around the
world in a commodious lecture room. Today's topic for contemplation:
the linear p-adic group, the p-adic Galois group, and the p-affine
Schur algebra.
But wait. I am not a mathematician (although I have sometimes
pretended to be one on NPR). I am a "trivial being," to use Paul
Erdos' term for those who are not among the mathematical elect. So
what am I doing in this Platonic heaven? I am here as a journalist in
residence. My mandate is to convey a little of the flavor of what goes
on in these ethereal precincts to my fellow trivial beings back in the
material world. I also cannot help thinking of myself as an
anthropologist, living among an alien tribe and observing their often
strange folkways. I must be careful not to give them measles.
How can I blend into this august tribe? As a longtime mathematical
dilettante, I sometimes understand a little of what they are saying. I
also do a good bit of faking. Luckily I have come up with a set of
all-purpose trick questions that have kept my ignorance from being
exposed in many a treacherous conversation. For example:
"Can that result be restated in terms of category theory?" (Category
theory is a ridiculously abstract framework that takes all the meaning
out of mathematics.)
"Isn't the constant in that equation suspiciously close to the square
root of pi divided by e cubed?"
"Wasn't your theorem prefigured in the work of Euler?" (Leonhard
Euler, who lived in the 18th century, was the most prolific
mathematician in history; nearly everything is prefigured in his
work.)
"But can you prove that lemma for the case of n=3?"
By the shrewd use of such feints, I, a trivial being, have been able
to chat as an apparent peer with many of my colleagues at MSRI. Above
all, I am careful not to let conversations about things like p-adic
Galois groups go on for too long. When skating over thin ice, speed is
your ally.
From rrosebru@mta.ca Tue Nov 28 17:16:17 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eASJbEU05226
for categories-list; Tue, 28 Nov 2000 15:37:14 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: Tue, 28 Nov 2000 14:57:46 -0400
From: "Robert J. MacG. Dawson"
Subject: categories: Re: David Benson's questions on terminology
To: categories@mta.ca
Message-id: <3A24002A.2762B24B@stmarys.ca>
MIME-version: 1.0
X-Mailer: Mozilla 4.72 [en] (WinNT; I)
Content-type: text/plain; charset=us-ascii
Content-transfer-encoding: 7bit
X-Accept-Language: en
References: <200011281143.LAA22264@koi-pc.dcs.qmw.ac.uk>
Sender: cat-dist@mta.ca
Precedence: bulk
Status: RO
X-Status:
X-Keywords:
X-UID: 42
Paul Taylor wrote:
>
> (1) I would say (rather strongly) that it is ill-conceived to
> try to generalise the successor relation from the natural numbers
> to arbitrary partial orders. The successor relation is an aspect
> of the inductive/recursive/well founded structure on N, and it
> is wrong to confuse well founded relations (which are necessarily
> IRreflexive) with partial arders (which are Reflexive).
>
> See Sections 2.7, 3.1 and elsewhere in "Practical Foundations".
I don't think David was trying to generalize the successor
relation in the sense of finding a "moral equivalent" in a poset for
the natural numbers' successor _function_. All he wants - I think -
is a notation for "a > b and there is no a>c>b". I would suggest
using an indefinite article with a noun formation:
" a is _a_ successor of b"
or a prepositional formation that does not connote uniqueness or
necessary existence:
"a is immediately above b"
Bob Pare and I used "
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eATFmqX29837
for categories-list; Wed, 29 Nov 2000 11:48:52 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Message-Id: <200011290925.BAA17540@coraki.Stanford.EDU>
To: categories@mta.ca
Subject: categories: Re: David Benson's questions on terminology
Date: Wed, 29 Nov 2000 01:25:48 -0800
From: Vaughan Pratt
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 43
Universal algebraists (but not category theorists??) call b the _cover_ of
a when a**
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eATFmFb30082
for categories-list; Wed, 29 Nov 2000 11:48:15 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: Tue, 28 Nov 2000 12:51:18 -0800
Message-Id: <200011282051.MAA32220@kamiak.eecs.wsu.edu>
From: "David B. Benson"
To: categories@mta.ca
Subject: categories: More about names and notation
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 44
Dear Colleagues,
Thank you for the responses!
(1) Several pointed out that my <> relations are
said to be <> relations in combinatorics.
These relations are defined as relations which are
1. acyclic
2. without interpolants, as Robert Dawson mentioned.
A followers relation for discrete partial order R is
the least relation whose reflexive and transitive closure
is R.
This agrees entirely with the definition of a
successor relation being the least relation whose
transitive closure is a discrete strict total order and whose
reflexive and transitive closure is a discrete total order.
In the case of successor, there is a distinct
next element, as in the succession of the Kings (and Queens)
of England. In the case of followers, there is in
general a set of next elements, such as the followers
of Cromwell.
(2) While several alternatives were offered, I will try
Paul Taylor's <> of a relation to describe
an ordered pair (x,y) \in R.
(3) The problem of a good name for the sets Nat_k remains.
Suggestions included
finite ordinals
numerals
order ideals
and by far the most appropriate for my purposes,
index sets
[This problem of a good name is worthy of some further attention.
Computer science second year students will think
of <> as a number, not a set,
of <> as representations of the digits in a number system,
and have not be exposed to order ideals.]
Cheers,
David
--
Professor David B. Benson (509) 335-2706
School of EE and Computer Science (EME 102A) (509) 335-3818 fax
PO Box 642752, Washington State University dbenson@eecs.wsu.edu
Pullman WA 99164-2752 U.S.A.
From rrosebru@mta.ca Wed Nov 29 12:26:52 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eATFn6U32756
for categories-list; Wed, 29 Nov 2000 11:49:06 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: Wed, 29 Nov 2000 15:12:53 +0200 (EET)
From: Mamuka Jibladze
Reply-To: Mamuka Jibladze
To: categories@mta.ca
Subject: categories: Re: David Benson's questions on terminology
In-Reply-To: <3A24002A.2762B24B@stmarys.ca>
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 45
> I don't think David was trying to generalize the successor
> relation in the sense of finding a "moral equivalent" in a poset for
> the natural numbers' successor _function_. All he wants - I think -
> is a notation for "a > b and there is no a>c>b". I would suggest
> using an indefinite article with a noun formation:
>
> " a is _a_ successor of b"
>
> or a prepositional formation that does not connote uniqueness or
> necessary existence:
>
> "a is immediately above b"
>
> Bob Pare and I used "
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eATFni225428
for categories-list; Wed, 29 Nov 2000 11:49:44 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Mime-Version: 1.0
X-Sender: duskin@mail.buffnet.net
Message-Id:
Date: Wed, 29 Nov 2000 08:39:26 -0500
To: categories@mta.ca
From: John Duskin
Subject: categories: Re: Categories ridiculously abstract
Content-Type: text/plain; charset="us-ascii" ; format="flowed"
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 46
Readers of the cat list may be interested in the one meaningful post
to Slate's "The Fray" in reply to Holt's MSRI "Diary" article. It was
made by David Yetter:
category theory
David Yetter
28 Nov 2000 20:29
It is sad more than a decade on since the
proof of the remarkable categorical coherence
theorem of Shum that mathematicians can
continue to view category theory as a mere
linguistic convention or useless abstraction.
Shum's theorem shows that axioms
completely natural from the internal dynamic of
category theory completely characterize
framed tangles, relative versions of the framed
knots and links which are central to
smooth topology in 3 and 4 dimensions (notice
the dimensionality of space and of
space-time: hardly divorced from meaning.) Other
categories satisfying the same axioms
include the categories of representations of
quantum groups, physically motivated
algebraic structures which have become central
objects of study for mathematicians from
many old branches of mathematics.
Indeed, Shum's theorem, a theorem of
category theory, is the only really satisfying
explanation for the intimate connection
between quantum groups and low-dimensional
topology.
From rrosebru@mta.ca Wed Nov 29 12:29:34 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eATFlfK22213
for categories-list; Wed, 29 Nov 2000 11:47:41 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Message-ID: <000f01c05646$bd346180$f47179a5@osherphd>
From: "Osher Doctorow"
To:
Subject: categories: My recent publication - Doctorow
Date: Fri, 24 Nov 2000 10:44:43 -0800
MIME-Version: 1.0
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
X-Priority: 3
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook Express 5.50.4133.2400
X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4133.2400
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 47
From: Osher Doctorow, Ph.D. osher@ix.netcom.com, Fri. Nov. 24, 2000 10:41AM
My paper applying logic-based probability (LBP) to mathematical physics was
just published, and is entitled "Magnetic monopoles, massive neutrinos and
gravitation via logic-experimental unification theory (LEUT) and
Kursunoglu's theory," pages 89-97 of the volume Quantum Gravity, Generalized
Theory of Gravitation, and Superstring Theory-Based Unification, Editors B.
N. Kursunoglu (Ph.D. from Cambridge University under Professor Paul Dirac),
S. L. Mintz, and A. Perlmutter, Kluwer Academic/Plenum: New York 2000. The
relevance of LBP to categories is largely in its ability to generalize
across categories, which it shares with Clifford algebra/octonions/Grassmann
algebra (Bayliss, Crawford, Chisholm, Pezzaglia, Hestenes, Benn, Okubo,
etc.) and in string theory with the orientation of S. Weinberg. Much of the
generalizing work has been done since the above paper, and hopefully I will
be able to succinctly present some of it here in future. I will say in
preview that LBP isolates the transition from division to subtraction (often
ignored by other fields) and keeps track of logic-algebra relationships and
I regard these as a major source of its ability to transcend categories and
apply across disciplines. Most of the people cited above also have unusual
tolerance for new ideas, even those which disagree with their own theories
and those of the majority of theorists. I like to think of at as partly a
great sensitivity to the past, present, and future - not just to one of
them.
Osher Doctorow
From rrosebru@mta.ca Thu Nov 30 09:41:06 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eAUD1qE11110
for categories-list; Thu, 30 Nov 2000 09:01:52 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
X-Authentication-Warning: triples.math.mcgill.ca: barr owned process doing -bs
Date: Wed, 29 Nov 2000 11:48:59 -0500 (EST)
From: Michael Barr
X-Sender: barr@triples.math.mcgill.ca
To: categories@mta.ca
Subject: categories: Re: Categories ridiculously abstract
In-Reply-To:
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 48
I don't think one should blame the guy whose remarks Peter quoted. He is
not a mathematician and presumably knows nothing more than some college
level mathematics. He has picked up that attitude from the high-powered
mathematicians that inhabit places like MSRI (and the CRM, Fields Inst.,
and PIMS in Canada). Ignoring the fact that category theory was fathered
by two of the most eminent mathematicians of the last century and
god-fathered by arguably the very greatest, they still go around saying
that it is without content and nothing but meaningless abstraction. I was
unaware of what David Yetter mentioned, but I am certainly aware of the
crucial role categories had in proving the Weil conjectures and the fact
that people like John Baez seem to believe that higher dimensional
categories will be important in physics. I might also point out that
categories were the right framework for Kaplansky's very elegant proof of
the Auslander-Buchsbaum theorem. And here is a question: are categories
more abstract or less abstract than sets?
Michael
From rrosebru@mta.ca Thu Nov 30 09:42:06 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eAUCvD108719
for categories-list; Thu, 30 Nov 2000 08:57:13 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: Wed, 29 Nov 2000 17:10:21 -0500 (EST)
From: Jason C Reed
Reply-To: godel@cmu.edu
To: categories@mta.ca
Subject: categories: Monads without unit?
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: cat-dist@mta.ca
Precedence: bulk
Status: RO
X-Status:
X-Keywords:
X-UID: 49
I had been looking at the standard way the topological closure A |-> CA
can be recovered from the derived set operation A |-> A' (which takes A to
the set of the accumulation points of A) by setting CA := A' u A, and
observed that it can be generalized to categorical language. If you take
thing made up of a coproduct-preserving functor D and a natural
transformation t : D^2 -> D, such that t is `associative' in the usual
sense of asserting that t o t_D = t o Dt, and also
p_{X,Y} o t_{X + Y} = (t_X + t_Y) o p_{DX,DY} o Dp_{X,Y}
where p is the canonical natural transformation D(X + Y) -> DX + DY , then
if one defines
TX := DX + X
eta_X := inr_{DX + X}
mu_X := ([1_{DX},1_{DX}] + X) a_{DX,DX,X} (([t_X,1_{DX}] o p_{DX,X}) + TX)
(where [ , ] is copairing and a_{X,Y,Z} is the associativity isomorphism X
+ (Y + Z) -> (X + Y) + Z) then turns out that (T, eta, mu) is a monad.
Has anyone already studied these? I'd be particularly interested in a
type-theoretic or logical (along the lines of the correspondence between
monads and modal operators) interpretation of such a structure, if any.
---Jason
From rrosebru@mta.ca Thu Nov 30 09:42:10 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eAUD0Yv09164
for categories-list; Thu, 30 Nov 2000 09:00:34 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: Wed, 29 Nov 2000 18:02:27 -0500 (EST)
Message-Id: <200011292302.eATN2R506948@csb.bu.edu>
From: Paul Levy
To: categories@mta.ca
In-reply-to: <200011271710.RAA07285@bruno.dcs.qmw.ac.uk> (message from Paul
Levy on Mon, 27 Nov 2000 17:10:00 GMT)
Subject: categories: Re: RFN (Request for Notation)
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 50
>
> (3) I badly need a good name for the sets
> Nat_k = {n \in Nat | n < k }
> These are widely used and I am surprised that
> there is no satisfactory name in wide-spread use.
> These are NOT the sets Z_k = Z mod k,
> although the Nat_k form a system of distinct,
> canonical representatives for the Z_k.
> These are the set of array indices in computer
> languages such as C and SML. In this use, the
> Nat_k have nothing whatsoever to do with Z_k
> and I certainly do not want to confuse the students!
>
I agree that there is a need for a standard name, and that Nat_k would
be a confusing name. I have been calling
this set $k for some time but I am happy to change my macro if there
is some other accepted name or if $ has some other mathematical meaning.
More generally, if k is an ordinal, one writes $k for the set of
ordinals less than k, the canonical well-ordered set of order-type k.
(The traditional ZF definition of ordinal makes k equal to $k, but
that is just an implementation.)
A similarly useful terminology for arrays and the like is
"obaz", which indicates the use of the "ordinals begin at zero"
convention. Thus you can refer to the cell with index 7 in your array
as the obaz 7th cell instead of as the 8th cell.
You can't call it the 7th cell, without qualification, because in
English the obao ("ordinals begin at one") convention is the
established default, unfortunately.
As an example, today is the obaz 28th day of the obaz 10th month of the
year obaz 1999, which is the final year of the obaz 19th century and not
the obaz zeroth year of the obaz 20th century as many obaoists mistakenly
believe. Though I'm hardly the zeroth person to point this out (obaz).
Warning: this usage may alienate the less tolerant of your friends.
Regards
Paul
--
Paul Blain Levy
Computer Science Department, Boston University
http://www.dcs.qmw.ac.uk/~pbl/
If language were arbitrary, it wouldn't be interesting.
From rrosebru@mta.ca Thu Nov 30 09:43:42 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eAUCpff28633
for categories-list; Thu, 30 Nov 2000 08:51:41 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Message-Id: <200011300954.KAA08299@irmast2.u-strasbg.fr>
Date: Thu, 30 Nov 2000 10:54:53 +0100 (MET)
From: Philippe Gaucher
Reply-To: Philippe Gaucher
Subject: categories: category of fraction and set-theoretic problem
To: categories@mta.ca
MIME-Version: 1.0
Content-Type: TEXT/plain; charset=us-ascii
Content-MD5: zCglKwm3JN2Ju86xZMFrog==
X-Mailer: dtmail 1.3.0 CDE Version 1.3 SunOS 5.7 sun4u sparc
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 51
Bonjour,
I have a general question about localizations.
I know that for any category C, if S is a set of morphisms, then
C[S^-1] exists. And moreover if C is small, then C[S^{-1}] is small
as well (as in the Borceux's book Handbook of categorical algebra I)
If S is not small, and if we suppose that all sets are in some universe
U, then the previous construction gives a solution as a V-small category
for some universe V with U \in V (the objects are the same but the homsets
need not to be U-small). So it does not work if one wants to get U-small
homsets.
Another way is to have a calculus of fractions (left or right) and if
S is locally small as defined in Weibel's book "Introduction to homological
algebra".
But in my case, the Ore condition is not satisfied. Hence the question :
is there other constructions for C[S^{-1}] ?
Thanks in advance. pg.
From rrosebru@mta.ca Thu Nov 30 14:04:19 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eAUHTjK09986
for categories-list; Thu, 30 Nov 2000 13:29:45 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Message-ID: <3A266593.657FD639@bangor.ac.uk>
Date: Thu, 30 Nov 2000 14:34:59 +0000
From: "Prof. T.Porter"
X-Mailer: Mozilla 4.7 [en] (X11; I; FreeBSD 3.3-RELEASE i386)
X-Accept-Language: en, fr
MIME-Version: 1.0
To: Philippe Gaucher ,
"categories@mta.ca"
Subject: categories: Re: category of fraction and set-theoretic problem
References: <200011300954.KAA08299@irmast2.u-strasbg.fr>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 52
Philippe Gaucher wrote:
>
> Bonjour,
>
> I have a general question about localizations.
>
> I know that for any category C, if S is a set of morphisms, then
> C[S^-1] exists. And moreover if C is small, then C[S^{-1}] is small
> as well (as in the Borceux's book Handbook of categorical algebra I)
>
> If S is not small, and if we suppose that all sets are in some universe
> U, then the previous construction gives a solution as a V-small category
> for some universe V with U \in V (the objects are the same but the homsets
> need not to be U-small). So it does not work if one wants to get U-small
> homsets.
>
> Another way is to have a calculus of fractions (left or right) and if
> S is locally small as defined in Weibel's book "Introduction to homological
> algebra".
>
> But in my case, the Ore condition is not satisfied. Hence the question :
> is there other constructions for C[S^{-1}] ?
>
> Thanks in advance. pg.
Dear All,
Philippe's question may be answered in part by looking
at the construction by Baues and Dugundji (Trans Amer Math Soc 140
(1969) 239 - 256). Another point is that in the homotopical applications
it is not that the Ore condition is satisfied but that it is satisfied
up to homotopy that counts. A discussion of this in at least one case is
to be found on pages 90 - 111 of the book by Heiner Kamps and myself.
(see my homepage for the detailed coordinates if you want. The set
theoretic question was looked at by various people including Markus
Pfenniger in an unpublished manuscript in 1989.
Tim
************************************************************
Timothy Porter
Mathematics Division,
School of Informatics,
University of Wales Bangor
Gwynedd LL57 1UT
United Kingdom
tel direct: +44 1248 382492
home page: http://www.bangor.ac.uk/~mas013
Mathematics and Knots exhibition: http://www.bangor.ac.uk/ma/CPM/
From rrosebru@mta.ca Thu Nov 30 14:04:40 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eAUHVAv16898
for categories-list; Thu, 30 Nov 2000 13:31:10 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: Thu, 30 Nov 2000 10:20:40 -0500 (EST)
From: F W Lawvere
Reply-To: wlawvere@ACSU.Buffalo.EDU
To: categories@mta.ca
Subject: categories: Re: Monads without unit?
In-Reply-To:
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 53
Jason Reed's construction, adjoining a unit to obtain a monad,
seems to generalize one of the steps in the proof by Pare', Rosebrugh,
and Wood that any lex idempotent can be split in two steps, one of
the steps involving a left adjoint splitting and the other a right
adjoint splitting. I believe this result was published about ten years
ago in Australia.
************************************************************
F. William Lawvere
Mathematics Department, State University of New York
244 Mathematics Building, Buffalo, N.Y. 14260-2900 USA
Tel. 716-645-6284
HOMEPAGE: http://www.acsu.buffalo.edu/~wlawvere
************************************************************
From rrosebru@mta.ca Thu Nov 30 14:07:06 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eAUHVsb30089
for categories-list; Thu, 30 Nov 2000 13:31:54 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
X-Authentication-Warning: triples.math.mcgill.ca: barr owned process doing -bs
Date: Thu, 30 Nov 2000 09:20:52 -0500 (EST)
From: Michael Barr
X-Sender: barr@triples.math.mcgill.ca
To: categories@mta.ca
Subject: categories: Re: category of fraction and set-theoretic problem
In-Reply-To: <200011300954.KAA08299@irmast2.u-strasbg.fr>
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 54
It is not clear if you are interested in special cases or in general
conditions. If the latter, I cannot help, but here is an example of a
special case. But first, I might ask why it matters. Gabriel-Zisman
ignores the question and I think they are right to. Every category is
small in another universe.
Consider the category C of chain complexes from some abelian category. By
this I mean bounded below with a boundary operator of degree -1. Arrows
are chain maps of degree 0. Let S denote the class of homotopy
equivalences and T the class of homology isomorphisms. Then S < T and
there is neither a calculus of right or left fractions for either. On the
other hand S^{-1}C is equivalent to C/~ in which you have identified
homotopic arrows. This is locally small because you leave the objects
alone and it is a quotient. From S < T, it follows that T^{-1}C =
T^{-1}S^{-1}C = T^{-1}(C/~) and the image of T in C/~ does have a calculus
of fractions (both left and right; duality implies that they are
equivalent). Thus there is a notion of homotopy calculus of fractions in
this case. I have tried, without success, to find a general condition
of which this would be a special case.
Michael
On Thu, 30 Nov 2000, Philippe Gaucher wrote:
> Bonjour,
>
>
> I have a general question about localizations.
>
> I know that for any category C, if S is a set of morphisms, then
> C[S^-1] exists. And moreover if C is small, then C[S^{-1}] is small
> as well (as in the Borceux's book Handbook of categorical algebra I)
>
> If S is not small, and if we suppose that all sets are in some universe
> U, then the previous construction gives a solution as a V-small category
> for some universe V with U \in V (the objects are the same but the homsets
> need not to be U-small). So it does not work if one wants to get U-small
> homsets.
>
> Another way is to have a calculus of fractions (left or right) and if
> S is locally small as defined in Weibel's book "Introduction to homological
> algebra".
>
> But in my case, the Ore condition is not satisfied. Hence the question :
> is there other constructions for C[S^{-1}] ?
>
>
> Thanks in advance. pg.
>
>
From rrosebru@mta.ca Fri Dec 1 15:15:17 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eB1IXvj09440
for categories-list; Fri, 1 Dec 2000 14:33:57 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
From: Todd Wilson
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Message-ID: <14886.48682.377864.620074@goedel.engr.csufresno.edu>
Date: Thu, 30 Nov 2000 12:52:58 -0800 (PST)
To: categories@mta.ca
Subject: categories: Re: Categories ridiculously abstract
In-Reply-To:
References:
X-Mailer: VM 6.75 under 21.1 (patch 8) "Bryce Canyon" XEmacs Lucid
Content-Transfer-Encoding: 8bit
X-MIME-Autoconverted: from quoted-printable to 8bit by mailserv.mta.ca id eAUKrFt03291
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 55
On Wed, 29 Nov 2000, Michael Barr wrote:
> And here is a question: are categories more abstract or less
> abstract than sets?
There is a trap lurking in this question, and it has to do with
understanding the term "abstract": different notions of "abstract"
can lead to different answers to the question. In the case of sets
and categories, since these are of different similarity types,
something other than inclusion of classes of models is meant. For
example "abstract", applied to sets and categories, might mean:
1. Having wider applicability. In this case, we can observe that the
theorems of category theory (e.g., products are unique up to unique
isomorphism) are generally more widely applicable than theorems of
set theory (e.g., the powerset of a set has greater cardinality
than the set itself), and so we would be inclined to say that
categories are more abstract than sets on this criterion.
2. Having more general conditions for being an instance. In order to
specify a set, we need only give (list, characterize) its members.
To specify a category we need to do the same thing for both the
collection of objects and the collection of arrows, and then we
need to specify the composition law. (Even in an arrows-only
formulation of category theory, we still need to specify both the
collection of arrows and the composition law.) So, on this
criterion, sets come out as more abstract.
Some time ago, on the Foundations of Mathematics mailing list (FOM),
there was a long and sometimes heated debate on alternative
foundations of mathematics (where alternative meant non-set-theoretic)
-- in particular on the viability of some kind of category-theoretic
foundation for mathematics (e.g., elementary topos theory + some
additional axioms) -- and the majority view seemed to be that
- Set theory is more all-encompassing. The standard arguments about
the bi-interpretability of category theory and set theory were met
with the challenge (unanswered, as far as I know) to produce, in a
category-theoretic foundation, a natural linearly-ordered sequence
of axioms of higher infinity that can be used to "calibrate" the
existential commitments of extensions to the basic axioms comparable
to the large cardinal axioms of set theory, where the naturality
requirement supposedly precludes the slavish translation of these
large cardinal axioms into the language of category theory. (Recall
that all known large cardinal axioms for set theory fall into a very
nice linear hierarchy that can be used to gauge the consistency
strength of a theory.)
- Set theory is conceptually simpler. Set theory axiomatizes a
single, very basic concept (membership), expressed using a single
binary relation, and posits a natural set of axioms for this
relation that are (more or less) neatly justified in terms of a
fairly (some would say perfectly) clear semantic conception, the
cumulative hierarchy. Category theory, the view goes, could only
approach the scope of set theory, if at all, by adding many axioms
that are unnatural and quite complicated to state and work with
without the aid of multiple layers of definitions and definitional
theorems (for products, exponentials, power-objects/subobject
classifier, higher replacement-like closure conditions on the
category, etc.).
The arguments put forward in support of these views were very similar
to those that are implicit in the labeling of category theory as
"ridiculously abstract", and there are no doubt many readers of this
list who would disagree with part or all of these views (me, for one).
However, my intention in reporting them here is *not* to start another
set-theory vs category theory thread, but rather to point out that,
although category theorists have yet to make a convincing case -- at
least I haven't seen one -- that category theory is more fundamental
or foundational in any important sense (sorry, Paul), recent research
in cognitive science on the embodied and metaphorical nature of our
thinking indicates that category theory may well be able to make such
a claim after all. See the books
G. Lakoff and M. Johnson. Philosophy in the Flesh: The Embodied
Mind and Its Challenge to Western Thought. Basic Books, 1999.
G. Lakoff and R. Nuñez. Where Mathematics Comes From: How the
Embodied Mind Brings Mathematics into Being. Basic Books, 2000.
for a popular account of this research. I should mention, of course,
that, closer to home, the book
F.W. Lawvere and S.H. Schanuel, Conceptual Mathematics: A First
Introduction to Category Theory. Cambridge University Press, 1997.
is certainly a step in this direction.
--
Todd Wilson A smile is not an individual
Computer Science Department product; it is a co-product.
California State University, Fresno -- Thich Nhat Hanh
From rrosebru@mta.ca Fri Dec 1 15:15:17 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eB1IZT315002
for categories-list; Fri, 1 Dec 2000 14:35:29 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
From: baez@newmath.UCR.EDU
Message-Id: <200011302341.eAUNf1X20986@math-cl-n06.ucr.edu>
Subject: categories: Categories - too abstract?
To: categories@mta.ca
Date: Thu, 30 Nov 2000 15:41:01 -0800 (PST)
X-Mailer: ELM [version 2.5 PL2]
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 56
Michael Barr write:
> I don't think one should blame the guy whose remarks Peter quoted. He is
> not a mathematician and presumably knows nothing more than some college
> level mathematics. He has picked up that attitude from the high-powered
> mathematicians that inhabit places like MSRI (and the CRM, Fields Inst.,
> and PIMS in Canada). Ignoring the fact that category theory was fathered
> by two of the most eminent mathematicians of the last century and
> god-fathered by arguably the very greatest, they still go around saying
> that it is without content and nothing but meaningless abstraction.
When I am confronted with this attitude, I sometimes use a couple of
arguments in addition to the usual one of listing things that category
theory is good for. I present them here in a rather blunt form; they
can be toned down as politeness dictates.
1) "You say category theory is `too abstract'. But if you don't like
abstraction, why in the world are you doing mathematics? Maybe you
should be in finance, where the numbers all have dollar signs in front
of them. Complaining that a piece of mathematics is `too abstract'
is a bit like saying that the ocean is `too wet'."
2) "You say category theory is `too abstract'. Good! Don't learn it!
That way, I'll make progress in my research faster than you."
> And here is a question: are categories more abstract or less abstract
> than sets?
Indeed, what we often take as "greater abstraction" is really
unfamiliarity. The real answer to the problem of people thinking
categories are "too abstract" is to keep explaining category theory
and how it's useful in a wide variety of problems... until people
get used to it. Physicists used to think groups were too abstract!
John Baez
From rrosebru@mta.ca Fri Dec 1 15:15:23 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eB1IUCn13727
for categories-list; Fri, 1 Dec 2000 14:30:12 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Subject: categories: Re: Categories ridiculously abstract
To: categories@mta.ca
Date: Thu, 30 Nov 2000 17:30:30 +0000 (GMT)
From: Tom Leinster
X-Mailer: ELM [version 2.5 PL3]
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Message-Id:
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 57
Michael Barr wrote:
>
> And here is a question: are categories more abstract or less abstract than
> sets?
A higher-dimensional category theorist's answer:
"Neither - a set is merely a 0-category, and a category a 1-category."
There's a more serious thought behind this. Sometimes I've wondered, in a
vague way, whether the much-discussed hierarchy
0-categories (sets) form a (1-)category,
(1-)categories form a 2-category,
...
has a role to play in foundations. After all, set-theorists seek to found
mathematics on the theory of 0-categories; category-theorists sometimes talk
about founding mathematics on the theory of 1-categories and providing a
(Lawverian) axiomatization of the 1-category of 0-categories; you might ask
"what next"? Axiomatize the 2-category of (1-)categories? Or the
(n+1)-category of n-categories? Could it even be, I ask with tongue in cheek
and head in clouds, that general n-categories provide a more natural
foundation than either 0-categories or 1-categories?
Tom
From rrosebru@mta.ca Fri Dec 1 15:15:38 2000 -0400
Return-Path:
Received: (from Majordom@localhost)
by mailserv.mta.ca (8.11.1/8.11.1) id eB1IUjv14510
for categories-list; Fri, 1 Dec 2000 14:30:45 -0400 (AST)
X-Authentication-Warning: mailserv.mta.ca: Majordom set sender to cat-dist@mta.ca using -f
Date: Thu, 30 Nov 2000 13:01:51 -0500 (EST)
From: Jiri Rosicky
X-Sender: rosicky@pascal.math.yorku.ca
To: categories@mta.ca
Subject: categories: Re: category of fraction and set-theoretic problem
In-Reply-To: <200011300954.KAA08299@irmast2.u-strasbg.fr>
Message-ID:
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Sender: cat-dist@mta.ca
Precedence: bulk
Status: O
X-Status:
X-Keywords:
X-UID: 58
If S is the class of weak equivalences in a Quillen model structure then
C[S^{-1}] is always locally small. See, e.g., M. Hovey, Model categories,
AMS 1999,
Jiri Rosicky
On Thu, 30 Nov 2000, Philippe Gaucher wrote:
> Bonjour,
>
>
> I have a general question about localizations.
>
> I know that for any category C, if S is a set of morphisms, then
> C[S^-1] exists. And moreover if C is small, then C[S^{-1}] is small
> as well (as in the Borceux's book Handbook of categorical algebra I)
>
> If S is not small, and if we suppose that all sets are in some universe
> U, then the previous construction gives a solution as a V-small category
> for some universe V with U \in V (the objects are the same but the homsets
> need not to be U-small). So it does not work if one wants to get U-small
> homsets.
>
> Another way is to have a calculus of fractions (left or right) and if
> S is locally small as defined in Weibel's book "Introduction to homological
> algebra".
>
> But in my case, the Ore condition is not satisfied. Hence the question :
> is there other constructions for C[S^{-1}] ?
>
>
> Thanks in advance. pg.
>
>
>
**