I was randomly walking down Dalal Street — no pun intended — when a mishmash of Gödelian ideas coalesced into the question, why isn’t BSE listed on BSE? Can the corporation that operates the Bombay Stock Exchange (and earns transaction fees) itself be listed on the platform that is the Bombay Stock Exchange?
A similar (though somewhat weaker) question is, can a mutual fund run by Blackrock invest in Blackrock the asset management company?
Take a look at this picture — Drawing Hands by M. C. Escher.
Now consider the Epimenides paradox: ‘This sentence is false.’ Is the statement true or false?
Such self-referential paradoxes plagued mathematics in the early 1900s, most famously as Russell’s paradox. Then came along Kurt Gödel, who in 1931 published a dense paper that left all of mathematics stunned. It showed that there must be true statements in number theory (or any axiomatic system) that cannot be proven to be true. In other words, there are ‘gaps’: unreachable truths.
The finer nuances of Gödel’s proof are far too convoluted, but a big picture view of his method — as in Nagel and Newman’s 90-page book — is accessible to anyone who is so inclined.
From Russell to Richard
Suppose that, in a given city, there is a barber who shaves all those who don’t shave themselves. Now, does the barber shave himself?
This is an incarnation of Russell’s paradox: suppose normal sets are sets that do not contain themselves as members (e.g., the set of books is not a book itself) and abnormal sets are those that do (e.g., the set of all things is itself a member of the set). Now, is the set of all normal sets normal or abnormal?
Another way of posing such a paradox was formulated by Jules Richard. Suppose one creates a numbered list defining various types of numbers, such as:
Irrational numbers are those that cannot be written as a fraction of two integers
Odd numbers are those that when divided by two, leave remainder one
Prime numbers are those that are divisible only by one and the number itself
and so on. Notice how the number 1 is not irrational, the number 2 is not odd, and the number 3 is prime.
Now, by this categorisation, let us call 1 and 2 type-A numbers, and 3 a type-B number. Let us append this definition to our original list:
Irrational numbers are those that cannot be written as a fraction of two integers
Odd numbers are those that when divided by two, leave remainder one
Prime numbers are those that are divisible only by one and the number itself
Type-A numbers are those where the numeral corresponding to the definition, when viewed as a number, does not have the property described by the definition
Notice that linguistically, a distinction must be made between numbers and numerals. The Richard paradox asks, is the number 4 type-A or type-B?
Think back to the BSE question I posed at the beginning. Notice the distinction between the levels of corporation and platform. A similar distinction must be made between numeral and number.
In fact, abstracting away the minutiae, there is in each of these problems a hierarchy of levels of reasoning. The gist of every single one of these paradoxes is that there are statements ‘in’ the system and ‘about’ the system — and that paradoxes arise when meta-sentences are spoken on the same level as ‘mere’ sentences.
Gödel’s Magic
What Gödel realised is that every statement in number theory can be written in a formal language of mathematical symbols. For example, the statement ‘there is no natural number whose successor is 0’ can be written as:
~∃x: Sx = 0
or equivalently as
∀x: ~Sx = 0
Moreover, every symbol in this formal language can be assigned a unique number. For instance,
~ corresponds to 1
∃ corresponds to 2
x corresponds to 3
: corresponds to 4
S corresponds to 5
= corresponds to 6
0 corresponds to 7
and so on.
Since every theorem can be written as a string of symbols, and each symbol assigned a number, every theorem can be given a unique Gödel number.
To do this, raise every successive prime number to the exponent of the symbol and multiply them. For instance, the Gödel number of the theorem [~∃x: Sx = 0] is,
I know what you’re thinking. Isn’t this elaborate procedure merely an arbitrary way to name things, plucked out of thin air? It is — at least it seems so at first. But hold that thought.
The magic of Gödel’s system is that a theorem and a meta-theorem and a meta-meta-theorem all have a Gödel number: the hierarchy of levels is flattened! Statements ‘in’ the system and ‘about’ the system all have a Gödel number that can be cross-compared — without causing paradox.
One way to gain an intuition for this is, Gödel’s method creates a way to achieve paradoxical ends without paradoxical means.
As for the elephant in the room: the procedure of Gödel numbering that seems arbitrary at first is actually deliberately and carefully designed. It cleverly uses the fundamental theorem of arithmetic, which says that any number has a unique decomposition into prime factors.
This guarantees that every theorem has a unique Gödel number — and also ensures that, given a Gödel number, we can retrieve the theorem it represents.
As for the assignment of numbers to symbols, you could very well choose to let ~ correspond to 2, or any other number, instead of 1. The reason that doesn’t matter is, we’re usually not interested in calculating the actual Gödel number — they are astronomically huge, and of no real use. Take a look again at the Gödel number we wrote down: forget the entire multiplication, the last part alone (19^7) is equal to 893,871,739.
Funnily enough, the actual Gödel number is useless; what matters is the flattening of levels that it enables.