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

In light of these points and recent findings, I can no longer
confidently argue that Goedel's unprovable statement is meaningless. I
forfeit the argument, and I therefore apologize for the aggressive tone
in which I defended my position.

I may return to post a second draft of my analysis of Goedel's
Incompleteness Theorem. It is still unclear to me how Goedel's
unprovable statement can mean anything about numbers, since the act of
substitution occurs an infinite number of times.

Ryan Reich wrote:
mikeh106@xxxxxxxxxxx wrote:

<snip increasingly repetitive argument>

Let me see if I can summarize your argument relative to my last post.
You said:

* Because sentences and their Goedel numbers are in bijection, and
since the logical operations can all be defined arithmetically, all
logical notions are equivalent to the associated arithmetic notions
applied to Goedel numbers.

* The formula for a substitution (via the "sub" function) is to be
distinguished from the result of the substitution.

* If as usual we write

g = ~(E x) (Pf(x, y sub y))

and g_g = g sub g, then you claim that the Goedel number of g_g is
different than the value of g sub g, which appears as an expression
with in g_g.

Your claim about Goedel's proof is then that: all the sentences in
question are, in fact, simply Goedel numbers, and since arithmetic is
the same as logic we can talk about free variables within Goedel
numbers (which are to be identified from their prime factorizations).
In forming g_g we substitute the Goedel number g, which has a free
variable, into itself, resulting in a Goedel number g_g with a free
variable.

You then claim that this Goedel number, considered as a sentence, is
meaningless. Well, you're right. It is meaningless, and as you claim,
it does contain a free variable, when we make the appropriate
correspondence of Goedel numbers and sentences. However, it's also not
what Goedel wrote, and here's why. Arithmetic is not an elementary
object, but is defined by formal logic according to the various axioms
of arithmetic. It is, in other words, a concrete reflection of a
formal logical system. It is the formal logic, written with symbols
and not Goedel numbers, that defines the properties of arithmetic and
which proves statements about them. Goedel's proof constructs a
sentence of formal logic which has the effect of declaring its own
unprovability, which it accomplishes by discussing a certain number.
This numbers, which happens to be its own Goedel number, has no formal
meaning; it is simply an integer. It does not have free variables in
the formal sense, and a statement containing it is a sentence without
free variables in that same formal sense, which is all that matters to
logic.

The arithmetic side of the proof is based on the Goedel numbering
scheme. I'd like to note for clarity here that this scheme is purely
metamathematical: we as humans know how to compute Goedel numbers, but
the actual transformation between sentences and numbers is never
performed in the proof. We simply encode the effects. Within this
scheme, we can perform manipulations on the prime factorizations of
integers which, were we to replace these integers with formal sentences
via the Goedel numbering, would correspond to manipulations of formal
logic. Using this analogy, we get two functions in particular:

* The Pf function, which says of numbers what "provability" says of
sentences;

* The sub function, which does to numbers what substitution of a
constant into a formula with one free variable does to sentences.

Note that at this point these procedures are all mental exercises:
numbers have no logical significance in and of themselves, even if they
can be made to behave like they do.

The crucial step in the proof connects statements of formal logic with
these arithmetic operations using a *metamathematical* construction.
First we form the formal sentence which I will denote G(y) (not g,
since that letter is overused now, and to emphasize that G depends on a
free variable):

G(y) = ~(E x) (Pf(x, y sub y)).

This, I repeat, is a formal sentence, written just like that and not
"standing in" for its own Goedel number. The Pf and sub functions in
it are also formal expressions of the arithmetic operations mentioned
in the last paragraph. And yes, it has a free variable. Now, we as
people, outside the formal system, can compute the Goedel number of
G(y), which I'll continue calling g like you did. This is an integer;
it has no formal meaning. Since it's a constant, we can make a formal
replacement in G(y):

G(g) = ~(E x) (Pf(x, g sub g))

which is now a formal sentence with all occurrences of y that were in
G(y) replaced by this number g. It, too, has a Goedel number, which we
compute in our metamathematical language, which I'll call g_g like we
have been. If there were some proof P of G(g), with Goedel number p,
then these two numbers would satisfy Pf(p, g_g). However, if we
interpret G(g) into a statement of arithmetic, it directs us to search
for an integer x such that Pf(x, g sub g) holds. Observe that since
the arithmetical operation "sub" was designed to do the same thing to
Goedel numbers that syntactic replacement does to sentences, the value
of the expression "g sub g" is just g_g; that is, now that we are
interpreting G(g) within arithmetic, the formal expression "g sub g"
*is* interchangeable with the numerical value of the function it
denotes, which is g_g. Therefore G(g) asks for x such that Pf(x, g_g)
holds, and if P exists as claimed, then its Goedel number p is such an
x. Thus, G(g) asserts its own unprovability.

I write this out in full, again, to illustrate what is and what is not
a Goedel number, and what is done within the formal system, what within
arithmetic, and what as a purely metamathematical construction. In
particular, I wanted to present responses to your three points:

1. Formal logic is identical to its arithmetic analogue via Goedel
numbers.

Response: It is identical in form, but in function the difference is
that formal logic defines meaning, while arithmetic does not. Formal
logic is the designated mechanism for establishing mathematical truths,
and even if there exist arithmetic operations that mirror the logical
ones, these are not operations on logical statements, but merely on
numbers.

2. The formula for a substitution versus the result of the
substitution.

Response: I performed three different kinds of substitution in this
proof. One was to replace y by g within G(y); this was what I called
"syntactic" before. It eliminates the free variable y and replaces it
with an integer. The second was to write the expression "g sub g"
within G(g); this is what you are calling "the formula for a
substitution". You are correct; within G(g), this expression may not
be reduced. However, there was the third substitution: when G(g) was
interpreted as a statement of arithmetic, "g sub g" *was* allowed to be
reduced, because as a statement of arithmetic, it was simply a function
of g, hence equal to its value. To deny that it could be reduced would
be the same as denying that if f(x) = x + 1, then f(1) could be
replaced by 2. As numbers, these two are equal, and it is within the
system of numbers that G(g) was interpreted.

3. The Goedel number of G(g) is not equal to the value of g sub g.

Response: The "sub" function is defined to have the following effect.
First, let n denote the Goedel numbering function, which as I've said
is a metamathematical construction but it is good to have a compact
notation. Then for any formal sentence S(y) with one free variable and
any constant (that is, integer) m, then "sub" satisfies

n( S(m) ) = n(S) sub m

where on the left, S(m) means replacing y with m everywhere, and on the
right, "sub" is the arithmetic function. In particular, let's take
S(y) = G(y) and m = n(G) = g, which is how I defined g above. Then
this equation reads

n( G(g) ) = n(G) sub g = g sub g.

Now, this presentation is obviously different than what you'd been
proposing. However, your proposal was based on what I think is a
misunderstanding of the principles of formal logic and also of the
proof you read elsewhere. Before you object and give me a
point-by-point deconstruction telling me how this is different from
what you were saying, do my proposal the same courtesy I did yours and
figure out how you still disagree with it (if you still do).

--
Ryan Reich
ryan.reich@xxxxxxxxx

.

Relevant Pages