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