October 2011 - Categories - categories.org.au

Research positions
by Maria Manuel Clementino 26 Feb '14

26 Feb '14

5-YEAR RESEARCH POSITIONS The Centre for Mathematics of the University of Coimbra (CMUC) invites applications for five 5-year research positions in all areas of Mathematics. Applicants should have a PhD in Mathematics and at least three years of post-doctoral experience, with an international-level publication record and demonstrated ability to perform independent research. Preference will be given to candidates working in one of the areas in which the members of CMUC are currently active. A very good command of English is required. The appointments will be made for three years, renewable for two more. Successful applicants are expected to develop research within the areas of interest of CMUC. They should also contribute to graduate studies, supervising students from the Department of Mathematics. The basic salary is equivalent to the index 195 of the Portuguese research career (in the order of 42 500 euros a year), in accordance with the Ciência 2008 guidelines http://alfa.fct.mctes.pt/apoios/contratacaodoutorados/edital2008 Benefits include private health insurance and social security. Applicants should send • cover sheet (available from www.mat.uc.pt/cmuc/coversheet.pdf) including names and contact information of three persons who can provide a letter of recommendation • curriculum vitae (publication list included) • a 5-year research proposal (2 pages max), emphasizing their own research goals as pdf files to cmuc(a)mat.uc.pt. The subject of the e-mail message must include the job reference C2008 FCTUC CMUC v15-v19. The deadline for applications is *September 10, 2008.* ------------------------------ More information can be found at www.mat.uc.pt

1 1

separable locale
by Thomas Streicher 17 May '13

17 May '13

Recently rereading Fourman's "Continuous Truth" I came across the term "separable locale" but could nowhere find an explanation. Does it mean a cHa A for which there exists a countable subset B such that ever a in A is the supremum of those b in B with b leq a. This would be the point free account of "second countable", i.e. having a countable basis. Of course, second countable T_) spaces are separable, i.e. have a countable dense set. Is this reading the "usual" one? Thomas [For admin and other information see: http://www.mta.ca/~cat-dist/ ]

5 4

Dualizing comma categories
by David Leduc 01 Nov '11

01 Nov '11

Hi, A comma category is a comma object in the 2-category Cat of categories and functors. And a comma object is defined by a universal property. Now, one can dualize the notion of comma object by turning around the 1-cells and/or 2-cells in its definition. My question is: when we instantiate those dualized definitions to Cat, what do we obtain? In other words, what is a "co-comma category"? For example, since the product of two categories is a special case of comma category, I would expect that the coproduct of two categories is a special case of "co-comma category". Thanks! [For admin and other information see: http://www.mta.ca/~cat-dist/ ]

3 2

Re: when does preservation of monos imply left exactness?
by George Janelidze 31 Oct '11

31 Oct '11

Dear Dmitry, Absolutely correct (although it does not change anything I said). Thank you for explaining "why". So your real question is about preservation of finite limits by functors of the form A+(-), in the case non-commutative algebras (of various kinds). Well, from this point of view the categories of algebras are 'difficult', and I don't recall any reasonable result at the moment. Moreover, I am surprised that Barr's theorem helps here (which does not mean that the theorem itself is not good of course!), and I would be very interested to learn, what exactly could you deduce from it? Best regards, George -------------------------------------------------- From: "Dmitry Roytenberg" <starrgazerr(a)gmail.com> Sent: Saturday, October 29, 2011 11:55 PM To: "George Janelidze" <janelg(a)telkomsa.net> Cc: "Steve Lack" <steve.lack(a)mq.edu.au>; <richard.garner(a)mq.edu.au>; <categories(a)mta.ca> Subject: Re: categories: Re: when does preservation of monos imply left exactness? > Dear George, > > First, a small correction: A@- should be considered as a functor to > A-Alg, not k-Alg, in order for what I said to be correct (I thank > Steve Lack for pointing that out). > > The square-zero extension is used to show that preservation of > monomorphisms in k-Alg by A@- -- a priori a weaker condition than > flatness -- actually implies preservation of monomorphisms in k-Mod, > i.e flatness. After that it's the classical story you recalled. > > As for why - fair enough: I'm interested to know whether this property > of commutative algebras is shared by other types of algebras (e.g > algebras over k-linear operads, or more general algebraic theories > like analytic or C-infinity rings). The fact that the coproduct > coincides with the tensor product of underlying modules is a very > special property of commutative algebras, so the classical proof fails > already for associative algebras. So I wonder what general exactness > results are available. For instance, I find Michael Barr's theorem > mentioned by Richard very useful. > > Best, > > Dmitry [For admin and other information see: http://www.mta.ca/~cat-dist/ ]

2 1

Re: Empty algebras
by Steve Vickers 31 Oct '11

31 Oct '11

Dear Dusko, First of all, what your "tautology" says is semantically incorrect in the case where A is empty: for then the meet of P is true and the join is false, so we don't have that the meet is lower than the join. Constructively, the product is an empty product and hence 1, while the coproduct is 0 and there is no morphism from the product to the coproduct. The composite morphism (all) x.P(x) --> P(a) --> (exists) x.P(x) exists only when we have a in A. Second, in your proof with contexts, you use "the equivalence true |-() ((all) b. ((all) a. P(a) --> (exists) x. P(x))) <-> (((all) a. P(a) --> (exists) x. P(x)))" You didn't give a proof of this equivalence, but anyway we have a counterexample. When A is empty, (all) a. P(a) and (exists) x. P(x) are true and false respectively, so (all) a. P(a) --> (exists) x. P (x) is false. But (all) b. ((all) a. P(a) --> (exists) x. P(x)) is true, so the biequivalence is false. Regards, Steve. On 24 Oct 2011, at 13:35, Dusko Pavlovic wrote: > hi steve, > > i am afraid that the "falsehood" > > (all) x.P(x) => (exists) x.P(x) > > is a *tautology* of predicate logic, in any topos, for any > predicate P:A-->Prop, with or without the free variables hanging > around. if it helps, think of P:A-->Prop as an A-indexed set of > elements of the lattice Prop. then > > (all) x.P(x) is the meet of P, whereas > (exists) x.P(x) is the join of P, > > and the tautology says the meet is lower than the join. or > constructively, > > (all) x.P(x) is the product of the A-indexed family P(x) > (exists)x.P(x) is the coproduct > > so that > > (all) x.P(x) -->P(a) is a projection, and > P(a) --> (exists) x.P(x) is an injection. > >> with a sequent calculus that keeps track of the possible free >> variables - see e.g. part C of the Elephant. With this notation >> you distinguish between, on the one hand, >> >> true |-(b) ((all) a. P(a) --> (exists) x. P(x)) >> or >> (all) a. P(a) |-(b) (exists) x. P(x) >> >> (both valid) and, on the other, >> >> true |-() ((all) a. P(a) --> (exists) x. P(x)) >> or >> (all) a. P(a) |-() (exists) x. P(x) >> >> (both not valid). > > to prove these last two formulas, observe that > from > true |-(b) ((all) a. P(a) --> (exists) x. P(x)) > we can derive > true |-() (all) b. ((all) a. P(a) --> (exists) x. P(x)) > now use the equivalence > true |-() ((all) b. ((all) a. P(a) --> (exists) x. P(x))) <-> > (((all) a. P(a) --> (exists) x. P(x))) > to conclude that the RHS is true. > > -- dusko [For admin and other information see: http://www.mta.ca/~cat-dist/ ]

5 7

Re: when does preservation of monos imply left exactness?
by Dmitry Roytenberg 30 Oct '11

30 Oct '11

Dear George, First, a small correction: A@- should be considered as a functor to A-Alg, not k-Alg, in order for what I said to be correct (I thank Steve Lack for pointing that out). The square-zero extension is used to show that preservation of monomorphisms in k-Alg by A@- -- a priori a weaker condition than flatness -- actually implies preservation of monomorphisms in k-Mod, i.e flatness. After that it's the classical story you recalled. As for why - fair enough: I'm interested to know whether this property of commutative algebras is shared by other types of algebras (e.g algebras over k-linear operads, or more general algebraic theories like analytic or C-infinity rings). The fact that the coproduct coincides with the tensor product of underlying modules is a very special property of commutative algebras, so the classical proof fails already for associative algebras. So I wonder what general exactness results are available. For instance, I find Michael Barr's theorem mentioned by Richard very useful. Best, Dmitry On Fri, Oct 28, 2011 at 11:36 PM, George Janelidze <janelg(a)telkomsa.net> wrote: > Dear Dmitry, > > Let me write then F(X) = A@X, denoting the tensor product over k by @. > Hence, briefly, @ is + (coproduct) in k-Alg. The fact that, when A is flat > as a k-module, A+(-) : k-Alg --> k-Alg preserves finite limits is absolutely > classical, as well as its proof via modules. However, you do not need the > fully faithful functor from k-Mod to k-Alg given by the square-zero > extension for that: simply use the fact the forgetful functor k-Alg --> > k-Mod not only preserves limits, but also reflects isomorphisms (Some people > prefer to say/use "creates isomorphisms"). > > The preservation of finite limits by A+(-) : k-Alg --> k-Alg (already for > modules) implies, for example, Grothendieck's Descent Theorem saying that if > A is flat, then k --> A is an effective descent morphism. However, much > stronger result is known now: k --> A is an effective descent morphism if > and only if it is pure as a monomorphism of k-modules. This stronger result, > commonly known as an unpublished theorem of A. Joyal and M. Tierney, was > claimed several times by various authors, and I can tell you more if you are > interested. > > Anyway, since the category k-Alg has very bad exactness properties in a > sense, modules were used by category-theorists themselves. And, in spite of > nice results mentioned by Richard Gardner and Steve Lack, I still suggest > not to go through a generalization of the abelian case. Well, such a > suggestion surely cannot be "universal", and if you need a better > suggestion, you should tell us why are you doing this - if I may say so. > > Best regards, > > George Janelidze > [For admin and other information see: http://www.mta.ca/~cat-dist/ ]

1 0

Re: when does preservation of monos imply left exactness?
by Dmitry Roytenberg 29 Oct '11

29 Oct '11

I'll try again... On Mon, Oct 24, 2011 at 11:23 AM, Dmitry Roytenberg <starrgazerr(a)gmail.com> wrote: > Dear category theorists, > > It is well known that any functor that preserves finite limits > preserves monomorphisms, and that for an additive right-exact functor > between abelian categories, the converse is also true. Is it known how > far this extends to the non-additive setting? In other words, what > exactness properties of two categories and a functor between them > would suffice to conclude that the functor preserves finite limits if > and only if it preserves monos? For instance, is it enough to assume > that the categories be Barr-exact and that the functor preserve all > colimits, finite products and monos to conclude that it also preserves > equalizers? > > Any references would be extremely helpful. > > Thanks, > Dmitry > [For admin and other information see: http://www.mta.ca/~cat-dist/ ]

4 6

Re: Simplicial versus (cubical) with connections)
by F William Lawvere 29 Oct '11

29 Oct '11

[Note from moderator: an earlier version of this message was badly formatted and may have been difficult to read so it is being reposted; as a reminder, posts should be sent with text-only formatting] Dear Todd, Ross, Vaughn, et al Trivial objects should NOT be admitted to categories A whose set-valued functors are intended to form a combinatorial topos to serve as a surrogate for some sort of continuous spaces. That is to say, there is a reason why the delta of simplicial sets does not have a unit object (unlike the delta that, as a strict monoid in CAT, has precisely all monads as its actions). Similarly, the basic cubical sets are functors on the part A (of the algebraic category involving two nullary operations) which consists of finitely-presented STRICT algebras; thus this is the classifying topos for those bi-pointed objects (in arbitrary toposes) that satisfy the non-equational entailment front = back entails false. The reason is this: if a site C = Aop has an initial object, then the left adjoint to the inclusion of constant functors, which should model the notion of connected components, is representable, hence preserves equalizers; but the basic intuitive examples of spaces with non-trivial connectivity are constructed as equalizers of maps between connected spaces! (Note that restrictions (on the structures classified) involving falsity, disjunction, or existential quantification typically give sheaf toposes, but exceptionally may just give smaller presheaf categories; another related example is in algebraic geometry, where classifying the algebras subject to the disjunctive condition x^2=x entails x=0 or x=1 merely involves the topos of all functors on those finitely-presented algebras that satisfy the same condition.) According to the paradigm set by Milnor, the relation between continuous and combinatorial is a pair of adjoint functors called traditionally “singular” and “realization”. ("Singular", as emphasized by Eilenberg, means that the figures, on which the combinatorial structure of a space lives, should not be required to be monomorphisms, achieving functoriality with respect to all continuous changes of space; "realization" refers to a process analogous to the passage from blueprints to actual buildings of beton and steel). As emphasized by Gabriel & Zisman, the exactness of realization forces us to refine the default notion of space itself, in the direction proposed by Hurewicz in the late 40s and described by J.L.Kelley in 1955. Further refinements suggest that the notion of continuous could well be taken as a topos, of a cohesive (or gros) kind. The exactness of realization helps the combinatorial topos to describe the continuous category as closely as possible. In the same spirit, the finite products of combinatorial intervals could be required to admit the diagonal maps that their realizations will have. There is one point however where perfect agreement cannot be achieved: the contrast between continuous and combinatorial forced Whitehead to introduce a specific notion he called weak equivalence, (as explained by Gabriel & Zisman) in order to extract the correct homotopy category. The contrast can readily be seen in my list of axioms for Cohesion (TAC): the reasonable combinatorial toposes satisfy all but one of the axioms, but only the continuous examples satisfy that one. This Continuity axiom (preservation of infinite products by pizero) I introduced in order to obtain homotopy types that are "qualities" in an intuitive sense (as they are automatically in suitable continuous cases). I hope these remarks are useful. Bill [For admin and other information see: http://www.mta.ca/~cat-dist/ ]

1 0

CMCS 2012: second call for papers
by A.M.Silva＠cwi.nl 29 Oct '11

29 Oct '11

[- Please note submission deadline January 4 2011 -] ------------------------------------------------------------------------------ CMCS 2012 second call for papers ------------------------------------------------------------------------------ The 11th International Workshop on Coalgebraic Methods in Computer Science 31 March - 1 April 2012, Tallinn, Estonia (co-located with ETAPS 2012) www.coalg.org/cmcs12 *** Proceedings to be published in Springer LNCS *** Aims and scope -------------- In more than a decade of research, it has been established that a wide variety of state-based dynamical systems, like transition systems, automata (including weighted and probabilistic variants), Markov chains, and game-based systems, can be treated uniformly as coalgebras. Coalgebra has developed into a field of its own interest presenting a deep mathematical foundation, a growing field of applications, and interactions with various other fields such as reactive and interactive system theory, object-oriented and concurrent programming, formal system specification, modal and description logics, artificial intelligence, dynamical systems, control systems, category theory, algebra, analysis, etc. The aim of the CMCS workshop series is to bring together researchers with a common interest in the theory of coalgebras, their logics, and their applications. The topics of the workshop include, but are not limited to: * the theory of coalgebras (including set theoretic and categorical approaches); * coalgebras as computational and semantic models (for programming languages, dynamical systems, etc.); * coalgebras in (functional, object-oriented, concurrent) programming; * coalgebras and data types; * (coinductive) definition and proof principles for coalgebras (with bisimulations or invariants); * coalgebras and algebras; * coalgebraic specification and verification; * coalgebras and (modal) logic; * coalgebra and control theory (notably of discrete event and hybrid systems). Keynote Speaker --------------- Samson Abramsky, Oxford University, UK Invited Speakers ---------------- Marcello Bonsangue, Leiden University, The Netherlands Pawel Sobocinski, University of Southampton, UK Submissions ----------- Submission is electronic via the easychair system at http://www.easychair.org/conferences/?conf=cmcs2012 following the submission guidelines below. We solicit two types of contributions: (a) Regular papers to be evaluated by the PC for publication in the proceedings: They must have a length no greater than 20 pages, formatted in LNCS style (http://www.springer.de/comp/lncs/authors.html) They must contain original contributions, be clearly written, and include appropriate reference to and comparison with related work. (b) Short contributions: These will not be published in the proceedings but will be bundled in a technical report. They should be no more than two pages in LNCS format and may describe work in progress, summarise work submitted to a conference or workshop elsewhere, or in some other way appeal to the CMCS audience. Proceedings Publication ----------------------- The proceedings of CMCS 2012 will be published in Springer Lecture Notes in Computer Science. The final proceedings will be published post-conference and feature revised versions of the accepted regular papers. Preliminary proceedings will be made available at the conference in electronic form. Depending on the number and quality of submissions, we will consider publishing extended and revised papers as a journal special issue, subject to the usual reviewing procedure. Previous special issues of CMCS have appeared in high-ranking journals including Information and Computation and Theoretical Computer Science. Important dates --------------- ( for regular papers ) * 4 January 2012: submission deadline (strict) * 3 February 2012: author notification * 7 February 2012: final version ( for short contributions ) * 27 February 2012: submission deadline (strict) * 6 March 2010: author notification ( workshop ) * 31 March - 1 April 2012 Programme Committee ------------------- Luis Barbosa, University of Minho, Braga, Portugal Filippo Bonchi, LIP ENS-Lyon, France Josee Desharnais, Université Laval, Canada Mai Gehrke, Radboud University Nijmegen, The Netherlands H. Peter Gumm, University of Marburg, Germany Ichiro Hasuo, University of Tokyo, Japan Patricia Johann, University of Strathclyde, Glasgow, Scotland, UK Ekaterina Komendantskaya, University of Dundee, Scotland, UK Dexter Kozen, Cornell University, Ithaca, NY, USA Dorel Lucanu, Alexandru Ioan Cuza University, Iasi, Romania Stefan Milius, Technical University of Braunschweig, Germany Larry Moss, Indiana University, Bloomington, USA Prakash Panangaden, McGill University, Montreal, Canada Dirk Pattinson, Imperial College London, UK (co-chair) Dusko Pavlovic, Royal Holloway, London, UK Daniela Petrisan, University of Leicester, UK Grigore Rosu, University of Illinois at Urbana-Champaign, USA Jan Rutten, CWI and Radboud University Nijmegen, The Netherlands Luigi Santocanale, University of Provence, Marseille, France Lutz Schröder, DFKI GmbH, Bremen, Germany (co-chair) Alexandra Silva, CWI, Amsterdam, The Netherlands Ana Sokolova, University of Salzburg, Austria Sam Staton, University of Cambridge, UK Yde Venema, University of Amsterdam, The Netherlands Steering Committee ------------------ Jiri Adamek, Technical University of Braunschweig, Germany Corina Cirstea, University of Southampton, UK H. Peter Gumm (chair), University of Marburg, Germany Bart Jacobs, Radboud University Nijmegen, The Netherlands Alexander Kurz, University of Leicester, UK Marina Lenisa, University of Udine, Italy Ugo Montanari, University of Pisa, Italy Larry Moss, Indiana University, Bloomington, USA Dirk Pattinson, Imperial College London, UK John Power, University of Bath, UK Horst Reichel, Technical University of Dresden, Germany Jan Rutten, CWI and Radboud University Nijmegen, The Netherlands Lutz Schröder, DFKI GmbH and University of Bremen, Germany . [For admin and other information see: http://www.mta.ca/~cat-dist/ ]

1 0

Postdoc and Graduate School programmes of the FSMP
by Thomas Ehrhard 27 Oct '11

27 Oct '11

Dear Colleagues, I would like to draw your attention to the programmes of the FSMP (Paris Foundation of Mathematical Science), please have a look at the web page of the Foundation: http://www.sciencesmaths-paris.fr/index.php?page=16&lien=index.php?page=39&… Notice that "Mathematical Sciences" include "Fundamental Computer Science" and that PPS (http://www.pps.jussieu.fr/) as well as LIAFA (http://www.lafa.jussieu.fr) and the CS Department of the ENS (http://http://www.di.ens.fr/) are part of the Foundation. I'd like to insist in particular on: - The post-doc programme, application deadline December 13th: if you have good candidates please tell them to get in touch with me (or with other colleagues of PPS) as soon as possible, deadline for application December 13th. - The Graduate School programme which provides funding for foreign students in the masters of the FSMP, including Computer Science, deadline for application December 14th. The two following Masters, in which PPS is particularly involved, are associated to this programme: MPRI, https://wikimpri.dptinfo.ens-cachan.fr/doku.php LMFI, http://www.logique.jussieu.fr/www.M2-LMFI/ Don't hesitate to ask us for more information on these programmes and on the application process. Best regards, Thomas Ehrhard thomas.ehrhard(a)pps.jussieu.fr Preuves, Programmes, Systèmes CNRS and University Paris Diderot [For admin and other information see: http://www.mta.ca/~cat-dist/ ]

1 1