January 1992 - Categories - categories.org.au

extensional realizability refutes Scotts axiom
by Thomas Streicher 31 Jan '92

31 Jan '92

EXTENSIONAL REALIZABILITY REFUTES SCOTT'S AXIOM It is well known that in the category of w-Sets there are several full small internally complete subcategories : - PER : interprets propositions - complete extensional pers , Sigma replete pers : candidates for effective domains ! Now the idea might be to use PER as propositions to speak about effective domains. Of course, this is possible ! BUT the logic is quite weak in the sense that the Proposition expressing Scott's Axiom is not realized !! PROOF : Let SIG denote the per corresponding to the r.e. subobject classifier . If Scott's Axiom (see e.g. M. Hyland in the Como Proc. or P. Taylor in the LICS'91 Proc. !) were realizable then there would exist a realizable morphism M : ((N -> SIG) -> SIG) -> N* ( N is the predomain of natural numbers and N* is N with bottom) such that for all F in (N -> SIG) -> SIG) : (a) M(F) = )bot) iff F()lambda ) x . )top)) = )bot) and (b) M(F) = n implies F()lambda) x < n . )top)) = )top) . As M is realizable it is monotonic we have that for all F in (N -> SIG) -> SIG) : M(F) less_or_equal M()lambda ) f . )top)) . Thus M applied to the least element gives )bot) and there exists a natural number n such that for all other F M(F) = n . But that would mean that for all F which are not least it holds that f(k) = )top) for all k < n implies F(f) = )top) . BUT THIS IS A CONTRADICTION : consider F := )lambda) f . f(n) ; this F is nontrivial and F()lambda) x < n . )top)) = )bot) . Thus such an M (Modulus of Continuity) cannot exist . END OF PROOF Of course, this proof can be performed for any reasonable axiomatization of SDT in an extensional type theory : If N is a proposition we can prove that all elements of N are equal ! Thus all propositions contain at most one element ! Thus we are again back at the effective tripos over w-Set , i.e. in some sense the topos-theoretic approach to SDT is the best we can expect. Actually to my opinion we do not need the full topos logic it is sufficient to consider triposes. I think the axiom of comprehension : A type , P predicate on A --------------------------------- { x : A | P(x) } type is not very nice to work with syntactically. At least I do not know a nice treatment by proof rules. By the way it is not a real restriction : from any tripos we can construct the associated topos. Thomas Streicher ======================================

2 2

None
by beck＠math.cornell.edu 30 Jan '92

30 Jan '92

Stephen Chase tells me that the answer to the question, if he understands it correctly, is contained in J.-L. Loday, "Spaces with finitely many nontrivial homotopy groups", JPAA 24(l982), Lemma 2.2, p. l83 and is "a crossed module." Jon Beck +++++++++++++++++++++

1 0

None
by street＠macadam.mpce.mq.edu.au 30 Jan '92

30 Jan '92

Dear David, In a bit of a hurry, but saw your message. Groups in GPD are crossed modules a la Whitehead. Is this what you want? There are many references (eg the Mq Math Report on Braided monoidal categories --1986 version). Regards, Ross ++++++++++++++++++++++

1 0

None
by Paul Taylor 30 Jan '92

30 Jan '92

Internal categories in the category of groupoids. David Yetter asked whether there is a structure theorem for "groups in GROUPOIDS". I interpret this question as "models of the finite-product theory of groups in the category (which has finite products) of groupoids and homomorphisms". I have a suspicion that David had something different in mind, such as "groupoids in groups", but shall consider the question as posed. Remember, incidentally, that the category of sets is a full subcategory (preserving all sorts of structure) of the category of groupoids. [The latter is, unlike groups, (locally?) cartesian closed as well.] Now internal *categories* in groupoids [and this easily specialises to groups] seem a natural generalisation of the quotienting of a preorder to give a poset, ie the "skeletalisation". We know that there's no natural way of just picking one object from each isomorphism class - so instead take the entire isomorphism class and consider it as a group, ie as a component of the groupoid of objects. Commutative squares with two sides isomorphisms provide the groupoid of morphisms. The construction is universal in a way which I shall leave to the reader to formulate. This idea has an application to polymorphism. Eugenio Moggi and Martin Hyland once proposed as a categorical interpretation of quantification over types simply taking the product indexed by the set of [names of] objects of the category. [We have in mind categories with a small number of isomorphism classes of objects - it's quite possible to have a cartesian closed category with exactly two (nonisomorphic) objects - we call it a model of the lambda calculus with eta and surjective pairing.] Unfortunately this idea is not invariant under categorical equivalence, and is therefore objectionable to the sensibilities of semantic categoricians such as myself. However the idea may be re-interpreted internally in the category of groupoids, and then becomes invariant, as Edmund Robinson observed. In fact something similar, though slightly more complicated, arises naturally in stable domain theory. The trace factorisation (see my unpublished 1988 paper, available by anonymous FTP from theory.doc.ic.ac.uk) expresses stable functors as spans and cartesian transformations as rigid comparisons between them, making the original 2-category an internal category in the category of domains and rigid comparisons. In the case of coherence spaces, the latter is equivalent to just the category of graphs and embeddings; this easily generalises to dI-domains. For (my) quantitative domains [see my paper in the Manchester Category Theory and Computer Science proceedings, LNCS 389, also FTP] it is the category of groupoids and homomorphisms. In both these cases, second order quantification in the standard domain way [which has been attributed to Girard, but was in my thesis before, and I didn't regard it as original, though I don't know to whom to attribute it - probably Plotkin] coincides with the Moggi-Hyland-Robinson interpretation. Paul Taylor ======================================

1 0

my recent question whether a complex is Kan if homotopy is an ER.
by kelly_m＠maths.su.oz.au 29 Jan '92

29 Jan '92

Michael Barr's letter of 19 Jan to the bulletin board about this seems to me to be based on a misunderstanding. He says he shows how to fill in a 1-horn; but all he does is to produce the third side of a triangle when two sides are given - while what the Kan property demands is that one be able to fill in the whole triangle, interior and all. My difficulty was to see how to get any non- -trivial stuff on the interior at all, using "homotopy is an ER". At any rate, I have now received a counter-example from Bill Dwyer at Notre Dame; here it is: -------------------------------------------------- I'm beginning to think that the answer to your question is "no". Here's a possible counterexample and a line of argument. Suppose that E is the category with one object x and one non-identity morphism e: x-->x, where e^2=e. Then (1) If C is a category and F, G: C --> E are functors, then F and G are connected by a natural transformation. In fact, the function which assigns to any morphism of C the map e: x --> x is a natural transformation from F to G. There are only four diagrams to check: 1 1 e e x ---> x x ---> x x ---> x x ---> x e | | e e | | e e | | e e | | e V V V V V V V V x ---> x x ---> x x ---> x x ---> x 1 e 1 e (2) Let N be the nerve functor from categories to simplicial sets and L its left adjoint. L assigns to any simplicial set A the category whose objects are the vertices of A and whose morphisms are generated by the one-simplices of A, with one relation for each two-simplex. Let f, g: A --> N(E) be two simplicial maps. These correspond to functors F, G: L(A) --> E. As in (1) there is a natural transformation between F and G, which passes to a homotopy H : N(L(A)) x \Delta[1] ----> N(E) between N(F) and N(G). Composing H with the map A x \Delta[1] -----> N(L(A)) x \Delta [1] induced by the adjunction map A --> N(L(A)) gives a homotopy between f and g. In other words, for any two maps f, g: A --> N(E) there is a homotopy from f to g, so that in particular homotopy is an equivalence relation on maps A -> N(E). (3) N(E) is not a Kan complex. The nerve of a category is a Kan complex iff the category is a groupoid. For instance, in N(E) the following cofiguration cannot be extended to a two-simplex, because e does not have an inverse. x A e / / x ---> z 1 I think this is ok. Let me know if you find a hole in it. Bill Dwyer ---------------------------------------------------------- Max Kelly, 24 Jan. ======================================

2 1

groups in GROUPOIDS
by dyetter＠math.ksu.edu 28 Jan '92

28 Jan '92

I'm wondering whether anyone (most likely by anyone I mean Ross Street, Andre Joyal or Ronnie Brown, but I thought I'd ask the net) knows a structure theorem for groups in GROUPOIDS. I've worked out that if G is the group of objects, H the group of connected components and A the (necessarily abelian) group of automorphisms of the identity object, then the group of arrows must by a semi-direct product of G x_H G with A, with source and target maps being projections, but I have not been able to show or find a counter-example to the conjecture that the map assigning identity maps to objects must be (\Delta, 0) and composition must be addition on the A components, and forgetting the common target/source in the other components. This seems to be something which should be known, so before putting more time in, I thought I'd ask. --David Yetter ======================================

1 0

None
by barr＠triples.Math.McGill.CA 27 Jan '92

27 Jan '92

The example from Philip Ehlers is interesting and, although I haven't checked it, I presume it is correct. On the other hand, my last posting is also right (and his example fails it too). And I _do_ remember being told that a complex is Kan iff homotopy is an ER. So what gives? Well, way back when I studied algebraic topology, we were told that two k simplexes in a SS were homotopy if there was an n-simplex (n > k) of which they were faces. Then homotopy of simplexes is the ER generated by this. Now when you triangulate a square (that is, I x I) you get two triangles, so that, for example, two 1-simplexes are homotopic, by the reln that Ehlers used, if there are a pair of simplexes with a common edge of which these are faces of the one and the other. Of course, these generate the same ER, but they are not the same ER and it is possible for one, but not the other, to be an ER. Michael ======================================

1 0

None
by barr＠triples.Math.McGill.CA 27 Jan '92

27 Jan '92

Kan complexes Max is right; I forgot what I was doing. Nevertheless, I learned long ago that a simplicial set is Kan iff the homotopy relation on maps to that set is an equivalence. I tried to prove it here with no references and I cannot, but I can certainly give a plausibility argument. I'm not sure I ever knew the whole proof. It must be in papers of Kan, in the late 50s. The plausibility argument is that if x^0 and x^1, say, are such that d^0x^0 = d^0x^1 and I want to find a 2-simplex of which x^0 and x^1 are d^0 and d^1, I begin by showing that x^0 ~ s^0d^0x^0 = s^0d^0x^1 ~ x^1. It follows that there is a simplex of which x^0 and x^1 are two of the faces. Then you have to find one of which it is the first two faces and I am not sure how to proceed. To see that x^0 ~ s^0d^0x^0, we calculate that d^0s^1x^0 = s^0d^0x^0, while d^1s^1x^0 = x^0. Dwyer's example seems to be that the nerve of a category isn't Kan. Yes, in fact about 1970, Boardman and Vogt showed that the nerve of a category always satisfies the "middle Kan" condition, meaning that it satisfies the condition for all missing indices except the first and last, but is not in general Kan. But it is not clear what is the point of including Dwyer's example. It is certainly not an example of a complex in which homotopy is an equivalence relation. Michael ++++++++++++++++++++++++++

1 0

2-natural transformations
by kelly_m＠maths.su.oz.au 25 Jan '92

25 Jan '92

Does the community have any reaction to the following observation, that we have made these last few days? Let A and B be 2-categories, and F,G : A ---> B be 2-functors. There is a notion of 2-natural transformation t : F ---> G; such a t is not only to be natural, in the usual sense, with respect to 1-cells, but to have the appropriate property with respect to 2-cells as well. Certainly mere natural- ity does not imply 2-naturality, as one sees on taking for A the free-living 2-cell. Yet it DOES imply 2-naturality if A admits tensor products with the arrow-category 2 (or dually cotensor products with 2). A consequence is that the forgetful functor, from the category of finitary 2-monads on a locally-finitely-presentable 2-category A to the category of finitary monads on the underling category of A, is a fully-faithful functor with both adjoints. In particular, a finitary monad on Cat or such-like has at most one enrichment (although usually none) to a 2-monad; and similarly for the more common case of enrichability over the closed category of groupoids. John Power and Max Kelly, at Sydney - 24 Jan. ======================================

1 0

with some trepidation
by MAP010＠vaxa.bangor.ac.uk 24 Jan '92

24 Jan '92

%This is a LaTeX file which outlines a possible counterexample %to the conjecture which was on the mailing board at the %beginning of the week. I apologise for forgetting who %originally asked the question, and for the somewhat eccentric %style of the answer! \documentstyle{article} \title{A Counter Example} \date{23 January 1991} \begin{document} \maketitle The question was asked, on the category theory mailing board, as to whether this conjecture is true. \newtheorem{Kan}{Conjecture} \begin{Kan} Let $B$ be a simplicial complex. If homotopy is an equivalence relation on ${\em SS}(A,B)$ for all $A \in ob({\em SS})$, then $B$ is a Kan complex. \end{Kan} I think I have a counter example, and would appreciate it if anyone could spot the flaw(s) in the argument. \rule{0mm}{20mm} Let B be the simplicial set which is the complete directed graph on three vertices. Pictorially, this is the following:- \begin{picture}(200,150) \put(50,110){\circle*{5}} \put(150,110){\circle*{5}} \put(100,20){\circle*{5}} \put(55,112){\vector(1,0){90}} \put(145,108){\vector(-1,0){90}} \put(55,105){\vector(1,-2){40}} \put(90,25){\vector(-1,2){40}} \put(145,105){\vector(-1,-2){40}} \put(110,25){\vector(1,2){40}} \end{picture} This simplicial set is clearly not Kan. \rule{0mm}{10mm} There are nine simplicial set morphisms $I \longrightarrow B$ which we shall call $f_{jk}$ where this maps the non-degenerate element of $I_1$ to the edge from $j$ to $k$ (for $j = k$ this is just the degenerate edge at $j$). We shall denote the non-degenerate element of $I_1$ by $\iota$. \rule{0mm}{10mm} Now, consider any $f:A \longrightarrow B$ for any simplicial set $A$. Since all $n$-simplices in $B$ are degenerate for $n \geq 2$, we have that $f_n(a) = sf_{jk}$ where $s$ is some combination of degeneracy maps; note that if $j = k$, then $s = s_0^n$. Since simplicial morphisms commute with the face and degeneracy maps, this means that $f$ is completely determined by its effect on the $0$-simplices and $1$-simplices. \rule{0mm}{10mm} We require to show that the relation of homotopy is an equivalence relation on the hom-set $\underline{\em SSets}(A,B)$ for any $A$. Clearly it is reflexive, as there is a simplicial set morphism from $(A \times I)$ to $B$ which is dummy in the second variable. \rule{0mm}{10mm} If we now consider any two simplicial morphims $f,g:A \longrightarrow B$ and a homotopy $F:(A \times I) \longrightarrow B$ from $f$ to $g$, we construct a homotopy $G$ from $g$ to $f$ as follows:- \[G_0(a,0) = F_0(a,1) \;\;\; \mbox{and} \;\;\; G_0(a,1) = F_0(a,0) \;\;\; \mbox{for} \;\;\; a \in A_0\] \[ \mbox{If} \;\;\; F_1(a,\iota) = f_{jk}(\iota) \;\;\; \mbox{then} \;\; \; G_1(a,\iota) = f_{kj}(\iota) \;\;\; \mbox{for} \;\;\; a \in A_1 .\] Since these are all the elements of $B$, this determines $G$. Clearly \[ G(a,s_0^n1) = F(a,s_0^n0) = g(a) \;\;\; \forall a \in A_n \] \[ G(a,s_0^n0) = F(a,s_0^n1) = f(a) \;\;\; \forall a \in A_n \] \rule{0mm}{10mm} Lastly, assume we have two homotopies, $F$ from $f$ to $g$ and $G$ from $g$ to $h$. Then, we construct a homotopy $H$ from $f$ to $h$ as follows:- \[ H_0(a,0) = G_0(a,0) = h_0(a) \;\;\; \mbox{and} \;\;\; H_0(a,1) = F_0(a,1) = f_0(a) \;\;\; \mbox{for} \;\;\; a \in A_0 .\] If $F_1(a,\iota) = f_{jk}(\iota)$ and If $G_1(a,\iota) = f_{kl}(\iota)$ then $H_1(a,\iota) = f_{jl}(\iota)$ for $a \in A_1$. This is transitivity, and so the example is complete. \rule{0mm}{20mm} Comments, please! \rule{100mm}{0mm} ${\em Phil}$ \end{document} ====================================== Subj: Kan complexes (twice)

1 0