Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!iuvax!cogsci!dave From: dave@cogsci.indiana.edu (David Chalmers) Newsgroups: comp.ai Subject: Re: Natural Paradox Message-ID: <17167@iuvax.cs.indiana.edu> Date: 2 Feb 89 21:42:02 GMT References: <1706@tank.uchicago.edu> Sender: root@iuvax.cs.indiana.edu Reply-To: dave@duckie.cogsci.indiana.edu (David Chalmers) Organization: Indiana University, Bloomington Lines: 119 Newsgroups: comp.ai Subject: Re: Natural Paradox Summary: Expires: References: <1706@tank.uchicago.edu> Sender: Reply-To: dave@cogsci.indiana.edu (David Chalmers) Followup-To: Distribution: Organization: Concepts and Cognition, Indiana University Keywords: In article <1706@tank.uchicago.edu> staff_bob@gsbacd.uchicago.edu (bob kohout) writes: >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. >> >>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... I know. I never argued with this. I made the "provable implies provably provable" comment to aid the demonstration that the above two sentences CAN'T be true simultaneously. (Coming up.) > >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. This is incoherent. The "provability" of a statement is not dependent upon the capacities of us limited human beings to find and construct such a proof. This applies even when the statement whose provability we are investigating is of the form "Statement X is provable." "Provability" is a well-defined mathematical notion that is independent of arbitrary human exigencies, in the same way that, say, "triangularity" is. Just as the four-color theorem was in fact TRUE even before 1974 (when some people found the proof), it was also provable before then. Upon Haken & Apell's proof in 1974, then humans DISCOVERED for sure that not only was the theorem true, but that it was provable, and that it was provable that it was provable, and so on. But none of these are time-dependent concepts. >>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. You've missed the point, or maybe I wasn't clear enough. I was demonstrating that it's impossible for both statements to be true simultaneously. To do this, I ASSUMED that S.1 was true, and showed that under this assumption S.2 has to be false. (And along the way I showed that all kinds of other paradoxical things were entailed). Another way of looking at this is to realize that, by my previous argument, it is impossible for a statement of the form "X is provable" to be true but unprovable. So your (and BK's) statement, that it is possible for Sentence 1 to be true but unprovable, is wrong. > >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. That's absolutely right. If we ever have a genuine paradox, grounded in a well-defined system of reality (or mathematical reality), then our system falls apart. Given that we don't want our system to fall apart, then like Russell we have to make damn sure that there aren't any real paradoxes. The usual way to do this is to deem statements like "This sentence is false" ill-defined or meaningless. Godel's great insight is that statements like this (well, actually like "This statement is unprovable") can actually be grounded (with a lot of work) in concrete mathematical reality (if that's not a contradiction in terms). After he did this, the "meaningless" escape route was no longer available, so people had to accept "true but unprovable" statements. Very annoying, but a small sacrifice to make to save all of mathematics from destruction. (See my last posting for more on Godel, paradoxes and meaninglessness.) Dave Chalmers