I Am a Strange Loop

The hypothetical Imp scenario and the genuine KG scenario are, as I’m sure you can tell, radically different from how mathematics has traditionally been done. They amount to upside-down reasoning — reasoning from a would-be theorem downwards, rather than from axioms upwards, and in particular, reasoning from a hidden meaning of the would-be theorem, rather than from its surface-level claim about numbers.

Göru and the Futile Quest for a Truth Machine

Do you remember Göru, the hypothetical machine that tells prim numbers from saucy (non-prim) numbers? Back in Chapter 10, I pointed out that if we had built such a Göru, or if someone had simply given us one, then we could determine the truth or falsity of any number-theoretical conjecture at all. To do so, we would merely translate conjecture C into a PM formula, calculate its Gödel number c (a straightforward task), and then ask Göru, “Is c prim or saucy?” If Göru came back with the answer “c is prim”, we’d proclaim, “Since c is prim, conjecture C is provable, hence it is true”, whereas if Göru came back with the answer “c is saucy”, then we’d proclaim, “Since c is saucy, conjecture C is not provable, hence it is false.” And since Göru would always (by stipulation) eventually give us one or the other of these answers, we could just sit back and let it solve whatever math puzzle we dreamt up, of whatever level of profundity.

It’s a great scenario for solving all problems with just one little gadget, but unfortunately we can now see that it is fatally flawed. Gödel revealed to us that there is a profound gulf between truth and provability in PM (indeed, in any formal axiomatic system like PM). That is, there are many true statements that are not provable, alas. So if a formula of PM fails to be a theorem, you can’t take that as a sure sign that it is false (although luckily, whenever a formula is a theorem, that’s a sure sign that it is true). So even if Göru works exactly as advertised, always giving us a correct ‘yes’ or ‘no’ answer to any question of the form “Is n prim?”, it won’t be able to answer all mathematical questions for us, after all.

Despite being less informative than we had hoped, Göru would still be a nice machine to own, but it turns out that even that is not in the cards. No reliable prim/saucy distinguisher can exist at all. (I won’t go into the details here, but they can be found in many texts of mathematical logic or computability.) All of a sudden, it seems as if dreams are coming crashing down all around us — and in a sense, this is what happened in the 1930’s, when the great gulf between the abstract concept of truth and mechanical ways to ascertain truth was first discovered, and the stunning size of this gulf started to dawn on people.

It was logician Alfred Tarski who put one of the last nails in the coffin of mathematicians’ dreams in this arena, when he showed that there is not even any way to express in PM notation the English statement “n is the Gödel number of a true formula of number theory”. What Tarski’s finding means is that although there is an infinite set of numbers that stand for true statements (using some particular Gödel numbering), and a complementary infinite set of numbers that stand for false statements, there is no way to express that distinction as a number-theoretical one. In other words, the set of all wff numbers is divided into two complementary parts by the true/false dichotomy, but the boundary line is so peculiar and elusive that it is not characterizable in any mathematical fashion at all.

All of this may seem terribly perverse, but if so, it is a wonderful kind of perversity, in that it reveals the profundity of humanity’s age-old goals in mathematics. Our collective quest for mathematical truth is shown to be a quest for something indescribably subtle and therefore, in a sense, sacred. I’m reminded again that the name “Gödel” contains the word “God” — and who knows what further mysteries are lurking in the two dots on top?

The Upside-down Perceptions of Evolved Creatures