August 1994 - Categories - categories.org.au

Top\op is a quasi-variety
by Michael Barr 02 Sep '94

02 Sep '94

by Michael Barr and M. Cristina Pedicchio We show that there is a certain variety (= category tripleable over sets) and a simple Horn sentence in it of the form phi(u) = phi(v) ==> psi(u) = psi(v) whose category of models is equivalent to the opposite of topological spaces. The theory consists of that of frames together with a unary operation we denote ' (it is a kind of pseudocomplement) satisfying a small set of equations plus an equation scheme that forces all intervals of the form [u /\ u',u \/ u'] to be complete atomic boolean algebras with the Sup and ' as operations. The underlying set functor on Top\op takes a space to the set of all pairs (U,A) where U is open and A is an arbitrary subset of U. The frame operations are the usual, while (U,A)' = (U,U - A). The Horn clause is u \/ u' \/ 1' = v \/ v' \/ 1' ==> u \/ u' = v \/ v'. [note from moderator: Michael says the paper will be available by ftp from triples.math.mcgill.ca soon.]

2 1

distributivity
by Michael Barr 31 Aug '94

31 Aug '94

I pass on to you a curious fact that was mentioned to me by Richard Squire and he credited it to Jim Loveys. Let P and Q be quantifiers. (What is a quantifier? Well as a first approximation it is a map from X--o L to L which is in some obscure (to me) sense polymorphic. Limits (both in categories and posets), integrals and, evidently, univeral and existential quantifiers in logic, where L is the object of truth values. Looking at all the examples, you realize immediately that polymorphism is certainly not functoriality and if some of them give inequalities or morphisms, they do so in different directions (say SUP vs INF or A vs E).) Well, anyway, P and Q are quantifiers. Say that P distributes over Q if there is an equation P(x:X).Q(y:Y).f(x,y) = Q(s:X--o Y).P(x:X).f(x,s(x)) One aspect of polymorphism is that this makes sense. Here f: X x Y --> L and if treat this as a map Y --> (X--o L), then the LHS makes sense. As for the RHS, we are doing the same thing with X x (X--o Y) --> X x Y --> L, where the first map is <id,eval> and the second is f. Here are 2 1/2 examples: If P is universal quantification, Q is existential and L is the object of truth values in a topos, then this is the axiom of choice. If P is sup in a lattice and Q is inf and if X and Y are restricted to finite sets, then this is the statement of distributivity. If P is SUP in a complete lattice and Q is INF, then this is the complete distributivity identity. Now here is the startling fact. In all three cases, the distributivity of P over Q implies that of Q over P! For the lattices, these facts are well-known. For the AC, it is easy to see (at least in a boolean topos) since you can negate and replace f by its complementary relation. (Yes a topos that satisfies AC is boolean, but it does not immediately follow that these two complementary conditions are equivalent, since perhaps only one of them implies AC in the non-boolean case.) This doesn't always hold. For example, in a topos, finite products distribute over (finite) sums, but the converse is certainly false.

3 2

Partial Topos
by Thomas Streicher 30 Aug '94

30 Aug '94

Dear All, I'd like to know whether the following is aloready well known ? Around 1980 in a lecture course at Louvain-la-Neuve Jean Benabou introduced the notion of partial topos. He defined it as a category IB with pullbacks such that each slice is an elementary topos and the reindexing functors f* are logical and have right adjoints Pi_f . One immediately can see that it is enough to claim that each slice is an elementary topos : slices having products means that one has pullbacks and for any f : J -> I the reindexing functor f* is logical and has a right adjoint as it is isomorphic to the functor (f : f -> id_I)* : (IB/I) -> (IB/I)/f which is the inverse image part of a local homeomorphism. Nevertheless this definition of partial topos as a category all whose slices are toposes has a certain defect - pointed out by Benabou himself - namely that ANY groupoid is a partial topos as it has pullbacks and any slice is the trivial topos. Now what is a natural condition ruling out this defect. I propose the following condition (Weakening) for any I the forgetful functor Sigma_I : IB/I -> IB has a right adjoint I* : IB -> IB/I I call this weakening as any category with pullbacks is a model of extensional type theory not allowing empty contexts (which would be interpreted as the (non-existing) terminal object). Nevertheless we would like to have weakening by a type which corresponds to the rule Gamma |- B A a type --------------------------- A , Gamma |- B the categorical semantics of "weakening by A" is applying the right adjoint to Sigma_A : IB/A -> IB. LEMMA 1 An ARBITRARY category IB has weakening iff IB has binary products. Proof : If Sigma_I -| I* then I*X : I*X -> I is the first projection and the counit eps_X : I*X -> X is the second projection. end_of_proof Now the condition of weakening rules out nontrivial groupoids. LEMMA 2 If IB is a groupoid satisfying weakening then for any I in IB the functor Sigma_I : IB/I -> IB has a right adjoint and therefore preserves colimits. Now id_I considered as an object of IB/I is initial and therefore I = Sigma_I(id_I) is initial. Thus all objects of the groupoid are initial and the groupoid is trivial. end_of_proof This suggests the following new DEFINITION A category IB is a PARTIAL TOPOS iff (i) any slice of IB is a topos (ii) IB has weakening, i.e. all binary products. Immediate consequences of the definition : LEMMA 3 Let IB be a partial topos. The the following hold (i) IB has equalizers (ii) any finite diagram in IB has a colimit iff it has at least one cocone (iii) IB / O is trivial (iv) if f : A -> B and the exponential object B^A exists then IB has a terminal object . In more elementary terms partial toposes can be characterized as follows. LEMMA 4 IB is a partial topos iff (i) IB has pullbacks and binary products (ii) any f* has a right adjoint Pi_f (iii) for any I the category IB/I has a subobject classifier (i.e. there exists an epi Omega_I : Omega_I -> I split by T_I : I -> Omega_I such that for any f : A -> I and subobject m : A' >--> A there exists a unique morphism chi : A -> Omega_I with chi ; Omega_I = f and m = chi*T_I ) Proof : (ii) is equivalent to any slice being cartesian closed. EXAMPLES of Partial Toposes (i) (Benabou 1980) Let IE be an elementary topos and F a nonempty downward closed subset of Sub_IE(1). Let IE_F be the full subcategory of IE consisting of those subobjects X s.t. support(X) is in F . Then IE_F is a partial topos. Taking IE = Set^I and for F the subsets of I containing at most one element (the downward closure of the atoms in Sub_IE(1)) then IE/F is not closed under finite sums. (ii) the category of finite trees is a partial topos (Benabou, private communication) (iii) the category of spaces and local homemorphisms is a partial topos (cf. mail of Freyd in April '94 on CATEGORIES) (iv) the category of small (finite) categories and discrete fibrations is a partial topos (the slice over C is equivalent to the topos of (finite) presheaves over C) binary products can be constructed by showing that for any C Sigma_C has a right adjoint; the construction of the right adjoint is suggested by the Yoneda lemma Are there other useful examples ?? Is this the "correct" definition of "partial topos" ? Thomas Streicher

1 0

duality in 2-categories
by john baez 23 Aug '94

23 Aug '94

Does anyone know a good treatment of duality in 2-categories? I'm interested in situations where the objects have duals but also the objects in the Hom-categories have duals. I guess Fischer discusses this in his paper on 2-categories and 2-knots, but I'm looking for a more detailed and extended treatment. Regards, John

1 0

Gordon Plotkin
by John Power 18 Aug '94

18 Aug '94

Those category theorists involved with computer science may like to hear the happy news that Gordon Plotkin was married to his long time friend Hephzi last weekend in California. They now live in Edinburgh, with summer visits to California. John Power.

1 0