CT95 Abstracts

ADÁMEK, J. Finitary sketches II

An (α-)geometric sketch is a small category with a choice of finite limits and arbitrary colimits (of size smaller than α); a category is said to be (α-)geometrically sketchable provided that it is equivalent to the category of all models of an (α-)geometric sketch.

We prove that for any α-geometric sketch S, where α is smaller or equal to the first measurable cardinal, there is a finitary sketch which is equivalent to S in the sense that their categories of set-valued models are equivalent. Thus, if measurable cardinals do not exist, any geometric sketch is equivalent to a finitary one. The same is true for finite set-valued models. While the equivaΣe of geometric and finitary sketches is equivalent to the non-existence of measurable cardinals, for finite sets this problem is open.

This is joint work with P. T. Johnstone, J. Makowsky and J. Rosický.

BARR, M. Acyclic Models

Acyclic models is a powerful technique in algebraic topology and homological algebra in which facts about homology theories are verified by first verifying them on “models” (on which the homology theory is trivial) and then showing that there are enough models to present arbitrary objects. One version of the theorem allows one to conclude that two chain complex functors are naturally homotopic and another that two such functors are object-wise homologous. Neither is entirely satisfactory. The purpose of this account is to provide a uniform account of these two, fixing what is unsatisfactory and also finding intermediate forms of the theorem.

BETTI, R. Factorizations in bicategories

Many factorization structures which are known in Cat and in other bicategories are of a “regular” type, in the sense that they can be obtained by universal (weighted) constructions. For an arrow in a bicategory, the kernel is defined by suitable weighted limits while a colimit construction relative to the same weights gives the corresponding notion of quotient. The main result consists in the fact that the process of taking kernels is right bi-adjoint to that of taking quotients. The counit of this bi-adjunction provides a canonical factorization of any arrow. We give suitable conditions, both on weights and on bicategories, in order that this canonical construction provide a factorization structure.

This is joint work with D. Schumacher.

BISSON, T. Covering Spaces as Operations in Cobordism Theory

For any finite covering space over a closed manifold we define an operation in the category of manifolds and study the behavior of these operations up to cobordism. In particular we get a theory of Dyer-Lashof operations in the bordism of any E-infinity space. A complete description of the algebra of these operations is given via the algebraic theory of D-rings, which is formulated by using Lubin’s theory of isogenies of formal group laws. We also describe the (Nishida) relations between the Dyer-Lashof and Landweber-Novikov operations, and show how to represent the Dyer-Lashof operations in terms of their actions on the characteristic numbers of manifolds.

The entire theory can be viewed as a geometric and categorical lifting of mod 2 homology with its Steenrod algebra and Dyer-Lashof algebra.

This is joint work with A. Joyal.

BLUTE, R. Linear Lauchli Semantics

We introduce a linear analogue of Lauchli’s semantics for intuitionistic logic. In fact, our result is a strengthening of Lauchli’s work to the level of proofs, rather than provability. This is obtained by considering continuous actions of the additive group of integers on a category of topological vector spaces. The semantics, based on functorial polymorphism, consists of dinatural transformations which are equivariant with respect to all such actions. Such dinatural transformations are called uniform. To any sequent in Multiplicative Linear Logic (MLL), we associate a vector space of “diadditive” uniform transformations. We then show that this space is generated by denotations of cut-free proofs of the sequent in the theory MLL+MIX. Thus we obtain a full completeness theorem in the sense of Abramsky and Jagadeesan, although our result differs from theirs in the use of dinatural transformations.

As corollaries, we show that these dinatural transformations compose, and obtain a conservativity result: diadditive dinatural transformations which are uniform with respect to actions of the additive group of integers are also uniform with respect to the actions of arbitrary cocommutative Hopf algebras. Finally, we discuss several possible extensions of this work to noncommutative logic.

This is joint work with P. Scott.

BOURN, D. Characterization of the nerve of n-Groupoids

In a previous work, I showed that the category of n-groupoids is monadic over the category of normalized (n − 1)-groupoids, i.e. (n − 1)-groupoids equipped with the choice of a point in each connected component, of a 1-morphism between every pair of points, of a 2-cell between every pair of 1-morphism and so on, in a way which provides a natural polyhedral presentation of n-groupoids.

This monadicity theorem allows us to define naturally a functor K_{n} from the category n-Grd B of n-groupoids in IB to the category (n + 1)-Simpl B of the simplicial objects of length (n + 1) in IB, which is the nerve functor for n-groupoids.

Actually it is even possible to characterize the nerve of n-groupoids as (n + 1)-simplicial objects plus further operations, which provides a complete simplicial presentation of n-groupoids. In this description, the normalized (n − 1)-groupoids play the role of the split (n − 1)-simplicial objects.

BUNGE, M. Fundamental group of a topos : paths versus coverings

A connected locally connected topological space (such as the long circle) may have a trivial paths fundamental group yet a non-trivial Chevalley group of automorphisms of a universal cover (Barr & Diaconescu 1981). This “anomaly” often disappears if the topological space is replaced by its topos of sheaves. It is our aim to analyse this situation under conditions as general as possible on the topos in question.

The paths fundamental group of a bounded topos was given in somewhat different forms in (Moerdijk & Wraith 1986) and in (Moerdijk 1988), using descent and classifying toposes. The coverings fundamental group of a topos originated in (Grothendieck 1981) and was subsequently generalized in several directions. The unpointed case dealt with in (Bunge 1992) uses the (classifying topos of a) localic groupoid approach to the subject and is thus suitable for the comparison with the paths definition, initiated in (Bunge 1992a).

After exploring further the two paths and the coverings definitions mentioned above, we prove that, in the case of a connected, locally connected, and locally paths simply connected bounded topos, all three agree. The example of the long circle is thus recovered and other examples given.

This is joint work with I. Moerdijk.

CLEMENTINO, M. M. Separation versus connectedness

Approaching separation and connectedness via closedness and denseness, relative to a closure operator, of diagonals, I introduce and study a Galois correspondence that links the two concepts.

COCKETT, R. Coherence for MIX

Categorical models for (the multiplicative fragment of) linear logic which satisfy the mix rule should also satisfy a simple coherence theorem which allows morphisms to be represented as proof nets. Unfortunately, this theorem does not provide a description of the basic coherence diagrams which must be satisfied.

While it is certainly the case that the units of the two tensors must be isomorphic, it is significant that this by itself is not sufficient to secure the above coherence theorem. There is a further and more subtle condition which can best be described using the weak distributions between the tensors.

The talk will describe this extra condition and how one can obtain the desired coherence theorem which allows nets to represent the morphisms. The results rely on the coherence theorems available for weakly distributive categories.

CUBRIC, D. Semantics for the Universal Quantifier

We study the “right adjoint” fragment of intuitionistic multisorted predicate logic, that is the connectives (T, &, →, ∀) with Lawvere/Lambek/Prawitz equality of proofs. The categorical models are forall fibrations - a generalization of hyperdoctrines. In the indexed category language they can be defined as follows: the base has finite products, fibers are cartesian closed categories, pullback functors preserve the structure and the pullback functors along projections have stable right adjoints. We show that many of the well known properties of cartesian closed categories hold here as well. We organize them in the form of three representation theorems. The first one represents every forall fibration as a classifying fibration for a typed calculus and as a consequence every forall fibration is equivalent to one which is strict, normal, and the pullback functors preserve the structure “on the nose”. Next, we have a Yoneda-like representation of forall fibrations obtained using a variant of Street-Walters Yoneda structure on the 2category of fibrations. As a corollary, we obtain some conservativeness results for our fragment. Our third representation theorem is a Friedman-like completeness for the free forall fibrations with respect to families of Sets. A corollary of this result can be stated as follows: a diagram commutes in every forall fibration if and only if it commutes when interpreted in sets. Also, we present some of the syntactic properties of our calculus e.g. a solution of the word problem.

DAMPHOUSSE, P. Distorted logic for full subcategories of finite sets

The power set construction X ↦ PX is basic to set theory and logic. The inverse image functor (written C), and the functors ∃ and ∀ defined by its left- and right- adjoints on each object are endofunctors of sets which have the value PX on each set X. Are there others? The question is closely related to the existence of endofunctors F of Set not isomorphic to the identity endofunctor but nevertheless fixing objects (i.e. F X = X for each set X). Given any such “fixing object endofunctor” (fixob) F of Set, the composites ∃F, CF and ∀F still satisfy ∃F ⊣ CF ⊣ ∀F and ∃F X = CF X = ∀F X = PX. Moreover, given a full subcategory of Set (stable or not for the power set construction), what are its “fixobs”? We give a complete anwer to this question for full subcategories of finite sets and examine the meaning of the corresponding quantifiers ∃F, CF and ∀F.

DUSKIN, J. Some Applications of 2-Category Techniques in the Theory of Braided Tensor Categories

Two years ago, in a Montreal talk before an audience composed mostly of category theorists, Pierre Cartier suggested that the theory of 2-categories might prove useful in the study of quantum groups and related topics. This work is the result of one such investigation.

A strict tensor (=monoidal) category may be equivalently viewed as monoid object in Cat or a category object in Mon. As a cat-monoid, its nerve is a simplicial monoid whose underlying double complex is that of a 2-category with a single object (= 0-cell) with 1-cells provided by the objects of the tensor category and composition of 1-cells provided by the tensor product. The arrows of the tensor category and their composition give the 2-cells and their composition, and the functoriality of the tensor product gives the ∗-composition of 2-cells and the “interchange law”. Strict tensor functors between tensor categories become strict 2-functors between 2-categories with a single object, and it is from this entirely equivalent point of view that we wish to pursue the subject of this talk.

First, about Joyal-Street “braidings”: In any 2-category one can form the double category of “lax-(commutative) squares” which consists of squares of composable 1-cells together with a 2-cell connecting the compositions of the 1-cells on each side of the diagonal. There is an obvious “horizontal composition” of such lax-squares as well as a vertical one and they are easily seen to satisfy the interchange law of a double category. Moreover, there is an obvious way to introduce 2-cells between lax-squares which makes the lax-squares into a category object in 2-Cat which plays the role of representing “lax functors between 2-categories”. Now, among these lax-squares are those which define the “epi-center” of the 2-category, the lax squares whose two vertical 1-cells are identical and whose horizontal 1-cells are as well. This condition forces all of the corners of square to be the same 0-cell and to have its “interior” to be 2-cell of the form A ⊗ B ⇒ B ⊗ A when the 2-category is that associated to a strict tensor category. We define a (normalized) braiding on a 2-category with a single object C as a bi-functorial (i.e., functorial in each variable) section c of the epi-center of C c_{A,B} : A ⊗ B ⇒ B ⊗ A is easily seen to satisfy exactly the conditions of the Joyal-Street definition, including naturality, when the associativity isomorphisms are all identities, except that c_{A,B} is not required to be invertible but we require c_{1,B} = id(B) and c_{A,1} = id(A), “normalization”.

The chief advantage of this 2-category point of view of strict tensor categories is that it gives an easy “geometric” way to handle braidings using the Sydney School’s highly efficient way of dealing with equations and proofs in 2-categories using “pasting diagrams”.

Now any 2-category C has its own “oriented geometric nerve” which can be defined as the simplicial set which has the 0-cells of C for 0-simplices and the 1-cells for 1-simplices. 2-simplices x are defined as triangles of 1-cells together with a 2-cell x : d_{1}(x) ⇒ d_{2}(x)⊗d_{0}(x) for interior. 3-simplices consist of the “commutative tetrahedra” each made of four compatible 2-simplices of the foregoing sort for which the unique composition of the odd faces is equal to that of the even faces, a condition easily expressed as an equality of the corresponding pasting diagrams. Degeneracies are equally well supplied, and the full nerve is just the coskeleton of the just defined truncated complex. From a simplicial point of view this nerve just corresponds to the classifying space of the simplicial category defined by the original 2-category which is its fiber. In the case here at hand of a tensor category this geometric nerve is a reduced (i.e., only one 0-simplex) simplicial set and its fiber is the simplicial monoid defined by the strict tensor category. The nerve is thus seen to form the first step in a simplicial spectrum as we will see below. (One equally well has the oppositely oriented version of this nerve where the 2-simplices interior is of the form x : d_{0}(x) ⊗ d_{2}(x) ⇒ d_{1}(x). Both are needed in the applications.)

Now suppose that the tensor category has a braiding c, then the nerve of C has the structure of a simplicial monoid which is trivial in dimension 0, has the composition of 1-cells (tensor product) as multiplication in dimension 1, but uses the braiding to define the product of two arbitrary 2-simplices x and y using their interiors by pasting the square c(x_{2}, y_{0}) between the triangles x and y to form a new 2-simplex whose faces are exactly the products of the corresponding 1-cell faces (so that the face maps become homomorphisms). This product is associative and unitary (using s_{0}(1) as unit) and the product of commutative tetrahedra is commutative. Thus a braiding defines the structure of a simplicial monoid on the classifying space of \overline{W} (C) with C as its loop complex. This allows us to iterate the construction for one more step and obtain a new simplicial set \overline{W}^{2}(C) which has \overline{W} (C) as its fiber. \overline{W}^{2}(C) is supplied the structure of a simplicial monoid if and only if the braiding is symmetric (c^{2} = id), in which case the iteration can be continued indefinitely. (That symmetric monoidal categories are infinite loop spaces was first observed by Peter May, so what we have here is the low dimensional fragment of the symmetric case.)

Now given any structure of a simplicial monoid on the nerve of a tensor category viewed in the fashion which has C as its kernel, the product of the degenerate 2-simplices s_{1}(x)s_{0}(y) may be seen to define a 2-cell c(x, y) : x ⊗ y ⇒ y ⊗ x which may be seen to define a braiding on the original tensor category C and we have the Theorem: There is a bijective correspondence between braidings on a strict tensor category and simplicial monoid structures on its nerve. They define spectra if and only if the braiding is symmetric.

Note: Most of the objects of interest in braided tensor categories such as algebras, co-algebras, bialgebras, braided-algebras, commutative algebras, modules etc. have a pretty geometric picture when put in this 2-category frame, for example, an associative co-algebra is just a commutative tetrahedron in the above sense which has all of its 1-cell faces equal.

FIORE, M. Aspects of Axiomatic Domain Theory

The purpose of axiomatic domain theory is to understand domain-theoretic models of computation. The aim is both at explaining domain theory as it has been developed and at enriching it with new theorems and models.

I will show how a detailed axiomatic analysis of the notions of approximation and passage to the limit leads to models of domain theory (with uniform fixed-point operators and supporting the solution of domain equations) which are not Cpo-enriched in a relevant sense.

And I will present enrichment and representation theorems showing that there is a model of domain theory with respect to which all models enrich and such that all models can be fully and faithfully represented in a power of it.

FUNK, J. Geometric Spreads

The notion of a spread, due to R. Fox (1957), has a natural formulation for geometric morphisms (in terms of definable subobjects in the sense of Barr and Paré (1980) ). With this formulation of spread we extend to arbitrary (bounded) toposes the identification, established by Funk (1993), of the distributions (Lawvere, 1983) on a localic topos with the category of complete spreads with locally connected domains over the given topos. Related to this result is the pure/spread factorization for TOP/S, for a base topos S (analogous to that of Collins and Dyckhoff (1977) ). A consequence of the factorization is that a locally connected spread is a local homeomorphism. Geometric spreads are, as in topology, fiberwise zero-dimensional, where zero-dimensionality is defined in terms of relatively complemented opens (Kock and Reyes, 1994).

This is joint work with M. Bunge.

GATES, R. A construction of the initial distributive category with P (X) ≅ X

Given a polynomial P and an object X of a distributive category C, we may form the object P (X) of C. Suppose also we are given a distinguished isomorphism P (X) ≅ X in C. Then X may be thought of as a data type object in C – the arrow P (X) → X giving constructors for the data type, and the arrow X → P (X) giving destructors.

For example, one might consider P (X) ≅ X + 1, in which case the object is a model of the natural numbers. Alternatively, one might consider P (X) ≅ X^{2} + 1, in which case the object is a model of binary trees.

A natural question to ask is: Given P, what is the initial such distributive category? The arrows in this initial category will be the straight line programs one can write using the operations of the data type, and usual distributive operations. What are the isomorphisms in this category?

This question was proposed by Lawvere, with the suggestion that two objects were isomorphic exactly when they were equal as elements of the free rig satisfying the given equation. Blass investigated the case of binary trees, using the notion of “particularly elementary” maps rather than the initial category. The author considered in a previous paper the case of natural numbers, constructing the initial such category and identifying the isomorphisms.

This question is answered by direct construction – the initial such category is given explicitly. The construction takes place in three stages - we first construct the initial category with products and the components of the constructor P (X) → X, then sums are freely added, and finally a category of fractions construction is used to invert the required arrow. Note that the category of fractions is produced from a calculus of right fractions, and thus the resultant category looks hopeful for explicit computations.

The category of Sets always has an initial model of a given data-type, and hence the initial category so produced may be equipped with a functor into Sets. Under reasonable conditions on the polynomial, this functor is faithful, and this allows the computations of the isomorphism classes in the initial category to be carried out.

GRANDIS, M. Limits in double categories

We define here the notion of horizontal limit for a double functor F : I → A with values in a double category. And we give a construction theorem for such limits.

Theorem: The double category A has all (small) horizontal limits iff it has (small) horizontal products, horizontal equalizers and horizontal tabulators (of vertical arrows).

For a vertical arrow u : A → B, the horizontal tabulator is the horizontal limit of the double diagram consisting of u. In other words, it consists of an object Tab u, universally equipped with two horizontal maps p : Tab u → A, q : Tab u → B and a cell p connecting them to u (its horizontal ends are p, q; its vertical ends are the vertical identity of Tab u and u).

In particular, if A is a 2-category, the cotensor 2 ∩A is the same as the tabulator of the vertical identity of A. Thus, one recovers Street’s construction theorem of weighted limits through ordinary limits and such cotensors.

As a preparatory lemma, we show that the double category A has horizontal limits of “horizontal functors” HI → A iff it has horizontal products and horizontal equalizers. The construction of such limits is the standard one. Here HI is the obvious “horizontal” double category over the category I, all of whose vertical arrows and cells are identities.

Then, the theorem is proved, roughly speaking, by constructing a new 1-dimensional graph Î, by replacing every vertical arrow u of I with a new object ⟨u⟩, simulating its horizontal tabulator, and every vertical composition w = vu in I, with a new object ⟨u, v⟩, simulating the “double tabulator” Tab (u, v) (the obvious pullback of the tabulators of u and v). The double functor F : I → A produces a “horizontal functor” G : HÎ → A, and its horizontal limit (by horizontal products and equalizers, because of the previous lemma) is the horizontal limit of F.

This is joint work with R. Paré.

HU, H. On pure morphisms in accessible categories

As a generalization of pure embedding in accessible categories, “pure morphism” is one of the central concepts in the theory of accessible categories (see, J. Adámek and J. Rosický, Locally Presentable and Accessible Categories, Cambridge Univ. Press, 1994). This talk will summarize the recent progress on the problem of whether each κ-pure morphism in a κ-accessible category is a regular monomorphism.

JANELIDZE, G. Higher Dimensional Central Extensions: A Categorical Approach to Homology Theory of Groups

As shown in [2], the so-called double central extensions of groups can be described as the 2-dimensional coverings with respect to the standard adjunction between groups and abelian groups. Now we extend this result to higher dimensions. Using the generalized Hopf formula [1], we show that all homology groups of groups (with coefficients in Z) can be defined in terms of higher dimensional Galois groupoids.

Since this definition uses only purely categorical Galois theory, similar results might be expected for the homotopy groups in Topology and Algebraic geometry.

References

1. R. Brown and G. Ellis: Hopf formulae for the higher homology of a group, Bull. London Math. Soc. 20 (1988) 124-128.

2. G. Janelidze: What is a double central extension? (the question was asked by Ronald Brown), Cahiers de Topologie et Géométrie Différentielle Catégoriques XXXII-3 (1991) 191-201.

JOYAL, A. Bicompletions of Categories

KATIS, P. Circuits and the Grothendieck Construction

It has long been known that the algebraic structure of categories equipped with products provides a calculus for constructing straight-line circuits. In order to study feedback of circuits, and to take into account the fact that circuits have internal state (which is crucial to understanding abstraction and refinement), it is claimed that the theory of bicategories is needed.

The construction Circ (defined in [5]) is discussed. This provides a fundamental example of a bicategory of circuits (which is also called Circ), and it comes equipped with a tensor product and a feedback operation. In fact, this bicategory is an example of a (weak) equipment (see [2]). How the theory of the latter may be used as a tool for handling some constructions important to Computer Science is indicated.

The Grothendieck construction is shown to exhibit circuits as a class of spans of categories (which are characterized), relating the theory to [6]. As a result of this there is a natural way to define functors behaviour, equilibrium : Circ → Rel, which are proven to be structure preserving. This makes explicit the connection between this work and that of [3] and [1].

Though [4] and the concept of compact closed bicategory should clearly be part of an abstract treatment of feedback, there are subtleties regarding feeding-back circuits which indicate that more structures are involved. This will be discussed, as well as how the concepts of input and output may be clarified by an investigation of such structures.

References:

[1] Brown C. and Jeffrey A., Allegories of circuits, Proc. Logical Foundations of Computer Science, St. Petersburg, 1994.

[2] Carboni A., Kelly G. M. and Wood R. J., A 2-categorical approach to change of base and geometric morphisms I, Cahiers de topologie et géométrie différentielle catégoriques 32, 1991, 47-95.

[3] Jones G. and Sheeran M., Circuit design in Ruby, Formal methods for VLSI design, North-Holland, 1990, pp. 13-70.

[4] Joyal A., Street R. H. and Verity D., Traced Monoidal Categories, Macquarie Mathematics Report No. 94-156, August 1994.

[5] Katis P., Sabadini N. and Walters R. F. C., The bicategory of circuits, Technical Report 94-22, University of Sydney, June 1994.

[6] Lawvere F. W., State Categories and Response Functors, Preprint, May 1986.

KELLY, G. M. Enrichment for monads on the category of categories

It has long been known that many structures borne by categories – elementary toposes with logical morphisms provide an example – are algebras for a monad on the category Cat_{0} of (small) categories and functors; results of this kind are due to Burroni, Dubuc-Kelly, and others. Before, however, one can apply the results of [Blackwell, Power, and Kelly, Two-dimensional monad theory, JPAA 59 (1989), 1-41], one needs not a mere monad P on the category Cat_{0} but a 2-monad T on a suitable 2-category – which may be Cat, but is more commonly only the 2-category Cat_{g} of categories, functors, and natural isomorphisms.

We first show that a perfectly respectable monad P may fail to admit any such enrichment T but that – we thought this surprising – the enrichment T is unique if it exists; and we discuss what it says about the nature of the algebraic operations involved, when an enrichment does exist over Cat_{g} or over Cat.

A deeper examination of enrichment, using techniques that largely apply with any symmetric monoidal closed category in place of Cat, leads us to see the category of finitary 2-monads T on Cat_{g} (or on Cat) as a full subcategory of the category of finitary monads P on Cat_{0}, this subcategory being both reflective and coreflective.

We end by discussing how we may often infer, from a presentation of P in terms of operations and equations, that it does indeed lie in one of these subcategories of 2monads.

This is joint work with J. Power.

KLEISLI, H. How induced representations should be constructed

Let G be a completely regular group. Dorofeev and Kleisli introduced a group algebra M(G) as an algebra-object in a ∗–autonomous category due to Michael Barr, and therefore denoted by Barr. That group algebra allows to set up a natural bijection between k– continuous unitary representations ρ of G in a Hilbert space H and M(G)–Hilbert module structures on OH, i.e. continuous algebra-homomorphisms R : M(G) → [OH, OH] in Barr. We denote by M(G)–Hmod the category of M(G)–Hilbert modules and continuous M(G)–homomorphism.

Let S be a closed subgroup of G. Then there is a restriction functor Res : M(G) − Hmod → M(S)−Hmod. The left-adjoint and the right-adjoint of Res exist and coincide, and shall be denoted by Ind. If τ is a continuous unitary representation of S and X the associated M(S)–Hilbert module, then the unitary k–continuous representation of G obtained from the M(G)–Hilbert module Ind X satisfies the universal properties the representation ρ of G induced by τ is supposed to satisfy.

We are going to show how Ind X can be constructed, in spite of the fact that the category of Hilbert spaces and contracting linear maps is far from being complete or cocomplete. Then we compare it with the representation space for the classical construction of an induced unitary representation in the case where G is a locally compact second countable group.

KOCK, A. Natural Bundles over Smooth Étendues

We show how natural bundles, in the sense of differential geometry, extend to the category of smooth étendues. We specialize to cotangent- and frame- bundles, to obtain results on differential forms.

This is partly joint work with I. Moerdijk.

KOSLOWSKI, J. From bicategories of relations to bicategories of profunctors

Our goal is to analyze the relationships between

- set (or any elementary topos) and the corresponding bicategory rel of relations

- the bicategories ord of (pre-)ordered objects and idl of order-ideals

- the bicategories inf of infosys and below-preserving functions and kar, the Karoubian envelope of rel (cf. Rosebrugh and Wood).

We then wish to apply these results to other bicategories of relations induced by regular fibrations in the sense of Pavlovic, or hyperdoctrines in the sense of Lawvere.

This requires some bicategorical preliminaries. Given a bicategory R, the notion of a monad on an object A is well-known. We introduce the weaker notion of interpolad on A by dropping the unit and requiring the multiplication to be a retraction. For both interpolads and monads we introduce a new type of morphisms, called modules. These can be composed provided that the hom-categories of R have pushouts. In this case one obtains bicategories R-int and R-mon, respectively.

If, moreover, the bicategory R is bi-closed with respect to 1-cell composition ;, this property is inherited by R-int and R-mon. The proof of this uses the “bow-tie lemma”, a technical result concerning bi-closed bicategories.

For the power-set fibration on set, one obtains rel as bicategory of relations. Monads in this setting are just reflexive transitive relations (i.e., pre-orders or graphs), and interpolads turn out to be idempotent relations (i.e., transitive relations with the interpolation property, hence the name “interpolad”). In either case, modules are just structure-compatible relations, and one recovers the bicategories idl and kar.

The power-set fibration is equivalent to the full sub-fibration of the codomain functor V:set/set → set, spanned by all monos. V-relations are simply spans in set, the monads for which are small categories. In this situation our modules are just profunctors.

The weaker interpolads may be viewed as “categories without objects”, a notion already suggested by the concept of semifunctor as put forward by Hayashi, cf. also Hoofman. Here our modules could be interpreted as “semi-profunctors”.

Of course, one is interested in the maps of the bicategories obtained in this fashion. Our investigation was partly motivated by the fact that the maps of the bicategory idl form another bicategory (not just a category!) that is equivalent to ord^{co} (with reversed 2cells, i.e., the opposite of the pointwise order). This suggests the possibility of extending Pavlovic’s analysis of categories of maps to fibrations over bicategories. In particular, this requires a re-interpretation of the Beck-Chevalley condition.

References:

Hayashi, S.: Adjunction of Semifunctors: Categorical Structures in Non-Extensional Lambda Calculus, Theor. Comput. Sci 41 (1985), 95 - 104.

Hoofman, R.: Non-Stable Models of Linear Logic, Preprint (1993).

Lawvere, F.W.: Adjointness in foundations, Dialectica 23 (1969), 281 - 296.

Pavlovic, D.: Maps I: Relative to a factorization system, preprint (1993).

Pavlovic, D.: Maps II: Chasing proofs in the Lambek-Lawvere logic, preprint (1994).

Rosebrugh, R. and Wood, R. J.: Constructive complete distributivity IV, preprint (1992).

LAWSON, M. Constructing Inverse Semigroups from Category Actions

Inverse semigroups are amongst the most studied of semigroup classes. Modelled originally on the pseudogroups of transformations important in differential geometry, inverse semigroups are algebraically those semigroups in which each element has a unique generalised inverse.

In this talk, we show that all inverse semigroups can be constructed from categories acting on sets satisfying some simple conditions. Our construction can be viewed as a generalisation of the usual procedure for constructing categories of partial (injective) functions.

In addition to providing a possible way of applying category theory to the study of inverse semigroups, our construction yields examples of inverse semigroups from some natural examples of category actions. Two examples will suffice.

Examples

1. The free monoid on n generators acting on itself gives rise to the polycyclic monoid on n generators.

2. Given an operator domain Ω there is a category whose objects are finite sets and whose morphisms are term substitutions. This category acts on the set of Ω-terms [3]. The inverse semigroup constructed from this action we call the clause semigroup.

Both the polycyclic inverse semigroups and the clause semigroups play an important role in Girard’s ‘Geometry of interaction’. In fact, our work arose from the similarities we noticed between a construction to be found in [2] and a construction in [1].

References:

[1] J.Y. Girard, Geometry of interaction III: accommodating the additives, Preprint, Laboratoire de Mathématiques Discrètes, Marseille.

[2] D. B. McAlister, One-to-one partial right translations of a right cancellative semigroup, Journal of Algebra 43 (1976), 231–251.

[3] D. E. Rydeheard and J. G. Stell, Foundations of equational deduction: A categorical treatment of equational proofs and unification algorithms, in Category theory and computer science, Lecture Notes in Computer Science 283 (1987), 114–139.

LAWVERE, F. W. TBA

LIPPINCOTT, T. An Introduction to Diagrammatic Languages

Diagrammatic languages are a category-theoretic alternative to the traditional conception of a formal language as a set of strings. I will give the central definitions for diagrammatic languages and present some results demonstrating benefits these languages offer over traditional formal languages.

Mac LANE, S. Emmy Noether and Heinz Hopf Made Category Theory Possible

This talk will report on the prehistory of category theory, with attention to developments before 1945 which involved both abstract algebra and algebraic topology. Without such ideas, category theory could not have been discovered.

MacCAULL, W. Kripke semantics for substructural logics with weakening and no contraction

We present Kripke semantics (also known as relational semantics) for substructural logics with weakening, and no contraction. This work is a continuation of the work of Allwein and Dunn [1] on Kripke semantics for Linear logic (which gives, as a special case, the Routley and Meyer relational semantics for Relevance logic). The Allwein and Dunn semantics rests on Urquhart’s Representation Theory for non-distributive lattices.

The logics under consideration have algebraic semantics consisting of monoids with extra structure. Canonical relational models are found by generalizing the process of constructing Kripke models from Heyting algebras. The basic idea is to use maximally disjoint filter-ideal pairs (called maximal pairs) to separate points. The set of maximal pairs has two quasiorders: one determined by the filters, and the other by the ideals. Three ternary relations are defined on the maximal pairs which embody the properties of the algebraic operations & and →. A collection of subsets of the set of maximal pairs, the l-stable sets, forms a model called the canonical model. Properties of the ternary relations in the canonical model are expressed abstractly which yields the abstract definition of the Kripke (relational) semantics.

Our contribution to this area is the axioms for Kripke semantics for a substructural logic with weakening, exchange and no contraction [2]. Soundness and completeness are discussed. We close by discussing progress for logics with weakening, and no contraction or exchange.

References:

[1] Allwein, G. and J. M.Dunn, Kripke models for linear logic, Journal of Symbolic Logic, 58, 514-545, 1993.

[2] MacCaull, W., Relational semantics for a substructural logic with weakening and exchange, submitted.

MacLEOD, R. Substitution Systems

Conservation laws seem to be going out of vogue (at least in Cosmological Physics) but at the level of algebraic theories one law can (should?) be required to hold: Variables may neither be created nor destroyed. A straight forward generalization of “monad” produces “dyad” whose specialization to certain (bi)categories provides a restricted notion of algebraic theory which satisfies the above conservation law.

Examples of such algebraic theories (and their algebras) living in various categories are given. These include simplicial complexes, monoids (of course), but (significantly) not groups.

We will also discuss an adjoint version of these substitution systems and their relationship to the construction of algebras and tensor products.

MAKKAI, M. First order logic with dependent sorts, with applications to category theory

J. Cartmell [2] introduced a syntax of variable types, which I call dependent sorts, for the purposes of presenting generalized algebraic theories. Cartmell’s syntax was “abstracted from Martin-Lof type theory”. I add propositional connectives and quantification to a simplified version of Cartmell’s syntax, to obtain what I call First-Order Logic with Dependent Sorts (FOLDS). The simplification consists in the exclusion of operation symbols, and a severe restriction on the use of equality. Quantification is subject to the natural restriction that a quantifier “for all x ” or “there is x” cannot be applied if in the resulting formula there is a free variable whose sort depends on x.

An important special case of FOLDS was introduced by G. Blanc [1] for the purpose of characterizing first-order formulas in the language of categories that are invariant under equivalence of categories. P. Freyd’s earlier characterization [3], although not explicitly coached in an instance of FOLDS, is essentially the same as Blanc’s. A. Preller [7] gives an explicit comparison of Blanc’s and Freyd’s contexts. The main aim of the present work is to extend Blanc’s and Freyd’s characterization from statements about categories to statements about more complex categorical structures.

A similarity type for structures for FOLDS is given by a one-way category of sort-forming symbols and relation symbols. One-way categories were isolated by F. W. Lawvere [4], and were subsequently shown by him to be relevant for the generalized sketch-syntax of [5].

The basic metatheory of FOLDS is a simple extension of that of ordinary multisorted first-order logic. There are simply formulated complete formal systems for both classical and intuitionistic FOLDS, with Kripke-style completeness for the intuitionistic case. The systems use entailments-in-contexts as their basic units; contexts are systems of typings of variables as usual in Martin-Lof-style systems. We have Gentzen-style systems admitting cut-elimination. Natural forms of Craig Interpolation and Beth Definability are true in both classical and intuitionistic FOLDS. Much of the basic metatheory is done through the formalism of appropriate fibrations (hyper-doctrines).

The main new concept is a notion of equivalence of structures for FOLDS. Equivalent structures satisfy the same sentences of FOLDS. The main general result is that conversely, first order properties invariant under equivalence are expressible in FOLDS. A stronger version of the result takes the form of an interpolation theorem.

Two categories are equivalent in the usual sense iff they are equivalent as structures for FOLDS. This connection between the categorical concept of equivalence and FOLDSequivalence persists for more complex categorical structures such as (1) a diagram of categories, functors and natural transformations, or (2) a bicategory, or (3) a diagram of bicategories, etc., if we pass to “ana”-versions of the concepts of functor, bicategory, etc.; the latter were introduced in [6]. Every functor, bicategory, etc., has its so-called saturation, a simply defined saturated anafunctor, saturated anabicategory, etc., respectively. A property written in FOLDS of the saturation is a particular, “good”, kind of first-order property of the original.

Applications of the foregoing give syntactical characterizations of properties invariant under equivalence in the contexts mentioned. E.g., a first-order property of a variable bicategory is invariant under biequivalence iff it is expressible in FOLDS as a property of the saturated anabicategory canonically associated with the given bicategory.

References

[1] G. Blanc, Équivalence naturelle et formules logiques en théorie des catégories. Archiv math. Logik 19 (1978), 131-137.

[2] J. Cartmell, Generalised algebraic theories and contextual categories. Annals of Pure and Applied Logic 32 (1986), 209-243.

[3] P. Freyd, Properties invariant within equivalence types of categories. In: Algebra, Topology and Category Theories, ed. A. Heller and M. Tierney, Academic Press, New York, 1976; pp. 55-61.

[4] F. W. Lawvere, More on graphic toposes. Cah. de Top. et Géom. Diff. 32 (1991), 5-10.

[5] M. Makkai, Generalized sketches as a framework for completeness theorems. To appear in J. Pure and Applied Algebra.

[6] M. Makkai, Avoiding the axiom of choice in general category theory. To appear in J. Pure and Applied Algebra.

[7] A. Preller, A language for category theory in which natural equivalence implies elementary equivalence of models. Zeitschrift f. math. Logik und Grundlagen d. Math. 31 (1985), 227-234.

MARMOLEJO, F. Weak Limits and Algebras

A weak colimit in a category B is functorial if there is a functorial way of choosing the morphisms which factor a cocone through the given one. In the simplest case, a functorial weak initial object is a pair (Z, F) where Z is an object of B and F : B → Z/B is a functor such that 1_{A} = UF, where U : Z/B → B is the forgetful functor. It is well known that the existence of functorial weak colimits together with split idempotents implies that the category has colimits.

Given another category A, functors H : A → B, R : B → A and a natural isomorphism 1_{A} → RH, we show that the existence of functorial weak (co)limits in B implies their existence in A. We obtain limits for A if A has split idempotents. Notice that, in this situation, if B has split idempotents, then A has split idempotents too.

We explore some applications to categories of algebras for a 2-monad T over CAT. In particular the unit law has the form described in the previous paragraph. In case the category T A has ‘nice’ properties it is necessary for A to be ‘nice’ to have an algebra structure.

NIEFIELD, S. Constructing Quantales From Monoidal Categories

The following result will be applied (in the case where S is the category of sup lattices) to obtain a unified approach to certain examples of quantales (and in particular, locales) and their modules.

Let S be a monoidal category (with coequalizers which are preserved by the tensor product) and consider the categories MONCAT/S of monoidal categories over S and Mon(S) of monoids in S. Then ev : MONCAT/S → Mon(S)^{op} is left adjoint to mod : Mon(S)^{op} → MONCAT/S, where ev is evaluation at the unit object I, i.e. ev(p : V → S) = p(I) and mod(Q) = Q-Mod, the category of Q-Q-bimodules (with suitable definitions for morphisms).

PEDICCHIO, M. C. Internal Category Theory and Commutators

The aim of my talk is to describe the relations between internal category theory and commutator theory. I recall that commutators constitute a basic tool in Universal Algebra and have been widely studied in recent years (see “Commutator Theory for congruence modular varieties” by R. Freese and R. McKenzie).

If we consider a Mal’cev category, i.e. a category with permutable lattices of equivalences, internal groupoids (internal pregroupoids) exactly correspond to reflexive graphs (spans) equipped with a suitable trivial commutator; this kind of result can be used to give a characterization theorem for Mal’cev categories and moreover to construct the free groupoid (pregroupoid) on a reflexive graph (span).

The case of arithmetical categories i.e. categories with distributive and permutable lattices of equivalences, is also investigated; the only possible groupoids in this context are reflexive relations (=equivalence ones). Heyting algebras and duals of topoi are basic examples of this situation.

Finally I will consider the most general case of “modular” categories and discuss some open problems on the subject.

PLEWE, T. Localic triquotient maps are effective descent maps

Triquotient maps are ‘the least common (natural) generalization’ of open and proper surjections.

The main result to be presented here is that triquotient maps are effective descent maps, thus generalizing the corresponding results for proper surjections (Vermeulen), and open surjections (Joyal and Tierney). Because the proof is constructively valid one gets a corresponding result for geometric morphisms between Grothendieck toposes (over an arbitrary base topos) whose localic part is triquotient.

Further results concern stability of triquotiency under various operations, e.g. arbitrary products, filtered (inverse) limits. Among the applications are a new constructive proof of Tychonoff’s theorem, and a new(?) result on stability of open surjections under filtered limits.

ROSENTHAL, K. Quantaloids, Enriched Categories and Automata Theory

This talk is intended to be a survey outlining how the theory of quantaloids and categories enriched in them, provides an effective means of analyzing both automata and tree automata. The emphasis is on the unification of concepts and the simplification provided by categorical methods. Two applications are discussed; the first shows how the syntactic monoid construction for automata is captured by the notion of “syntactic nucleus” on a quantaloid, which can then be used to find the appropriate generalization to tree automata. The second looks at the relationship between context-free languages and tree automata by combining Walters’ work on using multigraphs and categorical methods to study context-free grammars and languages with the notion of relational presheaf on a quantaloid.

The applications described in this talk appear in:

K. Rosenthal, Quantaloidal nuclei, the syntactic congruence and tree automata, J. Pure Appl. Alg. 77, 1992, 189–205.

K. Rosenthal, A categorical look at tree automata and context-free languages, Math. Structures in Comp. Sci. vol 4, 1994, 287–293.

ROSICKÝ, J. Finitary Sketches I

A finitary sketch is a small category with a choice of finite limits and finite colimits; a category is said to be finitarily sketchable provided that it is equivalent to the category of all models of a finitary sketch, i.e., all set-valued functors preserving the specified limits and colimits. We prove that finitarily sketchable categories are precisely those which can be axiomatized by basic theories of the first-order logic which are finitary except that they admit countable disjunctions. It is not known whether this result can be extended to models in an arbitrary topos, but it holds for topoi with enough points or enough finite points (i.e., geometric morphisms into the category of finite sets).

This is joint work with J. Adámek, P. Johnstone, and J. Makowsky.

SQUIRE, R. Ω co-generates simplicial sets

It is known that Ω co-generates the topos of 1-truncated simplicial sets. We show that the statement remains true for the topos of simplicial sets, and, for any n, for the topos of n-truncated simplicial sets.

STEINER, R. Presentations of omega-categories by directed complexes

An omega-category (sometimes called an infinity-category) is a set with an infinite sequence of composition operations subject to axioms generalising those of a 2-category. A directed complex is a complex of arbitrary dimension with a structure generalising the structure of a directed graph. In a loop-free directed graph, the paths form a particularly simple category; generalising this, if a directed complex is loop-free in a natural sense then there is a class of subcomplexes forming a particularly simple omega-category. When an omega-category is represented in this way, the composition operations are all represented by union; this makes multiple composites easy to handle. Methods due to Crans show that an arbitrary omega-category can be represented by loop-free directed complexes in a similar way, provided that one uses equivalence classes.

STREET, R. Low-dimensional topology and higher-order categories I

The Hurewicz arrow notation f : A → B for functions appeared in topology around 1940. It is now standard throughout mathematics and seems indispensable to category theory. The diagrams that result give categorical algebra a geometric flavour. Yet, it is the Poincaré dual notation which makes a deeper connection between categories and low-dimensional topology. Here, f becomes a node while A and B become edges into and out of that node. In the same way that braid groups provide the algebra for braids, higher categories provide the algebra for certain precise classes of manifolds embedded in Euclidean space (braids are a special case).

This is joint work with D. Verity.

THOLEN, W. The categorical notions of separation, compactness and connectedness

Based on notions of closedness and denseness, which may be (but don’t have to be) provided by a closure operator, one may establish the notions mentioned in the title for arbitrary categories. In this talk we concentrate on proving product theorems, and on giving applications for them.

TIERNEY, M. On the theory of path groupoids I

In this paper we use topos theoretic methods to study various aspects of the homotopy theory of simplicial groupoids. In particular, as Kan constructed a loop space that was a group, so we construct and investigate path spaces that are groupoids. These are important, among other reasons, because functorial, colimit preserving path groupoids have right adjoints that lead to classifying spaces.

Thus, we introduce the notions of path space, path groupoid, and adequate graph. Next we define and study the fundamental class of locally transitive groupoids. Our main theorem is that the free groupoid on an adequate reflexive graph is a path groupoid.

This is joint work with A. Joyal.

TRIMBLE, T. Parity Structures on Associahedra and Higher-Dimensional Categories

Parity complexes, introduced by Ross Street, are combinatorial structures used to present higher-dimensional categories. One important use of these structures has been to describe precisely the higher-dimensional cocycle conditions used in non-abelian cohomology. Similar cocycle conditions are used to define the notion of bicategory, tricategory, and presumably their analogues in higher dimensions (called weak n-categories), which have yet to be given precise definitions.

Examination of the cases so far developed reveals a suggestive relationship between such higher-dimensional categorical structures and the associahedra of Jim Stasheff. In this talk we describe a program being developed whose aim is to define such structures in terms of parity complex structures on associahedra. The production of these new parity structures is based on observations of Dominic Verity on his recent surface diagram structures for simplexes. We outline these observations and apply them to the problem of writing down axioms for weak n-categories, including equations for units.

This is joint work with D. Verity.

VERITY, D. Surface Diagrams and Associahedra

Recent work of Street and Verity has established surface diagrams embedded in three space as the appropriate calculus for general composites in Tricategories (weak-3-cate-gories). In higher dimensions it is conjectured that the appropriate calculus for weakn-categories involves embeddings of (n-1)-dimensional graphs in n-space. Of course, this conjecture makes little sense until weak-n-categories have been given a workable definition.

In the first part of this talk I will examine a couple of examples in the Tricategory case which demonstrate both the practical and aesthetic qualities of this calculus. Later I will turn to examining the Associahedra, which Stasheff introduced in his study of loop spaces, using higher surface diagrams. This application is part of recent work, due to Trimble and Verity, which uses surface diagrams as an central step in the process of defining weak-n-categories using operads and associahedra.

WALTERS, R. F. C. Bicategories and Concurrency WALTERS-WAYLAND, J. Commutativity of certain coreflections and reflections in the category of uniform frames

We consider the general question of when reflections and coreflections commute in the category of uniform frames. In particular, we look at the Samuel compactification, the completion functor and variations of the fine reflection. The notion of G_{δ}–density is lifted to the frame setting and used to characterize this commutativity in certain cases.

WENDT, M. Towards an Algebraic Theory of Integration

The space of probability measures on a measurable space forms the object function of a functor which has a left adjoint. Schiopu called the morphisms of the Kleisli category for the monad determined by this adjunction “probabilistic borel maps.” The question arises: what is the Eilenberg-Moore category for the monad? We explore this question by noting the similarities with the totally convex spaces of Pumpluen and Rhoerl. We introduce a category of “integral algebras” (sets with a formal integral) and explore an application to the Bochner integral for Banach space valued measures (this is a straightforward generalization of the classical Lebesgue integral with absolute value replaced by norm). This material leads to the possibility of translating much of the knowledge about totally convex spaces into the context of probability and measure theory.

WICK PELLETIER, J. On the quantisation of points

In the study of quantales arising naturally in the theory of C*-algebras, Gelfand quantales have emerged as the basic setting. In this paper the problem of defining the concept of point of the spectrum of a C*-algebra A , which is the motivating example of a Gelfand quantale, is considered. One intuitively feels that points should correspond to irreducible representations of A . The classical notion of irreducible representation of A is characterized in quantale terms by means of a notion of irreducible representation of the Gelfand quantale Max A on a Hilbert quantale. This characterization leads to an appropriate concept of point for Max A .

This is joint work with C. J. Mulvey

WOOD, R. J. A 2-categorical approach to geometric morphisms and change of base, II

For suitable categories E, the importance of studying relE, parE, spnE, etcetera is well known. Usually, these are regarded as bicategories with the first two examples being locally ordered. For suitable functors T : E ⟶ F, it is possible to codify the effect of such change of base on these examples in bicategorical terms. For example, if E and F are regular and T preserves strong epimorphisms then one has a colax functor relE ⟶ relE that is reasonably named relT. However, for reasons that we have described elsewhere, it is necessary to have a definition of relT that requires no preservation properties of T.

Write conE for a construction typical of the kind above. Presence of a homomorphism of bicategories (−)_{∗} : E ⟶ conE suggests, by analogy with rings, that conE be regarded as an E-algebra and treating the resulting E-bimodule structure as basic turns out to be convenient for the very general change of base problems that we have in mind. This extends earlier published work that was applicable for locally ordered conE. The new framework is dimensionally simpler but we retain the adjunction theorems that enabled a concise description of cartesian bicategories. Thus, one of the many consequences of our study is the extension of the latter concept beyond the locally ordered case.

This is joint work with A. Carboni, G. M. Kelly and D. Verity.