We Don't Talk About The Integers
We Don't Talk About The Integers
Gödel's search for incompleteness and the original Pandora Box
Long-time fans of true crime know that, whenever some deeply unsettling truth about somebody is unearthed, there will always be some neighbour commenting “Oh, but he was so kind, so polite.” No matter if the person in question has committed several gruesome murders, there is a very high chance that those who knew him on a daily basis will say that they would have never expected it.
Similar paradoxes are scattered throughout mathematics; objects that appear innocent and harmless to one mathematician, reveal themselves to be intricate jungles of unsolvable mysteries to another. Each working mathematician operates by wearing coloured glasses, isolating only certain shades of an object (one might argue that the key to success is being able to wear various coloured lenses at the same time, accessing the intertwined nuances of otherwise plain surfaces). What might seem like an unremarkable alley to someone, appears full of shadows and threats to someone else. While a topologist might be able to reduce some shape to another, easier to understand shape, a differential geometer might argue that the two shapes don’t look alike at all, for angles and lengths are awfully deformed by the transformation in question. Twisting and molding like play dough is perfectly acceptable for one mathematician, but might break down properties that other mathematicians care about.
While the community might disagree on which objects are easy, accessible, and which ones aren’t, there is a structure so common, polite and kind that nobody would expect it to pull any form of gruesome crime: the integers. After all, ‘God created the Integers,’ wrote once Kronecker.
Model theorists, much like the suspicious officer in a true crime story, are able to see beyond the cute face of this seemingly harmless mathematical structure. They know which sins they are guilty of, even when the rest of the world believes them to be saints, granting miracles to those who praise them.
The breaking point of the idilliac picture of the ring of integers and its simple orations is a procedure known as Gödelization. The representation was introduced — as the name suggests — by Kurt Gödel, in an effort to prove his famous ‘incompleteness’ theorems. He sought to argue that certain systems of axioms, as long as they were complex enough, would not be able to prove or disprove all possible statements; what was called being incomplete. Before his work, some believed that it was possible to isolate some axioms and then derive the whole of mathematics from them through formal operations and deductions; this was how, for example, theorems in Euclidean geometry were proved. To some mathematicians, notably Hilbert, it seemed reasonable that the whole of mathematics behaved like Euclidean geometry. They believed that through enough sweat and tears, the community would be able to come up with some basic axioms and then derive all known theorems of mathematics, and all future ones. Proofs would then be a matter of cleverly manipulating symbols and formal systems.
Gödel — and others — disagreed. In the 1930s, he proved that, as long as a formal system (that was ‘effective,’ i.e. could be listed by an algorithm) was able to perform the arithmetic of the natural numbers, then it would not be able to prove or disprove all possible statements about them. To do so, he created a translation procedure that transformed formal statements (like ‘2=2,’ or ‘n+1 = n+1 => n = n’) into (very big) natural numbers. Axioms and proof were encoded into integers and their properties; the provability of a statement, then, was an arithmetical fact about the so-called ‘Gödel number’ of that statement.
(Some examples of Gödel numbers of some statements are available here. For example, the statement ‘n+1 = m+1 => n = m’ that I wrote above is encoded as 2×14348907×48828125×232630513987207×4177248169415651×1792160394037×239072435685151324847153×322687697779×504036361936467383×29×25408476896404831×456487940826035155404146917×550329031716248441×10861771343660416614908294685907×1119130473102767).
Gödel would then proceed to construct a ‘Gödel sentence,’ a sentence expressing its own unprovability (through the arithmetic properties of its Gödel number), and thus achieve his goal. This impressive theorem, however, is not the reason why the integers prove to be a real nightmare for model theorists. The true trouble is the Gödelization itself.
This translation procedure allows us to encode entire formal systems inside arithmetic. Once the integers, with their whole ring structure (sum and multiplication), are available, we are able to encode — through very complicated and certainly very long arithmetical sentences — entire mathematical structures of almost arbitrary complexity. If the integers are definable, or interpretable, then our mathematical objects are so expressive than a model theoretic analysis is de facto impossible.
There is a fine line between ‘complex enough to be interesting’ and ‘too complex to be dealt with’. While model theorists have been striving to classify mathematical structures for ages, they have come up with notions of tameness and accessibility that directly relate to what sorts of patterns can be constructed. In a crescendo of possible complexities, linear orders, graphs, trees are omitted to remove — or at least push into a neat little box — chaos for long enough for theorems to be proved, formulae to be analyzed, definable sets to be understood.
All of this is impossible in the integers. They sport an impossible, almost supernatural level of expressitivity; one can certainly expect that any conceivable pattern can be encoded or reconstructed inside the ring of integers. Their arithmetic is far too intricate to be decoded through formal properties, making them whatever the opposite of a Holy Grail is for model theorists. They are a cancer that spreads fast, a toxic creature that poisons everything it touches, making it super tricky to tackle with the methods we have.
To many mathematicians, they are the simplest object we can think of; they are, after all, not too far from just putting one pebble after the other, recursively — counting like children count, with our hands. They provide the base to many of our grandiose castles of ideas and theories, the foundations to many explorations into unknown mathematical lands.
To model theorists, however, they reveal a different face. A twisted expression, a creepy smile. The source of all darkness, the original Pandora Box. We don’t talk about them, hoping that in our cautious adventures we will never find ourselves alone with the ring of integers in a dim-lit alley.