[FOM] Godel's Theorems

[Harvey Friedman]

Reply to Bays, 10:15AM 5/1, Murphy 4:54PM  4/30/03.

For convenience, I reproduce the questions I raised previously.

***********

Let PA be the usual Peano Arithmetic. Consider the claim

*) there is a true sentence in the language of PA which is not provable in PA.

1. Conventional wisdom is that this is now a fully established
theorem of mathematics (or ordinary mathematics as currently
practiced by the overwhelming majority of mathematicians). Is there
agreement on this?

2. For those who do not agree, do they believe that *) is not a
mathematical statement capable of mathematical proof? E.g., this
could be on the grounds that they do not accept the usual
mathematical definition of "true sentence in the language of PA".

3. For those who believe that *) is a mathematical statement capable
of mathematical proof, but do not agree with 1. Do you see a flawed
step in the mathematical proof of *)? E.g., that it uses some
questionable inductions and/or definitions by recursion.

On a related but separate, matter,

4. Conventional wisdom is that the establishing of *) would be a very
major event in philosophy of mathematics and/or foundations of
mathematics. Do you agree with this?

5. For those who do not agree with 4, please elaborate.

**********

Bays:

>Harvey,
>
>FWIW, I take it that the answers to 1 and 4 are pretty obviously 
>"yes."  I would guess that anyone who says "no" does so for the 
>reasons hinted at in your 2---i.e., they don't like to equate the 
>intuitive notion "true" with any of the formal definitions 
>mathematicians use to specify this notion.
>
>Best -- Tim
>

I will take Godel's theorem to be about PA - a modern move, but PA is 
much better known than PM. Incidentally, perhaps some view PM as 
enough different from PA to make a difference to the discussion??

Now here we have a very specific sentence in the language of PA. 
Admittedly, it is rather complicated as a sentence in the language of 
PA, because as a sentence in the language of PA, there are rather 
complicated primitive recursive functions involving the 
arithmetization of syntax that are involved.

It is clear that the general form of the statement in the language of 
PA is what is called Pi-0-1 form. I.e., some universal quantifiers 
followed by a formula with bounded quantifiers only.

It would appear to me that the notion of truth for sentences of that 
form is unproblematic. Furthermore, since the sentence is a specific 
sentence that can and has been written out in full, with the help of 
abbreviations, no truth definition per se is required to show that it 
is true. One simply has to observe that the primitives involved are 
standard mathematical notions of the most primitive kind. And then 
one can show that this sentence is true by simply outright proving it 
by commonly accepted mathematical methods.

However, let me bring up a new claim.

**) there is a true sentence in the language of PA whose truth value 
we do not know.

I claim that this is trivially true, and not quite what I want to 
ask. For either Goldbach's conjecture is true or not(Goldbach's 
conjecture) is true. It is clear that we don't know the truth value 
of either. QED

This is more interesting:

***) there is a true sentence in the language of PA whose truth value 
will never be known.

This is also trivially true, and again not quite what I want to ask. 
For let A be any sentence in the language of PA of length 
2^2^2^2^2^2^2^2^1000. Then either A is true or not(A) is true. We 
will never know the truth value of A since we will never be able to 
even read A.

An objection can be made to this argument. Consider a sentence of the form

(0 = S0 and A)

in the language of PA, where A is as above. We can read only the 
first six symbols (just past "and") and already know that this 
sentence is false.

DIGRESSION. So this suggests an interesting problem. Suppose we have 
an enormous sentence A in the language of PA, and we are allowed to 
make queries about A as a finite string. Can we determine the truth 
value of A? Here is a result.

If the queries have an apriori bound on the number of quantifiers, 
then there is a sentence A which cannot be proved or refuted even 
from the answers to all such queries. END OF DIGRESSION.

Now we come to another formulation.

****) there is a true sentence in the language of PA of reasonable 
length whose truth value will never be known.

One way to argue this is to claim that there is a deterministic 
algorithm for the complete evolution of human thought that is of 
reasonable program size (and take "known" to refer to human thought).

Another approach is to find a reasonable length sentence A in the 
language of PA such that there is a compelling form of symmetry 
between A and not(A), and we can argue that any way of knowing A 
would also be a way of knowing not(A), and vice versa. But that is 
far far beyond anything we can do now.

Murphy:

>I'd be inclined to reconstruct the argument in the [Floyd,Putnam] 
>paper (at least in its
>"for dummies" version) as follows.

>Godel gets a formal result in Russel's
>symbolism (PM) which he would like to translate into English as "P is not
>provable in Russel's system."

What if Godel is to claim that he has shown, in English, that

##the consistency of PA is not provable in PA##?

Would Floyd and Putnam have any objections to this claim, or put 
forward that Wittgenstein would have an objection to this claim?

This seems to me to be a more interesting claim in English than the 
claim everybody is talking about here. Why not study this claim?

>I guess English here is to be regarded as
>seperate system, and moreover the system in which we "do" the philosophy of
>mathematics in.  In fact I wonder if it would be fair to say that English is
>standing in here for "Natural Language" or "Ordinary Language" as LW tends
>to use these terms (especially the latter term.  See below)?


>The paper's
>authors (and LW) allow Godel the formal result,  but do not accept  the
>proposed English translation of the formal result.

Again,would they give up the English translation of the second 
incompleteness theorem for PA?

>Their claim is that,
>when speaking English, we would be prepared to give up "P is not provable in
>Russel's system." as the translation of the formal result under certain
>circumstances.  For this reason, Godel is unjustified in giving that
>sentence as the English counterpart of the formal result.  Presumably it is
>in English that any metaphysical claims (philosophy of math claims) must be
>couched, so rejecting the sentence as an English translation means that
>Godel is unjustified in making metaphysical claims based upon it.  I say
>"presumably" English is the system into which philosophy of math claims must
>be cast because otherwise you could demonstrate the philosophical
>significance of Godel's theorem by simply giving the proof itself.  But
>Godel wants to say something "broader" than the proof itself.

Isn't this "broader" already served by my

*) there is a true sentence in the language of PA which is not provable in PA.?

And what about

#the consistency of PA is not provable in PA#

together with

##PA is consistent##.?

Also,

###"PA is consistent" is true###

where "PA is consistent" is formalized in the language of PA?

>
>Put this way, the "notorious remark" looks like a variant of LW's contention
>that technical philosophical languages are "de-linked " from Ordinary
>Language, to the detriment of technical philosophy.  This seems to be the
>point behind Hempel's statement, quoted in the paper, that all formal
>languages are "explained in" ordinary language, and that formal language
>should/ought to bear a "hereditary" relationship to Natural Language.  In
>the absence of such a relationship the move from the formal result to some
>Natural Language counterpart is a leap across the abyss, as it were, and
need not be accepted.

But why isn't the link between Ordinary Language and formal languages 
and systems such as the language of PA and the system PA, already 
solid enough to justify such "leaps"?