Penrose's argument in a nutshell

Hi there,

For those who have maybe never read his book
or read Godel's theorem, or who read it long
ago and maybe have forgotten the basic idea
behind it now, maybe a quick summary
may help with this thread, just enough so that
you can understand what it is about, or a
reminder for those who have seen it all before.
Idea is to convey the main gist of the argument so
will use no more than is needed for that.

Godel's theorem applies as soon as you have addition,
multiplication, and the normal way of deducing results
about numbers. That last is the rule that if you
have a result that you can prove for each individual
number, and can go on proving it endlessly for larger
and larger numbers, then it is true for all of them.

So if you have all that, the next step was to find
a way of coding results about numbers up as an
individual number. You would have a number
like 4548930254 or some such thing
(though normally much larger than that)
which if you understood the coding would
say e.g. that there is no largest
prime number, or whatever, any mathematical
result could be coded up as a number.

It is just an encoding of the symbols of the
formulae like the way
you can code up e.g. letters as numbers.
E.g. you could convert letters to numbers
and multiply by 100 for each new letter as
you move leftwards, and so convert something like "Hi there"
into 8 09 20 08 05 18 05 or as a single number,
8,092,008,051,805

For reasons of arithmetical convenience he uses a slightly
different coding from that one, but the idea is the same.

You also find a way of coding up proofs as
numbers in the same way, just code up
all the symbols of the proof into one
enormously large number.

This coding can be called your Godel encoding.

Now comes the first tricky bit.
You find a statement f(p,n) which if you
understood the coding says that the number p is
a number encoding a proof of the result
encoded by n.

By a statement there I just mean something like
e.g. p < n - except of course f(p,n) is a much
more complicated statement than that, but the details
needn't concern us, just that you can
construct such a statement.

So for instance if n was a godel encoding of the
statement that there are infinitely many primes
and p was an encoding of a proof of that result,
then your arithmetical formula f(p,n) would
be true. If p was a number that didn't encode
a proof then f(p,n) would be false.

Then Godel's idea is to construct a setence g which says
of itself that it can't be proved.
So g is the coding of the statement
that there is no p with f(p,g).

g there is going to be some particular
number. E.g. you would like to be able
to have a number say 578970 (but much larger)
which is the number for the statement:

"There is no number p which satisfies
f(p,578979)"

Well that isn't quite going to work as
it stands because it so happens that the
way the encoding work is that the code
for any sentence must be larger than
any of the numbers included in the
sentence, so g would have to
be larger than itself.

But Godel figured a way around that with his
clever substitution trick
which we needn't go into here
(makes your mind spin a bit to think about
it), and ones head is probably spinning
enough as it is - just to say it works.
We don't need to know how it works to understand
the basic idea.

So then anyway as a result of his clever
idea, you end up with a number
g which is a number for a statement
which if you understand the trick
is an encoding of the statement that

"there is no p with f(p,g)" (G)

Let's call that statement G (as I have
indicated after it in brackets).

(capitals for the statements, lower case
letters for their encodings)

So g is an encoding of the statement G

G itself is an encoding of the statement:
There is no proof P of G in this axiom system.

But if you forget about the encoding,
G is just an ordinary arithmetical postulate,
not a very interesting one perhaps, but
one that one could try to prove:

"there is no p with f(p,g)"

where f there is just a very complex arithmetical
formula, and g a fixed number.

It is just the same sort of statement as one like
"There is no integer whose square is 1000"
but much more complex than that of course.

So, one could think about trying to prove
G. What Godel asked was - can it have a proof
in this axiom system?

Could that ever happen?

This is just like asking, could there be a proof
that there is an integer whose square is 1000
- but the statement is much more complex of course.

He ended up showing that it can't but to do that
he first had to look into the consequences
that would follow if it did have a proof.

If there was such a proof, then that proof would
be a proof P of G, in the axiom system.

So, the proof could be encoded, so it would give
you a p which satisfies f(p,g)

But that can never happen because G itself says

"there is no p with f(p,g)" (G)

So therefore, we have looked into the consequences
of such a proof and found that it leads to a
contradiction so there can be no such proof.

(sorry if this argument makes your head spin
but it is the only way to show something to
be false in maths. Indeed in constructive
mathematics, you actually go so far as to define
falsity as meaning that there exists such a proof
of a contradiction).

So therefore by this argument we can
see that G can never be proved in this
axiom system. So we see that G is in
fact true, because G via our encoding
is an encoding of the statement that
it has no proof in this axiom system.

But, since it can never be proved,
it is also consistent to add in the
assumption that it is false as a new
axiom.

Humans, having an innate idea of truth,
can see that G, though not provable
from these axioms,is in fact true.

A computer program could be programmed
to add in such an axiom as this
endlessly often. But in some sense
it seems that no computer program can
be programmed to understand the
argument given here in the way that
a human can. I know that it is tough
going but all you need is your innate
idea of what is truth and plenty
of persistence and you can come to see it.
But a computer can't be programmed
to understand truth in this way.
Only to add in particular instances
of the axiom. You can program it to
understand one particular statement
of the result and to be able to
make new Godel sentences in an algorithmic
way - but you can always come up with
some other way of presenting the argument
that takes account of the programming
you did to let it understand more Godel
sentences, and once you do that,
you end up with a new Godel sentence
that it won't understand.

You can't do the same thing
with a human being. Therefore
humans understand truth
intrinsically in a way that
computers can't be programmed to do.

That is the idea in a nutshell though
there are endless elaborations of it.

Robert