[FOM] Feasible and Utterable Numbers

[Karlis Podnieks]

----- Original Message ----- 
From: <V.Sazonov at csc.liv.ac.uk>
To: "Foundations of Mathematics" <fom at cs.nyu.edu>
Cc: <V.Sazonov at csc.liv.ac.uk>
Sent: Wednesday, August 02, 2006 11:50 AM
...

Thank you very much, Vladimir, for your response.

The vision behind my attempts to initiate this discussion comes from the 
1973 paper "On the dogma of natural numbers" by Pyotr Konstantinovich 
Rashevsky (translated also as Petr, or Rashevskii) - already mentioned on 
the FOM list (http://www.cs.nyu.edu/pipermail/fom/1998-April/001825.html).

1) The traditional natural number system (as defined by the axioms of PA, or 
ZF) is not an exact copy of any real world structure. Only small initial 
segments of this system can be regarded as exact copies of real world 
structures. Already the "set" of elementary particles contained in a 
macroscopic body behaves in a more complicated way than can be described by 
"iterations of the successor function".

2) So, let us search for a "more adequate" arithmetic. For large numbers, 
this arithmetic must yield a more complicated structure than "iterations of 
the successor function". The number 2^1000 must be "feasible" in this 
arithmetic (or, better - "utterable", as proposed by Mirco Mannucci), 
because, if there is a set of 1000 members, then there is also the set of 
all subsets of it. Etc. - all numbers (i.e. expressions) used in 
combinatorics must be "utterable".

Thus, couldn't the "system of exponential expressions" serve as a model of 
this more complicated structure? To reveal this structure, we must restrict 
our logic in such a way that proving of most "non-observable facts" becomes 
impossible.  For example, the expression 2^1000 is "easily utterable", it 
can be represented as 2*2*...*2 (1000 times), but not as "iterations of the 
successor function".

The first purely mathematical problem that arises under this approach: how 
complicated is comparing the numerical values of two exponential expressions 
of size n? I tried to propose it in my posting 
http://www.cs.nyu.edu/pipermail/fom/2005-December/009504.html. According to 
two very prominent complexity theory experts, this problem is not yet 
solved.

Bounded Arithmetic, where ALL sufficiently large numbers are qualified as 
unfeasible, represents a different way of thinking.


My best wishes,
Karlis Podnieks