rigorous logical derivations of new theorems from previous ones — could somehow be “mirrored” in an exact manner inside the world of numbers. An inner voice told him that this connection was not just a vague resemblance but could in all likelihood be turned into an absolutely precise correspondence.
More specifically, Godel envisioned a set of whole numbers that would organically grow out of each other via arithmetical calculations much as Fibonacci’s F numbers did, but that would also correspond in an exact oneto-one way with the set of theorems of PM. For instance, if you made theorem Z out of theorems X and Y by using typographical rule R5, and if you made the number z out of numbers x and y using computational rule r5, then everything would match up. That is to say, if x were the number corresponding to theorem X and y were the number corresponding to theorem ?, then z would “miraculously” turn out to be the number corresponding to theorem Z. There would be perfect synchrony; the two sides (typographical and numerical) would move together in lock-step. At first this vision of miraculous synchrony was just a little spark, but Godel quickly realized that his inchoate dream might be made so precise that it could be spelled out to others, so he started pursuing it in a dogged fashion.
Flipping between Formulas and Very Big Integers
In order to convert his intuitive hunch into a serious, precise, and respectable idea, Godel first had to figure out how any string of PM symbols (irrespective of whether it asserted a truth or a falsity, or even was just a random jumble of symbols haphazardly thrown together) could be systematically converted into a positive integer, and conversely, how such an integer could be “decoded” to give back the string from which it had come. This first stage of Godel’s dream, a systematic mapping by which every formula would receive a numerical “name”, came about as follows.
The basic alphabet of PM consisted of only about a dozen symbols (other symbols were introduced later but they were all defined in terms of the original few, so they were not conceptually necessary), and to each of these symbols Godel assigned a different small integer (these initial few choices were quite arbitrary — it really didn’t matter what number was associated with an isolated symbol).
For multi-symbol formulas (by the way, in this book the terms “string of symbols” — “string” for short — and “formula” are synonymous), the idea was to replace the symbols, one by one, moving left to right, by their code numbers, and then to combine all of those individual code numbers (by using them as exponents to which successive prime numbers are raised) into one unique big integer. Thus, once isolated symbols had been assigned numbers, the numbers assigned to strings of symbols were not arbitrary.
For instance, suppose that the (arbitrary) code number for the symbol “0” is 2, and the code number for the symbol “=” is 6. Then for the three symbols in the very simple formula “0=0”, the code numbers are 2, 6, 2, and these three numbers are used as exponents for the first three prime numbers (2, 3, and 5) as follows:
22 · 36 · 52 = 72900
So we see that 72900 is the single number that corresponds to the formula “0=0”. Of course this is a rather large integer for such a short formula, and you can easily imagine that the integer corresponding to a fifty-symbol formula is astronomical, since it involves putting the first fifty prime numbers to various powers and then multiplying all those big numbers together, to make a true colossus. But no matter — numbers are just numbers, no matter how big they are. (Luckily for Godel, there are infinitely many primes, since if there had been merely, say, one billion of them, then his method would only have let him encode formulas made of a billion symbols or fewer. Now that would be a crying shame!)
The decoding process works by finding the prime factorization of 72900 (which is unique), and reading off the exponents that the ascending primes are raised to, one by one — 2, 6, 2 in this case.
To summarize, then, in this non-obvious but simple manner, Godel had found a way to replace any given formula of PM by an equivalent number (which other people soon would dub its Godel number). He then extended this idea of “arithmetization” to cover arbitrary sequences of formulas, since proofs in PM are sequences of formulas, and he wanted to be able to deal with proofs, not just isolated formulas. Thus an arbitrarily long sequence of formulas could be converted into one large integer via essentially the same technique, using primes and exponents. You can imagine that we’re talking really big numbers here.
In short, Godel showed how any visual symbol-pattern whatsoever in the idiosyncratic notation of Principia Mathematica could be assigned a unique number, which could easily be decoded to give back the visual pattern (i.e., sequence of symbols) to which it corresponded. Conceiving of and polishing this precise two-way mapping, now universally called “Godel numbering”, constituted the first key step of Godel’s work.
Very Big Integers Moving in Lock-step with Formulas
The next key step was to make Fibonacci-like recursive definitions of special sets of integers — integers that would organically grow out of previously generated ones by addition or multiplication or more complex computations. One example would be the wff numbers, which are those integers that, via Godel’s code, represent “well-formed” or “meaningful” formulas of PM, as opposed to those that represent meaningless or ungrammatical strings. (A sample well-formed formula, or “wff ” for short, would be “0+0=sss0”. Though it asserts a falsity, it’s still a meaningful statement. On the other hand, “=)0(=” and “00==0+=” are not wffs. Like the arbitrary sequence of pseudo-words “zzip dubbiwubbi pizz”, they don’t assert anything.) Since, as it happens, longer wffs are built up in PM from shorter wffs by just a few simple and standard rules of typographical juxtaposition, their larger code numbers can likewise be built up from the smaller code numbers of shorter ones by just a few simple and standard rules of numerical calculation.
I’ve said the foregoing rather casually, but in fact this step was perhaps the deepest of Godel’s key insights — namely, that once strings of symbols had been “arithmetized” (given numerical counterparts), then any kind of rule-based typographical shunting-around of strings on paper could be perfectly paralleled by some kind of purely arithmetical calculation involving their numerical proxies — which were huge numbers, to be sure, but still just numbers. What to Russell and Whitehead looked like elaborate symbol-shunting looked like a lot of straightforward number- crunching to Kurt Godel (although of course he didn’t use that colorful modern term, since this was all taking place back in the prehistoric days when computers didn’t yet exist). These were simply two different views of what was going on — views that were 100 percent equivalent and interchangeable.
Glimmerings of How PM Can Twist Around and See Itself
Godel saw that the game of building up an infinite class of numbers, such as wff numbers, through recursion — that is, making new “members of the club” by combining older, established members via some number-crunching rule — is essentially the same idea as Fibonacci’s recursive game of building up the class of F numbers by taking sums of earlier members. Of course recursive processes can be far more complicated than just taking the sum of the latest two members of the club.
What a recursive definition does, albeit implicitly, is to divide the entire set of integers into members and non-members of the club — that is, those numbers that are reachable, sooner or later, via the recursive building-up process, and those that are never reachable, no matter how long one waits. Thus 34 is a member of the F club, whereas 35 is a non-member. How do we know 35 is not an F number? That’s very easy — the rule that makes new
