[FOM] Gödel, Darwin and creating mathematics
Paul Budnik
paul at mtnmath.com
Thu Jul 1 16:47:07 EDT 2010
Gödel's Incompleteness Theorems suggests a philosophy of mathematical
truth that is both objective and creative. Logically determined
statements, like the consistency of a formal system, are objectively
true or false even though there can be no general process for deciding
this. Emil Post reached a similar conclusion over 60 years ago: "The
conclusion is unescapable that even for such a fixed, well defined body
of mathematical propositions [a formulation of the recursively
enumerable sets], _mathematical thinking is, and must remain,
essentially creative_." (from the published lecture "Recursively
enumerable sets of positive integers and their decision problems"
www.projecteuclid.org/euclid.bams/1183505800 ).
I discussed objective mathematics in
www.cs.nyu.edu/pipermail/fom/2010-May/014792.html This posting focuses
on the creation of mathematics. My assumptions are that physical reality
is always finite but could be potentially infinite and the laws of
physics are recursive.
In the light of Gödel's work, these assumptions may seem to be an
obstacle to the evolution of a mind capable of developing mathematics.
Gödel established limits on what mathematics a recursive process can
decide, but not on what it can explore. It is straight forward to write
a single nondeterministic TM program to enumerate all the axiom systems
definable in a formal language and to deduce all the theorems decidable
in each of these systems. While this is not a practical way for us to
create new mathematics, biological evolution did something a bit like
this in evolving the mathematically capable mind. That process involved
an immense diversity of life over billions of years.
Our sense of the innate truth of fragments of mathematics is an
evolutionary legacy. It evolved because there are modes of thought that
consistently lead to accurate conclusions. These modes of thought were
refined and formalized through cultural evolution. This suggests two
questions. How close are we to the limits of what is achievable with our
evolutionary legacy? That is how far can we confidently extend our
ability to decide questions about objective mathematics? The second
question is what happens when we approach the limits of what is
achievable from that legacy?
I suspect the answer to the first question is that we are far from those
limits in part because computers have not been used as a research tool
for expanding the foundations of mathematics. They are used for
automated theorem proving and proof verification, but not to explore and
understand the ordinal hierarchy that is essential to expanding the
logical power of mathematics. There is a combinatorial explosion of
complexity in developing the ordinal hierarchy at the level of the
recursive and countable admissible ordinals, where it is directly
connected to recursive processes and can be investigated using computer
experiments. Although currently the most powerful expansions of this
hierarchy come from large cardinal axioms, I suspect that, eventually,
more powerful results will be obtained through a mastery of the innate
complexity of the ordinal hierarchy at these lower levels. At some point
it becomes impossible to manage this complexity without the aid of
computers. For more about this see my page on the ordinal calculator,
www.mtnmath.com/ord .
Appel and Haken pioneered using computers to manage complexity in
mathematics over 30 years ago in their proof of the four color theorem.
They used the computer to deal with the combinatorial explosion of
special cases that had to be considered. The complexity of their proof
justified a careful process of acceptance, but the use of computers
should have been recognized as a powerful new technique for dealing with
complexity and not seen as a possible reason for rejecting the proof.
My answer to the second question is that we will eventually need to
return to the nondeterministic search of biological evolution. This will
require following an ever increasing number of paths as resources become
available. Unlike biological evolution, this increasingly divergent
search will be guided by a deep understanding of which paths may be
worth pursuing. Under my assumptions about physical reality, any
approach limited to a fixed finite number of alternatives will run up
against what I call a Gödel limit. Continual progress can be made
defining more powerful axiom systems into an unbounded future but the
entire sequence of correct results will be theorems provable from a more
general axiom that will never be considered or explored.
Paul Budnik
www.mtnmath.com
More information about the FOM
mailing list