[FOM] Feasible and Utterable Numbers

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

This is the answer to Charles Silver and Mirco Mannucci

Quoting Charles Silver <silver_1 at mindspring.com> Mon, 07 Aug 2006:

> 	I believe I understood your various distinctions, and of course I
> know the difference between modifying the logical versus the non-
> logical features of your theory.

By the way, quantifier rules and therefore implicit abbreviating 
mechanisms (due to also cut rule) are considered traditionally as 
logical principles. But once abbreviation of terms allows us to 
introduce non-feasible numbers in an arithmetical theory they serve, in 
fact, as non-logical principles. They have influence on the subject 
matter! So, logics and mathematics are interrelated here.

Since there are many unusual
> characteristics and variants, I am led to an extremely primitive
> question: What makes your theory a theory of some "concept"?   This
> relates to the question of "naturalness".    For example, I could
> make up some non-logical axioms and declare that certain inference
> rules are off limits, but that would not make the resultant theory a
> theory of anything.

Yes, if it is done arbitrarily or randomly.

So, could you please explain--I know this is a
> decidedly primitive question--why "feasibility" is a real concept,
> and also why it seems to resist formalization?

For me it is real (mathematical) concept because it is formalisable.

In a sense the concept of feasible numbers (F) is not worse than the 
ordinary concept of natural numbers (N) based on the abstraction of 
potential infinity. The latter abstraction is actually extremely vague 
idea involving implicitly (complicated iteration of) the idea of 
feasibility. I omit any further supporting comments on vagueness of N. 
Anyway, N was successfully formalised, say by formal systems PRA or PA 
which are quite comfortable to work with. They are sufficiently 
self-contained and quite formal, and we have *developed* a very good 
intuition allowing to work even without explicit reference to these 
formalisms.


Now, let us consider the concept F of feasible numbers (or feasible 
computations, i.e.  only those computations which can happen in our 
real (physical) world. This is a vague concept. But its degree of 
vagueness is much less than that of N which involves iterations of 
iterations ... of vagueness of feasible numbers. N is actually a 
"vagueness of vagueness ... of vagueness". But we have a way how to 
ignore or avoid this vagueness by our formal tools. (This is why we do 
not even notice the vagueness of N. Just do not ask questions on vague 
features of N.) Can we do the same for the sub(semi)set F of N 
consisting of feasible numbers? That is, can we describe F formally in 
any way? Let even approximately, but formally. Say, let us formally 
postulate that

0 in F, F+1 subset of F, F+F subset of F, 2^1000 is not in F.

The latter statement should hold because 2^1000 is definitely non-feasible.

The closure property of F under successor is postulated because it 
looks strange to assert that there is a last feasible number n such 
that n+1 is already non-feasible. The reason is essentially that why it 
is (traditionally) considered non-natural to assert that N has the 
biggest number. This is our conscious decision about N and F. (And, of 
course, this is not a decision of the God.) We (our predecessors) 
decided that this is mathematically convenient (and this is indeed 
convenient!) and smooth to have a theory of numbers assuming the 
closure under successor (and other operations) despite the fact that 
nobody can count infinitely long.

But are the above axioms on F consistent if the ordinary classical 
logic is assumed for deriving consequences? It proves that we can 
easily (feasibly) derive a contradiction (in much less number of steps 
that 2^1000; see 
http://www.cs.nyu.edu/pipermail/fom/2006-February/009746.html or my 
paper.)

It is in this sense the theory of feasibility is difficult to 
formalise. The ordinary classical logic which served us so well does 
not work! This is against of our intuition. It seems that the above 
axioms on F are true. At least the first attempt of formalising F is 
not successful. Thus, we cannot avoid some restriction of logic. 
Implicitly, the classical logic allows using abbreviation of terms 
which leads to existence of non-feasible numbers like 2^1000 (and even 
to much bigger numbers) and therefore to formal contradiction. Likewise 
in naive set theory where (formally very natural) non-restricted 
comprehension axiom leads to paradoxes, we also should do something 
with the formal rules leading to non-feasible numbers. Thus, 
abbreviating of terms should not be allowed at all, or should be 
restricted in some way. That is all.

After doing that we can look at the formal consequences from the above 
axioms on F. Some of them are somewhat unexpected. (The ordinary formal 
theories also have unexpected consequences. And so what? We are able 
and agree to co-exist with that.) If somebody is unsatisfied with such 
a formalisation of F, they could try to do this better. Anyway, we see 
that there is a possibility to work with F in a mathematical manner, 
and the surprising consequences (like "the World is simultaneously 
discrete and continuous") could be further investigated also in a 
mathematical manner, that is quite rigorously.


> 	Also, according to my intuitions (which may be bad), it seems to me
> that a feasible number should not have a sharp cut-off.

Yes, F is closed under successor and so has no biggest number.

That is, I
> think there should be numbers in between those accepted by most
> people as feasible and much larger numbers considered non-feasible,
> with a lot of numbers in between.   Call these numbers the Betweens.

I do not agree to use here any sociological terms like "accepted by 
most people". Let us accept some formal "rules of the game" (like in 
the case of the ordinary arithmetic or set theory) and decide whether 
they are sufficiently *adequate* for the idea of feasibility or not.

The (semi)set of feasible numbers is extremely vague. But we take the 
style of first order logic presentation as if each number is either 
feasible or not. This is like a non-standard model of arithmetic where 
each number is either standard or not, and there exists neither the 
biggest standard number nor the least non-standard one (nor any numbers 
like your Betweens depending in a way on "acceptance by most people").

Here I tried to use some semi-formal presentation. But you already know 
that everything can be done quite formally.

> But then, the question would arise why the largest number in the
> Betweens is not really non-feasible, and why the least number in the
> Betweens should not be considered feasible.

Even if you still want to think in terms of Betweens, you should 
realise that this "set", as you say, depends on opinions of people and 
therefore is something too vague to assert that it has the largest or 
the least number or to assert anything of mathematical character.

Thanks for your interest, Charles. Unfortunately I should interrupt my 
postings due to lack of time. However, I would like to know (may be for 
a reaction in the future) whether you are satisfied with my answer.


-------
To Mirco Mannucci:

My problem with your postings was that I did not understand well your 
point of view and whether what you suggest is really formalisable. (My 
understanding changed several times.) I am still unsure what do you 
really mean, in particular when you refer to vagueness or the like. 
Probably a full detailed text would be more helpful.



P.S. Thanks to everybody participating in the discussion.

Vladimir Sazonov


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