[FOM] Closure under addition

[Vladimir Sazonov]

Arnon Avron wrote:
> It is beyond me how is it possible for our Real World to be closed
> under addition and not under multiplication or even exponentiation.
> Thus 2^1000 is the output of the following simple program that 
> need only closure under addition:
> 
>    n:=0 x:=1
>    Until n:=1000 do x:= x+x n:=n+1 od
> 
> What can the meaning of "closure under addition" possibly be if
> the above program (requiring just 2000 additions) is not executable
> (according to Sazonov)?

Dear Arnon,

This is just the question which should be asked!
The answer is both very simple and somewhat tricky.

You actually introduced the new operation f(x)=x+x, that is,
abbreviation of the term x+x. Here we should be very careful
with such kind of things.

The mechanism of abbreviations is not something what should be 
selfevidently allowed in this situation. It can have some influence
on the "world" which we are describing, i.e., if we will use such
abbreviations without appropriate caution we will actually describe
some other "world", different from the intended one. The intended
world should consist only of feasible numbers which are surely < 2^1000.
If we have only 0, 1 and +, but no abbreviating mechanism then we cannot
"logically" reach 2^1000.

You may like this or not, but if we want to formalize the feasibility
concept appropriately we should chose adequate tools. (Watchmaker do
not use sledge-hammer.)

The goal is NOT to find new foundations of mathematics, at least
this is not the primary or the current goal. A rigorous approach
to what is feasible computability, or the like - this is the goal.
This approach is discussed and *formalized* in detail in my paper
V.Yu.Sazonov, On Feasible Numbers, in: Leivant D., ed., Logic and
Computational Complexity, LNCS Vol. 960, Springer, 1995, pp.30--51.
Some simple proof-theoretical considerations are crucial here.

The feasibility concept and related details are somewhat difficult
to explain because the topic is still too unusual. People usually
even do not expect that there may be anything mathematically precise
here, and that speculations are the only possibility.


Vladimir Sazonov