Problems, Problems Everywhere
There’s a particular kind of mathematical paper that begins with a modest goal and ends up quietly connecting half a century of ideas across logic, category theory, and the philosophy of mathematics. Today I want to talk about one of those papers.
In Kolmogorov–Veloso Problems and Dialectica Categories, Samuel and I set out to understand something that sounds deceptively simple: what is a problem?
Now, if you’re a working mathematician, you might be tempted to answer: “a problem is something I can’t solve yet.” Fair enough. But historically, people have taken this question much more seriously—and much more abstractly.
Kolmogorov, for instance, thought of problems as primitive mathematical objects. Not sets, not functions, not proofs—but problems. Meanwhile, Veloso developed a notion of problems that behave beautifully… provided you are willing to assume the Axiom of Choice. And Blass came along and reframed problems as games of questions and answers, connecting them to computation and complexity.
So naturally, we thought: what could possibly tie all of these together?
Enter Dialectica categories.
If you’ve ever met a Dialectica construction, you’ll know it has a certain personality. It takes something familiar—a category—and turns it into something slightly uncanny: objects become pairs of “witnesses” and “counter-witnesses,” morphisms become strategies, and suddenly everything starts to look like a dialogue. Or a duel.
Or, as it turns out, a problem.
One of the small delights of this paper is realizing that Kolmogorov had already intuited something like this decades earlier. His abstract notion of a problem—so far removed from computation or complexity—fits remarkably well into the Dialectica perspective. It’s as if he had glimpsed the categorical structure before the language was available.
Veloso’s problems, on the other hand, are a bit more demanding. They work beautifully—but only if you’re willing to pay the price of the Axiom of Choice. This gives the whole story a slightly mischievous twist: some problems exist only if you believe in certain kinds of choice, while others are perfectly happy in a more constructive world.
And then there’s Blass, who brings everything down to earth with his questions-and-answers framework. Suddenly, problems are not just abstract entities—they are interactive processes. You ask, I answer; I challenge, you respond. It’s mathematics as conversation, or perhaps as negotiation.
What the categorical perspective does—quietly, but powerfully—is show that these are not competing views. They are different facets of the same underlying structure. A version of the Dialectica construction acts as a kind of translator, moving between Kolmogorov’s abstractions, Veloso’s set-theoretic universe, and Blass’s interactive games.
Along the way, something else becomes clear: the Axiom of Choice is not just a technical convenience. It shapes the very nature of the problems we are allowed to talk about. With full choice, Veloso’s world opens up. With weaker forms—countable or dependent choice—we get more nuanced landscapes. And without choice, we are back in a more constructive, and perhaps more disciplined, universe.
So, what is a problem?
After all this, we still don’t have a single answer—and that’s probably a good thing. Instead, we have a small constellation of answers, connected by categorical structure:
- a problem as an abstract mathematical entity (Kolmogorov),
- a problem as a set-theoretic construction (Veloso),
- a problem as an interactive process (Blass),
- and a problem as a kind of a Dialectica object, living somewhere in between.
If there’s a moral to the story, it might be this: sometimes the best way to understand a concept is not to define it once and for all, but to see how it transforms as you move between different worlds.
And if those worlds happen to be connected by category theory—well, that’s just a bonus.
---------------------------------------------------------------------------------
de Paiva, Valeria, and Samuel G. da Silva. "Kolmogorov-Veloso problems and Dialectica categories." arXiv preprint arXiv:2107.07854 (2021).
No comments:
Post a Comment