1 Dec 15:06 2000

### CFP: Workshop on Implicit Computational Complexity

Third international workshop on Implicit Computational Complexity-2001 (ICC'01)
-------------------------------------------------------------------------------

The Implicit Complexity Workshop (ICC'01) will be held on Sunday, 20
May 2001 in Aarhus as part of the joint PADO/MFPS 2000 conferences.

Topics of Interest:
-------------------

The synergy between Logic, Computational Complexity and Programming
Language Theory has gained importance and vigour in recent years,
cutting across areas such as Proof Theory, Computation Theory,
Applicative Programming, and Philosophical Logic. Several
machine-independent approaches to computational complexity have been
developed, which characterize complexity classes by conceptual
measures borrowed primarily from mathematical logic. Collectively
these approaches might be dubbed IMPLICIT COMPUTATIONAL COMPLEXITY.

Practically, implicit computational complexity provides a framework
for a streamlined incorporation of computational complexity into areas
such as formal methods in software development, programming language
implicit computational complexity, practical contributions bridging
the gap between Computational Complexity and Programming Language
Theory are therefore of particular interest.

Previous Workshops
------------------


1 Dec 23:19 2000

### Re: Categories ridiculously abstract

In "Towards a categorical foundation of mathematics" (Logic Colloquium
'95, ed's: J. A. Makowsky and E. V. Ravve, Springer Lecture Notes in Logic
no.11, 1998; pp.153-190) and in subsequent work, I am proposing an
approach to a foundation whose universe consists of the weak n-categories
and whatever things are needed to connect them. This is done on the basis
of a general point of view concerning the role of identity of mathematical
objects. Readers of said paper who have followed developments on weak
higher dimensional categories will note that much has been done since
towards fleshing out the program.

Michael Makkai

On Thu, 30 Nov 2000, Tom Leinster wrote:

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


1 Dec 22:13 2000

### localization : more precise question

Re-bonjour,

Thank you for your answers. My question was very general. So here is
the example.

I am going to define the category C and the collection of morphisms S,
with respect to what I would like to localize.

The object of C are the oriented graph. Such an object X is a
topological space obtained by choosing a discrete set X^0 and by
attaching 1-dimensional cells *with orientations*. It is a
1-dimensional CW-complex with oriented arrows.

The morphisms of C are the continuous maps f from X to Y satisfying
this conditions :

1) f(X^0)\subset Y^0

2) f is orientation-preserving

3) f is non-contracting in the sense that a 1-cell is never contracted
to one point.

Remark I : in C, an arrow x--> is not isomorphic to a point.

Remark II : an arrow a-->b can be mapped on the loop a-->a with one
oriented arrow from a to a.

A morphism f of C is in S if and only if f induces an homeomorphism on
the underlying topological spaces. Now here is an example of f\in S


2 Dec 14:34 2000

### Re: Categories ridiculously abstract


Tom Leinster wrote:
>
> 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?

-Robert Dawson



2 Dec 19:05 2000

### Re: localization : more precise question

Philippe Gaucher <gaucher <at> irmasrv1.u-strasbg.fr> writes:

> The object of C are the oriented graph. Such an object X is a
> topological space obtained by choosing a discrete set X^0 and by
> attaching 1-dimensional cells *with orientations*. It is a
> 1-dimensional CW-complex with oriented arrows.
>
> The morphisms of C are the continuous maps f from X to Y satisfying
> this conditions :
>
> 1) f(X^0)\subset Y^0
> 2) f is orientation-preserving
> 3) f is non-contracting in the sense that a 1-cell is never contracted
> to one point.
>
> A morphism f of C is in S if and only if f induces an homeomorphism on
> the underlying topological spaces.
>
> I would like to know if C[S^{-1}] exists or no (in the same universe).
>
> The irresistible conjecture is of course that C[S^{-1}] is equivalent
> to the category whose objects are that of C and whose morphisms from A
> to B are the subset of C^0(A,B) (the set of continuous maps from A to
> B) containing all composites of the form
> g_1.f_1^{-1}.g_2...g_n.f_n^{-1}.g_{n+1} where g_1,...,g_{n+1}, are
> morphisms of C and f_1,...,f_n morphisms in S.

Call the category you describe D.  There is an obvious functor C --> D
which inverts the morphisms of S.  So there is an induced functor
C[S^{-1}] --> D, which is the identity on objects and is clearly full,


3 Dec 00:33 2000

### Re: localization : more precise question


>The question is whether the functor C[S^{-1}] --> D is faithful.
>
>I suspect that this is true in general, but can only prove it if
>you restrict yourself to CW-complexes with a finite number of cells.

I believe that you are wrong somewhere. The explanation is in
post-scriptum (borrowed from a question in sci.math.research which
is not yet posted by now). Or maybe I am wrong in the reasonning ?

>For infinite CW-complexes, this Ore condition doesn't hold, but I
>still suspect that the functor is faithful.  In part it depends upon
>what you mean by "orientation preserving".  Does this mean "having a
>'positive' derivative at all times"?  Or 'non-negative'?  Or can the
>map go forwards and backwards as long as overall it has degree one?

I meant 'non-negative'. Maybe the definition of the category still needs
to be debugged. I don't know. (The motivation of this question was to encode
the notion of 1-dimensional HDA up to dihomotopy for those who know the
subject in a "true" category such that isomorphism classes represent
1-dimensional HDA up to dihomotopy). "having a 'positive' derivative at
all times" would be also sufficient I think.

Cheers. pg.

PS :

The natural conjecture is that C[S^{-1}] is equivalent to the category
D whose objects are that of C and whose morphisms from A to B are the
subset of C^0(A,B) (the set of continuous maps from A to B) containing


4 Dec 06:30 2000

### Re: Categories ridiculously abstract


1 ab.stract \ab-'strakt, 'ab-,\ adj (15c)
[ML abstractus, fr. L, pp. of abstrahere to draw away, fr. abs-, ab- +
trahere to draw -- more at DRAW]
1a: disassociated from any specific instance <abstract entity>
1b: difficult to understand: ABSTRUSE <abstract problems>
1c: IDEAL <abstract justice>
1d: insufficiently factual: FORMAL <possessed only an abstract right>

2: expressing a quality apart from an object <the word poem is concrete,
poetry is abstract>
3a: dealing with a subject in its abstract aspects: THEORETICAL <abstract
science>
3b: IMPERSONAL, DETACHED <the abstract compassion of a surgeon --Time>

4: having only intrinsic form with little or no attempt at pictorial
representation or narrative content <abstract painting> -- ab.stract.ly
\ab-'strak-(t)l<e^->, 'ab-,\ adv -- ab.stract.ness \ab-'strak(t)-n<e>s,
'ab-,\ n

1a: Sets and categories as mathematical abstractions are equally
disassociated from specific instances.

1b: For almost every interesting known theorem of category theory there
is a harder interesting known theorem of set theory, and vice versa.
It is plausible that the exceptions from set theory outnumber those
from category theory, but it is equally plausible that a majority of
mathematical literates judge category theory harder than set theory.
No clear winner here.



3 Dec 23:39 2000

### Re: localization : more precise question

Philippe Gaucher <gaucher <at> irmasrv1.u-strasbg.fr> writes:

> Dan Christensen wrote:
>
> >I suspect that this is true in general, but can only prove it if
> >you restrict yourself to CW-complexes with a finite number of cells.
>
> I believe that you are wrong somewhere.

...

> If U is a universe containing all sets, let V be a universe with U\in
> V. The categorical construction of C[S^{-1}] (let us call it
> "C[S^{-1}]") gives a V-small category. "C[S^{-1}]"(A,B) is generally
> not a set. To see that, take an object like g_1.f_1^{-1}.g_2 with g_1
> and g_2 not invertible in C (this is a reduced form which cannot be
> simplified in "C[S^{-1}]"). Then replace f_1^{-1} by
>
> f_1^{-1} \sqcup Id_{codom(f_1^{-1})} \sqcup Id_{codom(f_1^{-1})}
> \sqcup...
>
> and g_1 by
>
> g_1 \sqcup g_1 \sqcup g_1 ...
>
> Then "C[S^{-1}]"(dom(g_2),codom(g_1)) has as many elements as the sets
> of U-small cardinals. Therefore "C[S^{-1}]"(dom(g_1),codom(g_2)) is
> not a set.

The maps you've described all represent the same map in C[S^{-1}].


3 Dec 17:44 2000

### Re: localization : more precise question


>I meant 'non-negative'. Maybe the definition of the category still needs
>to be debugged. I don't know. (The motivation of this question was to encode
>the notion of 1-dimensional HDA up to dihomotopy for those who know the
>subject in a "true" category such that isomorphism classes represent
>1-dimensional HDA up to dihomotopy). "having a 'positive' derivative at
>all times" would be also sufficient I think.

I would like to add : I meant 'non-negative' locally. Because one needs that the
morphism from an arrow a-->b to a loop a-->a exists. The exact definition is :
morphism of local po-spaces (see "Algebraic topology and concurrency", by
Fajstrup, Goubault & Rau{\ss}en ; preprint R-99-2008, Aalborg University).

pg.


4 Dec 21:41 2000

### (-1)-categories and (-2)-categories

Robert Dawson wrote:

Actually we should start at least a little bit before that, with
(-2)-categories.  Let me explain....

Once upon a time I showed what I called the "periodic table" to
Chris Isham, a physicist who works on quantum gravity.  It starts
like this:

k-tuply monoidal n-categories

n = 0           n = 1             n = 2

k = 0         sets          categories         2-categories

k = 1        monoids         monoidal           monoidal
categories        2-categories

k = 2       commutative      braided            braided
monoids         monoidal           monoidal
categories        2-categories

k = 3         " "           symmetric           sylleptic
monoidal           monoidal
categories        2-categories

k = 4         " "             " "               symmetric
monoidal