Date: Thu 28 Jul 1988 22:57-EDT From: AIList Moderator Nick Papadakis Reply-To: AIList@mc.lcs.mit.edu Us-Mail: MIT Mail Stop 38-390, Cambridge MA 02139 Phone: (617) 253-2737 Subject: AIList Digest V8 #29 To: AIList@mc.lcs.mit.edu Status: R AIList Digest Friday, 29 Jul 1988 Volume 8 : Issue 29 Today's Topics: Mathematical Logic: (This began as part of the 'free will' discussion, but seems to have branched out since ...) Are all reasoning systems inconsistent? Bounded systems are too limited Goedel's Theorem self reference paradox ---------------------------------------------------------------------- Date: Wed, 27 Jul 88 08:47:38 EDT From: PAUL_MALENFANT@VOID.CEO.DG.COM Reply-to: Subject: Re: Are all reasoning systems inconsistent? Jon, after reading your proof beginning with S = (S -> A), I constructed the truth table for it. S A | (S -> A) | S = (S -> A) ========================================= T T | T | T F T | T | F T F | F | F F F | T | F As you can see, it can only be true iffi both S and A are true, so your proof isn't saying anything new. A must be true by definition, not by deduction. Similarly, S = (P(n) -> A) can be constructed in the same way. S P(n) A | (P(n) -> A) | S = (P(n) -> A) ============================================== T T T | T | T F T T | T | F T F T | T | T * F F T | T | F T T F | F | F F T F | F | T * T F F | T | T * F F F | T | F Here, there are more true combinations, but the ones that are marked by * must be discarded because they violate (S = P(n)) which was not in the original expression - if it was, then the only instance of truth for the expression would require S, P(n) and A to be all true. So in answer to your question, the reasoning system wasn't inconsistent, it just revealed something which had to be true about the expression in the first place. Paul ------------------------------ Date: 27 Jul 88 14:30:34 GMT From: cik@l.cc.purdue.edu (Herman Rubin) Subject: Bounded systems are too limited In a previous article, John B. Nagle writes: > Goetz writes: > > > Goedel's Theorem showed that you WILL have an > > unbounded number of axioms following the method you propose. That is why > > most mathematicians consider it an important theorem - it states you can > > never have an axiomatic system "as complex as" > > arithmetic without having true statements which are unprovable. > > Always bear in mind that this implies an infinite system. Neither > undecidability nor the halting problem apply in finite spaces. A > constructive mathematics in a finite space should not suffer from either > problem. Real computers, of course, can be thought of as a form of > constructive mathematics in a finite space. > > There are times when I wonder if it is time to displace infinity from > its place of importance in mathematics. The concept of infinity is often > introduced as a mathematical convenience, so as to avoid seemingly ugly > case analysis. The price paid for this convenience may be too high. > > Current thinking in physics seems to be that everything is quantized > and that the universe is of finite size. Thus, a mathematics with infinity > may not be needed to describe the physical universe. > > It's worth considering that a century from now, infinity may be looked > upon as a mathematical crutch and a holdover from an era in which people > believed that the universe was continuous and developed a mathematics to > match. > > John Nagle The finiteness of size of the universe is irrelevant to the question of whether an infinite system is needed. The number of points in the smallest interval in one dimension is the same and the number needed for any finite- dimensional model of the universe. The resolution of the various paradoxes require a concept of infinity, but not of an unbounded universe. And even if the universe is finite and quantized, so that at any physical time there are only finitely many points in space (with the appropriate relativistic modifications), and any history has only a finite number of time points, the probabilistic considerations require that the parameter space is infinite. Mathematics does not allow infinitely long arguments in most of its branches. A proof must have finite length in its language. However, bounded length cannot be required. I cannot imagine a remotely reasonable system which would allow proofs to have 65535 lines but not 65536. Or a system which would allow an argument to use 1988 variables but not 1999. The postulates about the integers state that for every integer there is a next integer-- a next _larger_ integer. Do not confuse unboundedness with infinity. I know of no mathematical system in which the objects and axioms are not recursively enumerable. That means that they can be listed. I have referred above to having arbitrarily many variables. The rules also require a listing. The ability to substitute an expression of an appropriate type for a variable is actually an axiom schema, a separate axiom for each variable and each expression. Thus there must be an infinite number of rules. A Turing machine can do all mathematics in principle. So can any computer with an infinite tape if it of even moderate size. But remember the infinity. If a particular computer with a particular memory, including externals, cannot do a particular job does not mean that that job cannot be done by computers. Also do not confuse the size of an object within a mathematical system with the size as seen from a model. There are also different notions of size, and a competent mathematician has no problems in using the appropriate notion in a given situation. -- Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907 Phone: (317)494-6054 hrubin@l.cc.purdue.edu (Internet, bitnet, UUCP) ------------------------------ Date: Wed, 27 Jul 88 15:42:05 +0100 From: "Gordon Joly, Statistics, UCL" Subject: Re: Goedel's Theorem > From AIList Vol 8 # 22 > Shame on you, professor! Goedel's Theorem showed that you WILL > have an unbounded number of axioms following the method you propose. > That is why most mathematicians consider it an important theorem - it > states you can never have an axiomatic system "as complex as" > arithmetic without having true statements which are unprovable. > Phil Goetz Shame on who? Anyway, the theorem is important to *pure* mathematicians, in particular number theorists, as is the concept of infinity. But does that worry *applied* computer scientists? I believe you need to have system as complex as the real numbers (countable infinity) to get into the "Goedel domain". > op. cit. > Since you CAN think of ways to disprove f=ma, you may avoid being > run over by a bus. > -- Rich Brandau Einstein showed that f=ma was a first approximation. He also showed that is was fundamentally incorrect to think if the apple as being pulled; it falls since nothing holds it up. f=ma was DISproven in this sense. Gordon Joly. P.S. Is cosmology a science? ------------------------------ Date: Wed, 27 Jul 88 11:35:48 EDT From: "Bruce E. Nevin" Subject: self reference paradox In AIList Digest for Wednesday, 27 Jul 1988 (Volume 8, Issue 28), in his message of 24 Jul 88 23:36:25 GMT, buengc!bph@bu-cs.bu.edu (Blair P. Houghton) writes: BH> One of the simplest examples of unproveability is the paradox | | "This sentence is false." | | It drives you nuts if you analyze it semantically; but, it's blithering | at a very low level if you hit it with logic: call the sentence S; | the sentence then says . . . | | "S = not-S." 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. For this reason, the above translation into symbolic notation is not licit. It does not even capture what we suppose the sentence to be saying, precisely because it does not capture the paradox. And why does it fail in this? Because it is a metalanguage statement referring to the sentence abbreviated by S. It is not a self-reference by a sentence to itself, it is a reference to a separate sentence, abbreviated S. This failure of self-reference is a limitation, if you want to think of it that way, due to the fact that natural languages contain their own metalanguages, rather than having a separate metalanguage. See Harris _Mathematical Structures of Language_ and _Language and Information_ for discussion. The logical apparatus of deduction and other forms of inference are required only for various uses to which language may be put, rather than being the semantic basis for natural language, as has been sometimes claimed. Translation of natural language texts into logical notations is always and necessarily incomplete. (Same references, for starters.) Bruce Nevin bn@cch.bbn.com ------------------------------ End of AIList Digest ********************