Date: Mon 15 Aug 1988 23:30-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 #51 To: AIList@mc.lcs.mit.edu Status: R AIList Digest Tuesday, 16 Aug 1988 Volume 8 : Issue 51 Mathematics and Logic: Nitpicking about the Axiom of Choice Are all Reasoning Systems Inconsistent? Ineluctable self reference ---------------------------------------------------------------------- Date: 1 Aug 1988 1819-PDT (Monday) From: aspnes@decwrl.dec.com (Jim Aspnes) Subject: Nitpicking about the Axiom of Choice > From: bwk@mitre-bedford.ARPA (Barry W. Kort) > In the above scenarios, the resolution is to pick a path at random > and pursue it first. To operationalize the decision, one needs to > implement the Axiom of Choice. One needs a random number generator. > Fortunately, it is possible to build one using a Quantum Amplifier. > (Casting lots will do, if you live in a low-tech society.) Technically speaking, the Axiom of Choice claims only that choice functions exist for collections of infinite sets. These choice functions _must_ be deterministic (although what the function maps each set to is not specified by the axiom), and always exist for finite sets with or without the Axiom of Choice. So Quantum Amplifiers would not be terribly useful in the operationalization of the Axiom of Choice, unless your scenario included a previous operationalization of a representationalization of arbitrary infinite sets. Jim Aspnes ------------------------------ Date: Mon, 8 Aug 88 13:16:12 EDT From: jon@XN.LL.MIT.EDU (Jonathan Leivent) Subject: Are all Reasoning Systems Inconsistent? It seems that I keep making the same mistakes. Here is a full version of the contradiction that I am claiming exists. I'm making this as complete as possible because previous versions of my assertion have all suffered from my own clumsiness (abstractly, they were on the right track; formally, they were all wrong). So here goes: Definition of functions and predicates: Q(a,b) : equality of numbers predicate (so we don't get mixed up with =) Aa[Q(a,a)], AaAb[Distinct(a,b) -> ~Q(a,b)] "X" : the Godel number of X s("X",a) : the Godel number of X with all occurrences of * replaced by the Godel number of the number a : s("R(*)",14) is "R(14)" P(a) : the predicate of provability within this reasoning system I won't go into proofs of the existence of s and P. Chapter 24 of Doug Hofstadter's book _Godel, Escher, Bach_ has the best explanations of these I've seen (Hofstadter's versions of the functions are a bit different from mine - I've chosen mine for conciseness, Hofstadter probably chose his to simplify the proofs of their existence). Theorems: T1. AaAb[Q(a,b)P(a) = P(b)] ; just says that P behaves normally T2. Aa[P(s("~P(*)",a)) -> ~P(a)] ; If I can prove that I can't prove X, then I can't prove X T3. If X can be proven within this reasoning system, then P("X") is true Definitions of numbers: Let F such that Q(F,"~P(s(*,*))") Let G such that Q(G,s(F,F)) ; this means that G is s("~P(s(*,*))",F), which is "~P(s(F,F))" : so Q(G,"~P(G)") and G is our Godel sentence (remember that F and G are numbers, not variables) The inconsistency itself: 1. P(G) = P("~P(G)") ; from T1 and the defintion of G 2. P("~P(G)") -> ~P(G) ; from T2 3. P(G) -> ~P(G) ; from 1 and 2 by substitution of P(G) for P("~P(G)") 4. ~P(G) ; from 3 (3 is equivalent to ~P(G) v ~P(G)) 5. P("~P(G)") ; from T3 and the fact that 1 thru 4 proves ~P(G) 6. P(G) ; from 1 and 5 4 and 6 contradict. All that I have done is to show that the existence of a Godel sentence within a reasoning system equipped to reason about itself is inconsistent. This differs from Godel's theorem in that Godel shows that a Godel sentence cannot be proven within a reasoning system in which it is true. Perhaps the weak link in the contradiction is step 5, which is somewhat of a "meta" step. What bothers me most is that there seems to be no formal way of writing T3, even though it seems to be obviously true (it is only asserting the equivalence of P with the implied proof predicate in this reasoning system, which is true by definition of P). Note that T3 does not claim that if X is true, then P("X") is true - it requires X to be proven within this reasoning system, which is a stronger requirement than truth (because of the incompleteness of P). Well, I hope I haven't goofed up here as I did previously. This finally seems to be a formal statement of what was on my mind after reading Smullyan's article "Logicians who Reason about Themselves". -- Jon Leivent ------------------------------ Date: Mon, 8 Aug 88 14:26:16 EDT From: "Bruce E. Nevin" Subject: ineluctable self reference In AIList Digest for Sunday, 7 Aug 1988 (Volume 8, Issue 39), Mike Dante writes: MD>| 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. These are both metalanguage sentences. Each is talking about a metalanguage sentence (the other). Part of the construal of the metalanguage predicate `false' is the inference that the negation of its argument is true. Thus, in the metalinguistic baggage that sentence 2 carries with it is the negation of sentence 1. But since sentence 1 incorporates a reference to sentence 2, sentence 2 incorporates (as part of the metalanguage baggage required to understand it) a reference to itself. In more intuitive terms: what's wrong here is that somewhere it is being asserted that sentence 1 is both true and false. Thus, there must be two distinct series of readings of sentence 1: an odd-numbered series in which it is true in what it asserts of sentence 2, and an even-numbered series in which it is false because of what sentence 2 asserts. (The same goes, ceteris paribus, for sentence 2.) When you get tired of that loop, you fall back on assuming that the two readings are but one sentence, even while trying to reconcile the two readings (which leads into the next two reading-tokens, and so on, each round `meta-' wrt the prior). +---+==>[I affirm that] the next sentence I write will be true. | +-|-->[I affirm that] the previous sentence is false [and so I deny that]+ | | | | | | +----------------------------------------------(loop 1)----------------+ | | [and so I deny that] + | | | (loop 2) | +--------------------------+ | [and so] + | | (loop 3) +----------------+ Added metalanguage material is in square braces. The loop is perhaps clearer (although misrepresented a bit) this way: +->I affirm S1 | I affirm S2, | and so I deny S1 (loop 1) | and so I deny S2 (loop 2) | and so + | | (loop 3) +---------------+ All of the looping is part of S2, even though it is by reference to both S1 and S2, because it is a succession of conjunctions to S2 under `and so' or `therefore' or the like. And until you have finished construing all the metalanguage conjuncts that you need to understand the sentence you haven't finished understanding the sentence, and so it is not available to you as an object of reference as regards its meaning. (As regards spelling, or handwriting, or depth of incision in stone, or authorship, etc., it is of course available for reference, but that is reference with different ends, and that is why it does not matter whether the referential comes at the end or not.) It is the metalanguage performative predicates of assertion that bring about self-referentiality. (You see the need for these in e.g. `Clearly, John has left' where the adverb cannot apply to the verb `leave', still less to its argument `John', but can only apply to an elided `I infer' or the like. See _A Grammar of English on Mathematical Principles_ for discussion.) Again, self reference (where one reading-token of the sentence is `meta-' with respect to the other) is the syntactic core of these paradoxes. And this is why the obvious (but incomplete) translation into symbolic logic is something like S <=> ~S: you have to represent both readings separately to represent the fallacy. This is not a claim that all inferencing is part of the `metalinguistic baggage' that language users presume as though overtly conjoined when construing sentences and texts. Only that which can be thought of as obvious common knowledge. I realize this is a very large can of worms, but I won't take credit for opening it--the problem of coping with common knowledge in language understanding and language generation is hardly a new one. Barry W. Kort (bwk@mitre-bedford.ARPA) writes: BK>| 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".) This is straightforwardly self-referential. I addressed the confusion about `having the whole sentence' vs `resolving all the referentials in the sentence' in my contribution to AIList 8.39. Bruce Nevin bn@cch.bbn.com ------------------------------ End of AIList Digest ********************