Re: How can the meaning of Goedel's unprovable statement descend from infinity?

mikeh106@xxxxxxxxxxx wrote:

<snip long post; summary follows>

As I understand it, your argument is as follows: although Goedel did in
fact prove that there exist statements which can be neither proven nor
disporven, the statement he actually produced with this property is
completely uninteresting. The reason this is so is that rather than
being a complete logical sentence it contains "free variables", and
therefore does not express a property of numbers. You justify this by
considering the formula g_g, where g is the formula

g = ~(E x)(Pf(x, y_y))

so that when "expanded", g_g means

g_g = ~(E x)(Pf(x, g_g))

which requires further expansion to expunge the "free variable" g_g,
and so on, so that the statement does not arrive at a precise meaning
until it has been "expanded infinitely", at which point you claim the
resulting statement is "paradoxical".

I first of all disagree with you that the statement is meaningless, and
I think the reason your understanding is flawed is that you do not
quite understand the real necessity of the Goedel numbering system to
the proof. This may itself have something to do with the fact that you
are misusing the phrase "free variable": in logic, a variable is a
symbol, and a free variable is a symbol which is not quantified within
its scope. The sense you are using it seems to be that g_g is a "free
variable" in the above expression because it appears in its own literal
expansion, rather than being defined purely by basic logical entities.
This apparent self-reference is exactly the reason Goedel numbers are
necessary to make the proof work, and when they are used correctly, the
definition of g_g is not in fact self-referential: you don't need to
"substitute" g_g into itself to get an arithmetic statement.

Here's how I understand the proof. The end goal is to be able to write
a sentence which states "This sentence cannot be proven". The problem
is that in formal logic, if one wants to talk about a specific object
one needs to be able to define it; that is, produce a formula P(x) with
one free variable (this is "free variable" in the sense I explained it,
not the sense you are using it) which is satisfied only by the object
you desire to discuss. In order to apply a logical formula to another
logical formula, you need to interpret such formulae as objects of your
logical system. Once you do that, you still have to be able to state
in the language of formal logic what it means that a statement is
provable. That is, is there some kind of a relation like equality,
divisibility, etc., which determines whether a statement can be proven?
This relation has to be defined using only the axioms of your logical
system, in this case arithmetic.

The first part of the program is to make logical formulae into
something that arithmetic can discuss; namely, numbers. That's what
the Goedel numbering is: every formula is a number, so we can talk
about formulae by talking about their associated numbers. In fact, and
this is the key point, if you forget momentarily the fact that the
Goedel numbers correspond to logical statements, then any statements
you make about these numbers are simply expressions in number theory.
With an eye towards the proof, this means that when it comes time to
write a sentence about itself, we can get away with writing a sentence
about a number, and that number will just happen to be the Goedel
number of the sentence it's in. Another important fact about Goedel
numbers, which is where all the discussion of prime factorizations
comes in, is that the transformation that takes a formula and produces
its Goedel number is itself logically definable. If you like, you may
think of formulae as strings of numbers (replace each symbol by its
number), so that the Goedel-numbering function is just a function on
numbers written in, say, decimal notation. That is, it's an arithmetic
function. This means that the Goedel number construction used in the
proof is actually an arithmetic function, rather than an operation on
logical statements (although it has _implications_ for logic). Also,
in what follows I _will_ write all the occurrences of "Goedel number
of..." which you omitted, since it clarifies what's a number and what's
a formula. Thus, n(x) means "The Goedel number of x", which is an
arithmetically defined function.

Note that the "sub" operation x_y is subtle, and occurs in two
contexts: "numerical" context and "logical" context. Although 'x' and
'y' are _intended_ to be formulae, they _are_ simply variables. The
"sub" operation as applied to two numbers m and p performs the
arithmetic operation on them that would be performed on two Goedel
numbers n(x) and n(y), namely the operation which corresponds to the
formal substitution of n(y) into the free variables of a formula 'x'
and then taking the Goedel number of the result. The point here is
that the formal substitution of a number into a free variable of a
formula can itself be formalized as an arithmetic function. However,
in the eventual proof, "sub" is used not only in a formula but as an
operation on formulae: we produce g_g from g by substituting n(g) into
the free variable of g. In this case, 'g' is an honest logical formula
and our ability to do this operation is simply an axiom of logic that
says we can substsitute any constant expression into any free variable.

The second part of the program is to talk about provability of logical
statements as a property of their Goedel numbers. After various
contortions one arrives at the conclusion that the relationship Pf
between two numbers (in particular, the Goedel number of a proof and
the Goedel number of a formula) is in fact definable in arithmetic;
that is, there's a logical formula which for any string of formulae x
and any formula y, when you plug in n(x) and n(y) tells whether x is a
proof of y; the important fact is that Pf takes numbers as arguments,
not formulae. Therefore it's a logical object.

Now the sentence

g = ~(E x) ( Pf(x, y_y) ),

which has one free variable, can be written down. That's the hard
part. What we accomplish by doing this is to obtain a formula which,
if we insert any Goedel number into the free variable 'y', tells us (by
the truth or falsity of the resulting sentence) whether or not the
sentence of which 'y' is the Goedel number, has a proof. Now I repeat;
g is a _formula_ of logic, merely a string of symbols. It has a Goedel
number, and that's an integer. When we form g_g we replace y by g in
the above expression, which means first we compute its Goedel number,
then we substitute that number into g in all the places that y occurs
as a free variable (which are hiding inside the very complicated
arithmetic operation y_y), at the end of which we have no free
variables left, just a lot of symbols and numbers; this gives us g_g.
Now, g_g is also a sentence, since in arithmetic, all numbers are
logical objects. And as you noted, g_g states that it does not have a
proof, and also implies that it does not have a disproof.

_This is not circular_. There are no unresolved variables left in g_g;
the only free variable in g was 'y', and it got filled in with some
number when we made g_g. The fact that this number is actually the
Goedel number of g itself is not relevant if we are simply wondering
whether g_g is a sensible statement; it is, because it consists only of
logical symbols and numbers. It is the intricate web of relations that
tie together the Goedel-numbering scheme, the Pf function, and the
actual logical meaning of a sentence, which ends up leading to g_g
talking about its own unprovability.

That's as much as I can say on the subject. Goedel numbering is like
two people talking behind each others' backs: person A says "Person B
never lies" and person B says "Person A is an idiot", and the net
result is that Person A insults himself, without ever knowing that's
what he's doing. Actually, though, Goedel's proof is more airtight
than this, since in addition it has a way of talking about what it
means for a person to lie without actually having to talk about people.

Well, there is one more thing I can say. You are right in that the
sentence Goedel wrote is pretty useless, as well as almost impossible
to identify in practice. In later years people have identified actual
statements which are independent of a logical system (like the
continuum hypothesis).

--
Ryan Reich
ryan.reich@xxxxxxxxx

.

Relevant Pages