[FOM] feasibility (was PA Incompleteness)

[Vladimir Sazonov]

On 15 Oct 2007 at 8:03, Feng Ye wrote:

> I am always wondering what will be the answer if 'normal mathematics' is
> replaced by 'mathematics with potential applications in sciences', or
> 'mathematics relevant to this physical universe'. The problem is that all
> current independent propositions are related to fast growing functions, but
> the scope of the physical universe that sciences are dealing with is so
> 'ridiculously small' from the mathematical point of view.

[snip]

> This is related my post last month (an initial post), that
> is, there is a chance that strict finitism is already *in principle*
> sufficient for scientific applications to things within such a small range
> of the universe dealt with by current sciences.


Unfortunately, I am not acquainted yet with your approach. But what I 
see myself are the following possibilities.

1. To consider so called box-arithmetic PA_\Box (I am using Latex 
notation) with the postulated biggest number \Box and with all 
"\Box-recursive" functions in the language and appropriate axioms 
including induction schema. (We can also consider 2nd order version of 
this theory PA^2_\Box.)

For \Box there are two alternatives.

1a. Either to postulate nothing on its value (just like a parameter) so 
that PA_\Box will become, in fact, a theory of polynomial time 
computability (routinely equivalent under appropriate formulation, say, 
to Cook's theory PV), or

1b. To "fix" the value of the maximal number \Box, for example, to be 
sufficiently large "for all our purposes" or to be the upper bound for 
our real universe or just of our current "capabilities". Say, we can 
take that \Box = 2^1000 (or, in the language of PA_\Box having no 
non-restricted exponential, let log_2 \Box = 1000).

See more on this in my papers

A logical approach to the problem "P=?NP", in: MFCS'80, Lecture Notes 
in Computer Science, N88, Springer, New York, 1980, P.562-575. 
(particularly Section 7)

On Bounded Set Theory, 10th International, Congress on Logic, 
Methodology and Philosophy of Sciences, Florence, August 1995, in 
Volume I: Logic and Scientific Method, Kluwer Academic Publishers, 
1997, pp. 85--103 (See the appropriate parts devoted to PA_\Box)

both available from http://www.csc.liv.ac.uk/~sazonov/papers.html


This approach with the biggest number is, however, "against" the 
tradition of mathematics allowing the infinity, say, the continuum (the 
real numbers). Of course, we still can play in this "\Box-game" 
ignoring the idea of (actual or potential) infinity. One such related 
approach is being developed by Andrew Boucher (a member of this list). 
He, however, does not postulate the existence of \Box, taking as an 
axiom of his version of PA the assertion that "either there exist the 
maximal number or not". But as I understand, the alternative that there 
exist no maximal number (giving rise to the usual PA) is, in fact, not 
used in this approach in any serious technical way. (I hope Andrew will 
correct me if I am wrong.) In this sense, his research is (implicitly) 
concerning what can be done in the framework of (even more narrow than) 
a theory of polynomial time computability (i.e. in the framework of 
PA_\Box).

2. Another approach is based on Parikh's formalization of feasible 
numbers and, as I believe, more adequate formalization which I 
mentioned in my recent posting to FOM 
http://www.cs.nyu.edu/pipermail/fom/2007-October/012042.html

Here it is assumed that the "semi-set" (using the term of Vopenka) F of 
feasible numbers contains 0,1 and is closed under +, but is bounded by 
2^1000 (Alternatively, forall n log log n < 10 is postulated what means 
that 2^1024.) This is much more radical approach (which somebody would 
probably call ultrafinitism) which requires some serious reconsidering 
the underlying classical logic (cf. 
http://www.cs.nyu.edu/pipermail/fom/2007-October/012042.html ). This is 
an attempt to rescue infinity (in the form of the closure of F under + 
so that F has no maximal number, although bounded by 2^1000). The idea 
of infinity is a strong mathematical achievement and the instrument, 
say, to deal with continuum, etc. Now we would be interested in a 
feasible version of continuum.

Whatever of these approaches to choose, it is interesting to 
demonstrate that some reasonable part of mathematics is preserved in 
some form despite of all these restrictions. At least, in the real 
practice of application of mathematics everything is done via 
contemporary computers which deal only with numbers (I mean - in unary 
notation!) bounded by 2^1000. By some miracle we are able to 
apply/imitate (at least some fragments of) our "strongly infinite" 
mathematics in so restricted real world of computers. So, as you 
asserted, we can hope that some version of mathematics as a 
("feasible") theory can fit to this world. It is yet highly unknown how 
to do that, but, I repeat, we can probably hope.

On the other hand, it is evident that any such restrictive approach, 
even if successful to some degree, would be probably highly 
uncomfortable for mathematicians, at least at the beginning. I do not 
think that such an "ultra" goal should be stated now or even in the 
future. We should not reject what is already done in mathematics, all 
kind of infinities it uses or could use (such as any kinds of large 
cardinals). I believe that more appropriate and realistic goal is to 
"implant" or "graft" into mathematics the feasibility concept in such a 
way that the usual kind of mathematical reasoning would be completely 
preserved when feasibility is not involved, but when we are interested 
in applications of math to the real world the feasibility concept could 
probably start playing essential role. The approach of Parikh 
("conservatively" extending the ordinary Peano Arithmetic by F - not so 
strongly upperbounded as above) shows that it is possible in principle. 
For example, we could have the traditional set theory ZFC extended 
appropriately by "feasible" semisets (interspersed between the 
"ordinary" sets) so that the ordinary sets and semisets would interplay 
in some interesting and fruitful way.

But for the beginning we could start "playing" with some pure and very 
restrictive theories of feasibility, even if this will look mostly as 
some toy theories, like in the FOM link above.


Vladimir Sazonov

----------------------------------------------------------------
This message was sent using IMP, the Internet Messaging Program.