Seminars of the CENTRE de RECHERCHE en THEORIE des CATEGORIES CATEGORY THEORY RESEARCH CENTER C ---------> R | / | | / | | / | | / | v / v T ---------> C 20 January 2004 2:30 - 4:00 M. Makkai 2-topos: ? 27 January 2004 2:30 - 4:00 M. Barr Sub-pregroups of the Lambek pregroup 3 February 2004 2:30 - 4:00 M. Makkai 2-topos: ? (Part II) 10 February 2004 2:30 - 4:00 M. Bunge Johnstone's theorem and Fox completions Abstract In ``Schetches of an Elephant: A compendium of topos theory'', Oxford University Press, 2002, Peter Johnstone proves a new general result (Theorem C3.3.14) describing the pullback topology along bounded geometric morphisms in a surprisingly simple manner, although its proof is both subtle and difficult. One such pullback had been employed (Bunge and Funk, ``Spreads and the symmetric topos'' (SST), JPAA 113:1-38, 1996) in order to define in topos theory the notion of a complete spread, and to prove the equivalence between complete spreads over and distributions on a topos. However, the description of the topology (which strictly speaking was not needed in our categorical treatment) was sketchy. Johnstone's result has now become useful in my identification of an ingredient which renders the complete spread topology explicit. This ingredient is none other than a topos version of the Fox completion of a spread (R.H.Fox, ``Covering spaces with singularities'', Princeton, 1957, and E. Michael,``Cuts'', Acta Math. 111:1-36, 1964). The result that I have just obtained then brings around the motivating idea for the work in SST and completes a full circle of ideas. This will be the subject matter of my lecture. I will also mention in this connection that a different (but clearly related) aspect of an application of Johnstone's theorem to the complete spreads defining pullback of SST is to obtain an elementary (in the language of categories fibred over a base topos) notion of (definable) completeness for geometric morphisms, on a par with (but opposite to) the existing elementary notion of a spread from SST. This second aspect was originally undertaken as joint project with J.Funk, M. Jibladze and T. Streicher. 9 March 2004 2:30 - 4:00 J. Seldin Relating Church-style Typing and Curry-style Typing: Preliminary Report Abstract: There are two versions of type assignment in $\lambda$-calculus: Church-style, in which the type of each variable is fixed, and Curry-style (also called ``domain free''), in which it is not. As an example, in Church-style typing, $\lambda x : A . x$ is the identity function on type A, and it has type $A \rightarrow A$ but not $B \rightarrow B$ for a type $B$ different from $A$. In Curry-style typing, $\lambda x . x$ is a general identity function with type $C \rightarrow C$ for \emph{every} type $C$. In this talk, I will show how to interpret in a Curry-style system every Pure Type System (PTS) in the Church-style. (This generalizes some unpublished work with Garrel Pottinger.) I will then show how to interpret in a system of the Church-style (a modified PTS) every PTS-like system in the Curry style. 23 March 2004 2:30 - 4:00 Bob Coecke Abstract quantum mechanics (Samson Abramsky and Bob Coecke) ABSTRACT We recast the standard axiomatic presentation of quantum mechanics, due to von Neumann, at a more abstract level, of: strongly compact closed categories with biproducts. We show how the essential structures found in key quantum information protocols such as quantum teleportation can be captured at this abstract level. Moreover, from the combination of the --apparently purely qualitative-- structures of compact closure and biproducts there emerge `scalars', `inner-products' and even a `Born rule to calculate the quantum probabilities'. This abstract point of view opens up new possibilities for describing and reasoning about quantum systems. It also shows the degrees of axiomatic freedom: we can show what requirements are placed on the (semi)ring of scalars C(I,I), where C is the category and I is the tensor unit, in order to perform various protocols such as teleportation. Our formalism captures both the information-flow aspect of the protocols (see quant-ph/0402014), and the branching due to quantum indeterminism. This contrasts with the standard accounts, in which the classical information flows are `outside' the usual quantum-mechanical formalism. Hence the abstract formalism can be conceived as `quantum mechanics extended with (both classical and quantum) information flow. 30 March 2004 2:30 - 4:00 Bob Coecke Abstract quantum mechanics II 27 April 2004 2:30 - 4:00 Andrea Schalk Games Played on Graphs (joint work with Martin Hyland) Abstract: Games have been used very successfully to model both, proofs and computations. For some applications we want to be able to identify positions in a game tree. For example, when playing Chess we might only want to know which board position we're in, but now how we got there. In a natural way this leads to games played on graphs rather than trees. Our games have two players which move alternatingly as is standard in game semantics. We do not allow the game to contain cycles. In order for composition to be well-defined, strategies have to satisfy a new condition we call `conflict-freeness'. This amounts to the idea that if a Player strategy is prepared to reach some Player-position then he must be committed to doing so: Whenever it is Player's turn at a position from which he can reach a P-position which he is prepared to reach (by some other path in the game graph), then his answer must move towards this position. A good example for this are games were Opponent moves consist of questions regarding data and Player moves of supplying data, such as Curien's sequential data structures, or concrete data structures if we want to be more general. We will outline the structure which makes our graph games a model for intuitionistic linear logic, and how a closely related category of abstract games can be obtained. 4 May 2004 2:00 - 3:30 John Kennison On CR-epic spaces 18 May 2004 2:30 - 4:00 Claudia Casadio Pregroups and non-commutative linear logic 25 May 2004 2:30 - 4:00 Heinrich Kleisli Complexity clauses in categories 1 June 2004 2:30 - 4:00 Georges Maltsiniotis Structures d'asphericite et categories fibrees Dans "Pursuing stacks", Grothendieck a introduit la notion de localisateur fondamental en degageant les proprietes formelles satisfaites par les equivalences faibles usuelles de la categorie des petites categories, dont la plus importante est le theoreme A de Quillen. A un localisateur fondamental, il associe une classe de foncteurs, appeles foncteurs lisses, partageant la plupart des proprietes des fibrations (au sens des categories fibrees). Dans cet expose, on introduit le concept de structure d'asphericite, generalisant celui de localisateur fondamental, et on y associe une notion de lissite englobant a la fois celle des foncteurs lisses de Grothendieck et celle des fibrations. 6 July 2004 2:30 - 4:00 M. Barr Perfect maps of spaces Abstract: A perfect map is continuous, closed, and compact (inverse image of a compact set is compact). Let Perf be the category of Hausdorff spaces and perfect maps. Then Perf is not complete (lacks a terminal object) but has all fibre products. Moreover Perf is an exact category. The result is that for any space Z, the underlying functor Perf/Z --> Perf/|Z| is tripleable. Moreover, a perfect map Z --> Z' induces a functor Perf/Z' --> Perf/Z (pullback) that has a left adjoint (composition) and is itself tripleable iff Z --> Z' is (regular) epic. (All epics are surjective quotient mappings.) 13 July 2004 2:30 - 4:00 Mark Weber (Ottawa) A general notion of operad 7 Sept 2004 4:00 - 5:30 Claudio Hermida A roadmap to the unification of weak categorical structures: transformations and equivalences among the various notions of pseudo-algebra Abstract: A quick tour of the constructions/equivalences monoidal category :: representable multicategory :: covariantly fibrant multicategory :: pseudo-monoid in Cat, and their general pseudo-algebra versions, with the simplest proof of coherence for lax-idempotent 2-monads. http://maggie.cs.queensu.ca/chermida/papers/roadmap.pdf or http://www.ima.umn.edu/talks/workshops/SP6.7-18.04/hermida/roadmap.pdf 14 Sept 2004 4:00 - 5:30 M Barr Characterizing Lindelof absolute CR-epics. ABSTRACT: There have been several talks during the past year or so by John Kennison and me on absolute CR-epic spaces, which are spaces X such that for any embedding X --> Y, the induced map C(Y) --> C(X) on the real-valued function rings is epic in the category CR of commutative rings. In his last talk, Kennison introduced a concept we called CNP (for countable neighbourhood property) that says that the intersection of any countable family of beta X-neighbourhoods of X is also a beta X-neighbourhood of X. Kennison showed that Lindelof CNP space is absolute CR-epic, but otherwise did not emphasize the property. Now, following an ingeneous suggestion of R. Levy we have shown that for Lindelof spaces, CNP is equivalent to absolute CR-epic. I will attempt to make this talk self-contained by proving both halves of the equivalence. It is worth mentioning that, while there are absolute CR-epic spaces that are not Lindelof, a necessary (but not sufficient) condition on such a space X is that be embeddable in a Lindelof absolute CR-epic space Y in such a way that C(X) = C(Y) and |Y-X| = 1. 21 Sept 2004 4:00 - 5:30 M Makkai Computads and higher dimensional categories: a new approach. 28 Sept 2004 4:00 - 5:30 M Makkai Computads and higher dimensional categories: a new approach II 5 Oct 2004 4:00 - 5:30 Gavin Seal Lax algebras and topological-like structures Abstract: Following the description by Manes [1] of the category of compact Hausdorff spaces as the Eilenberg-Moore category for the ultrafilter monad, Barr [2] showed that by weakening the axioms for a monad and the subsequent algebras, the Eilenberg-Moore category could be seen to be isomorphic to the category of topological spaces. Metric spaces also benefitted from a similar treatment in Lawere's fundamental paper [3], but for the identity monad this time. In recent years, a unified setting emerged, which allowed for a description of these categories, along with the categories of approach and uniform spaces, as categories of so-called "lax algebras" (see [4]). In this talk, we will present this approach and explain how lax algebras may be related to closure spaces. [1] E.G. Manes, "A triple theoretic construction of compact algebras", Springer Lecture Notes in Math. 80 (1969) 91-118. [2] M. Barr, "Relational algebras", Springer Lecture Notes in Math. 137 (1970) 39-55. [3] F.W. Lawere, "Metric spaces, generalized logic, and closed categories", Rend. Sem. Mat. Fis. Milano 43 (1973) 135-166. [4] M.M. Clementino, D. Hofman and W. Tholen, "One setting for all: metric, topology, uniformity, approach structure", Appl. Cat. Struct. 12 (2004) 127-154. 12 Oct 2004 4:00 - 5:30 Prakash Panangaden A Domain of spacetime intervals (joint work with Keye Martin) OCTOBERFEST: 16-17 OCTOBER 2004 19 October 2004 4:00 - 5:30 Nicola Gambino Wellfounded trees in locally cartesian closed categories (Abstract on web page) 26 October 2004 2:30 - 3:45 M Makkai The Word Problem for Computads Coffee break 4:15 - 5:30 Jim Loveys Linear reducts of the complex field Abstract: A {\em reduct} of a first-order structure is simply a structure with the same underlying set, but possibly fewer definable sets. (We allow parameters in the definitions.) If we start with the structure that is the field of complex numbers, it has many reducts, a great number of which are trivial in a certain sense. Any such reduct has a kind of combinatorial geometry (akin to that provided by linear span in vector spaces). If the closed sets yield a distributive lattice, we consider the reduct trivial. If it is not trival in this sense, but the reduct is proper (not the entire field), we call it {\em linear}. We give a list of linear reducts, which is complete up to a finite cover. (That is, for any linear reduct M, there is a constructible map f with finite fibres such that f(M) with the induced structure is on our list.) 2 November 2004 2:30 - 3:45 Joachim Kock On the notion of unit in monoidal categories and monoidal 2-categories Abstract: (This is joint work with Andri Joyal.) First I will explain how the notion of unit in a monoidal category can be formulated in terms of cancellative idempotents. This formulation does not involve left or right constraints, and it is independent of associativity of the tensor. Then I will illustrate how this approach is well-suited to higher dimensional generalisation, by working out the case of monoidal 2-categories, comparing with the notion of unit coming from tricategories. Finally I will outline the proof of the basic result that the category of cancellative idempotents is contractible. This means that up to homotopy 'being unital' is a property, although introduced as a structure. Coffee Break 4:15 - 5:30 Eric Paquette Towards A Categorical Semantics For Topological Quantum Computing (Abstract on web page) 9 November 2004 2:30 - 4:00 J Funk Purely Skeletal Geometric Morphisms (II) Joint work with Marta Bunge Coffee Break 4:30 - 5:30 Jim Loveys Linear reducts of the complex field II (Abstract on webpage) 16 November 2004 2:30 - 3:30 M Makkai The Word Problem for Computads II Coffee break 4:00 - 5:30 C.Barry Jay The pattern calculus (Abstract on webpage) 23 November 2004 4:00 - 5:30 Tsemo Aristide Geometric cohomology