PDF version of this paper
This paper is published in the the online journal, Philosophy of Mathematics
Education,
number 22 November 2007.
Mathematical
Infinity and Human Destiny Video---transcript
Related Foundations of Mathematics (FOM) postings
Formalizing objective mathematics
What is Mathematics About?
Paul Budnik
Mountain Math
Software
paul@mtnmath.com
Abstract
As the Platonic philosophy of mathematics is increasingly being
questioned, computer technology is able to approach Platonic
perfection in limited domains. This paper argues for a mathematical
philosophy that is both objective and creative. It is objective in
that it limits the domain of mathematics to questions that are
logically determined by a recursively enumerable sequence of
events. This includes the arithmetical and hyperarithmetical
hierarchies but excludes questions like the Continuum Hypothesis.
This philosophy is creative in recognizing that Gödel's
Incompleteness Theorem implies one can only fully explore this
mathematics by considering an ever increasing number of
incompatible possibilities without deciding which is correct. This
is how biological evolution created the mathematically capable
human mind.
Introduction
Mathematics began with counting and measuring as useful procedures
for dealing with physical reality. Counting and measuring are
abstract in that the same approach applies to different situations.
As these techniques were developed and refined, problems arose in
connecting highly refined abstractions to physical reality. The
circles that exist physically were never the same as the ideal
geometric circle. The length of the diagonal of an ideal square
could not be expressed in the standard way that fractional
numerical values were defined as the ratio of two integers.
Mathematical thought seemed to be creating an abstract reality that
could never be realized physically.
Plato had a solution to this problem. He thought all of physical
reality was a dim reflection of some ideal perfect reality.
Mathematics was about this ideal reality that could be approached
through the mind. The difficulties with connecting mathematical
abstractions to physical reality often involved the infinite. It
takes a continuous plane with an infinite number of points to
construct the ideal circle or diagonal of an ideal square. Plato's
ideal reality seemed to require that the infinite exists. The idea
that infinite mathematical abstractions are an objective Platonic
reality became the dominant philosophy of mathematics after Cantor
seemed to discover a complex hierarchy of infinite sets.
This hierarchy has its origins in Cantor's proof that there are
`more' reals than integers. Set A is larger than set B if one
cannot define a map or function that gives a unique member
of B for every member of A. This is fine for finite
mathematics where one can physically construct the map by pairing
off members of A and B. It becomes problematic for infinite sets.
If A is larger than B it is said to have larger cardinality than B.
The smallest infinite set has the cardinality of the integers. Such
sets are said to be countable.
Problems with Infinite Sets
The definition of cardinality creates problems because it depends
on what infinite maps are defined in a mathematical system. Formal
mathematical systems are, in effect, computer programs for
enumerating theorems1 and thus can only define a countable
number of objects. Because all possible maps from integers to reals
are not countable, no formal system will contain all of these maps.
Thus we have the paradoxical Löwenheim Skolem Theorem. This
says that every formal system that has a model must have a
countable model. Thus no matter how large the cardinals one can
define in a formal system, there is some model of the formal system
in which all these cardinals can be mapped onto the integers.
However this cannot be done within the system itself. But when one
looks at the system from outside one can easily prove this is true
because a formal system is a computer program for enumerating
theorems. Every proof that some set exists comes at a unique finite
time and thus the collection of everything that provably exists is
countable.
A major question about the hierarchy of cardinal numbers is whether
the reals are the smallest cardinal larger than the integers. The
conjecture that this is true is called the Continuum Hypothesis. It
has been proved that both the Continuum Hypothesis and its negation
are consistent with the standard axioms of set theory. Thus the
question can only be settled by adding new axioms and there is
nothing remotely close to agreement about how to construct such
axioms. On the contrary there is increasing doubt as to whether the
Continuum Hypothesis is true or false in any objective sense.
Solomon Feferman, the editor of Gödel's collected works,
observed:
I am convinced that the Continuum Hypothesis is an
inherently vague problem that no new axiom will settle in a
convincingly definite way. Moreover, I think the Platonic
philosophy of mathematics that is currently claimed to justify set
theory and mathematics more generally is thoroughly unsatisfactory
and that some other philosophy grounded in inter-subjective human
conceptions will have to be sought to explain the apparent
objectivity of mathematics[4].
Alternative Philosophies
The Platonic philosophy of mathematical truth is dominant but not
universal. Constructivism demands that all proofs be constructive.
It disallows proof by contradiction[1]. The constructivist
treats only those mathematical objects that he knows how to
construct as having an objective mathematical existence. Social
constructivism has recently been applied to mathematics[3]. This
approach sees mathematics as a fallible social construction that
changes over time. That is an accurate appraisal of the history of
mathematics.
The dominant Platonic philosophy and the extreme form of social
constructivism are at opposite ends of a spectrum. In Platonic
philosophy there is only absolute truth that must be discovered. In
extreme social constructivism all truth is relative to some
cultural group that creates and recognizes `truth' through a
cultural process.
Constructivism sits between these extremes. It accepts constructive
proofs as being absolute but only allows truth values to be
assigned to propositions for which there is a constructive proof.
It rejects the idea that all valid mathematical questions must be
objectively true or false.
Rules in some form are a common element in all these approaches.
Mathematics based on a Platonic philosophy depends on formal
systems which are precise rules or algorithms (in effect computer
programs) for enumerating provable theorems from a set of assumed
axioms. Constructivists use similar formal systems with the
elimination of proof by contradiction. Social constructivism
emphasizes that real proofs are never carried out in complete
formal detail, that there are many errors in published work and
that there is no agreement about the fundamental axioms of
mathematics. This suggests that a social process is the primary
element in determining accepted mathematical truth at a given
period of time. Nonetheless social constructivism depends on the
"rules of the game" as providing a foundation for their philosophy.
If there were not rules that could be enforced with some, albeit
imperfect, consistency in a social milieu there could be no theory
of social constructivism.
Creativity Versus Objectivity
Platonic philosophy ignores the marvelous creativity of our
universe. Reproducing molecules have evolved to the depth and
richness of human consciousness and created the mathematically
capable human mind. One can only gasp in dumbfounded wonder at the
miracle of it all. Social constructivism minimizes the connection
between objective physical reality and mathematics. It sees
mathematical creativity is somewhat or mostly arbitrary like many
cultural practices seem to be. Is it possible to square this circle
with a philosophy of mathematics that integrates aspects of these
two philosophies to produce a creative philosophy of mathematics
rooted in the objectivity of physical reality and yet open to the
astounding creativity that characterizes the human condition? I
believe this is the direction the philosophy of mathematics should
pursue.
Finite mathematics is objective because we can physically build at
least some of what it talks about. Among the finite objects we can
construct are precise sets of rules in the form of computer
programs. One element common to all approaches to the philosophy of
mathematics described here can be made, through technology, to
approach the absolute perfection of Platonic philosophy. The
execution of computer programs, in contrast to semi-formal
mathematical proofs, obey a rigorous set of rules (defined by the
characteristics of the machine they are running on) with something
approaching absolute certainty. We cannot construct a perfect
circle but we can compute the ratio of the circumference to the
diameter of the perfect circle, pi, to a million or more decimal
places with a very high certainty that we have done it correctly.
The same is true for the diagonal of the perfect square. We can
write a program that could, if it were possible for it to run
forever with no errors, eventually output each digit of pi or
square root of 2.
There is a basis in physical reality for the perfection (or
something very close to it) that Plato first described. However,
when we move beyond finite questions and procedures, things become
more ambiguous. This first happens in mathematics when we ask if
some recursive property is true of all integers. To be recursive
the condition must be verifiable in a finite number of finite
operations for each integer. The ability to verify the condition
for each integer does not allow one to determine the
question for all integers. Such questions are cultural
creations. There is no physical reality that embodies the solution.
Yet such questions are logically determined by a recursively
enumerable set of events i. e. by a set of events that can be
output by a single computer program that runs error free forever
and has access to unlimited storage.
One can of course argue that the universe is not infinite or
potentially infinite and thus such questions do not have a
connection with our physical reality. Brian Rotman, a social
constructivist, has written a book objecting to the idea of
potential infinity[5]. We can never know if the universe is
potentially infinite, but it would be hard to prove this is not the
case. Throughout history, theories of the universe have given a
limit to its size. Those limits have repeatedly been vastly
expanded. Cosmology is, of necessity, a highly speculative science.
It projects what we think we understand about physical reality over
vast distances and epochs of time using very limited information.
The existence of ultimate limits to the size of the universe
will be an open question for the foreseeable future even as the
dominant cosmology confidently quotes its estimate of the size of
the universe.
Because of this uncertainty and more importantly because of the
practical value of proofs about properties of all integers, I
assume such questions are meaningful and objectively true or false
even though there exists no general method for deciding them. This
is where I part company with both constructivism and social
constructivism. On the other hand I do not come remotely close to
embracing the hierarchy of infinity in the Platonic philosophy of
mathematics. For me infinity is deeply connected to the creative
evolution over time that characterizes biological evolution and is
the richest and most interesting aspect of existence that I know
of.
Objective Mathematics
Questions about all integers have a unique existential status with
their tenuous connection to physical reality. On the one hand they
are logically determined by a recursively enumerable sequence of
events. They can be falsified by counter examples. However there is
no general way to determine if they are true. Gödel's
Incompleteness Theorem established this. Gödel proved that any
system that is powerful enough to embed any computer program (or
equivalently embed the primitive recursive functions) must be
incomplete. In particular such formal systems could not prove their
own consistency unless they were inconsistent.
The consistency of any formal system is equivalent to the halting
problem for some particular computer program. (The halting problems
asks will a computer program, with access to unlimited storage and
able to run error free forever, eventually halt.) Similarly all
integers satisfy some recursive property if and only if some
particular computer program never halts. In the former case we can
program the computer to enumerate every theorem of the formal
system and test each theorem against all previous theorems. If a
contradiction is discovered the program halts. Otherwise it runs
forever. In the latter case we program the computer to test the
condition for each integer in succession and halt if and only if
the conditions fails for some integer.
The question does a computer have an infinite number of outputs has
an even more tenuous connection to objective reality then does the
halting problem. The latter question can be falsified by a finite
event, the former cannot. To prove a program has an infinite number
of outputs requires some form of induction. The proof can be
trivial. A program might produce an output and then return to
exactly the same state it had before the output was generated
implying it will loop forever continually producing new outputs.
But no finite event can establish or contradict this proof.
How far do we take this process? What is objective mathematics? It
turns out that much of set theory is about questions that are
determined by a recursively enumerable sequence of events. The
arithmetical hierarchy includes all questions defined by a
recursive relationship and a finite number of existential and
universal quantifiers over the integers. This hierarchy is
equivalent to the series of questions does a computer have an
infinite number of outputs, does it have an infinite number of
outputs such that an infinite subset of these are programs that
themselves have an infinite number of outputs etc. The nth question
in this hierarchy asks does the computer have an infinite number of
outputs and infinite subset of which satisfy the n-1 condition in the hierarchy. A single computer
program can nondeterministically2 enumerate all events
at any level in this hierarchy by simulating what all computer
programs do for all time. To enumerate all computer programs take
the programming language for any Universal Turing Machine3
and generate all possible finite sequences in that language. Then
nondeterministically simulate each of these programs to enumerate
what every computer program will do at every point in time.
Even some questions that require quantification over the reals are
determined by a recursively enumerable sequence of events. For
example consider a computer program that accepts an integer as
input and outputs either 0 or another computer program with the
same definition as itself. We can apply a sequence of integers to
such a program. The first integer is applied to the base program.
If we get 0 we do nothing and say the path terminates. Otherwise we
apply the next integer in the sequence to the computer program that
was previously output. We keep doing this for every integer in the
sequence until and unless we get a zero output. If applying every
sequence of integers to the base computer results in a terminated
path after some finite number of steps the original base computer
program is said to be well founded.
Asking if a computer program is well founded requires
quantification over the reals. Every question in the
hyperarithmetical hierarchy is equivalent to the question is a
particular computer program well founded. Yet each such question is
determined by a recursively enumerable sequence of events. A single
program can nondeterministically do what every computer program
will do for every integer input. This includes all the events that
determine if a computer program is well founded.
The property of a computer program being well founded is
impredicative. Properties defined in terms of all reals or all
infinite sequences of integers can be circular because they can be
used to define new reals. This is an issue because such circular
definitions have, in the past, led to contradictions in
mathematical systems. Claiming that some impredicative definitions
must be objectively true or false crosses a major boundary. None
the less I think a computer being well founded is an objective
property with important practical significance.
We can attribute a limited form of objectivity to any question
logically determined by a recursively enumerable sequence of
events. Everything that determines the outcome could happen in a
finite but potentially infinite universe. This definition separates
the Continuum Hypothesis (not objectively true or false) from the
question of whether a computer program is well founded. However it
does not constrain objective mathematics to a particular set of
propositions.
A Creative Objective Philosophy
A philosophy of mathematics must deal with two opposing forces.
Computer technology allows us to create, in limited ways,
structures that can approach the ideal perfection of Plato's
philosophy. One can never eliminate all possibility of error but,
in limited domains and with enough resources, the error rate can be
made arbitrarily small. Today's computers perform billions of
operations a second with rare hardware failures. Application and
even operating system program bugs are far more common but the
basic hardware is extremely stable.
Simple programs carefully reviewed can be error free. Complex
programs are another matter. However what they produce can
be made relatively error free. The largest computer chips today
have hundreds of millions of switches and can only be designed with
the aid of computer programs. Those programs are not error free but
the entire design process allows one to produce a chip that
ultimately is error free. Furthermore one must be able to detect
all manufacturing faults in every chip produced. Thus the computer
chip must be designed to make such verification possible. A limited
form of Plato's heaven exists today in the engineering labs of
Intel and AMD.
The opposing force is Gödel's Incompleteness Theorem and its
implications. The hope that there can be a precise set of rules
that determine all mathematical truth has been dashed forever.
There can be no general solution even to a question as basic as the
halting problems for computers. For me this is a reflection of the
creative reality of our existence. One cannot determine all
mathematical truth, even in a potentially infinite universe, but
one can explore all of it in such a universe. If we insist
on a single approach to mathematics we will inevitably run up
against a Gödelian limit. This will not be a fixed limit or
specific event. Rather it will be never ending progress that
continually generates new results. However the collection of all
these results will be subsumed in a single mathematical truth that
we will never discover or explore.
If, on the other hand, mathematics becomes a divergent process that
continually explores ever more possibilities, then there is no
limit to the mathematics we may explore. This may seem as fanciful
as Plato's heaven or a measurable cardinal but a divergent process,
biological evolution, created the mathematically capable human
mind. Evolution on this planet is enormously diverse. Over a vast
expanse of time this diversity has increased enormously from the
first reproducing molecules to today's biosphere. It is a safe bet
that without this diversity, the enormous complexity and enormous
depth of the human mind could never have evolved.
This suggests to me that the stakes are much higher than what
happens with our mathematical knowledge. The hierarchy of
mathematical truth involves ever more complex levels of abstraction
and self reflection. The evolution of the mathematically capable
human mind and the evolution of the depth and richness of human
consciousness both seem to depend in part on the rich and subtle
powers of abstraction and self reflection that uniquely
characterize human thought and awareness. We are entering a unique
period in biological evolution. Evolution has become, through us,
conscious of itself and is acquiring the tools to control its
future destiny. Understanding the role of diversity in not limiting
the potential of future evolution may be crucial to what we can
become [2].
A Cultural Prescription
Ironically the key to expanding mathematical diversity lies in
embracing the technology through which humanity has obtained
something approaching Platonic perfection. One must turn the
foundations of mathematics into an experimental science embracing
computer technology as an essential research tool just as every
other major branch of science has done.
There is a cultural bias in mathematics to come up with the
simplest most elegant approach possible. Most mathematical research
is done using pencil, paper and the mathematician's mind, limiting
the complexity that can be dealt with. Computers may be used to
replace pencil and paper but they are rarely used as a research
tool or to verify proofs. Of course elegance and simplicity are
worthy goals, but one must not insist on them to the point of
failing to deal with the enormous complexity that the foundations
of mathematics suggests we can explore. The strength of a formal
system is determined, in large measure, by the ordinals definable
within it. Notations for recursive ordinals and recursive
operations on these notation can be explored experimentally using
computers. Recent history of science suggests that leveraging human
intuition with the combinatorial power of computers will lead to
results far beyond what the unaided human mind is capable of. I do
not think the foundations of mathematics will be an exception.
References
- [1]
- L. E. J. Brouwer.
Intuitionism and Formalism. Bull. Amer. Math. Soc.,
20:81-96, 1913.
- [2]
- Paul Budnik. What is and what will be:
Integrating spirituality and science. Mountain Math
Software, Los Gatos, CA, 2006.
- [3]
- Paul Ernest. Social Constructivism as a
Philosophy of Mathematics. State University of New York Press,
1998.
- [4]
- Solomon Feferman. Does
mathematics need new axioms? American Mathematical
Monthly, 106:99-111, 1999.
- [5]
- Brian Rotman. Ad Infinitum. Stanford
Univeristy Press, 1993.
Footnotes:
1 It is tedious but straightforward to
go from the axioms of a formal system such as set theory and the
laws of logic to a computer program that would enumerate every
theorem provable from those axioms and laws of logic. This however
is not a practical way to generate new mathematics because most
theorems would be trivial.
2A nondeterministic computer program
can simulate an infinite sequence of computer programs by
simulating the first program for one time step, followed by
simulating the first two programs for two time steps, followed by
simulating the first three programs for three time steps, etc.
3 A Universal Turing Machine is a
computer that can simulate any computer that it is possible to
build. It can be a simple device, but it requires access to
unlimited storage.
File translated from TEX
by TTH, version 3.77.
On 22 Mar 2007, 10:49.