June 2009 - 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

Foundations?
by F W Lawvere 03 Sep '10

03 Sep '10

Down with "Foundations"! Up with algebra! Dear Friends, Presumably I am among those who are being "vilified" as "lovers of categories as foundation". By avoiding any precise definition, such a formulation might appeal to the widespread justified boredom induced by the past hundred years of "foundations as justification". Whenever I used the word "foundation" in my writings over the past forty years, I have explicitly rejected that reactionary use of the term and instead used the definition implicit in the work of my teachers Truesdell and Eilenberg. Namely, an important component of mathematical practice is the careful study of historical and contemporary analysis, geometry, etc. to extract the essential recurring concepts and constructions; making those concepts and constructions (such as homomorphism, functional, adjoint functor, etc.) explicit provides powerful guidance for further unified development of all mathematical subjects, old and new. What is the primary tool for such summing up of the essence of ongoing mathematics? Algebra! Nodal points in the progress of this kind of research occur when, as is the case with the finite number of axioms for the metacategory of categories, all that we know so far can be expressed in a single sort of algebra. I am proud to have participated with Eilenberg, Mac Lane, Freyd, and many others, in bringing about the contemporary awareness of Algebra as Category Theory Had it not been for the century of excessive attention given to the alleged possibility that mathematics is inconsistent, with the accompanying degradation of the F-word, we would still be using it in the sense known to the general public: the search for what is "basic". We, who supposedly know the explicit algebra of homomorphisms, functionals, etc. are long remiss in our duty to find ways to utilize those concepts also in guiding high school calculus. Best wishes, Bill Bibliography: - The Category of Categories as a Foundation for Mathematics, La Jolla conference 1965, Springer (1966) - Adjointness in Foundations, Dialectica, (1969), to be reprinted in TAC - Foundations and Applications: Axiomatization and Education, Bulletin of Symbolic Logic, (2003) vol 9, pp 213-224 - Sets for Mathematics, w/ Bob Rosebrugh, Cambridge Univ. Press, (2003) ************************************************************ F. William Lawvere Mathematics Department, State University of New York 244 Mathematics Building, Buffalo, N.Y. 14260-2900 USA Tel. 716-645-6284 HOMEPAGE: http://www.acsu.buffalo.edu/~wlawvere ************************************************************

2 1

Yoneda Theorem < Yoneda Lemma < Dense Yoneda Theorem
by Vaughan Pratt 11 Jul '09

11 Jul '09

(This continues the "no fundamental theorems please" thread under a more apropos heading.) On 6/24/2009 8:17 AM, Steve Vickers wrote: > Vaughan Pratt wrote: >> ... The Yoneda Lemma usually states that J embeds (meaning >> fully) in [J^op,Set], ... > The usual statement is significantly stronger than that (see e.g. Mac > Lane, Mac Lane and Moerdijk, or Wikipedia). It says that, for > contravariant functors F: C -> Set, the elements of FX are in bijection > with transformations to F from the representable functor for X. Your > statement can be deduced by considering the particular case where F too > is representable. Quite right, I should have used something other than "lemma" for that weaker statement. Misplaced force of habit. Googling "Theorem 5.1 (Yoneda)" returns section 5, on full completeness, of Phil Scott's nice Handbook of Algebra chapter. Phil introduces that section with "The most basic representation theorem of all is the Yoneda embedding: Theorem 5.1 (Yoneda) If J is locally small, the Yoneda functor Y: J --> [J^op,Set], where Y(j) = J(-,j), is a fully faithful embedding." (Phil's A is my J, which I'll use throughout as the base whether small or not in order to make it easier to compare theorems.) If "theorem" is good enough for Phil it's good enough for me. For definiteness let's name the theorems as follows. YT (Yoneda Theorem): [J^op,Set] fully extends J. YL (Yoneda Lemma): For any functor F: J^op --> Set and object j of J, F(j) is in bijection with [J^op,Set](J(-,j),F). (This replaces C in Steve's version with J^op.) DYT (Dense Yoneda Theorem): C is equivalent to a category of presheaves on a *small* category J if and only if C densely extends J. Here a category of presheaves on J means a full subcategory of [J^op,Set] containing the functors J(-,j) for all objects j of J (that is, "on J" qualifies not just the individual presheaves but the whole category of them, as in "free group on X"(*)). C densely extends J just when there exists a full, faithful, and dense functor K: J --> C. (If someone has a use for a broader notion of dense extension I wouldn't object to saying "fully densely extends.") For now assume "dense" is defined as in X.6 of CWM, namely that every object of C arises as a colimit of FP for the evident functor P: (K,c) --> J, (K,c) being the comma category whose morphisms are of the form Kj-->c, j in ob(J). (I'll consider equivalent ways of defining density in a followup message.) This has the effect of representing each object c of C as the presheaf C(K-,c): J^op --> Set (namely C(Kj,c) is the set of morphisms of (K,c) of the form Kj-->c) and each homset C(c,d) as [J^op,Set](C(K-,c),C(K-,d)) (that is, Nat(C(K-,c),C(K-,d)) in the CWM notation Steve is using), via the adjunction defining "colimit." The homsets [J^op,Set](J(-,j),F) used by YL (and hence YT) are always small even if J isn't. DYT however deals with arbitrary homsets [J^op,Set](F,G), which may be large when J is, whence DYT's requirement that J be small. (Steve Lack would be the person to ask what form DYT might take for large J.) The applicability of YL and YT to large J makes them incomparable with DYT. However if we require J to be small then we have YT < YL < DYT in the sense that each of them represents entities by using progressively more of [J^op,Set]. YT uses just the image of the Yoneda embedding to represent J, YL takes one step beyond YT by using all the homsets from that image to an arbitrary presheaf in [J^op,Set] to represent carriers of algebras with unary operations (aka presheaves), and DYT takes one more step than YL by using homsets between more general presheaves of [J^op,Set] to represent *all* homsets of C. Replacing "equivalent to" by "representable as" in DYT makes more explicit the sense in which DYT is unambiguously a representation theorem for certain abstractly defined categories, namely dense extensions of a small category, which are of greater generality than the categories contemplated in YT or YL. > There can be no doubt that this strong Yoneda Lemma is vitally important > when calculating with presheaves - for example, it shows immediately how > to calculate exponentials and powerobjects. If F and G are two > presheaves, then the exponential G^F is calculated by > > G^F(X) = nt(Y(X), G^F) (by Yoneda's Lemma) > = nt(Y(X) x F, G) (by definition of exponential) I would only buy that reasoning for small J (otherwise why should G^F be a functor to Set?), where YL isn't benefiting from the additional generality of YL over DYT. Is there any other reason to prefer YL to DYT? It doesn't seem a very natural candidate for theorem-hood (perhaps that's why it's relegated to the status of a lemma). It's hard to argue for it as the fundamental theorem of CT when it's sandwiched in between YT and DYT, both of which *do* come across as real theorems (the reason I'm comfortable calling both of them theorems). Anyone remember the history of why YL rose to the top? > I don't think you can get it and its useful consequences from your > weaker statement, even if you start strengthening yours in the way you > suggest by supplying converses. Don't underestimate the power of the converse. YL < DYT because it's only a partial converse, DYT is the whole thing. > Another closely related and important result, though not known as > Yoneda's Lemma as far as I know, is that the presheaf category over C is > a free cocompletion of C, and the Yoneda embedding is the injection of > generators. The colimit-based definition of dense functor shows that this is pretty much equivalent to DYT and therefore stronger than YL in what I take to be the sense in which you consider YL stronger than YT. (Is there a stronger sense of "stronger," e.g. a natural nonstandard model in which YT is true and YL false, or YL true and DYT false?) Michael Shulman's comment about the enriched case is apropos here: defining cocompletion for conical (co)limits isn't sufficient when V doesn't permit them (for want of diagonal functors). This limitation can be avoided with left Kan extensions as treated in Chapter 4 of Kelly, "Basic Concepts of Enriched Category Theory." Kelly arrives at the notion of free cocompletion 15 pages into Chapter 4 and long after indexed (nowadays weighted) colimits (Chapter 3) as a satisfactory generalization of conical colimits. (Incidentally, of what use are non-free cocompletions? Is there any reason not to define "cocompletion" to make it free? I seem to recall people being happy to drop "free" in this context. Who ordered "free"?) This post is quite long enough already so I'll stop it here with the interesting question (to me anyway), what is the earliest point in the development of (ordinary or unenriched) category theory at which one can introduce either cocompletion or density in order to have functors that are dense, full, and faithful? Can either be usefully introduced before functor categories, for example? And can this be done with sufficient generality to carry over essentially unchanged to the enriched case? I imagine this would reduce to just avoiding conical colimits. Vaughan Pratt (*) But not as in "free beer on Stallman." [For admin and other information see: http://www.mta.ca/~cat-dist/ ]

3 2

Proofs from THE BOOK
by Ellis D. Cooper 30 Jun '09

30 Jun '09

Dedicated to the memory of Paul Erdos, Martin Aigner and Gunter M. Ziegler's book (with the Subject title) offers examples of proofs with "brilliant ideas, clever insights and wonderful observations." They include chapters on Number Theory, Geometry, Analysis, Combinatorics, and Graph Theory. My question is, what would likely be included if there were a chapter on Category Theory? Ellis D. Cooper [For admin and other information see: http://www.mta.ca/~cat-dist/ ]

3 2

query
by jim stasheff 27 Jun '09

27 Jun '09

Mac Lane coherence can be deduced from the simple connectivity of the associahedron Is it written that way anywhere? jim [For admin and other information see: http://www.mta.ca/~cat-dist/ ]

3 2

no fundamental theorems please
by Paul Taylor 26 Jun '09

26 Jun '09

I see that Takuo and I have still not overcome the "royalist" forces. Claudio, Vaughan, Ross and others have mentioned various more "sophisticated" versions of the Yoneda Lemma. However, I contend that the more sophisticated the result is, the LESS it deserves to be called "the fundamental theorem of category theory". I particularly like Euclid's algorithm for the highest common factor as a historical and methodological example, Without meaning to dictate to number theorists how their subject should be organised, let me suggest for the sake of argument that it is a pretty good candidate for being called the "fundamental theorem of number theory". Gauss used the same idea to factorise polynomials, and no doubt number theorists have many more "sophisticated" developments of it. But the principal idea was Euclid's (or one of his colleagues), not Gauss's, and definitely not that of any subsequent number theorist! Saunders Mac Lane said something about "the right" generality, as opposed to the greatest generality. As I say, I like Euclid's algorithm because the idea has survived many many revolutions in the "official" foundations of mathematics. Theorems, like royalty, are rightly the victims of revolutions, because the way in which we encapsulate a piece of theory as a "theorem" depends as much on our current cultural prejudices as it does on the real underlying mathematics. For example, there is Cantor's "theorem" about a powerset being strictly bigger than a set. This belongs entirely to the dogma of set theory. When set theory is overturned, this miserable and wholely misguided "theorem" will go in the dustbin of mathematical history with it. But Euclid's algorithm will live forever. And the Yoneda Lemma will survive as long as Category Theory does in a recognisable form. But it still shouldn't be called the "fundamental theorem"! Paul [For admin and other information see: http://www.mta.ca/~cat-dist/ ]

9 8

Injective objects in topoi.
by Toby Kenney 26 Jun '09

26 Jun '09

Dear Category theorists, I'm sure the following lemma is either known, or I've made some mistake in proving it: Lemma: If I is an injective object in a topos, then for any monomorphism I>---m--->A, the object of splittings of m, i.e. S={f:I^A|(\forall i:I)(f(m(i))=i)} is also injective. Could someone let me know of a reference to it. Thanks a lot. Toby [For admin and other information see: http://www.mta.ca/~cat-dist/ ]

1 0

Equideductive categories and their logic
by Paul Taylor 26 Jun '09

26 Jun '09

"Equideductive categories and their logic" www.PaulTaylor.EU/ASD/extension Under the heading "Locally cartesian closed categories", on 8 October 2007, I asked whether anybody had investigated to what extent the true statement but an incorrect definition > Any topos is a CCC with an internal Heyting algebra, actually gives rise to interesting structure. However, I didn't get much response. I went on > Suppose that the category has all FINITE LIMITS (terminal object, > finite products and equalisers) and POWERS Sigma^X of an internal > DISTRIBUTIVE LATTICE (Sigma, top, bot, meet, join). Maybe there > is also a natural numbers object N and joins Sigma^N->Sigma with > the Frobenius law. (I would also like this to obey the monadic > and Phoa principles of ASD, but I'm not going to spell them out here.) > > Maps X->Sigma give rise to a "geometric logic" of "open" subspaces. > > Then the order relation between maps X->Sigma^Y leads to a richer > logic of "general" subspaces, with => and forall_Y. > > A logical formula of the more general form consists of geometric > sub-formulae joined together with => and forall, to which we might > add the other first order connectives as "syntactic sugar", defined > in the usual classical way. If a geometric sub-formula is immediately > enclosed in forall_K or exists_N, where K happens to be compact or > N overt, then this a priori more general quantifier may be considered > to be part of the geometric sub-formula. The draft paper advertised above investigates these ideas. This work was part of a re-formulation of Dana Scott's equilogical space construction about which you can find three sets of slides at www.PaulTaylor.EU/slides/ and the details will follow shortly. My lengthy posting on "Applications of the Yoneda embedding" on 20 June 2009 also provides background material for this. However, it has turned out to be very fruitful to leave the CCC aside and first consider the properties of a category that "lies nicely" within its cartesian closed extensions. The categories of sets, of sober topological spaces (in the textbook sense) and of affine varieties have the appropriate properties. However, because of the counterexample that I gave in "Aspects of locale theory" on 9 June 2009, the category of locales does not (products do not preserve epis). As I suggested in 2007, the key idea is to study equalisers targeted at exponentials. In terms of the Yoneda embedding, if we have a pair of maps from a representable presheaf to the exponential (Sigma^-) of another representable, is the equaliser representable too? We can reformulate this in the original category, without using presheaves, as a (kind of) PARTIAL PRODUCT. The categories of sets, topological spaces and affine varieties have these partial products. (I would like to thank Andrea Schalk, Mike Barr and possibly Robin Cockett for joining me in banging our heads against the brick wall of trying to find out whether locales have them too. Probably they don't, but I'm not sure whether it is this or something else that goes wrong.) An EQUIDEDUCTIVE CATEGORY is one that has finite limits, (my) partial products, an object Sigma that is injective wrt the monos that arise from partial products, and enough injectives. It turns out that those objects A that have exponentials Sigma^A are SOBER in my abstract sense, and the adjunction Sigma^- -| Sigma^- on this subcategory is monadic. In other words we have the characteristic properties of the subcategory of locally compact spaces within the category of sober topological spaces, without assuming any structure on Sigma such as being a lattice. EQUIDEDUCTIVE LOGIC captures this categorical structure in symbolic form. It is a predicate calculus whose object language is the sober lambda calculus. The chief feature is a quantified implication that justifies the (recursive) notation E = { x:A | All y:B. q(y) => fxy=gxy } for the equaliser E >--> A ====> Sigma^Y where Y = {b:B | q(y)}. Note that the predicates that are defined by this logic are general subobjects, not terms of type Sigma^A. Using quantification over terms of type Sigma^A, one can define an "existential quantifier". This is the most striking aspect of equideductive logic: although this is an old idea (maybe due to Russell) from higher order logic, it turns out to characterise the EPIs in the category, which have to be preserved by products. Of course, epis need not be surjective. For example N-->>X is epi amongst sober spaces, where X is the domain of ascending natural numbers, with T=oo. This means that one has to be EXTREMELY careful in using this quantifier -- it only has a restricted Frobenius law and doesn't allow substitution -- but I think that it will turn out to be very useful. For example, Scott continuity can be expressed in the form that, for phi:Sigma^N, "there exists" a finite set S such that phi n <=> n in S. What this means is that it is sufficient to test this case when proving equality of terms of type Sigma. We recover topology (in the style of ASD) by requiring SOME of these quantifiers to agree with structure on Sigma. That is, a space {x:A|p(x)} is compact or overt if the PREDICATE given by quantification of a term of type Sigma^A agreed with another term of type Sigma. On the other hand, and coming back to the question at the top of this posting, we recover set theory (ie an elementary topos) by requiring ALL quantifiers to agree with operators on Sigma. I trust that I will not hear any further repetition of the claim that ASD is restricted to locally compact spaces. This paper essentially replaces "Subspaces in ASD" and the monadic lambda calculus. It also fills in several gaps in other papers, such as allowing equational hypotheses and constructing the compact and overt subspaces that are described by modal operators. Paul Taylor [For admin and other information see: http://www.mta.ca/~cat-dist/ ]

1 0

Can you spot a flaw in this argument?
by Meredith Gregory 26 Jun '09

26 Jun '09

All, This is an argument about effective theories and so i would love to hear from the topos-theory crowd. i'll state the argument in lowly computational terms, using two distinct proposals for foundational models of computing: the lambda calculus and the π-calculus. Both the lambda calculus and the π-calculus suffer a dependence on a theory of names (aka variables). Both require two things of whatever theory of names is provided to them: - at least countably infinitely many names - an effective equality on names Now, to this recent proposals[1] add a third constraint, namely - names are atomic -- they have no internal structure To my way of thinking these three constraints are incompatible. i cannot see how to make an effective equality on a countably infinite set of entities that have no internal structure on which to rest the equality check. It seems to me that the only possible expression of the equality is an infinite table which states the results of comparing every single pair of atoms -- which is not going to fit into any realizable model of computation of which i'm aware and understand. Is there a way around this? If there is, i would be eternally grateful to be enlightened. The reason i focus on foundational proposals for theories of computation is that one could drop the atomic requirement and allow names to have internal structure, but because of the other two constraints one is dangerously close to sneaking into a supposedly foundational account a theory of names that is -- itself -- already sufficiently rich to model computation. (For example, in many implementations of lambda or π-calculus, names are ultimately represented as integers.) This would appear to undermine the foundational character of the model of computation in question. This has led me to constructions in which the internal structure of names *reflects* the structure of computations. In fact, this idea has a simple monadic characterization, but that's for another discussion. i've already posted to this list an intuitive account of red/black set theories that also side-step the issue of atoms with no structure which allows to recast the FM-Set-Theory-based accounts of names onto what appears to me to be the only construction that meets all the requirements mentioned above: sufficiently many names, effective equality, restricting internal structure of names to the structure of the proposal at hand. Again, if there is a way to skate around this argumentation or debunk it, please consider this a sincere call for help to do so. Best wishes, --greg [1] See the Gabbay-Pitts papers on using FM-Set Theory for an account of fresh names and alpha-equivalence. -- L.G. Meredith Managing Partner Biosimilarity LLC 1219 NW 83rd St Seattle, WA 98117 +1 206.650.3740 http://biosimilarity.blogspot.com [For admin and other information see: http://www.mta.ca/~cat-dist/ ]

2 1