|
|
In article <1146347529.948840.147510@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
david petry <david_lawrence_petry@xxxxxxxxx> wrote:
>The way I have handled this is to introduce a notion of
>"accessibility", which is not a binary notion but rather a continuous
>one. Very large numbers are less accessible than small ones. At some
>level of precision for the accessibility variable, very large numbers
>may become indistinguishable from infinity. I just see no sense in
>asserting the existence of some cutoff between what is accessible
>(feasible) and what is not.
Interesting. To what extent have you formalized your notion of
accessibility? Is this part of the foundational work you were doing as a
graduate student before you abandoned (or were forced to abandon?) it?
If Sazonov's approach does not strike the right chord with you, what about
Simpson's subsystems of second-order arithmetic? The first chapter of his
book is downloadable at http://www.math.psu.edu/simpson/sosoa (though I
should mention that it's fairly heavy going if you're not a mathematician).
Here's a quick summary. A subsystem of second-order arithmetic is a set
of first-order axioms, whose "intended model" is a structure with two sorts:
natural numbers, and sets of natural numbers. The mention of sets may raise
a red flag with you, but the sets in question here are far tamer than in
what you've been calling "Cantorian set theory," because one is not allowed
to ascend to (for example) sets of sets of naturals, or to speak directly of
uncountable sets.
One gets different systems depending on how many axioms one wishes to
introduce. Simpson studies five systems, of strictly increasing strength.
The lowest one is RCA_0, then comes WKL_0, then ACA_0, then two more that
I find a little more arcane. The "R" in "RCA_0" stands for "recursive,"
and it is weak enough that one can get a model for it by taking only the
*computable* sets of integers instead of *all* sets of integers.
Intuitively, this means that anything you can prove in RCA_0 can be
interpreted as being a statement about computable sets only. This would
seem to be promising for anyone who doubts the meaningfulness of assertions
about sets of integers that aren't computable.
A surprising amount of ordinary mathematics can be formalized in RCA_0.
Perhaps the simplest famous theorem that is beyond the reach of RCA_0 is
Brouwer's fixed-point theorem. For that you need to ascend to WKL_0 (WKL
stands for the weak Koenig lemma). Brouwer's fixed-point theorem is used a
lot in theoretical economics, so this makes for some interesting discussion
about whether "noncomputable things" can be "useful."
The arithmetic part of ACA_0 is equivalent to first-order Peano arithmetic
(PA), and in informal discussion one can conflate the two without much
danger. As you probably know, most of "applied mathematics" can be
captured in PA.
There are two potential problems you might have with RCA_0 (assuming you
don't mind throwing out Brouwer's fixed-point theorem and such). The first
is that there is no notion of feasibility or accessibility built in. So
RCA_0 merrily talks about outrageously hard-to-compute recursive functions
like the busy beaver. The second problem you might have is that RCA_0 is
based on classical logic, including the law of the excluded middle. I don't
know how you feel about nonconstructive existence proofs, like the proof
that an elliptic curve over Q has finite rank (there is no known algorithm
for computing said rank).
If you're O.K. with classical logic but want feasibility built in, then
there are so-called systems of bounded arithmetic. The most accessible
introduction to these systems, in my opinion, are written by Stephen Cook.
You can download materials from his homepage
www.cs.toronto.edu/~sacook">http://www.cs.toronto.edu/~sacook
There are some very interesting connections to computational complexity
theory. My personal opinion is that any eventual proof of P != NP will
borrow ideas from the study of bounded arithmetic.
--
Tim Chow tchow-at-alum-dot-mit-dot-edu
The range of our projectiles---even ... the artillery---however great, will
never exceed four of those miles of which as many thousand separate us from
the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
|
|