You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.
This question could easily be dismissed as naïve, but I hope it will spark some discussion. To make matters worse, the very nature of the question prevents me from specifying exactly what kind of answer I’m looking for.
So, here’s the thing. Lately, for various reasons, I’ve been thinking a lot about how to formulate problems that draw on the language of category theory yet require a problem-solver’s mindset rather than a theory-builder’s.
Such problems are hard to come by—not for lack of trying. With some effort, one can construct Frankenstein-esque problems, like determining the cardinality of a hom set using a combinatorial trick or analyzing the analytic properties of the formal power series , where is the number of finite categories (i.e., categories with a finite set of arrows) on a set with elements. This is fine; perhaps the only problem being that questions like these tend to be either standard or monstrously difficult counting problems, with no middle ground.
More importantly however, they are not problems in category theory per se, but rather combinatorial problems with a categorical veneer—much like how finding the cardinality of is ultimately a combinatorial problem, even if the question is stated in the language of linear algebra. What I am looking for are problems that do not draw from the body of techniques usually associated with "concrete mathematics", and yet are approachable by the novice, while at the same time not being the kind of grunt work we leave to students (a certain diagram commutes; a certain functor is indeed such; routine check that something is a natural transformation, a monoid object, the colimit of a diagram). I suspect here enters a cultural bias: we are inclined to call "exercises" rote, unenlightening verification that add nothing to the understanding of the matter but are, indeed, very boring ways to occupy time, that is always limited and instead we prefer to use isjusting the audience with another insightful idea.
All these things considered, I’m not convinced that this difficulty is purely an intrinsic mathematical obstruction. Instead, I suspect it stems, at least in part, from said cultural bias. I can offer various explanations for this, the most obvious being that category theory, especially in its early stages, reshapes the way one thinks about mathematical objects rather than encouraging direct symbolic manipulation. Whoever enters category theory feels disconnected for a very long time after starting: it is unclear what constitutes a proof; it is unclear how to argument because mechanical but lenghty verifications are dismissed as obvious -mistaking simplicity with velocity); all these things make it very hard to "solve a problem", because the problem we face is reshape our language -in a way that cavalier manipulations of infinite sums don't require. So the fundamental question remains: are these problems inherently rare, or have we simply not looked hard enough?
I’m sure everyone here is familiar with the International Mathematical Olympiad and the book Concrete Mathematics. There seems to be an inherent tension—an almost irreconcilable duality—between these two mathematical aesthetics. On one side, we have the style of mathematics that an IMO contestant practices and develops a taste for; on the other, the structural approach that we, as category theorists, pursue. The two seem largely incompatible and impenetrable to each other. While some areas of structural mathematics intersect meaningfully with the core knowledge of an IMOist, examples of problems that genuinely require both a solid grounding in category theory—addressing a categorical question—and also demand the problem-solving skills honed through IMO training appear to be exceedingly rare.
What we do see, however, is a strong movement in one direction: brilliant IMOists who later become brilliant mathematicians, some of whom eventually adopt the structural perspective. The common explanation for this asymmetry is that category theory requires a certain level of mathematical maturity, so those who learn it have already transcended the distinction between problem-solver and theory-builder. But is that really the whole story? What about books like Conceptual Mathematics and other pedagogical experiments that attempt to introduce categorical thinking earlier—at the same point in time when kids showing an interest for mathematics are exposed to IMOs?
In his book Kan Extensions, Dubuc interpreted Freyd’s famous epigram—“everything in mathematics that can be categorized is trivial”—saying that category theory is about good ideas rather than complicated techniques. But isn’t that precisely what the best IMO problems also promote—good, concise, elegant ideas over brute-force wheel-turning?
There's a difference between a problem-solver's mindset, and something suitable for IMO. You can being doing 'problem solving' mathematics that requires a PhD
Some of my work, for instance, is about finding certain examples, looking for solutions to certain equations, but it also requires a lot of background that is certainly not IMO-level.
Some of John Baez's work feels a bit like what you envisage. Is proving the isomorphism of species in his most recent paper a theory-building thing, or a problem-solving thing?
Well, yes, certain problems in graph theory or certain diophantine equations require a PhD to be tackled; is category theory inherently tied to PhD level mathematics? Isn't instead that we have used it with profit primarily for advanced stuff, and thus we believe it can only be presented to mature mathematicians?
I have seen many examples corroborating the latter idea, but I can't find a definitive answer. We are back at the "conceptual mathematics" example: is it wishful thinking to teach category theory to a young person? (related, but offtopic: is it possible to teach it to a non-mathematician?)
alas, it's now late-late night in my timezone. I will come back tomorrow!
The question about IMO-ish problems in category theory is very intriguing to me, but it seems substantially orthogonal to the question of teaching category theory to a young person or to a non-mathematician. The vast majority of young people learn a little bit of math without ever doing anything much at all like IMO-style problem solving, even at a far lower level.
I should have worded it better, but it was 2am. I would argue the two things are related, but I also think it doesn't matter for the discussion here.
There is certainly some intersection between my question and the need/desire to teach category theory to non-mathematicians. And I should take my question as an opportunity to have a deeper look into @David Spivak Category theory for the sciences -which I have only looked at superficially. But anyway, probably off topic as well
fosco, you wrote::
I’m sure everyone here is familiar with the International Mathematical Olympiad and the book Concrete Mathematics. There seems to be an inherent tension—an almost irreconcilable duality—between these two mathematical aesthetics.
Did you mean to link Lawvere and Schanuel's Conceptual Mathematics here? As I recall, Graham-Knuth-Patashnik's Concrete Mathematics is very much written in the problem-solving tradition!
Interesting question anyway. Let me share my view. I regard the usual process for introducing advanced mathematical topics into competition problems as follows:
A researcher in a specific mathematical area M realizes that a general result from their field applies to existing competition problems or slight modifications of them. For instance, Berlekamp observed that linear algebra over F2 makes very quick work of certain competition-style problems about extremal set systems.
The researcher identifies a problem that standard competition techniques struggle to solve, but which M handles efficiently. This creates a new source of challenging (but still solvable by the old tricks, only more difficulty) problem instances. Such instances are always in demand. For example, Berlekamp's insight leads to Oddtown/Eventown.
Problems related to M proliferate in competitions. Coaches start teaching the basics of M to students, adding another tool to their problem-solving toolkit. In our running example, a topic that was once considered university level, finite-field linear algebra, becomes standard and expected knowledge among top competitors. Of course, high school competitions nominally have to stick to problems that could be stated and solved using the "average" global high school curriculum, even if realistically one would always use advanced techniques (see e.g. any additive combinatorics or any recent functional equations problem from the IMO archives), so there will never be an IMO problem stated directly in terms of, say, group actions, even though all competitors will know Burnside's lemma or Polya counting and recognize problems which are best solved using it.
I find this 3-step framework helpful when I speculate about why category theory has failed to produce competition-style problems.
One possibility is that no category theorists engages with competition-style problems, stalling the process in step 1. I don't find this especially likely: as you point out, there are people who start out in competition math and become category theorists.
Alternatively, category theory might not provide especially useful tools for competition problems, either because it lacks such methods (so the process stalls at step 1) or because other specialized techniques solve the same problems more efficiently (so the process stalls at step 2). Given the generality of category theory, the latter seems especially likely to me. Category-theoretic ideas can solve IMO Shortlist 2005 C5, but group actions are a better, easier, more specialized tool that also does the job, and that competitors will know anyway. Similarly, I'm sure there are some olympiad-style problems that could be tackled by groupoid cardinality, but I doubt there are any where groupoid cardinality is the best available tool. In exchange, groupoid cardinality is more general than whatever the actual best tool is.
Another issue could be that problems involving category theory do not translate well into the standard problem-solving format, breaking the process at step 3. I find this very plausible. As somebody who likes to do problem-solving work in a very theory-building field (proof theory and wider logic), I can come up with problems about, say, the topology of subsets of that are approximately IMO-level in difficulty, and are best solved using, say, Heyting algebras. Or visibility problems in the style of the art gallery problem, where o-minimal theory can be used to obtain a polynomial counting the number of different guard arrangements. One can almost phrase these in high school terms, but not quite. It's tantalizingly close, but not actually possible. And even if I succeeded, they'd be too distinct from existing competition-style problems to be picked up.
Finally, there might be an incentive issue as well. If a category theorist were to write an article proposing and solving problems at roughly IMO level, some would (rightly or wrongly) suggest that they work on something more ambitious. This is not to say that IMO problems are easy (hell no), but applying the field to elementary problems will probably seem unremarkable to specialists, even if the problems themselves are difficult.
Thank you, this is an interesting answer with ideas for further discussion.
Zoltan A. Kocsis (Z.A.K.) said:
fosco, you wrote::
I’m sure everyone here is familiar with the International Mathematical Olympiad and the book Concrete Mathematics. There seems to be an inherent tension—an almost irreconcilable duality—between these two mathematical aesthetics.
Did you mean to link Lawvere and Schanuel's Conceptual Mathematics here? As I recall, Graham-Knuth-Patashnik's Concrete Mathematics is very much written in the problem-solving tradition!
Heh, no, the two are IMO-style and Graham-Knuth-Patashnik on one side, and conceptual mathematics / structural thinking on the other.
Oh, I see. It all makes sense now. I read your sentence as implying tension between IMO and Concrete Mathematics, and could not imagine where the tension would be coming from.
Zoltan A. Kocsis (Z.A.K.) said:
One possibility is that no category theorists engages with competition-style problems, stalling the process in step 1. I don't find this especially likely: as you point out, there are people who start out in competition math and become category theorists.
I suppose one way to frame my restlessness about this question is this: yes, we see many examples of movement in this direction. But do people ever walk the opposite path? Are there people who, after mastering mathematics that is elementary in the sense of Grothendieck—where problems are deceptively simple to solve yet carry deep structural insights (like the Yoneda lemma)—later develop an interest and taste for mathematics that is elementary in the sense of Erdős—where problems are deceptively simple to state yet require deep ingenuity to solve?
Can these two mathematical sensibilities be reconciled? Can they coexist within a single mind, or are they destined to remain separate? In my (relatively short) career, the only theory I’ve encountered that seems to embody both perspectives is the theory of combinatorial species, and the only person I've seen walking the path into concrete mathematics is Joyal. Which is why he's one of my favourite mathematicians! :smile:
Zoltan A. Kocsis (Z.A.K.) said:
I can come up with problems about, say, the topology of subsets of that are approximately IMO-level in difficulty, and are best solved using, say, Heyting algebras.
Can you give an example? I'd be curious to see!
Another part of what I want to say is, one can state the Chinese Remainder Theorem as a way to address the solvability of a system of congruences, or as a theorem about an isomorphism between a quotient ring and a certain product of quotient rings. Either way, using CRT requires computation
Zoltan A. Kocsis (Z.A.K.) said:
And even if I succeeded, they'd be too distinct from existing competition-style problems to be picked up.
This is mostly a cultural problem (not that it makes it a smaller one). And I don't think it's true, we just lack the vocabulary (terms like "Oddtown/Eventown", "pigeonhole", "knights" and "fools", and other colorful terms) to make these problems "readable". I could easily come up with a question that considers a finite quantale , finite sets , and some concrete intuition for two -valued relations , and ask a gifted teenager to compute the element . This is a problem in category theory -yet, it can be "sold" to someone who doesn't know Freyd SAFT or the definition of a classifying topos of a geometric theory.
by which I mean, more or less, that some problems would look like a pink zebra among IMO tests mostly because we don't have the jargon to talk about category-theoretic constructions to non-experts. Totally understandable, we started talking about category theory to non-category theorists fifteen minutes ago.
(See why I believe that this problem is more than intersecting the task of teaching CT to non-mathematicians?)
I cannot engage in the philosophical discussion. The following is a list of facts in Category theory whose proof requires an Olympionic brain, as opposed to a theory builder brain, at least for every proof I could imagine of any of them. I may add more later if they come to mind. Also, I do not see how anything that Baez or Spivak have done could have anything to do with Olympionic-maths.
(*) A conservative right adjoint (between complete categories) is faithful.
(*) A sup preserving morphism of complete lattices has a right adjoint.
(*) A strong generator in an infinitary pretopos is dense.
(*) The category of algebras for a cocontinuous monad over Set is of presheaf type.
(*) If H is a pullback stable set of morphisms, the reflector to its orthogonal will preserve finite limits.
(*) (Paré) A cartesian closed category with finite limits and a subobject classifier has finite colimits.
(*)(Freyd) Every locally small category has a conservative functor to Set.
(*)(Freyd) Ho(Top) is not concrete.
(*) (Blass) there exists a nontrivial exact endofunctor of Set (that is, preserving finite limits and colimits) iff there exists a measurable cardinal.
(*) (Lovász) Lovász-Type theorems for locally finite categories of relational algebras.
(*) (Linton?) The Kleisli category is dense in the category of algebras.
(*) (Rosicky-Adamek) In a cocomplete category, the closure under finite colimits of a strong generator made of finitely presentable objects is dense.
(*) Presheaf topoi have a subobject classifier, and lex-reflective subcategories of preshaf topoi have it too.
(*)(Deligne) A coherent locale has enough points.
(*) A compact locale has at least a point.
(*) (Barr) Every topos admits a geometric surjection from a localic topos.
(*) (Henry) The inclusion induces an equivalence between the corresponding Scott topoi.
Given Ivan's examples, it seems like the problem is bigger than us not having nice words for the basic objects of category theory, it's that those basic objects aren't familiar or inuitively available to students. Counting and shapes that everyone learns about from an early age form a solid foundation for the number theory, combinatorics and Euclidean geometry that form the backbone of IMO problems. There is no such access point to finite limits or adjoints.
Possibly related to this: category theory has adopted all sorts of terminology and constructions from group theory and order theory, and the integration is almost seamless (up to a few conventions).
But for whatever reason, we seem to have almost no connection with graph theory, which I personally feel it's just as related.
One possible reason is that, while the structures we look at in category theory and graph theory are rather similar (diagrams!), the problems that we find interesting tend to differ. (Ever wondered whether a composite path in a diagram can cross all the objects exactly once?)
Another possible reason, related to the first one, is that the communities are different and very much disjoint. Category theorists tend to come from algebra, graph theorists from analysis and combinatorics. (And personally, as someone that works between category theory and probability, I find this very unfortunate.)
How the "causal arrow" goes here, is unclear to me: have the different communities focused on different problems just out of following their mindset, or have the types of problems in the subjects attracted different crowds?
Probably both, and as mathematics becomes more and more specialized and insular, both of these effects are in danger of becoming even more intense.
Morgan Rogers (he/him) said:
Given Ivan's examples, it seems like the problem is bigger than us not having nice words for the basic objects of category theory, it's that those basic objects aren't familiar or inuitively available to students.
I don't think that's quite it. Consider the Oddtown case study above. The notion of basis won't be intuitively accessible to most high school students who can perfectly well comprehend the Oddtown problem, which does not need to mention bases or independent sets at all.
To create successful Olympiad-style problems in category theory, the students don't need access to finite limits or adjoints. The students need access to elementary problems that are best solved using finite limits or adjoints.
But the structure of a category with finite limits has to emerge from the contents of a problem only involving elementary objects/concepts. While I can imagine some order theory/lattice theory emerging from a combinatorics problem, I can't so easily come up with a problem whose structure takes on the appearance of a category with finite limits from far away.
That could very well just be a failure of imagination on my part though.
Let me make two different meditations on the problem.
(A) There are somewhat two (both interesting) competing questions. (1) Can we present IMO-style problems in category theory, in the sense that these problems could be given to kids as the IMOs, or (2) Can we ask mathematical questions whose flavor, attitude, proof-style will be appealing to an IMO-ist? In my previous answer, I was focussing on (2) and as Morgan and Paolo have suggested, I would entail that there is no way we can answer positively to (1), but this problem is not typical of category theory and extends to almost every area of mathematics.
(B) Insisting on (A.2), and more generally on the tension between theory builder and problem solvers, I think that there are several types of problems on mathematics.
(*) Open handed questions: This is the case for Lawvere's introduction of hyperdoctrines, or algebraic theories. Can we find a different and more meaningful way to pack the information of a theory? In some sense, open handed questions are when life gives you lemons, and you invent lemonade.
(*) Brilliancies: This is the case of a theorem with a clear list of hypotheses, and a clear list of theses whose proof requires a clear leap. In some sense, all of the problems I listed fall in this class. Brilliancies are when life gives you lemons, and you make fucking tanks out of it. There is no intersection between Brilliances and open handed questions.
Now, the big problem is that most of category theory, mostly by attitude, falls in the open handed side of spectrum, and IMO-problems all fall on the brilliancy side. Notice, it is not true, as my list suggests, that brilliances do not appear in category theory, or that they do not play a very important role. Yet it is true that a lot of our work is on finding nice definitions and frameworks where the brilliancy is reduced to the smallest amount of lemmas possible.
fosco said:
by which I mean, more or less, that some problems would look like a pink zebra among IMO tests mostly because we don't have the jargon to talk about category-theoretic constructions to non-experts. Totally understandable, we started talking about category theory to non-category theorists fifteen minutes ago.
I 99% agree with what you wrote above, but I think the specific obstacle here is more complicated. In fact, this is precisely why I brought up the 3-stage pipeline model.
From where I stand, new ideas rarely seem to turn into high school competition problems unless sufficiently similar competition problems already exist. Completely new solution types spread into competition math only very gradually, and usually that also involves at least some of the new technology seeping into the high school curriculum first. Compelling framing stories for new problems do not suffice: one has to find existing problems, or very-similar-to-existing problems, which are amenable to solutions using categorial techniques.
Take probability. Framing stories are not hard to create there:
Julia wants to draw a circle and its inscribed square in her notebook. Her circle has a radius of 1cm. Unfortunately, Julia's blue pen runs out of ink after she draws only 5 cm of the outline. She finishes the rest of the circle with the red pen. Prove that, no matter how Julia drew her circle, she can still draw an inscribed square which has 4 blue vertices.
This problem has an intuitive, engaging setup. It can be understood without knowing any probabilistic concept. One could have posed similar questions in competitions in the 80s (or earlier, Markov already could talk about variants of this particular problem). But such a question would not have been well-received in 80s math competitions, because the required solution was unlike the problems circulating at the time. It took years for probability to seep into the high school curriculum at all. Eventually, when it did, and competitions started asking questions that had linearity-of-expectation solutions, the problems themselves at first still had to be amenable to standard finite combinatorics approaches too. It's different now that probability is part of the standard competition toolbox, but it took decades to get there.
Ivan Di Liberti said:
(A) There are somewhat two (both interesting) competing questions. (1) Can we present IMO-style problems in category theory, in the sense that these problems could be given to kids as the IMOs, or (2) Can we ask mathematical questions whose flavor, attitude, proof-style will be appealing to an IMO-ist? In my previous answer, I was focussing on (2) and as Morgan and Paolo have suggested, I would entail that there is no way we can answer positively to (1), but this problem is not typical of category theory and extends to almost every area of mathematics.
You're right that both questions were present, and that I am more interested in 2 than in 1.
Ivan Di Liberti said:
The following is a list of facts in Category theory whose proof requires an Olympionic brain, as opposed to a theory builder brain, at least for every proof I could imagine of any of them.
This is an interesting list; I think I see the point you're trying to make, and the empowerment of learning that "a category has a faithful and conservative functor into Set if and only it has a faithful one, and a conservative one".
In the sense of them being tricks up the sleeve of a problem-solver, these are good examples -probably what is missing is a "mythology" around them that makes them more widespread and delimits the boundary and the content of the toolbox we use everyday.
Sometimes (it's a conversation I tried to start long ago) I feel we category theorists are not used to think of ourselves as solvers of problems who at some point have to go beyond handwaving -sometimes because, again quoting Freyd, what we do is "trivially trivial" construct the only possible witness for the correct universal property. Hence it is difficult (or at least, I find it difficult) to tell a student what to do with a proof they are stuck on, because I have an handwavy argument I can't immediately make precise. Invariably, the process of filling all gaps, making it precise to a level that is not required for research, is very instructive for me. And from your list, I have to admit I wouldn't be able to prove some of those statements that I heard, but never needed to make part of my bloodstream. It's ok, I know other tricks, and when/if I need new ones, I will learn new ones; but this is what I mean by "mythology": problems of an elementary nature, like the ones in Concrete Mathematics (or for that matter, in Knuth's TAoCP), had a critical mass of users necessary to write texts like "101 ways of creative telescoping sum".
I think that the strands of category theory that roughly focus on “universality” and “compositionality”, respectively, have quite different flavours; the first one (which is also the one that the discussion has focussed on, mostly) seems quite removed from the IMO-style if anything because it tends to determine objects “up-to-equivalence” and equivalence rarely preserves “concrete” computational properties of the sort that IMO problems often reduce to --- perhaps one can “count” things in equivariant ways, e.g. the aforementioned groupoid cardinality, but the idea itself that this counts as “counting” seems to require a higher maturity.
On the other hand, I can see the “compositionality” side, which often focusses on particular presented higher-categorical structures, to be quite smoothly adaptable to IMO-style problems.
I am thinking for example of problems that introduce some string-diagrammatic equational theory and then ask to prove that a certain equation of diagrams does not hold, whose simplest solution is e.g. to find a “matrix representation” of the diagrams --- i.e. secretly a functor to for some field --- that satisfies the equations, such that the representations of the two given diagrams are not equal.
It's quite easy to find such presentations whose diagrams of a given type have nice descriptions in plain language!
For example the endo-morphisms of either 0-cell of the “walking ambidextrous adjunction”, as a 2-category, are diagrams of (possibly concentric) black and white disks. If you make it the “walking 2-sided dual” as a monoidal category, the scalars are (possibly concentric) circles. You can add some equations phrased in terms of “interactions of circles”. Then ask questions about derivable and non-derivable equations where the first can be proven with some algebra and the second with some small matrix interpretations. I think these are ideas and methods that could be taught to clever high schoolers.
(Do they count as “truly” category theory as opposed to e.g. representation theory for 2-categories? That may lead us down a “no true scotsman” where no TRUE category theory could ever be part of an IMO-style problem...)
Paolo Perrone said:
Another possible reason, related to the first one, is that the communities are different and very much disjoint. Category theorists tend to come from algebra, graph theorists from analysis and combinatorics. (And personally, as someone that works between category theory and probability, I find this very unfortunate.)
Coming from physics/geometry as I do, it's different again :-) And I find it unfortunate, too, since I have colleagues who write papers that calculate tensors with properties on homogeneous spaces, using things like covariant derivatives. I'd like them to be able to appreciate what I do, without needing to wade through dozens of pages of category theory.