I Am a Strange Loop - Douglas R. Hofstadter [107]
But suppose that through a stunning stroke of genius you discovered a new kind of “Gödel ray” (i.e., some clever new Gödel numbering, including all of the standard Gödel machinery that makes prim numbers dance in perfect synchrony with provable strings) that allowed you to see through to a hidden second level of meaning belonging to Imp — a hidden meaning that proclaimed, to those lucky few who knew how to decipher it, “The integer i is not prim”, where i happened to be the Gödel number of Imp itself. Well, dear reader, I suspect it wouldn’t take you long to recognize this scenario. You would quickly realize that Imp, just like KG, asserts of itself via your new Gödel code, “Imp has no proof in PM.”
In that most delightful though most unlikely of scenarios, you could immediately conclude, without any further search through the world of whole numbers and their factors, or through the world of rigorous proofs, that Imp was both true and unprovable. In other words, you would conclude that the statement “There are infinitely many perfect numbers” is true, and you would also conclude that it has no proof using PM’s axioms and rules of inference, and last of all (twisting the knife of irony), you would conclude that Imp’s lack of proof in PM is a direct consequence of its truth.
You may think the scenario I’ve just painted is nonsensical, but it is exactly analogous to what Gödel did. It’s just that instead of starting with an a priori well-known and interesting statement about numbers and then fortuitously bumping into a very strange alternate meaning hidden inside it, Gödel carefully concocted a statement about numbers and revealed that, because of how he had designed it, it had a very strange alternate meaning. Other than that, though, the two scenarios are identical.
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?”,