I recently spent eight days in Finland, at the provocatively named Arctic Number Theory School, which even had some penguins in its poster. (Needless to say, the conference took place well South of the Arctic circle, and there are no penguins (fr:manchot, not pingouin) in the northern hemisphere. The organisers succeeded in provoking several participants into sending them written queries on this matter; this is Finnish humour at work.)
Many readers must already be aware (if only through Sibelius) of the Kalevala, an epic poem detailing the exploits of ancient Finno-Ugric mathematicians. A fair bit of it is centered on the Sampo, a device of great importance. Unfortunately, nobody seems to agree on what the Sampo was.
The nineteenth-century compiler and editor of the Kalevala, Elias Lönnrot, believed it to be a mill for producing gold, wheat and salt out of nothing. Others claim it was not a device as such, but rather a world-tree, similar to the Yggdrasil. Somebody at the conference claimed it was a steel-rich meteorite that fell on what is now Estonia; his argument (or that of whoever first put forward that theory) was in part a functional one – a Sampo was, first and foremost, something that made its owner wealthy and powerful. (See here for more theories; one of them states that the Sampo was a die for producing counterfeit Byzantine coins, and another one claims that ‘Sampo’ was a name for the precession of the equinox.)
A friend and I argued that the Sampo must clearly be a machine for proving all theorems, or, at the very least, for deciding which Diophantine equations have integral solutions. In the first case, the role of the witch Louhi would be played by Gödel; in the second case, she and her acolytes would be called Yuri Matiyasevich, Julia Robinson and so on. (A computer scientist would postulate that the Sampo decided in finite time whether a computer program halts on all inputs.)
In either case, the witch would be particularly wicked: not only would the Sampo be destroyed – it would be shown to be impossible to begin with. All the proofs I know of Gödel’s result (or of the undecidability of halting problem) rest on a paradox induced by self-reference.
This makes me wonder whether there is any connection between the Sampo and the machine built by Trurl the Inventor in Lem‘s Cyberiad. This machine, as some of you may recall, could produce anything starting with the letter N. Being asked to produce Nothingness, it started to destroy the universe. There is one point in common with Gödel here, namely, the machine’s unexpected readiness to address semantic notions rather than just concrete entities. (This is an important point that Gödel and Tarski had to deal with: see below.) There is also a tragic twist, caused by the fact that – as in mathematics and life – one can refer to what one cannot construct: as the machine could not construct such objects as it had destroyed if their names did not start with the letter N, such wondrous objects as worches and gruncheons were never heard of again.
(Perhaps they sounded more beautiful in the Spanish translation I dimly recall…)
Deep down, one of the main tools of the witch is the sentence
This sentence is false.
It cannot be said to be either true or false. One can (try to) defend the edifice of logic by raising two objections: first, a sentence that mentions truth or falseness is referring to a semantic concept, and thus is different from a statement in arithmetic or geometry; we could decide that sentences referring to semantic concepts may sometimes be excused from being either true or false. (In contrast, if a statement in any branch of mathematics were well-defined but neither true or false, the entire edifice would fall apart – for one thing, all proofs by contradiction would become invalid.) Second, many formalisations of mathematical language do not allow for self-reference in any straightforward fashion. (The statement P can be “not Q”, if Q has already been defined, but not “not P”, since P has not yet be defined. In other words, we can decree that mathematics be written in a variety of ancient Finnish that does not allow for the phrase “this sentence” — we are still fully able to do mathematics in this restricted dialect, but we remove the paradox.)
The second objection can be got around if we are a little clever. A sentence can refer to itself by referring to an object constructed following certain instructions (an object that happens to be the sentence itself). The classic example is
“preceded by itself in quotes, is false”, preceded by itself in quotes, is false.
The first objection is more substantial. The way to get around it would be to find a way to encode truth in arithmetic. (Thus we could construct an arithmetical statement – i.e., a statement about the integers – that is true if and only if “This sentence is false” is true; this would create an arithmetical statement that is neither true nor false, thereby, presumably, destroying Finland and the universe.) Fortunately, this is shown to be impossible in a very precise sense by Tarski’s undefinability theorem.
What we can do, however, is encode provability (from a given set of axioms) in arithmetic. After all, a proof is a sequence of steps that can be followed and verified purely mechanically, by turning a crank. (In terms more familiar to people younger than Gödel: a precisely written proof can be verified by a computer, which can only perform arithmetical operations on 0s and 1s.) Thus the witch managed to find a purely arithmetical formulation for
“preceded by itself in quotes, is not provable”, preceded by itself in quotes, is not provable.
If this sentence is true, it is not provable; if it were false, then – even worse – it would be a false but provable statement (and so whatever axioms we were using are no good). The arithmetical statement corresponding to the above is thus an arithmetical statement that is true but not provable (or else false but provable).
Moment of unabashed (and very timely, though just about) proselytism: let me fully endorse my brother’s twenty reasons here.