[FOM] RE: Feasibility

[Vladimir Sazonov]

Quoting Matt Insall <montez at fidnet.com>:

> <<Say, postulate that (i) the "set" F of feasible numbers is
> closed under +1 (and even under +), once there is no clear
> boarderline between feasible and non-feasible, but that
> (ii) 2^1000 is not in F. >>
> 
> 
> Thank you for the reference.  I have not yet read all of it, but it seems to
> me that the choice of 2^1000 for a non-feasible number is too specific for
> the purposes you describe.  

The point is that this is more or less *minimal* choice of 
non-feasible number for which (i) and (ii) are consistent 
(in a sense which should be clearly defined). 2^100 may be 
also OK. 

Why do you not just have a symbol (a parameter,
> say K) in your language to stand for ``the ditinguished identifiably
> non-feasible number''?  In this setting, I think your axioms would be
> 
> (i)   If n is feasible, then n+1 is feasible.
> (ii)  K is not feasible.

If K is any concrete number (having a short denotation like 2^1000), 
then for the case of sufficiently small K this theory will be 
contradictory. 

The less is such K the more problematic is consistency of the 
resulting axioms and the more these axioms correspond to the 
"real" idea of feasibility. 

If K is just a symbol, then it could denote what is usually called 
non-standard number. This is quite usual and not so problematic 
as a "concrete" number K. 

> 
> But I do not see the benefit in calling such a K, or any other specific
> natural number, ``inifnity''.

If there is "set" F of (feasible) numbers < K which is closed under 
successor then this F, and therefore K,  may be naturally called 
infinite. 

Let me repeat that the idea of considering some F closed under 
successor (and probably also under + and *) and still upper 
bounded by some concrete K was seemingly developed first by 
Rohit Parikh. He elaborated this in the framework of PA (extended 
with such F) with the ordinary FOL as the underlying logic. But 
in this case K was too big (something like to exponential tower 
of the hight about 2^1000). It was rather unclear how to decrease 
this (too rough) upper bound K for F to something like 2^1000. 
This proves to be possible, but the price is some kind of 
restriction of underlying logic FOL with quite unusual consequences. 
These consequences and the price are probably most interesting 
subjects to discuss (although my current circumstances will hardly 
allow me to reply regularly). 

Best wishes, 

Vladimir



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