Date: Sat 6 Aug 1988 23:16-EDT From: AIList Moderator Nick Papadakis Reply-To: AIList@mc.lcs.mit.edu Us-Mail: MIT LCS, 545 Tech Square, Rm# NE43-504, Cambridge MA 02139 Phone: (617) 253-6524 Subject: AIList Digest V8 #39 To: AIList@mc.lcs.mit.edu Status: RO AIList Digest Sunday, 7 Aug 1988 Volume 8 : Issue 39 Mathematics and Logic: Re: undecidability Liar's paradox, AI .vs. human error Are all Reasoning Systems Inconsistent? Re: Self-reference and the Liar paradox and metalanguage gaffes ---------------------------------------------------------------------- Date: 4 Aug 88 13:09:36 GMT From: steve@hubcap.UUCP ("Steve" Stevenson) Subject: Re: undecidability >From a previous article, by asg@pyuxf.UUCP: > In a previous article, John B. Nagle writes: >> Goetz writes: >>> [Goedel's incompleteness ... unbounded number of axioms] >> Always bear in mind that this implies an infinite system. >> There are times when I wonder if it is time to displace infinity from >> its place of importance in mathematics.... > Actually, infinity arises in basic set theory, ... But isn't this the point? The nominalists/finitist won't let you get to that step. Take for example your mythical perfect(?) computer programmer. To such a person, the discussion of infinity in any guise is lost: there just aren't any infinite processes (by almost anybody's) definition. Intuitionist as a little better - only countable infinity allowed. The foundational issue is whether or not it is legit to propose successor and related things as legit bases for mathematics. That's John's point: The canon of infinity may not be all that good an idea.-- Steve (really "D. E.") Stevenson steve@hubcap.clemson.edu Department of Computer Science, (803)656-5880.mabell Clemson University, Clemson, SC 29634-1906 ------------------------------ Date: Thu 4 Aug 88 09:03:31-PDT From: Mike Dante Subject: Liar's paradox, AI .vs. human error 1. Bruce Nevin suggests that the solution to the "liar's paradox" lies in the self reference to an incomplete utterance. How would that analysis apply to the following pair of sentences? The next sentence I write will be true. The previous sentence is false. 2. Back when it appeared that the shooting down of the airliner in the Gulf was the result of an "AI" system error, there were a series of digests using the incident as a proof of the dangers of relying on computers to make decisions. Now that the latest analysis seems to show that the computer correctly identified the airliner but that the human operators erroneously interpreted the results, I look forward to an equally extensive series of postings pointing out that we should not leave such decisions to fallible humans but should rely on the AI systems. --- Or were the previous postings based more on presuppositions and political considerations than on an analysis of evidence? ------------------------------ Date: Fri, 5 Aug 88 15:52:04 EDT From: jon@XN.LL.MIT.EDU (Jonathan Leivent) Subject: Are all Reasoning Systems Inconsistent? A while ago, I posted a proof I had stumbled upon that seemed to lead to inconsistencies. After some more thought about it, and after reading some replies, I dcided to reformulate it. Originally, I claimed that the construction of the sentence S = P(n) -> A leads to a contradiction - what I meant is that a particular sentence could be constructed in a reasoning system such that the mere assertion of the existence of that sentence leads to a contradiction. I phrased the sentence as indicated above because I had thought of it while reading something about Lob's Theorem in a paper by Raymond Smullyan in the 1986 conf proceedings of Theoretical Aspects of Reasoning about Knowledge (title: "Logicians who reason about Themselves" - an interesting paper for people into Godel's theorem). Anyway, I decided that the sentence I was interested in was really: (En)[P(n) = ~P(n)] Where P(m) means "m is the Godel number of a theorem in this reasoning system". This theorem is actually a corollary of Godel's theorem - it is proven by constructing the sentence with Godel number n that satisfies the above theorem. The thing that bothers me is that the statement (En)[P(n) = ~P(n)] is contradictory itself, yet obviously true (by construction). I'm sorry about the delay in reposting: I was away from work for a week. -- Jon Leivent ------------------------------ Date: 5 Aug 88 21:33:47 GMT From: bwk@mitre-bedford.ARPA (Barry W. Kort) Reply-to: bwk@mbunix (Kort) Subject: Re: Self-reference and the Liar While we are having fun with self-referential sentences, perhaps we can have a go at this one: My advice to you is: Take no advice from me, including this piece. (At least the self referential part comes at the end, so that the listener has the whole sentence before parsing the deictic phrase, "this piece".) --Barry Kort ------------------------------ Date: Sat, 6 Aug 88 09:30:16 EDT From: "Bruce E. Nevin" Subject: paradox and metalanguage gaffes In AIList Digest for Thursday, 4 Aug 1988 (Volume 8, Issue 36) Chris Menzel writes: CM>| In AIList vol. 8 no. 29 Bruce Nevin provides the following analysis of the | liar paradox arising from the sentence "This sentence is false": | > The syntactic nexus of this and related paradoxes is that there is no | > referent for the deictic phrase "this sentence" at the time when it is | > uttered, nor even any basis for believing that the utterance in progress | > will in fact be a sentence when (or if!) it does end. A sentence cannot | > be legitimately referred to qua sentence until it is a sentence, that | > is, until it is ended. Therefore, it cannot contain a legitimate | > reference to itself qua sentence. | . . . If what Nevin says is right, then there is . . . | something semantically improper about an utterance of "This sentence is | in English", or again, "This sentence is grammatically well-formed." But | both are wholly unproblematically, aren't they? Wouldn't any English spkr | know what they meant? It won't do to trash respectable utterances like | this to solve a puzzle. They are not "wholly unproblematical," they engender a double-take kind of reaction. Of course people can cope with paradox, I am merely accounting for the source of the paradox. CM>| Nevin's analysis gets whatever plausibility it has by focusing on *English | utterances*, playing on the fact that, in the utterance of a self-ref | sentence, the term allegedly referring to the sentence being uttered has no | proper referent at the time of the term's utterance, since the sentence yet | isn't all the way of the speaker's mouth. . . . | it's just an accident that noun phrases usually come first in English | sentences; if they came last, then an utterance of the liar or one of | the other self-referential sentences above would be an utterance of a | complete sentence at the time of the utterance of the term referring to | it, and hence the term would have a referent after all. Surely a good | solution to the liar can't depend on anything so contingent as word | order in English. If I say it in Modern Greek, where the noun followed by deictic can come last, the normal reading is still for "this" to refer to a nearby prior sentence in the discourse. The paradoxical reading has to be forced by isolating the sentence, usually in a discourse context like "The sentence /psema ine i frasi afti/, translated literally 'Falsehood it is the sentence this', is paradoxical because if I suppose that it is false, then it is truthful, and if I suppose it is truthful, then it is false." These are metalanguage statements about the sentence. The crux of the matter (which word order in English only makes easier to see), is that a sentence (or any utterance) cannot be a metalanguage statement about itself--cannot be at the same time a sentence in the object language (English or Greek) and in the metalanguage (the metalanguage that is a sublanguage of English or of Greek). CM>| Second, the liar paradox arises just as robustly for | inscriptions, where the ephemeral character of utterances has no part. When you are reading the words "this sentence" or /frasi afti/ the thing referred to is not complete as an object for reference until you have finished reading it and have resolved all the referentials in it. But to resolve the reference of the deictic "this" or /afti/, the sentence must be complete. This is the bind. The metalanguage information necessary to understand a sentence must be in that sentence itself, else it could not be understood. One may make this metalanguage information explicit in the form of conjoined metalinguistic sentences that refer to already-completed *parts* of the sentence in process, but such conjuncts may not refer to the *whole* sentence, which includes themselves still in process. Having read the paradoxical sentence, and in the attempt to resolve the referentials, one mentally supplies the additional metalinguistic context indicated above in order to appreciate the paradox. One rereads the sentence as object language sentence and rereads it again as metalanguage sentence, mentally treating them as two tokens with one referring to the other. But they are not two, and to act as though they were is to step on the mental banana peel and take the pratfall of paradox. CM>| note there is nothing about the liar per se that appears in his analysis. I'm sorry, did I promise to say something about the liar paradox? I can't find any explicit reference prior to this. Blair Houghton didn't mention the liar paradox either. But since Chris Menzel brings it up, and since it is closely related. . . . To appreciate the paradox of the sentence "I am [always] a liar" one must adduce further contextual sentences, such as: "This_0 implies that everything I say is false; this_1 is something I say therefore this_1 is false; when something_0 is false then the opposite of that something_0 is true; the opposite of this_1 is 'Everything I say is true'; this_2 is something I say [because it is implied by . . .]; therefore this_2 is true; furthermore, therefore this_1 is true [[but this_1 contradicts this_2, TILT! And the preceding, this_3, contradicts the prior sentence, this_4: 'Therefore this_1 is false,' TILT!]]; when something is false . . . As many have noted, we are looping here, loops which would or could come to a halt when your (imputed) inference engine comes up with the metalanguage observations in doubled [[brackets]], but we might never get that far because within it the portion in single [braces] is also occasion for an infinite subloop. As usual, dualism gets you into a hall of mirrors. The dizzying effect is the titillating pleasure of paradox. (The benefit is or can be a release from dualism, but that is another tale.) To repeat one of the points that Chris Menzel ignored, the translation into logical symbolism as S <=> ~S and the like fails to capture the paradox precisely because it is uniquivocally and only a *separate* metalanguage statement about the sentence symbolized S, comparing it with its negation symbolized ~S. ~S represents a conclusion reached at a certain point in the loop of metalinguistic conjuncts, and so is part of the metalinguistic context; <=> is the metalanguage assertion that they are equivalent. This formula captures a small part of the problem. Try to formulate a metalanguage proposition in logical formalism such that it is also the object language proposition to which it refers. Not only can it not be done it is also improper to do, and it is that impropriety to which I refer. (In logical formalisms with which I am familiar, the metalanguage is separate from the object language, partly to prevent such errors. It has been observed that the ultimate metalanguage for mathematics and logic is the natural language shared by the mathematicians or logicians.) The subscripts of course are just a notational convenience. Natural language doesn't have a mechanism for addressing particular words by counting or the like. It can do it by next adjacency in an interrupting conjoined sentence, as follows: Our old friend Fred--Fred you always liked for his brinksmanship-- typically carries a dozen unclosed parens in his head when he writes anything. This reduces by elision and other commonplace operations to: Our old friend Fred, who you always liked for his brinksmanship, typically carries . . . This reduction from an interrupting subsentence with subordinated intonation under paratactic conjunction is the source for all the modifiers. (There is historical as well as syncronic evidence for this. This is formalized in the operator grammar of construction-reduction theory, see references cited earlier and S. Johnson's 1987 NYU dissertation implementing an analyzer for information content.) Words that cannot be made adjacent in this way at some point in the construction of a sentence, if necessary by topicalization as above, showing that the second occurrence carries very little information, cannot be reduced to pronouns, deictics, and so on. The condition of next adjacency, however, is not possible for a sentence that seems to refer to itself as a whole. I won't try, but just to illustrate the problem and display the loops in another form: Everything I say is false ^ ('something | ('something' is this present sentence | (the opposite of this present sentence is 'Everything I say | | +-----------------------------------------+ | ('Everything I say' includes this present sentence +-----which is | ) | is true') | ) | is false' means the opposite of something | ('something' is this present sentence | (the opposite of this present sentence is 'Everything I say | | +-----------------------------------------+ | ('Everything I say' includes this present sentence +-----which is ) is true') ) is true') One never can finish resolving the deictics. The reason again is that the metalanguage information necessary to understand a sentence must obviously be in that sentence itself, and finitely, else it could not be understood. And again, the only way we try to resolve this sentence and come to see it as paradoxical is to read it repeatedly, taking the second reading and each even-numbered reading thereafter as a separate token referring to the prior odd-numbered reading, and when we get tired of that loop to then turn around and say that these reading-tokens are not separate, that there is but one sentence. It is, as Chris Menzel points out, an error of logical typing to confuse metalanguage readings with object-language readings. The pratfall is to suppose that the sentence can as a whole at one and the same time be both. It cannot. Bruce Nevin bn@cch.bbn.com ------------------------------ End of AIList Digest ********************