[FOM] Feasible and Utterable Numbers

[V.Sazonov@csc.liv.ac.uk]

Quoting Karlis Podnieks <Karlis.Podnieks at mii.lu.lv> Thu, 03 Aug 2006:

Dear Karlis,

Yes, I know the paper of Rashevsky (Russian geometer, who does not 
know) "On the dogma of the natural numbers":

http://www.philosophy.ru/library/math/rashevski.html

I do not know whether there exists an English version. It is quite 
thought provoking, but do not suggest any formalism, in contrast with 
the paper of Parikh (JSL 1971).


> 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),


Yes, we should not confuse these concepts. Using "feasible" for 
"utterable" is just misleading.


> because, if there is a set of 1000 members, then there is also the set of
> all subsets of it.


Is it? In which sense if not in imaginary/mathematical? In our physical 
world we have the strings

000 ...  00 (one thousand of zeros)
111 ...  11
0101 ... 01 (alternating)

We can also toss the coin one thousand of times. Do that again, and again.

But in which sense will we get ALL these binary strings (of the length 
1000)? What does it mean ALL? Is this set of binary strings anything 
better than the continuum (whose precise cardinality is non-definite)? 
I already wrote on constructive vs. "arbitrary" finite binary strings 
(in the context of Bounded Arithmetic and in relation with an 
independence statement closely related with P=?NP). Some gaps in the 
above "finite" set are probably possible like in the continuum (due to 
its unknown cardinality). That is, axioms, probably, cannot grasp this 
"finite(?) and discrete continuum".


Etc. - all numbers (i.e. expressions) used in
> combinatorics must be "utterable".

What means "used"? Say, "quantified over"? We need to have a formalism 
for reasoning on such numbers. Then it is highly questionable that it 
will quantify over "utterable" numbers only if the language of terms 
denoting these numbers is as poor as exponential polynomials.

>
> Thus, couldn't the "system of exponential expressions" serve as a model of
> this more complicated structure?


Why only exponential? Why in so poor language?


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?

This is in the traditional style of complexity theory approach. But if 
you will restrict yourself to expressions of feasible size then formal 
consideration of feasible numbers becomes inevitable. In fact, this 
kind of feasibility may be considered as a foundational approach to 
complexity when instead of counting how much of computational resources 
are necessary for solving a task we declare some too complex 
computations as infinite. For example, 2^1000 is postulated 
(axiomatically) as the infinity.


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.

These ways are rather closely related than different. See my notes 
above on constructive vs. non-constructive finite binary strings in the 
framework of BA. (Compare constructive with "utterable"!) As to recent 
discussion on equivalence classes of terms up to (feasibly) provable 
equality, how can we ever prove that the corresponding relation is 
transitive without invoking the closure of feasible numbers under 
successor (which are bounded by 2^1000)? Appropriate formalisation of 
feasible numbers seems to be the *root* for all other related 
approaches and considerations (such as on utterable numbers). And the 
structure of feasible numbers (and feasible binary strings) is not so 
trivial and even very surprising (like there were surprising the 
counterexamples in Analysis). Please look at the formalisation in

http://www.cs.nyu.edu/pipermail/fom/2006-February/009746.html


All the best,

Vladimir Sazonov


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