Re: Yet another inane amateur Godel question

On Jun 17, 5:35 pm, Edward Green <spamspamsp...@xxxxxxxxxxx> wrote:
On Jun 17, 5:42 pm, Arturo Magidin <magi...@xxxxxxxxxxxxxx> wrote:



On Jun 17, 4:22 pm, Edward Green <spamspamsp...@xxxxxxxxxxx> wrote:

From my partial understanding, the proof seems to contain in outline
the idea that any sufficiently strong formal system for generating
proofs allows formation of the sentence "this sentence is
undecidable", with the obvious result.  

No; the system produces a statement which is *purely about numbers*
and relations between the numbers. It is at the meta-language level
that one can *interpret* the statement as making an assertion about
provability; what the statement actually says is something along the
lines of "if you the number n you get by performing the following
operations, then there does not exist a number m such that P(n,m)
holds", where P(n,m) is a numerical relation between numbers that has
already been defined.

It just so happens that we have already established a way to represent
certain kind of sentences and sequence of sentences in the first order
theory of arithmetic via numbers; in that interpretation, it just so
happens that P(n,m) holds exactly when n is the number of a sentence,
and m is the number of a proof of that sentence. And if you take the
particular sentence in question and try to figure out ->its<- number,
it turns out that its number is precisely the number  n mentioned in
the formula to begin with. So it is only at that level of
"interpretation" that one can say that the sentence is making an
assertion about its own provability; the Goedel statement, on its
face, however, is making an objective statement about numbers and
properties of numbers.

Thank you for your instantaneous amplification!  Your gloss will no
doubt repay careful consideration.

(In other words, I'm floored by your generosity, but trying to
understand the result, which is still kind of boggling to me, though
on exactly the right level).

Well, let me try in real time, real hard...

The sentence number "n" is...

"if you <consider> the number n you get by performing
 the following operations, then there does not exist
 a number m such that P(n,m) holds"

The "sentence number" is just that, a number. It is a number of a
particular form, satisfying certain numerical properties related to
its prime factorization; for example, its prime factorization involves
primes in order, does not skip primes, and so on. These properties are
->purely numerical<-; however, they are meant to "codify" the
grammatical rules for formal sentences. Thus, there is a particular
number associated to the left parenthesis "(", and a particular number
associated to the right parenthesis ")", and one of the numerical
properties that the setence number must satisfy is that the number for
")" cannot appear as the exponent of a prime unless the number for "("
appears as the exponent of a previous prime. But even though these
rules were set out thinking about the "meaning" of the numbers, they
are purely numerical; there is absolutely nothing non-numerical about
saying "in the prime factorization of n, the exponent 27 cannot occur
as the exponent of the kth prime p_k unless there exists an r, r<k,
such that the exponent of the rth prime p_r is 17".

Now, you have a sentence that describes a certain operation, which is
what you quote. This sentence, being a sentence, can be represented by
a particular number; call that number N. If you actually go ahead and
compute N, it will happen that N=n, where n is the number that is
mentioned in the sentence. It's as if you had a word, and sequence of
instructions on how to modify that word one letter at a time; and then
when you are done performing the sequence of instructions for
modifying that word, what you end up with the sequence of
instructions.

Now consider there were an m such that P(n,m).  The "n" would be true
(i.e., proved).

Okay: very important: "true" and "provable" are *not* the same thing.
In particular, the Goedel statment is not about truth, but about
provability. "True" refers to interpretation in specific models; there
is a connection between provable and "true in every model", but the
two concepts are not identical.

However, our interpretation of n as a sentence (the
sentence n labels) says there is no such m, so that is a
contradiction.

Right; if there is an m such that P(n,m), then that means that there
is a formal proof in the systeat m that ends with "there does not
exist m such that P(n,m)". If this is the case, then the system is
inonsistent, since we have an m such that P(n,m), and we have a proof
that implies that not(P(n,m)). So the system would be inconsistent.

 OTOH, suppose there were an m that corresponds to a
proof that "n" is false.  Then there in fact exists an m which proves
n is true,

Actually, an m', some other number. If there exists a number m such
that P(not(n),m) (where "not(n)" is an arithmetical operation
performed on a number, which in the metalanguage just happens to
correspond to negation), then we have a proof that ends with "there
exists M such that P(n,M)". Therefore, we have an m such that P(not
(n),m), and we have an M such that P(n,M), and so the system is
inconsistent again, since we can prove both a statement and its
negation.


which is again a contradiction.  So there exists no m
either for "n" or its negation (or else there exist both, so that the
structure is inconsistent), which is a statement about numbers, but
our meta-interpretation makes that a statement about proofs.

Right. The key is that the Goedel statement is just a statement about
numbers and numerical relations between them. It's a convoluted
statement, no doubt about it, but it still remains merely a statement
about numbers.

Almost there... it kind of fades in and out of focus.

One's first reaction is that
there should be a way to rule out such things as valid sentences:
after all, if one is out to prove things about the integers, say, such
a self referential "theorem" has nothing to say about the integers, so
who cares that it is in fact undecidable?

See above; you are not actually making a statement about theorems, you
are "really" making a statement about integers.

And the point is to show that there *are* statements that are formally
undecidable; not that there are "interesting" or "relevant" statements
that are undecidable.

I do like the distinction in Mostowksi's book, which I mentioned in a
following post, that we are not showing that there exist _essentially_
undecidable problems, merely that undecidable problems occur in
certain formal systems.  If I have that right.

I have no idea what "essentially undecidable" problems might be. In
any case, you might want to reflect on the fact that Goedel's paper is
entitled "On *formally undecidable* propositions of Principia
Mathematica and Related Systems I" [emphasis added]. Goedel is talking
about the concept of "formally undecidable", which is a specific,
technical concept, not a philosophical one. "Essentially undecidable"
sounds more like philosophy, in which case I might be tempted to
direct you to the great, late and lamented, Torkel Franzen's book on
not abusing Goedel.

--
Arturo Magidin



Thanks again.  I know I am not going to understand this in a moment.

.