Probably people are going to jump on me for saying this, but it seems to me that category theory is different from much of mathematics in that often the difficulty is in the definitions rather than the theorems, and in the questions rather than the answers. Thus, there are probably many unsolved problems in category theory, but we don't know what they are yet, because figuring out what they are is the main aspect of them that is unsolved. (-: Mike On Tue, Jun 2, 2009 at 11:31 AM, Hasse Riemann <rafaelb77@hotmail.com> wrote:

Hello categorists

I don't know what to make of the silence to my question. This is the easiest question i have. I can't believe it is so difficult. It is not like i am asking you to solve the problems.

There must be some important open problems in ordinary category theory. There are plenty of them in the theory of algebras and in representation theory, so there should be more of them in category theory.

Especially if you broaden the boundaries a bit of what ordinary category theory is. Take for instance: model categories, categorical logic, categorical quantization, topos theory-locales-sheaves. But i had originally pure category theory in mind.

Best regards Rafael Borowiecki

[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

Finding the "right" questions and notions is certainly a prominent theme in category theory, perhaps more prominently than in other fields. Still, just like in other fields, solving open problems was always part of the agenda. For example, half a century ago people asked whether every "standard construction" (=monad) is induced by an adjunction, and it took a few years to have two interesting answers. And there is ceratinly a string of examples leading all the way to today. I don't know whether there are any >famous< unsolved problems in ordinary category theory, but there are certainly non-trivial questions. Here is one that we formulated in an article with Reinhard B"orger (Can. J. Math 42 (1990) 213-229) two decades ago: A category A is total (Street-Walters) if its Yoneda embedding A ---> Set^{A^{op}} has a left adjoint. Then 1. A has small colimits, and 2. any functor A-->B that preserves all existing colimits of A has a right adjoint. Do properties 1 and 2 imply totality for A? I must admit that, after formulating the question we never considered it again, so there may well be a known or quick answer. So don't hold back please, especially since I plan to incorporate several questions of this type in my CT09 talk. Walter. Quoting Michael Shulman <shulman@uchicago.edu>:

Probably people are going to jump on me for saying this, but it seems to me that category theory is different from much of mathematics in that often the difficulty is in the definitions rather than the theorems, and in the questions rather than the answers. Thus, there are probably many unsolved problems in category theory, but we don't know what they are yet, because figuring out what they are is the main aspect of them that is unsolved. (-:

Mike

[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

One of my favorite quotes: The question you raise ``how can such a formulation lead to computations'' doesn't bother me in the least! Throughout my whole life as a mathematician, the possibility of making explicit, elegant computations has always come out by itself, as a byproduct of a thorough conceptual understanding of what was going on. Thus I never bothered about whether what would come out would be suitable for this or that, but just tried to understand -- and it always turned out that understanding was all that mattered. A. Grothendieck Raoul Bott reinforced this in a talk I had the privilige to hear back in 98. He said that mathematics, done well, never required the placing of your oar in the water (he probably put it better than that...). The idea I think is that if you continually ask and answer the questions that occur to you, and, thus, gain understanding, then you will inevitably make progress. And that is what matters, really. So often the person credited with solving a 'famous' problem only takes the final step in a hard journey of a thousand miles made by a thousand others. Glory and fame - such as it is in the world of mathematics - are nice, but they are not, in the end, mathematics. I think it is of high importance to avoid confusing them. John Iskra Ronnie Brown wrote:

In reply to Hasse Riemann's question (see below):

I remember being asked this kind of question at a Topology conference in Baku in 1987. It is worth discussing the background to this, as someone who has never gone for a `famous problem', but found myself trying to develop some mathematics to express some basic intuitions.

Saul Ulam remarked to me in 1964 at my first international conference (Syracuse, Sicily) that a young person may feel the most ambitious thing to do is to tackle a famous problem; but this may distract that person from developing the mathematics most appropriate to them. It was interesting that this remark came from someone as good as Ulam!

...

----- Original Message ----- From: "Hasse Riemann" <rafaelb77@hotmail.com> To: "Category mailing list" <categories@mta.ca> Sent: Tuesday, June 02, 2009 5:31 PM Subject: categories: Famous unsolved problems in ordinary category theory

Hello categorists

I don't know what to make of the silence to my question. This is the easiest question i have. I can't believe it is so difficult. It is not like i am asking you to solve the problems.

There must be some important open problems in ordinary category theory. There are plenty of them in the theory of algebras and in representation theory, so there should be more of them in category theory.

Especially if you broaden the boundaries a bit of what ordinary category theory is. Take for instance: model categories, categorical logic, categorical quantization, topos theory-locales-sheaves. But i had originally pure category theory in mind.

Best regards Rafael Borowiecki

[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

--------------------------------------------------------------------------------

No virus found in this incoming message. Checked by AVG - www.avg.com Version: 8.5.339 / Virus Database: 270.12.51/2151 - Release Date: 06/02/09 17:53:00

[For admin and other information see: http://www.mta.ca/~cat-dist/ ] .

[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

Rafael Borowiecki, under the alias Hasse Riemann, asked,

Are there any famous unsolved problems in category theory?

Ronnie Brown's posting in response to this is a classic, and deserves to be printed out and pinned up in every graduate student's office! I particularly like the military analogy with the choice between a frontal assault and making the obstacle obsolete. The following point is especially important:

I was early seduced (see my first two papers) by the idea of looking for questions satisfying 3 criteria: 1) no-one had previously asked it; 2) the question was technically easy to answer; 3) the answer was important. **** Usually it has been 2) which failed! ****

I sent (a version of) the following reply to "categories" when Rafael first asked the question, but then asked Bob to withdraw it as I thought I could write it better. I put off doing so because other topics were under discussion, but by his posting Ronnie has obliged me to send it, since otherwise I would just be a chicken. So here goes: Do I hear taunts of "do you have a Fields Medal?"? These are a bit like those of "do you have a girlfriend?". Well, no, I admit it. I don't. I have a boyfriend (Richard), and some of you have met him. If you bear with me, you will see that this is not a completely frivolous answer, even though it is a personal one. My point is that there are analogies between being a gay man and being a conceptual--constructive mathematician: - They both involve long periods of self-doubt and pretence in the face of real and perceived discrimation. This is very much still real in the mathematical case, as evidenced by that fact that categorists and consructivists are largely to be found in computer science departments, excluded from mathematics in case they might corrupt the youth. - The result of this is a significantly delayed adolescence -- I have met gay men going through adolescence in the 50s or 70s. - Finally, there is pride in being who you are, and the recognition of "Honi soit qui mal y pense" -- that it is the people who think ill of it that have the problem. In the words of a song from "La Cage aux Folles" that is known as the "sweet potato song", "I yam what I yam!". Before I came out as a categorist, I pretended to be interested in difficult puzzles, I was in the British team in the International Mathematical Olympiad in 1979, but didn't do very well. I started a magazine called QARCH, whose total output in 30 years amounts to less than one of my papers now. I was taught as an undergraduate by the Hungarian analyst and graph theorist Bela Bollobas. He set problems for first year students problems that took three weeks to solve, if at all. (Bela is a mathematician of considerable stature -- so great that it took me five years to notice that he is 10cm shorter than me -- and I remember him with great affection, in case he gets to read this.) However, I hope that Bela (along with Andrej Bauer, Imre Leader and Dorette Pronk, who help organise IMO things in Slovenia, Britain and Canada nowadays), will forgive me if I say that there is something fundamentally unsatisfying about IMO problems. Once you have the solution, that is it. They are like crosswords or jigsaws or sudoku. After that I had my delayed adolescence (with an unsuitable boyfriend). I studied continuous posets instead of algebraic ones and categories instead of posets, just to show that I could. Somebody should have told me to get a proper job as a programmer, but they didn't have the guts to say it to me. (If graduate students ask me for advice nowadays, I do tell them to get proper jobs, and not surprisingly they (mis)interpret this personally.) Long after this, the first paper on Abstract Stone Duality was published on my 40th birthday, more or less. According to G H Hardy's depressing "Mathematician's Apology", and to the rules for getting a Fields Medal, I was officially finished as a mathematician. But it is pretty clear that I have been doing my best mathematics during my fifth decade. On the other hand, all of those gratuitously difficult problems had gone into the mix. Before I return to the question. please refer to number 6 in en.wikipedia.org/wiki/Hilbert's_problems which asks for the axiomatisation of physics. Even in this most famous collection of gratuitously difficult problems, we find a conceptual question. The first of Hilbert's problems is called the "continuum hypothesis", but is about smashing the continuum into dust. Elsewhere, he said "no-one shall expell us from Cantor's Paradise", but I regard it as a dystopia. I dream of some eventual escape, returning to the Euclidean paradise. There we would actually talk about lines, circles, compact subsets or whatever, instead of families of subsets or arcane algebra (or, indeed, category theory). I am looking for a language for mathematics that would look like "set theory" (as mathematicians, not set theorists, perceive it) but would yields computable continua instead of dust. More categorically, I believe that there is some notion of category that is very similar to an elementary topos, but in which all morphisms are continuous (in particular Scott continuous with respect to an intrinsic order). I also believe that these ideas are applicable to other subjects. When I have made the appropriate tools, I hope to be able to understand algebraic geometry, which was a complete mystery to me as a student. I am in princple capable of doing this, BECAUSE I am a categorist, by following the analogy between frames and rings. One version of this problem that I still cannot solve is a question that Eugenio Moggi asked me in April 1993, although I forget the exact words. We wanted a class of monos (I said they should be the equalisers targetted at power of Sigma) that was closed under composition and application of the Sigma^2 functor (ie taking the exponential Sigma^(-) twice). Another is how to embed the category of locales in a CCC WITHOUT using illegitimate presheaves (Vickers and Townsend) or the axiom of collection (Heckmann). When I wrote the original version of this posting a couple of weeks back, I thought I could solve this one. I am still hopeful, but it turns out to be a powerful question, cf Ronnie's (2) above. Notice that I give the principal formulation of the question in vague language, not as a Diophantine equation. The more specific the question, the more likely it is to have been the WRONG one. Asking an impertinent question is the best way of getting a pertinent answer. This still involves very difficult problems and hundreds of journal pages of formal proofs. But for me the problems serve the concepts rather than the other way round. This is the essence of what it is to be a conceptual mathematician. Ronnie Brown has told you a different story of his own, but with the same message. Many other experienced categorists (including the ones in higher dimensions, which Rafael excluded from his original question, for some reason) would do likewise. What about Fields Medals? People will get them, using my work, two or three generations down the line. Paul Taylor [For admin and other information see: http://www.mta.ca/~cat-dist/ ]

Dear Rafael, here is a list of problems from categorical logic that I find difficult to solve and don't know the answer yet. Certainly they are more on the logical side but categories are involved in all of them. I don't claim that these problems are generally important for category theory but they simply do bother me. I write this mail to show that there are technically hard problems and with the salient hope that someone may come up with an answer. Nevertheless I am aware that the subsequent list of problems might easly get a prize for the "best collection of most misleading problems". (1) In their booklet "Algebraic Set Theory" Joyal and Moerdijk defined for every strongly inaccessible cardinal \kappa a class of \kappa-small maps inside the effective topos. Does there exist a "generic" \kappa-small map such that all other maps can be obtained as pullbacks from this generic one? In their book the authors show the existence of a weakly generic one but this doesn't imply the existence of a generic one and I suspect there is none. (2) Does there exist a model for Martin-L\"of's Intensional Type Theory which validates Church's Thesis? This question is due to M.Maietti and G.Sambin. Notice that type theory validates the axiom of choice and, accordingly, the statement is much stronger than saying that for every function from N to N there exists a code for an algorithm computing this function. (3) In my habilitation thesis (www.mathematik.tu-darmstadt.de/~streicher/HabilStreicher.pdf) I showed that the sconing of the effective topos (i.e. glueing Gamma : Eff -> Set) gives rise to a model of INTENSIONAL Martin-Loef type theory faithfully reflecting most of the weakness compared to EXTENSIONAL type theory. Martin Hofmann and I showed that the groupoid model refutes the principle UIP saying that all elements of identity types are equal. This has recently generalised to \omega-groupoids by M.Warren and there is recently some activity of constructing models based on abstract homotopy. Can one construct a categorical model model serving both purposes? This is an issue since the groupoid model and related ones constructed more recently have the defect that all types over N are fairly extensional and thus don't do the job which sconing of the effective topos does. (4) Is the realizability model for the polymorphic lambda calculus parametric in the sense of Reynolds? It needn't be realizability over natural numbers. Would be interesting already for some pca! Thomas [For admin and other information see: http://www.mta.ca/~cat-dist/ ]

Hi Paul I still think you are getting me wrong, as did Ronnie. But never mind, i am used to it since i don't follow the mainstream science ways to specialize, solve problems, publish, repeat. Yet the problems interest will pass very soon. I now know 19 ordinary category problems (if you explain this one) vs. at least 23 in higher category theory. This explains why i restricted to ordinary categories.

...

From the good side i should be thankful that you and Ronnie trie to direct me towards "true mathematics",

but i have already found my "true mathematics". A big part of the process to get there was precisely to ask own quastions and finding the answers to them. But some people just got irritated when i asked them questions (in their field!) they didn't have the answer to.

Another is how to embed the category of locales in a CCC WITHOUT using illegitimate presheaves (Vickers and Townsend) or the axiom of collection (Heckmann).

I don't follow to the end here. Why should presheaves be illegitimate? Then, i suppose the axiom of collection is valid at least in the CCC. But what is so bad about the axiom of collection in this case? Do the embedding get bad? Best regards Rafael Borowiecki [For admin and other information see: http://www.mta.ca/~cat-dist/ ]

Dear All - Here a question related to categorical logic (or categorical proof theory) of a very different type. I would like to put it here because it is an illustration of another part of the field and also because it is technically difficult and interesting. It is well known that certain systems of propositional logic have a natural structure of free category for certain classes of categories with structure. For example, we have a structure of free Symmetric Monoidal Closed Category on the Intuitionistic Multiplicative Linear Logic. In this structure formulas are objects and equivalence classes of derivations of the sequents A -> B are morphisms. Free SMCC (in presence of "tensor unit" I) is not "fully coherent": there are non-commutative diagrams. For example, one has the Mac Lane's example A*** -> B*** (called "triple dual diagram"). In terms of IMLL there exist two non-equivalent derivations of ((A-oI)-oI)-o I -> ((A-oI)-oI)-o I w.r.t. the equivalence of free SMCC on the derivations of IMLL. One derivation is identity, another derivation is obtained in obvious way using the derivability of ((A-oI)-oI)-o I -> A-o I. Let us denote these derivations 1 and f respectively. (For the sequent ((A-oI)-oI)-o I -> ((A-oI)-oI)-o I every derivation is equivalent to 1 or to f.) The "triple dual conjecture" says that if we declare f\equiv 1 then all the derivations with the same final sequent in IMLL will become equivalent. I.e. the stronger categorical structure than SMCC (obtained by adding this new axiom for equivalence/ commutativity of diagrams) will be "fully coherent". If it is true we would have an interesting new variety of categories (subvariety of SMCCs) in the sense of Universal Algebra. Proof-theoretically, the study of this conjecture requires to study the equivalence relations on derivations of IMLL between the relation of free SMCC and the relation that identifies all derivations with the same final sequent. In my paper S. Soloviev. On the conditions of full coherence in closed categories. Journal of Pure and Applied Algebra, 69:301-329, 1990. it was shown that - if the "triple dual diagram" is commutative w.r.t. some equivalence relation ~ (containing the relation of free SMCC) - and the following additional condition holds: [a-oI/a] h ~ [a-oI/a] g => h~g for any two derivations of the same sequent, then all the derivations of the same sequent in IMLL become equivalent. The additional condition is a) difficult to verify b) has the form different form the equational form ("commutativity of a diagram") required from the point of view of Universal Algebra approach. All the attempts to prove "pure" triple dual conjecture (by myself and others) did not yet succeed. One may mention that it is known that some intermediate equivalence relations between the relation of free SMCC and the "total" relation of derivations do exist: L. Mehats, S. Soloviev. Coherence in SMCCs and equivalences on deriva- tions in IMLL with unit. Annals of Pure and Applied Logic, v.147, 3, p. 127-179, august 2007. but all known intermediate relations are contained in the relation generated by commutativity of triple dual diagram. My ph.d. student Antoine El Khoury has checked also that the commutativity of triple dual diagram (equivalence of 1 and f) implies equivalence of derivations of the balanced sequents with 1, 2 or 3 variables (commutativity of corresponding diagrams in SMCC). Remark. Obviosly, the commutativity of triple dual diagram implies A*** isomorphe to A*. Best regards to all Sergei Soloviev [For admin and other information see: http://www.mta.ca/~cat-dist/ ]

Dear Hasse, The presheaves that Townsend and I used are on the category Loc of locales. The fact that Loc is large may be seen as a problem, but another illegitimacy is the way a presheaf is a functor to Sets. This means, for instance, that for a representable presheaf y(X), where X is a locale, we take y(X)(W) = Loc(W,X) to be a _set_ for any pair of locales X and W, and that is foundationally tendentious. Whatever kind of collection Loc(W,X) is (if W is locally compact then we can take it to be another locale, but otherwise not), the ability to extract a "set of points" from it is sensitive to the foundations. We tried to be foundationally conservative in what we did with the presheaves, and you can see come remarks on this in the conclusions of our paper. (I should stress that we did not claim to have embedded Loc in a CCC, and we tried not to make use of any particular categorical properties of Presh(Loc).) Insofar as the representable presheaves y(X) can be acceptable, then so too are their exponentials y(Y)^y(X), since y(Y)^y(X)(W) = Loc(WxX,Y). What we showed is that then the exponential y($)^(y($)^y(X)) also exists (where $ = the Sierpinski locale), and in fact is representable of the form y(PP(X)) where PP(X) is the "double powerlocale" on X. Thus PP(X) has a claim to be thought of as $^($^X) even when X is not exponentiable (locally compact). PP is a foundationally robust construction, available in both topos-valid locale theory and predicative formal topology. Regards, Steve Vickers. Hasse Riemann wrote:

...

Another is how to embed the category of locales in a CCC WITHOUT using illegitimate presheaves (Vickers and Townsend) or the axiom of collection (Heckmann).

I don't follow to the end here. Why should presheaves be illegitimate?

[For admin and other information see: http://www.mta.ca/~cat-dist/ ]