A blog post about infinity, categories, and a mathematical mystery.
Cantor showed that not all infinities are equal: the infinity of the natural numbers (ℵ₀) is genuinely smaller than the infinity of the real numbers (called c, the continuum). He then asked what seems like a natural follow-up: is there anything in between? His conjecture that the answer is no became known as the Continuum Hypothesis (CH).
He spent years trying to prove it. He failed. He had a breakdown. He died without knowing the answer. As it turned out, there was a good reason: Gödel (1940) and Cohen (1963) together showed that CH is neither provable nor disprovable from the standard axioms of mathematics. It is, in a precise sense, independent of everything we build mathematics on.
This is, philosophically speaking, quite alarming. But also liberating.
So Let's Assume It's False
If CH is false, there are cardinals strictly between aleph_0 and c (all of them infinite, of course). Set theorists have identified dozens of these that arise naturally in analysis and topology — measuring things like how many functions you need to dominate all others, or how many small sets it takes to cover the real line. These are called cardinal invariants of the continuum, or small cardinals, and their relationships to each other form a rich landscape, summarised in the beautiful Cichoń's Diagram.
This is where my friend Samuel Gomes da Silva comes in. Samuel is a set theorist at the Federal University of Bahia in Brazil, thinking hard about these cardinals and how to prove inequalities between them. I am a category theorist — my home territory is Dialectica categories, which I introduced in my PhD thesis in the late 1980s as a categorical version of Gödel's Dialectica interpretation. They turned out, somewhat surprisingly, to be models of Linear Logic — but that was not the original plan. Even more surprisingly, these categories had found an exciting connection to set theory through the insight of Andreas Blass, but no one had fully explained why.
Samuel and I started talking, and realised we were looking at the same mountain from opposite sides. Our paper — Dialectica Categories, Cardinalities of the Continuum, and Combinatorics of Ideals — is the attempt to build a path between those two viewpoints.
The Mystery We Were Trying to Solve
Here is the core puzzle, articulated beautifully by Blass himself:
"It is an empirical fact that proofs of inequalities between cardinal characteristics of the continuum usually proceed by representing the characteristics as norms of objects in PV and then exhibiting explicit morphisms between those objects."
Translation for non-specialists: there is a category (a mathematical structure of objects and arrows between them) — closely related to my Dialectica categories — such that almost every known proof of an inequality between small cardinals can be encoded as a morphism in that category. This is not a theorem anyone had proved. It was just... observed. An empirical fact. A pattern that kept showing up.
Blass pointed it out. Everyone nodded. Everyone just kept using the pattern without asking why it worked. Samuel and I found that strange: we felt that empirical facts deserve explanations.
The Key Idea (Gently)
The category in question — called PV, after de Paiva and Vojt́áš — has objects that are triples: a set of "problems," a set of "solutions," and a relation saying which solutions solve which problems. A morphism between two such objects is a way of translating problems and solutions between them, kind of preserving the solving relationship.
The norm of such an object — a cardinal number naturally associated to it — turns out to be: the minimum number of solutions needed to cover all problems. That is an "Abelard and Eloise cardinal," as we fondly called them in the paper, because their definitions always have the shape "for all... there exists..." — the classic back-and-forth of a logical argument, or a medieval philosophical debate.
The beautiful discovery is that most of the small cardinals that set theorists care about — b, d, add, cov, non, cof — can all be expressed as norms of natural objects in PV. And when one norm is smaller than another, there is (almost always) a morphism that witnesses this, in a constructive and categorical way.
In our paper, we showed this works beautifully for pre-orders and for ideals (a notion of "smallness" for collections of sets). For any reasonable notion of "bounded" in a pre-order, the associated cardinal invariants — how many bounded sets you need to cover everything, how large an unbounded family must be — all fall out as norms of Dialectica objects. The morphisms between them encode exactly the "witness-choosing" arguments that set theorists had been writing out by hand for decades.
What We Conjectured
We proposed four conjectural principles in the paper. The most important, roughly speaking, are:
1. Most natural cardinal invariants in set theory are "Abelard and Eloise" cardinals — they can be expressed as norms of objects in Dialectica.
2. Pre-orders are the archetypal case — understanding b(P) and d(P) for a pre-order P gives you the right intuition for all the others.
3. Any reasonable proof of an inequality between such cardinals, even one written without thinking about categories, secretly encodes a morphism — the morphism is hiding in the "witness-choosing" steps.
4. The deepest explanation will ultimately be categorical — there is something about the structure of Dialectica categories that makes them the natural home for this kind of mathematics.
We were honest in the paper: we hadn't fully answered our Main Question. We still haven't. But we had identified the right question to ask, which is, in mathematics, sometimes most of the work.
A Personal Note
I was not supposed to care about cardinal invariants. I was a categorical logician, interested in the internal structure of proofs, in models of computation, in the geometry of inference. The idea that the categories I built to model a fragment of logic would end up being the natural language for a corner of set theory about the size of infinity — that was not in my plan.
But that is what mathematics does. It finds its own connections across whatever disciplinary boundaries we have invented. Samuel and I came from different mathematical cultures, spoke different technical dialects, and cared about different problems. And yet the mathematics insisted that we were talking about the same thing.
That, perhaps, is the real moral of the Continuum Hypothesis: even a question we cannot answer has rich and surprising structure. Even undecidability is fertile ground. We might not know if there's something between ℵ₀ and c. But if there is, we're starting to understand what it looks like.
---------------------------------------------------------------------------------------
The paper discussed in this post is: Samuel G. da Silva and Valeria C. V. de Paiva, "Dialectical categories, cardinalities of the continuum and combinatorics of ideals," Logic Journal of the IGPL, Vol. 25, No. 4, 2017. Yes, there’s a typo in the name of the paper, it should be Dialectica, not Dialectical, this is what the errata is about—only this.
No comments:
Post a Comment