Seminars of the CENTRE de RECHERCHE en THEORIE des CATEGORIES CATEGORY THEORY RESEARCH CENTER C ---------> R | / | | / | | / | | / | v / v T ---------> C PLACE: BURNSIDE HALL 920, McGILL UNIVERSITY (COFFEE AND COOKIES AS USUAL AT 3:00 IN THE LOUNGE) Tuesday, 7 January 1992 1:30 - 3:00 D. Pavlovic (McGill) A "logical" adjoint functor theorem for small fibred categories 3:30 - 5:00 V. Harnik (McGill) Category theoretic aspects of Interpolation for Intitionistic logic. Tuesday, 21 January 1992 1:30 - 3:00 D. Pavlovic (McGill) Fibrations: definitions and examples Tuesday, 28 January 1992 1:30 - 3:00 D. Pavlovic (McGill) Fibrations: (Continued) Tuesday, 4 February 1992 1:30 - 3:00 D. Pavlovic (McGill) Fibrations: (Continued) Tuesday 11 February 1992 1:30 - 3:00 R. Blute (McGill) Coherence for linear logic (with quantifiers) . . . . . Tuesday, 25 February 1992 1:30 - 3:00 D. Pavlovic (McGill) Fibrations: (Continued) Tuesday 3 March 1992 1:30 - 3:00 D. Pavlovic (McGill) Fibrations: (Continued) 3:30 - 5:00 M. Barr (McGill) HSP theorems - reprise Tuesday 10 March 1992 1:30 - 3:00 M. Okada (Concordia) Extensions of Phase Semantics and Cut Elimination 3:30 - 5:00 M. Makkai (McGill) Completeness Theorems for Fibrations Tuesday 17 March 1992 1:30 - 3:00 B. Boshuck (McGill) "Reduced products and regular logic" 3:30 - 5:00 M. Makkai (McGill) Completeness Theorems for Fibrations II Tuesday 7 April 1992 1:30 - 3:00 S. Marcus Formal linguistic aspects of molecular genetics 3:30 - 5:00 S. Marcus From combinatorics to formal grammars; a new approach to Langford strings Tuesday 14 April 1992 1:30 - 3:00 D. Pavlovic (McGill) Descriptions in regular logic of factorisations Tuesday 26 May 1992 1:30 - 3:00 J Otto (McGill) Progress towards NP from categorical comprehension Tuesday 9 June 1992 1:30 - 3:00 S. Finkelstein (U. Penn.) "Categories, Relations, and Dynamic Programming" Tuesday 28 July 1992 1:30 - 3:00 Richard Squire "A Duality theory for the topos of finite directed graphs" Tuesday 4 August 1992 1:30 - 3:00 Richard Squire "Maximally ordered objects in a topos" PLACE: BURNSIDE HALL 920, McGILL UNIVERSITY ABSTRACT: In a series of 4 papers (1977-1981), Peter Johnstone investigated the consequences of adding to the axioms of a topos the DeMorgan law ~(p & q) <==> ~p v ~q He showed , in particular, that this law was equivalent to the theorem of classical mathamatics: ``every maximal ideal in a commutative unital ring is a prime ideal''. In this talk, we will carry through a similar investigation for laws /\ \ / /\ ~( / \ p_i ) <===> \/ (~ / \ p_i ) (Lee_n) 1<=i<=n 1<=j<=n i#j of which the DeMorgan law is the special case $n=2$. In place of maximal ideals in a ring, we shall instead study maximal orderings on a object. One consequence we derive is that the law $(\mbox{Lee}_n )$ holds iff the object of MacNeil reals (essentially the order completion of the rationals) has breadth less than or equal to $n$. Tuesday 11 August 1992 1:30 - 3:00 Richard Squire "Maximally ordered objects in a topos" continued ============================== Tuesday 15 September 1992 2:00 - 3:30 Michael Makkai "On 4x5 logical doctrines" Tuesday 22 September 1992 2:30 - 4:00 R.A.G. Seely (McGill U) "Proof nets at the Calgary Stampede (Coherence theorems with units)" Tuesday 29 September 1992 2:30 - 4:00 Silvio Ghilardi "Normal forms, 2nd order quantifiers and Lindenbaum algebras: a combinatorial approach to propositional modal logic" Tuesday 13 October 1992 2:30 - 4:00 Richard Jozsa (U de Montreal) "Quantum Mechanics and the Theory of Computation." -- ABSTRACT -- The operation of any computing machine is necessarily a physical process evolving the input of the computation to its output. The standard mathematical theory of computation based on the concept of Turing machine, rests on classical physics and disallows quantum mechanical effects, in particular the appearance of quantum superpositions of binary values during the course of the computation. The inclusion of quantum effects gives rise to new modes of computation not available to any classical machine. Some of these will be described and illustrated with basic examples. In particular we describe a class of problems that can be solved with certainty by quantum computation in exponentially less time than any classical deterministic computation, demonstrating the essential role quantum mechanics for issues in complexity theory. (For this talk only an elementary exposure to quantum mechanics will be assumed.) Tuesday 20 October 1992 2:30 - 4:00 Marek Zawadowski (McGill U) "Lax Descent Theorems for Left Exact Categories (Expanded version)" Tuesday 27 October 1992 2:30 - 4:00 R. Blute (McGill U) "Braided linear logic" Tuesday 3 November 1992 2:30 - 4:00 Michael Barr (McGill) "Cohomology of algebras" ** ABSTRACT ** Consider an adjunction F -| U, U: *A* --> *B* and F: *B* --> *A*. Suppose that *A* is a regular category and U a regular functor. Let T and G be the resultant triple and cotriple. Assume that B projective in *B* implies that TB is projective. Suppose the inclusion Ab(*A*) --> *A* has a left adjoint Diff. Suppose there is a chain complex functor C.: *A* --> ChComp(Ab(*A*)) that produces, for each A of *A*, for which UA is projective, a projective resolution of Diff(A). Suppose also that for each n >= 0, there is a ~C_n: *B* --> Ab(*A*) such that ~C_n o U = C_n (= here means natural equivalence). Then for any A of *A* such that UA is projective and any M of Ab(*A*), we have H^._G(A,M)=Ext^.(Diff(A),M). Applications include the well-known equivalence of the Hochschild cohomology of associative algebras with the cotriple cohomology for algebras that are projective over the ground ring, as well as that of the Eilenberg-Mac Lane cohomology of groups with the cotriple cohomology, but also gives the analogous result for Lie algebras, which has not, to my knowledge, been previously published. -------------------------- Tuesday 10 November 1992 2:30 - 4:00 T Fox (McGill, Vanier) "Drinfeld's bialgebras - introduction" Tuesday 17 November 1992 2:30 - 4:00 Silvio Ghilardi (McGill) ``A relational and topological version of intuitionoistic logic'' (some recent joint work with G. Meloni. A preprint is ready). Tuesday 24 November 1992 2:30 - 4:00 M. Barr (McGill) "Non-symmetric Chu construction." ABSTRACT Given a symmetric monoidal closed category, Chu shows how to embed it into a *-autonomous category, by choosing an arbitrary object as dualizing object. I will show that something of the same can be done in the non-symmetric (biclosed) situation provided the dualizing object _|_ is chosen so that for any object V, we have V --o _|_ is isomorphic to _|_ o-- V, the isomorphism natural in V. Although such objects are probably rare, a terminal object, if any, is sure to be one. Even in the symmetric case, that gives a particularly simple instance of the Chu construction that has not, to my knowledge, been previously looked at. Tuesday, 1 December 1992 J. Otto (McGill U) "From PR, Sigma^0_1, Pi^1_1 recursion to alternating complexity: results and speculations" (This talk will conclude the series of talks J Otto has given in J Lambek's Tuesday class -- he will begin with a rapid review of the issues covered (in detail) in the earlier talks.) Tuesday, 8 December 1992 2:30 - 4:00 M. Makkai (McGill U) "On Sketches" PLACE: BURNSIDE HALL 920, McGILL UNIVERSITY (COOKIES AND COFFEE AS USUAL AFTER THE TALK.)