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