CMENZEL@TAMLSR.BITNET (08/04/88)
Date: Fri, 29 Jul 88 22:45 EDT From: CMENZEL%TAMLSR.BITNET@MITVMA.MIT.EDU Subject: Non-r.e. systems, Godel, and Zermelo To: ailist@ai.ai.mit.edu X-Original-To: ailist@ai.ai.mit.edu, CMENZEL 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