cik@oracle (Herman Rubin) (07/29/88)
To: comp-ai-digest Path: l.cc.purdue.edu!cik From: Herman Rubin <cik@l.cc.purdue.edu> Newsgroups: comp.ai.digest Subject: Bounded systems are too limited Date: Wed, 27 Jul 88 10:30 EDT References: <19880727030404.9.NICK@HOWARD-JOHNSONS.LCS.MIT.EDU> Organization: Purdue University Statistics Department Lines: 74 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)