From Posted Sat Aug 17 05:57:09 BST 1996 Newsgroups: comp.ai.philosophy References: <4urn69$okb@Bayou.UH.EDU> <840180893snz@longley.demon.co.uk> <4v25t2$cum@ux.cs.niu.edu> Subject: How much of math is decidable? (was Re: mentality and design) rickert@cs.niu.edu (Neil Rickert) writes: > Date: 16 Aug 1996 10:59:30 -0500 > Organization: Northern Illinois University > In a way, though, I agree that the fuss about Goedel's result is not > justified. The "fuss" usually is in the form of a claim that > Goedel's result shows that mathematics does not reduce to logic. I > think it quite obvious that mathematics does not reduce to logic, and > Goedel's result was not needed to show that. Most mathematicians as far as I am aware (this is based only on informal surveys of mathematicians, plus what was written by outstanding mathematicians such as Poincare against logicism) do not believe that mathematics is reducible to logic. I.e. they accept neither of the two logicist claims of Frege and Russell (a) All mathematical concepts can be *defined* in terms of purely logical constructs (b) All mathematical results can be *derived* using purely logical methods of reasoning. Moreover it is fairly easy to establish empirically that if you give mathematicians mathematical problems to solve they do not restrict their reasoning to logical reasoning. Among the earliest examples are the use of diagrams in Euclid, but diagrams and spatial visualisation continue to be used, even in the most abstract realms of modern mathematics, e.g. category theory. Whether these non-logical forms of representation and reasoning are dispensable is not an empirical question, however. It requires a different sort of investigation. I don't know the answer. I suspect they are not dispensable for a working mathematician, human or artificial, actually searching in real time for answers to hard problems. > David Longley wrote [DL] > >The larger parts of logic and mathematics *are* decidable (a > >point Penrose makes himself) - we rely on that to teach, program > >and do engineering. [NR] > I doubt that you could support such a claim. All you can really show > is that the decidable parts of mathematics are decidable, and that > our teaching concentrates mainly on the decidable parts. Yes. It must be the case that the vast majority of mathematical truths are not decidable, since the decidable ones must be finitely expressible and have formal proofs of finite length, and such proofs are enumerable. However there are infinitely many mathematical truths that are not expressible finitely. An example is the true infinite conjunction of the following form, which states for each natural number whether it is prime or not: 2 is prime and 3 is prime and 4 is not prime and 5 is prime and ... and ... and... [NB the above is not equivalent to For all x if x is in N then prime(x) or not prime(x) which would be a theorem at least of classical logic.] If I had the patience I could probably construct a diagonal argument to prove that there are far more such non-trivial infinite true statements than there are derivable statements. No doubt someone else will. It's probably a standard meta-mathematical result. Certainly there are far more mathematical functions from the reals to the reals than can be defined explicitly, i.e. uncountably many. So presumably there are uncountably many truths about such functions. [DL] > >There are as many mystics in research on the foundations of > >mathematics as there are in "cognitive science". [NR] > Ah yes. Longley, the self appointed world expert in psychology, > statistics and computer science, has now appointed himself expert in > mathematics. Actually foundations of mathematics, if you read carefully. And it is quite tempting to be sort of mystical about all those infinite sets out there. The platonism of Penrose and others is not *just* a personal quirk. However, I've argued elsewhere that debates between platonists and anti-platonists look significant but turn out to be empty of real content if examined closely. What is more interesting is whether we can build models, using AI techniques of whatever kind (computers, neural nets, new AI quantum gravity engines of the future) of the process of acquiring the ability to think about infinite sets, including transfinite sets. New born infants presumably cannot do this. Later on many of them can. What exactly happens in between? Now there's a question with real substance. Aaron From posted Sat Aug 17 21:30:40 BST 1996 Newsgroups: comp.ai.philosophy References: <4v25t2$cum@ux.cs.niu.edu> <4v3jen$fnt@percy.cs.bham.ac.uk> <4v4ip1$eq7@ux.cs.niu.edu> Subject: Re: How much of math is decidable? (was Re: mentality and design) rickert@cs.niu.edu (Neil Rickert) writes: > Date: 17 Aug 1996 08:51:29 -0500 > Organization: Northern Illinois University > [AS] > >And it is quite tempting to be sort of mystical about all those > >infinite sets out there. The platonism of Penrose and others is not > >*just* a personal quirk. [NR] > Platonism is popular, I think, because it is the most easily > described alternative to formalism. The main feature of platonism that I was thinking of, is the claim that mathematical truths exist independently of mathematicians, as contrasted with the view that mathematical truths are really creations of mathematicians (there are half-way houses, like the view of Kronecker(?) that "God made the integers and man made the rest" or something like that). It was that particular platonist/anti-platonist debate that I was claiming was empty of real content. In that sense a formalist can be a platonist, saying that mathematicians discover "mind-independent, pre-existing" truths about formal systems, and an anti-platonist formalist would argue that those truths are created. Hilbert was, I think, a platonist formalist in that sense of "platonist". [NR] > ..If you read Penrose's "Shadows > of the Mind" as an argument against the adequacy of formalism, I > think it does reasonably well, even if less than watertight. Perhaps, though one doesn't need any of the incompleteness results to argue that there's more content to mathematics than the study of properties of formal systems. [NR] > It is > not so convincing against AI, because Penrose has not convincingly > shown that an AI mathematician must be a formalist. He has simply > taken it for granted as an a priori assumption. Also I don't think Penrose ever really understood what AI is. E.g. I don't think he knows anything about work on vision, robotics, architectures composed of asynchronous interacting subsystems, etc. I suspect the sets of philosophers on both sides on the issue of platonic existence of mathematical truths will include both defenders of AI and attackers. [AS] > >However, I've argued elsewhere that debates between platonists and > >anti-platonists look significant but turn out to be empty of real > >content if examined closely. [NR] > Perhaps that is an overstatement, I suspect you thought I was thinking of debates about formalism. I guess I should have explained what I meant by Platonism. I was not thinking of platonism defined in opposition to a formalist philosophy of mathematics. [NR] > ...although much depends on what you > intend by "real content". The Platonist holds that the truth of the > continuum hypothesis is a genuine question about the platonist's > reality. I'm not a platonist, and I hold that the proof of the > independence of the continuum hypothesis demonstrates that it it an > empty question, to be settled only by fiat. Not sure why you think that follows unless you think that mathematical truth is defined by what follows from the other axioms, which is close to a sort of formalism. I was thinking of much simpler cases, e.g. arguments over whether something like "the square root of 2 is irrational" is a creation of mathematical minds or an independent truth discovered by inspecting mathematical reality. When such claims are expanded in detail regarding what is actually implied about the practice of mathematics the opposition disappears. One reason is that all mathematical discovery involves invention of some proof, and all mathematical invention (of notation, proof, etc.) involves discovery of the possibility of that invention. >... [AS] > >What is more interesting is whether we can build models, using AI > >techniques of whatever kind (computers, neural nets, new AI quantum > >gravity engines of the future) of the process of acquiring the ability > >to think about infinite sets, including transfinite sets. > >New born infants presumably cannot do this. Later on many of them can. > >What exactly happens in between? > [NR] > What happens, is that infants *learn* in ways that have no basis in > formalism, and that are not explicable in terms of behaviorist > theories of learning. I guess you are not putting that forward as an answer to the question (which would require specifying precisely what they learn and how they learn it, i.e. what changes in them and how it changes). It's more a framework within which you expect the answer to be found, and I agree with you. Aaron From posting Sat Aug 17 21:51:40 BST 1996 Newsgroups: comp.ai.philosophy References: <4urn69$okb@Bayou.UH.EDU> <840180893snz@longley.demon.co.uk> <4v25t2$cum@ux.cs.niu.edu> <4v3jen$fnt@percy.cs.bham.ac.uk> <4v4sc9$cad@Bayou.UH.EDU> Subject: Re: How much of math is decidable? (was Re: mentality and design) > Date: 17 Aug 1996 11:35:21 -0500 > Organization: University of Houston math0@Bayou.UH.EDU (siemion fajtlowicz,) seemed to find what I wrote puzzling, though probably that was because the context was not clear. David Longley had previously claimed [DL] > >The larger parts of logic and mathematics *are* decidable (a > >point Penrose makes himself) - we rely on that to teach, program > >and do engineering. Neil Rickert gave a partial response saying that teaching happens to concentrate on the decidable parts, but did not explain why Longley's claim was false. I was trying to explain this by giving reasons why the larger parts of mathematics (i.e. most mathematical truths) must like outside the realm of the decidable. I suspect you found this so obvious that you could not see why I was saying it, e.g. [SF] > I think that decidability questions by definition deal with finite > expressions of countable languages. I was taking that for granted and pointing out consequences, and trying to give an indication of the reasons. [SF] > so I do not understand your point. I hope it is clearer now >... regarding the platonism/anti-platonism debate I had said I thought it had no real content. [SF] > What is the debate about? I think that most mathematicians are > Platonists six days a week (Diedonne's reflection) and they are formalists > on Sunday, realizing that neither can be taken too literarily. Yes. But there are philosophers of mathematics who get more worked up about it. [AS] > >What is more interesting is whether we can build models, using AI > >techniques of whatever kind (computers, neural nets, new AI quantum > >gravity engines of the future) of the process of acquiring the ability > >to think about infinite sets, including transfinite sets. [SF] > I would say that it is even more interesting to show that computers can > "think" about finite sets and first of all to explain sensibly what it > means. OK -- I don't want to claim that only my questions are interesting! [AS] > >New born infants presumably cannot do this. Later on many of them can. > >What exactly happens in between? > > > >Now there's a question with real substance. > [SF] > I think they learn to think about infinite sets when they learn to count. There is definitely a transition between first of all learning to count and answer questions about "how many?" and solve simple problems about concrete sets of objects and then later grasping that in principle the counting can go on forever, and the set of numbers is infinite and can be thought about reasoned about. Just saying when then learn all this does not explain what the learning processes are. I've argued elsewhere that there are far more transitions than most math teachers are aware of and that's partly why so much maths teaching is unsuccessful: the primary school teachers are unable to diagnose and debug cases where something goes wrong in the learning, so children start to think it's all because they are stupid. [SF] > Concerning transfinite, I think that they don't learn it at all unless > they are taught to. Nobody taught the first people who thought about it! But I guess you are right that the vast majority of people never think about it, and those who do make the transition only when prompted by some sort of teacher (or a book, etc.). But it still isn't obvious what is going on inside them when that happens (Hilbert might have said it was obvious, namely they were introduced to a formal system and they learnt to think about it.) Aaron