any useful and consistent formal system for reasoning about arithmetic

must contain a fundamental flaw. This flaw was that you could always

construct the true statement G, which says "G cannot be proven". This

shows that there must be true but unprovable statements in the

system.

If you think about it, something seems a little fishy here. We

started by saying you have a system for reasoning about arithmetic.

That means you can say things about numbers, like "1+1=2" or "The

number 37 is prime." But the Godel-statement isn't about numbers;

it's a statement about statements, actually about itself. Was Godel

cheating here? How could he say that a system for statements about

numbers let him make statements about statements? In fact, earlier

mathematicians had known that the ability to make self-referential

statements could lead to all sorts of logical problems, and had

constructed elaborate "theories of types" to avoid these kinds of

issues, and enforce statements about numbers to be *just* about

numbers.

Godel's genius was to come up with a couple of key insights that

allowed him to get around this limitation, and show that a system for

talking about numbers could always be twisted to enable talking about

other things, including about statements. The first key insight was

to create a system of encoding, that would convert any mathematical

statement to a "Godel number". These days, this doesn't seem that

exciting-- after all, any formula you type in Microsoft Excel is just a

series of numerical ASCII codes in your computer's memory. But back

in the 1930's, everyone didn't have a computer on their desks, and

this was not nearly as obvious.

Godel's second key insight was that once all mathematical

statements are encoded as numbers, the concept of proving a statement

could itself be viewed as a numerical operation, kind of like a more

complicated form of addition or subtraction. The allowable

transformations on numbers would be described by logical rules of

inference. So, for example, in plain English we might say "No prime

numbers are even. The number 44 is even. Thus the number 44 is not

prime." In Godel's system, we would transform the statement "No prime

numbers are even" into one Godel number, and "The number 44 is even"

into another Godel number. Then we could perform operations on those

two numbers and would come up with the Godel number that corresponds

to "The number 44 is not prime".

Once we realize this, we can define a property called provability,

the property of a number being the Godel encoding of a true theorem.

Since we have defined proofs as numerical operations, we can see

provability as just another numerical property. Just like we can ask

whether a number is even, or whether a number is prime, we can ask

whether a number is provable. And now you can see how Godel manages

to pervert a system that talks about numbers to one that talks about

theorems: rather than exactly saying that a particular theorem is not

provable, he just needs to say that a particular number is not a

provable number.

Of course, there are some more details to Godel's proof, since

even with this ability to make statements about provable numbers, it

isn't direcly obvious how to make a statement that incorporates its

own number. To do this, Godel came up with a few more mathematical

tricks involving statements that could contain free input variables,

which might later take on the value of their own number. There are a

few too many details to explain in this short podcast format, but if

you are interested in learning more, I would encourage you to read

Douglas Hoftstadter's Pulitzer-prize-winning classic "Godel Escher

Bach: An Eternal Golden Braid", linked in the show notes.

And this has been your math mutation for today.

## No comments:

## Post a Comment