Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ncar!tank!staff_bob@gsbacd.uchicago.edu
From: staff_bob@gsbacd.uchicago.edu (bob kohout)
Newsgroups: comp.ai
Subject: Natural Paradox
Message-ID: <1706@tank.uchicago.edu>
Date: 2 Feb 89 17:52:02 GMT
Sender: news@tank.uchicago.edu
Organization: University of Chicago Graduate School of Business
Lines: 96

In article <3091@silver.bacs.indiana.edu>, chalmer@silver.bacs.indiana.edu (david chalmers) writes...
 
>In article <44071@linus.UUCP> bwk@mbunix.mitre (Barry Kort) writes:
>>Consider, if you will, the following pair of sentences:
>>
>>	"The following sentence is provable."
>>	"The preceding sentence is unprovable."
>>
>>The paradox seems to have vanished.  The first statement
>>can be both True and Unprovable.  The second sentence
>>can be both True and Provable.  (But please don't ask
>>me to supply the proof.  I didn't say they were provable
>>by *me*!)
>>
>>The point is twofold:  Not all True sentences are provable
>>and not all unprovable sentences are False.  Thus we need
>>a third category: Undecidable.
>>
>>We can then resolve the paradox by chastising both sentences
>>for overstating the case.  They could have gotten along
>>very nicely if they had scaled back their dogmatic assertions
>>along the lines of the second, more harmonious pair.
> 
>Sorry.  It's kind of obvious that if a sentence is provable, then
>it's PROVABLE that it's provable.  Because if a proof exists, 
>a PROOF that the proof exists just consists in displaying the 
>original proof.  Got that?  (There may be weird logics in which
>this is untrue - for instance where a proof could 'exist' but be
>unable to be constructed - but this kind of thing isn't relevant
>here.)
> 
Mr.Kort said that not all TRUE sentences are provable. This is a well
known theorem, arrived at by Kurt Godel (o mit umlaut) in the earlier
part of this century. It has nothing to do with wierd logics; it
applies equally to any system suffienciently powerful to embody 
basic arithmetic.

Even your statement that 'if a sentence is provable, then it's 
PROVABLE that it's provable' does not hold. For many years,
one could not show the four color problem was provable, and yet it
was. Only upon discovery of a proof is your claim valid, but the
'provability' of a logicaL statement is invariant.

Basically, Godel has shown that for any sufficiently powerful system
of logic, either it is possible to construct true statements which
cannot be proven inside the system, or the system is inconsistant
(which, for those of you not familiar with mathematics, is much, much
worse. One can prove anything one likes in an inconsistant system.)
Thus, certain 'sentences' are undecidable. 

>Here are your two statements again:                   

>     1:  Sentence 2 is provable.
>     2:  Sentence 1 is unprovable.
> 
>So: if Sentence 1 above is True, then (by reading what it says)
>Sentence 2 is provable.  But as we've just said, this entails
>that the statement "Sentence 2 is provable" is itself provable.
>But this statement is just Sentence 1!  So now we see that 
>Sentence 1 is provable, CONTRADICTING Sentence 2.  So, oops,
>now Sentence 2 is FALSE, so it can't be provable.  
> 

I'm sorry, what do you mean 'this entails that the statement...' ?'
I think what you want to say is that if 1 is true, then we can
use it to prove 2 true. In so doing, we 'prove' 1 also. This
however is no proof, since we have had to assume 1 in order to 
prove 1. It is quite possible for 1 to be true, but not provable,
without creating a contradiction. If we make it an axiom (by 
assuming its truth) then we are in effect altering the logical
system we started with. The system then becomes

A) Sentence 1 is true
1) Sentence 2 is provable
2) Sentence 1 is unprovable

(plus the other rules of logic, which are implicit in the notion of
'provable', and which can theorectically be made explicit.)

This system is inconsistant, since we can prove 1 by A and disprove
it by 2. Thus this new system is worthless. Without introducing A
as an axiom, and thereby making it possible to prove anything,
how is it possible to prove 1?

I am not saying that there is not a paradox here, I just don't follow
your reasoning. People like Russell devoted their lives to the elimination
of paradox from logical systems, in the faith that paradox was anathema
to logic. In the more general case, Godel has proven that it is always possible
to create a statement which, basically, states 'this statement is false'
and yet cannot be proven inside of the system. This is not a shortcoming of 
English, it is a fundamental property of logic. Such statements may or 
may not be true, but they are undecidable.

				Bob Kohout