Date: Wed 3 Aug 1988 15:10-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 #36 To: AIList@mc.lcs.mit.edu Status: R AIList Digest Thursday, 4 Aug 1988 Volume 8 : Issue 36 Mathematics and Logic: Non-r.e. systems, Godel, and Zermelo Self-reference and the Liar Re: undecidability ---------------------------------------------------------------------- Date: Fri, 29 Jul 88 21:45 CDT From: Subject: Non-r.e. systems, Godel, and Zermelo In AIList vol. 8, no. 29 (July 29, 1988), Herman Rubin writes: > I know of no mathematical system in which the objects and axioms are not > recursively enumerable. I'm not sure what Rubin means by a mathematical system here, since the notion of an object suggests systems are mathematical structures like the natural numbers or the finite sets, while the notion of an axiom suggests systems are axiomatic theories. There is a counterexample to his claim in either case. If he means the former, consider the real numbers. Since no uncountable set is r.e., the set of reals isn't. If you want a countable set, consider the set of Godel numbers of sentences of the first-order language of arithmetic that are true in the natural numbers (relative to some coding for the language). Godel's theorem says that this set is not r.e. For a non-r.e axiomatic theory, take as axioms the set of the above true sentences of arithmetic. Same result. Granted the theory ain't good for much; but that's another kettle of fish. > A Turing machine can do all mathematics in principle. Certainly you don't mean that every mathematical truth is provable; cf. Godel again. But if not, what? Zermelo constructed an apparently--but not provably (Godel yet again)--consistent, and very powerful, set of axioms for set theory. Surely he was doing mathematics. Now write me a program for generating set theoretic axioms that avoid the paradoxes of naive set theory, and preserve arithmetic, classical analysis, and transfinite number theory. Chris Menzel Dept. of Philosophy/Knowledge Based Systems Lab Texas A&M University BITNET: cmenzel@tamlsr ARPANET: chris.menzel@lsr.tamu.edu ------------------------------ Date: Sat, 30 Jul 88 17:09 CDT From: Subject: Self-reference and the Liar 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. There are type-token problems here, but never mind. If what Nevin says is right, then there is something semantically improper in general about referring to the sentence one is uttering; note there is nothing about the liar per se that appears in his analysis. If so, however, 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 speaker know what they meant? It won't do to trash respectable utterances like this to solve a puzzle. Nevin's analysis gets whatever plausibility it has by focusing on *English utterances*, playing on the fact that, in the utterance of a self-referential 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. But, first, 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. Second, the liar paradox arises just as robustly for inscriptions, where the ephemeral character of utterances has no part. About these, though, Nevin's analysis has nothing to say. A proper solution must handle both cases. Recommended reading: R. L. Martin, {\it Recent Essays on Truth and the Liar Paradox}, Oxford, 1984. J. Barwise and J. Etchemendy, {\it The Liar: An Essay on Truth and Circularity}, Oxford, 1987. ---Chris Menzel Dept. of Philosophy/Knowledge Based Systems Lab Texas A&M University BITNET: cmenzel@tamlsr ARPANET: chris.menzel@lsr.tamu.edu ------------------------------ Date: 2 Aug 1988 10:43 EDT From: pyuxf!asg Subject: Re: undecidability Path: pyuxf!asg From: asg@pyuxf.UUCP (alan geller) Newsgroups: comp.ai.digest Subject: Re: undecidability Summary: Infinity IS natural Message-ID: <375@pyuxf.UUCP> Date: 2 Aug 88 13:51:14 GMT Article-I.D.: pyuxf.375 Posted: Tue Aug 2 09:51:14 1988 References: <19880727030404.9.NICK@HOWARD-JOHNSONS.LCS.MIT.EDU> Organization: Bell Communications Research Lines: 55 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 Actually, infinity arises in basic set theory, long before any notion of 'finite space' is introduced (viewing mathematics as an inverted pyramid, from lowest-level set theory and logic up). Two axioms suffice to introduce infinity: the axiom of the null set, which says that there exists a set 0, which is empty; and the axiom of construction (or of union, or whatever you prefer to call this axiom), which says that if a and b are sets, then so is {a, b}. These two axioms allow one to construct 0, {0}, {{0}}, etc., which is an infinite series. In fact, it is possible to create models of set theory which are constructed using only sets of this form. In physics, 'quantization' does not mean 'granularization', despite the popular understanding that this is so. While there are physicists who work on theories of granular space, mainstream quantum physics interprets space as a continuum. Indeed, even quantized measurables such as energy levels are seen as selected values 'chosen' out of a continuum by being the eigenvalues of some operator. Also, the notion that the universe is finite is still contraversial; while most cosmologists seem to believe that the universe is closed (i.e., finite), there is still no experimental evidence to support this view (this is why cosmologists talk about the 'missing mass', which is needed to close the universe gravitationally; nobody's found it yet). Alan Geller Bellcore Nobody at Bellcore takes me seriously. ------------------------------ End of AIList Digest ********************