FOM: counting - feasibility (Reply to Brian Rotman)

[Vladimir Sazonov]

First, a general note.

The concept of feasible numbers is usually rather difficult to 
discuss (or explain) to reach satisfactory mutual understanding.  
I believe that one reason for this are some dogmas (like that 
of standard model of arithmetic or of absolute mathematical 
truth) which prevent understanding and often lead discussion in 
a wrong direction. The other reason is traditionally (for this 
topic) philosophical rather than technical (i.e. mathematically 
oriented) level of consideration.  I strongly believe that the 
best way would be 

PRESENTING A FORMALISM (even if it is only preliminary and not 
very satisfactory for a while) WITH APPROPRIATE INFORMAL 
(PHILOSOPHICAL, RELATED WITH APPLICATIONS, ETC.) 
COMMENTS/BACKGROUNDS ON ITS MEANING. 

(This is essentially my understanding of WHAT IS MATHEMATICS in 
a very general sense.  Cf. also my posting to FOM from Jan 6.  
By the way, I strongly doubt that ZFC may serve as foundation of 
Mathematics understood in this way. I am very interested in 
comments of FOMers on such "definition" of Mathematics.) 

We can dispute on the philosophy behind a formal system as long 
as we want and as fruitful as we could. But the formalism may 
live in a full and relatively independent life as it usually 
happens in real mathematics. 


Brian Rotman wrote:
>
> fom.doc 5/14/98
>
> Patrick Peccatte (FOM 3/18) quotes some passages from my book AD
> INFINITUM ... about reconceptualizing the sequence 1, 2, 3, ... and
> suggests comparing the ideas behind them to those repeatedly expressed
> on FOM by Vladimir Sazonov on the nature of natural numbers. The
> suggestion is interesting. I have a lot of sympathy/solidarity with
> Sazonov's revisionism, his refusal to supress doubts about the orthodox
> understanding of the numbers, his insistence that we try re-think them
> from a distance,

Thanks! But I would characterize my views on Mathematics not as 
revisionstic, but as realistic ones. I believe that feasibility 
concept adds something essentially new (and realistic!) to 
traditional mathematical notion of finitude but not rejects it.  
What I reject and really would like to be revised is 
absolutistic (dogmatic) view on the nature of natural numbers 
and mathematical truth. Such a revision is related rather with 
Philosophy of Math. and does not reject any existing theorems, 
axioms, methods, proof rules, ways of thinking by working 
mathematicians, etc. This opens our eyes for looking new 
possibilities in Mathematics which are not covered even by 
ZFC (and any its traditional extension) usually considered as 
containing "ALL Mathematics". 

but I have a few problems with what he says or maybe
> how he says it.
>
> First, a point of rhetoric: it's not a good idea for Sazonov to attack
> the classical natural numbers or their conceptualization as unclear,
> indeterminate, illusory or unintelligible when it is precisely their
> clarity, determinacy, reality and intelligibility that makes them such
> an attractive, stable and universally accepted object of thought for
> generations of mathematicians.

I essentially agree that it would be safer for me to postpone 
such an attack until others (and, of course, I myself) will have 
sufficiently articulated motivations for that. Nevertheless, I 
never seen satisfactory detailed and contemporary explanation or 
conceptualization of what is the *standard* model of PA (not in 
terms of a set theory like ZFC).  Of course, it is indeed "an 
attractive, stable and universally accepted object of thought".  
But its stability or determinacy is not absolute. It depends on 
our goals or intentions whether we will ignore this 
not-absoluteness (say, to feel ourselves more comfortable and 
stable), or, by some serious reasons, we will doubt on this 
stability and try to find more and more evidence for our doubts.  
Each of us chose what he/she prefers.  Let, for a while, it be 
as it is. Let each one believe in its own God. It is more 
productive to pay, instead, more attention immediately to 
feasibility concept, putting aside (temporary, as soon as it is 
possible at all in this context) the question on whether the 
*pure* idea of standard model is sufficiently meaningful.


He would do better to question their
> claim to be the unique and impossible-to-think-otherwise idealization of
> the small, empirical magnitudes which anchor their meaning. Better, in
> other words, to attack what it means for mathematics to idealize
> palpable reality.

I would say "and formalize" because pure mathematical 
idealization cannot exist alone without some corresponding 
formalization or "apparatus", as you write below. "What it means 
for mathematics to idealize [and formalize! - VS] palpable 
reality" for the case of feasible numbers is exactly what I am 
doing (unfortunately, much less actively than I want).

> Second, designating, as he and others do, a huge `number' such as 2^1000
> as a remote upper bound to some feasible initial section far below it,
> has two problems: it is arbitrary in an unhelpful way

??? Very helpful!

and it is
> conceptually counter-productive.

???

1) On arbitrariness, the question goes
> beyond the obvious why this bound rather than any other, but why the
> deliberate remoteness. Presumably, the idea is to make an unbridgable
> gap between messy empirical questions of length of calculation, proof,
> definition, memory, and so on, and the purely mathematical investigation
> of the feasible numbers one wants to focus on. But doesn't this wash the
> baby out with the bathwater. Surely, such a bound can only do real --
> critical/conceptual/foundational -- work if it is an intrinsic
> construct, if it arises from the properties of the feasible numbers as a
> natural or inherent limit, or at the very least, is causally linked to
> them in some specifiable way. Perhaps Sazonov's loglogx < 10 law is a
> move in the direction of intrinsicality. But, as he gives it, it is
> still arbitrary. Why not some function other than loglog? And why 10? A
> more intrinsic formulation might be loglogx < r where the logarithm is
> taken base r; but then arbitrariness reappears in the choice of r.

Yes, 2^1000 serves *only* as an upper bound to feasible numbers. 
It is arbitrary and non-"inherent limit" as you say, because 
there exists evidently no least upper bound. But the 
corresponding axiom like (experimental law) loglogx < 10 plays 
its role in a good way.  It shows that *any* model for this 
axiom (if we ever could discuss on such unusual models) is much 
more alike to feasible numbers than, say, a model for Primitive 
Recursive Arithmetic where exponential, superexponential, etc. 
are postulated as total functions.  If we postulate that log x 
or loglog x is only bounded function without presenting an 
explicit bound like 10
	(or 9, or even 8, but not, say, 3 for which
	the axiom loglog x < 3 is evidently false on
	feasible numbers; thus 10 or 8 are rather close
	to be "intrinsic" or "exact")
then we also will have some approach to feasibility (this is 
possible in the framework of Bounded Arithmetic which is usually 
also related with the idea of feasibility), but, of course, less 
satisfactory one. Such weaker axiom gives much more rough upper 
bound to feasibility. My goal was to demonstrate truth and 
formal consistency of this stronger axiom loglog x < 10 in a 
reasonable precise sense and to find some consequences of this 
axiom.  They proved to be very unusual and unexpected.  I see 
nothing especially bad in the arbitrariness you mention.  Is not 
e.g. Peano Arithmetic also somewhat arbitrary (incomplete)?  I 
agree that PA is (seems?) more aesthetic. Also I do not say that 
my approach to feasibility is the last word of the science.  It 
is only a second (after and following Rohit Parikh) technical 
and conceptual attempt (I hope, reasonable one).

Of course, all of these may be properly understood only after 
reading the technical formulation and (actually rather simple, 
essentially based on Herbrand theorem) details of consistency 
proof and corresponding discussion in my paper in LNCS 960, 
1995; cf. also my web-page http://www.botik.ru/~logic/SAZONOV/.


2) It
> is misleading and counter-productive

???

if it gives the impression that the
> feasible numbers can be identified with an initial section of the
> classical progression of natural numbers.

Strictly speaking, in my formalization of feasible numbers there 
is no mention of the upper bound like 2^1000 (approx. = 2^{2^10}).  
I use only (base 2) logarithm function over the intended "model" 
of feasible numbers. Thus, there is no explicit statement by 
axioms that this "model" is (isomorphic to) an initial part of 
the "classical progression of natural numbers" (whatever they 
are).  But I can, at least, easily imagine (and even formalize) 
that it is an initial part. I cannot even guess what is 
misleading and counter-productive here.

>From Sazonov's contention (FOM
> 3/27) that feasible arithmetic, as he understands it, has no model in
> ZFC,

Yeas, no model in ZFC universe (whatever the latter is) 
satisfies the axiom loglog x < 10 ( + other more traditional 
axioms of Feasible Arithmetic). I think, there is nobody here 
who does not agree with or does not understand this trivial 
fact. Therefore we should use only some *non-traditional form of 
the axiomatic method*. (Cf. my paper. I think, without 
considering the simple formalism I suggest you may have wrong 
idea on what I am saying informally.) 

I don't think he wants that impression to be given, but I'm not
> clear.

I am also not clear, what bothers you so much.

If he doesn't want the feasible numbers to be identical to an
> initial section of the integers classically conceived, he shouldn't talk
> of 2^1000 as being a bound without qualifying what that is supposed to
> mean and shouldn't talk as as if it were identical to the classical
> number so named. The point is subtle since it bears on the very
> question, namely the meaning of `number' and `finite', that feasibility
> is supposed to be addressing.

It seems the following clarification will help.  I repeat, I can 
present my approach in two ways. 

(1) No *formal* mention of 2^1000 and using, instead, only 
logarithm function.  In this case 2^1000 arises only very 
informally as some imaginary "infinite" or "nonstandard", 
"non-feasible" number which may result from possible 
extrapolation outside feasible "horizon". Moreover, everybody in 
the "corridor of a university" looking on the above double 
logarithm law may ask: "What about 2^1000?".  That is why it is 
difficult to avoid at least informal mentioning this "number" at 
all.

(2) Take, as in Parikh's approach, axioms of, say, Peano 
Arithmetic (in the language containing symbols for primitive 
recursive functions) + some axioms on a new (not participating 
in the induction schema) predicate F(x) for feasible numbers, 
including

	F(0), F(1),
	x < y & F(y) => F(x),
	F(x) & F(y) => F(x+y) and
	F(x) => x < 2^1000.

Parikh used instead of (primitive recursive term) 2^1000 
exponential tower of exponential height

			      2
			     .
			    .
			   .
			  2
			 2
			2	,

just of the height about 2^1000. (This is also primitive 
recursive term.  Note, that the lower hight, even 1000 is 
insufficient for his approach to succeed, i.e. to get "almost" 
consistent theory.) In both these cases (1) and (2) the crucial 
problem consists in appropriate choosing underlying logical 
proof rules. (Say, the ordinary Hilbert style predicate calculus 
makes these axioms contradictory.) This is our payment for 
lowering Parikh's upper bound to much more realistic, "almost" 
exact bound 2^1000. The resulting formal system proves to be 
*feasibly consistent* in the sense that there exists no formal 
proof of feasible length (say, proof written in a book) which 
leads to a contradiction. It is Rohit Parikh who introduced (in 
his paper in JSL, 1971) this, still rather NEW AND UNFORTUNATELY 
COMPLETELY UNEXPLORED IN F.O.M.  UNDERSTANDING OF CONSISTENCY OF 
A FORMAL SYSTEM. (It seems he used the term *almost 
consistency*.) Only much less radical Bounded Arithmetic, which 
by my knowledge was actually started in the same paper of Parikh 
and which is based on the ordinary much more rough notion of 
consistency, have been successfully and extensively developing 
since that time.

Finally, about whether 2^1000 in this context is "identical to 
the classical number so named". I do not know what exactly is 
the classical number so named. We have a name, we know how to 
use it, how to prove some mathematical statements where this 
name participates. The same as in the case of 2^{Aleph_0}. Who 
knows its proper value? Is it equal to Aleph_1?

> Of course we already know what finite means: a set is finite (within
> first-order set theory such as ZFC) if it lacks a bijection onto a
> proper subset.

I would say more carefully something like "we know from our 
teachers".  We *should* learn from our teachers, but after that 
we also could make our own somewhat different *decisions* on 
which properties this notion should/may have. Thus, I would not 
take categorically the above or any other property of finite as 
the definition. Only temporary, for that or other goal.

But this characterization has deep problems from a
> foundational point of view. It requires an intuitive or informal notion
> of finite to be in place to even set up what a first order axiom system
> is.

Yes I also consider this as a crucial problem, but probably 
somewhat differently. Why to mix finiteness of the syntactic 
(concrete, feasible) objects with that of semantic (abstract) 
ones (even if these abstract objects are intended to serve, say, 
also as feasible numbers)? The conceptual difference between 
syntax and semantics seems inevitable. It is essentially 
*identification* of the finitude of arithmetical syntax with the 
corresponding finitude of semantics (the intended arithmetical 
model where it is interpreted), say, via Goedel numbering, which 
is the source of arising in our heads the (wrong) idea of 
"standard model".


It makes finitude logically inseparable from infinitude (each is the
> negation of the other), and so blocks off the possibility of it serving
> as a basis for discussing infinity. Most importantly, it supports a
> privative or negative definition of `finite', since from the orthodox
> view, which starts from an already present or given series of `the
> natural numbers', each initial section cannot but be understood as a
> falling short or truncation of the full and priorly given infinite
> series.

Sorry, I do not understand what do you want to say. (Probably 
the reason is that English is not my native language.)

The fundamental question then becomes: how can a non-privative,
> positive finite be conceptualized? A finite that instead of being
> understood top-down from infinity is constructed bottom-up from zero.
> Put another way, we are confronted with two conceptions and ontologies
> of the finite. The negative: that which falls short of a prior infinite,
> an idea entirely consonant with Plato's picture of the sensible world as
> an imperfect copy of a prior heaven; the positive: that which is the
> given condition for the possibility of the infinite, an idea consonant
> with the prior materiality and `finitude' of our sensible bodies.
>
> One obvious source for bottom-up finite is counting: replace remote-N
> feasibilism by identifying the feasible numbers as those which are
> empirically possible, those which the material constraints of the
> universe allow to be counted into existence.

This is exactly what I intuitively mean by feasible numbers.  
I think I wrote about this in my previous postings. But I have 
nothing to do with "remote-N feasibilism". N=2^1000 or N=2^347 
or the like are only more or less rough upper bounds to 
feasibility, no more than this.  These bounds do *not* serve to 
define feasibility. They give only some orientation where we are 
and *partial* characterization of feasibility. Also your words 
"empirically possible" show that you also consider feasible 
arithmetic from empiric point of view. How is it possible in 
this case to find pure, "intrinsic", "autonomous" (cf.  the next 
paragraph) mathematical characterization of feasibility with no 
using of "arbitrary" empirical laws which do not follow from 
some a priori and pure laws of thought? 


This could be made more
> precise by having the counting process executed by an ideal machine
> operating at the thermodynamic limits of action, and by appealing to the
> known finitude of the universe (of energy, for example) to arrive at an
> intrinsic limit to feasibility. Two such limits, which I won▓t elaborate
> on here, are 10^96 or 10^(19^98), depending on whether one integrates or
> differentiates energy usage respectively. But such a procedure, however
> interesting, is not mathematics; it is physics. Mathematics requires
> idealizations controlled by formalisms that are autonomous, cut free
> from empirical questions.

What about applied mathematics or presently pure branches of 
mathematics such as differential calculus, in particular, 
equations of mathematical physics (even simpler - Euclidean 
Geometry!) which arose under strong influence of practice? For 
me there are no doubts that arithmetic (in a general sense, 
including, in particular, PA) may be reasonably considered as 
deductive system having empirical base and roots. I do not 
believe that the ordinary mathematical formalisms, even ZFC, are 
absolutely "autonomous from empirical questions".  But I agree 
that we may be interested in *relatively* autonomous formalisms.

> Why not, then, try to conceptualize (in order to axiomatize) the feature
> of counting from zero in evidence here and common to all countings ever
> performed or performable in this universe, namely necessary cessation,
> by writing down a suitable set of arithmetical consequences of
> cessation.

I am not sure that I understand what do you mean by "cessation".  
Do you mean that any real counting has the very last step?  By 
the way, we may postulate that there is a resource bound (the 
last natural number with non-specified value) denoted as \Box 
(cf. my last recent posting to FOM). This leads us to what I 
call \Box-arithmetic (and its versions) whose goal is NOT 
exactly feasible numbers, but rather to play a role of an 
ARITHMETIC OF POLYNOMIAL TIME COMPUTABILITY. 

This is what I do in my book. I call the numbers that can be
> counted into existence from zero the iterates, and I take the principal
> consequence of the fact that such counting cannot go on ▒for ever▓ to be
> the phenomenon of exit points -- cuts or regions in the iterates -- at
> which each arithmetical operation undergoes a discontinuity. Thus for
> large enough iterates n, it will be the case, that is, one takes it as
> an axiom, that n+n will no longer be an iterate; similarly for
> multiplication, and so on.

It is analogous to what we have in Bounded Arithmetic: it is 
consistent with BA the formula \exists n \forall x (log x < n) 
or, equivalently, there exists n such that 2^n is infinite 
(undefined), i.e. the function 2^n is partial (recursive) one. 
Do you specify anyway how large is your "iterate" n such that 
n+n is undefined (I mean, that it is not an iterate).  
Unfortunately, I did not seen your book (and, I am sure, 
nowadays in Russia it is hardly available). Thus I should follow 
only this your message. It seems, your "iterates" conceptually 
correspond to (but not coincide with my formalization of) 
feasible numbers. (The latter are, of course, also iterates; but 
I would separate these two terms to not mix your and my 
approaches).  Thus, you postulate that iterates are not closed 
under addition operation (i.e. addition is partial recursive 
function on them). Unlike you, I postulate that this operation 
is total, just because it is harmless for my approach.  (I think 
this difference in our approaches is not very essential.) But, 
as it actually follows from other axioms of my system of 
feasible arithmetic, multiplication operation is inevitably 
partial one.  What about successor operation for your iterates?  
However you did not say explicitly, I guess, you consider that 
it is total.  Otherwise, I completely do not understand what do 
you want to do.  A kind of \Box-arithmetic?

Is there any "concrete" from the traditional point of view upper 
bound (like 2^1000) for your iterates? Is postulating of such a 
"concrete" upper bound consistent with your understanding of the 
iterates or, may be, in some unknown to me way existence of such 
an upper bound (or, alternatively, the law like loglog x < 10) 
for your iterates is a corollary of your approach (formalism)?
Is this law true, or what?

Such non-iterates will form a domain of
> transiterates whose arithmetical properties will be constrained only by
> their being sums, products, etc of iterates.

Are these transiterates just constant polynomials (i.e. 
variable-free terms constructed from 0,1,+,* and considered 
modulo some reasonable equivalence relation and linear preorder) 
or you allow also arbitrary primitive recursive functions? Are 
you shure that there are no gaps between these transiterates? 
(In principle, I would agree to have some gaps if they are 
harmful or "invisible" in a sense.)

In my paper on feasible numbers (cf. above) numbers bounded by 
such constant polynomials are called *polynomial* (and may be 
called also *multiplicative*) numbers.  Of course it is open the 
possibility to consider *exponential* numbers, etc.  Feasible 
numbers (which are closed under + ) may be also called 
*additive* ones.

The result is a large class
> of models of arithmetic

Are they some (possibly non-standard) models of PA or PRA or of 
a kind of Bounded Arithmetic? Is "the" standard model one of 
them?  (The latter question is rhetoric one because I see what 
you write below.) Is the goal of your work to explicate in a 
reasonable (predicative?) way what are the ordinary natural 
numbers used in mathematics (i.e.  satisfying traditional axioms 
like PA) with the help of iterates (i.e., essentially, feasible 
numbers), transiterates, transtransiterates, etc.?  I think, 
this would be very interesting! But first, do we understand 
sufficiently well the feasibility concept on which such a 
project would be based?

which (for reasons I won't go into here) I call
> non-Euclidean, whose immediate difference from the standard model is
> that they are already ▒non-standard▓ in that each is bifurcated into an
> initial, well-behaved section of iterates followed by an unruly and
> counter-intuitive domain of transiterates with a rich and complex
> structure.

(This paragraph is written for those who like devilry of 
feasibility concept and for whom standard model is not the "holy 
cow".  Now, I CANNOT NOT SAY that by my opinion ANY MODEL OF PA 
IS NON-STANDARD.  It is, in particular, because feasible numbers 
may be consistently and trivially thought of as initial part of 
any such model to be values of the terms 1+1+...+1 of feasible 
length, all these values being < 2^1000 and closed under 
successor.  [As I see you think somewhat differently, and I 
cannot understand why.] Thus, your "immediate difference" is 
just a tautology because the standard model does not exist at 
all and is only an illusion. Models of PA may be only *more or 
less* standard. Say, Any model of ZFC contains the ordinal 
\omega which serves as a model of PA. Models of such kind 
arising from models of ZFC are somewhat more "standard" than 
arbitrary models of PA.  By replacing ZFC with a stronger and 
stronger natural set theories we seemingly will obtain models of 
PA which are "standard" in more and more strong sense. Then in 
the "limit" we probably would get ABSOLUTELY TRUE STANDARD MODEL 
for PA. But even this model should contain feasible numbers as 
an initial part. Of course, I am not very serious here because I 
do not believe in the meaningfulness of such a limit process and 
the resulting model. I simply do not know what does it mean.)

What do your words "well-behaved " mean?  If your iterates are 
indeed close to what I call feasible numbers then I do not agree 
that they are well-behaved because they are extremely 
nonstandard, unusual, objects which do not satisfy the ordinary 
laws of logic (say, transitivity of implication).  Moreover, 
there are formally proved even more strange (but, I believe, 
quite reasonable) facts on these numbers; cf. my paper or my old 
postings to FOM.

>
> The idea is simple enough and seems totally obvious, but I had to
> overcome a great resistance (from my classically trained self whose
> attachment to `the' natural numbers was deeper that I realized) to get
> to it.

YES! I also had extremely strong psychological barrier due to 
which I wasted a lot of time before finding *any*, even simplest 
reasonable formalization of feasibility. (I started with the 
first known to me nice formalization by Rohit Parikh which I 
consider, nevertheless, not sufficiently adequate for "genuine" 
feasibility).


Thus, the bulk of my book is concerned not with axiomatics and
> formalism per se but with articulating an apparatus (a semiotic account
> of mathematical reasoning/imagining derived from ideas of Peirce) that
> allows a reconceptualization of ▒counting from zero▓ which doesn't
> collapse back into the great attractor of classical counting. The
> structure and details of this apparatus needn't concern us here,

I do not agree! They should concern us. Otherwise we hardly can 
reach satisfactory understanding.

but its
> outcome surely should. This is because, by initiating a thinking of
> ▒finite▓ whose motivating intuition assigns a coherent meaning to the
> ideogram `...' different from its classical meaning, it makes it
> possible to think (i.e. in the present context, axiomatize) a positive
> or non-privative finitude -- literally so from the bottom up, from
> below, which is, after all, where we all are.

It is especially interesting to me which kind of axiomatic 
formalism may arise from your approach or, at least, some more 
hints on the structure and details of your "apparatus". In my 
case such details were a crucial point. Also, what kind of 
applications may your approach have in principle? As to my 
approach, I wrote on possible applications in my paper and in 
many posting to FOM.


> Name: Brian Rotman
> Position: Research Scientist
> Institution: Ohio State University
> Research Interests: foundations of mathematics, semiotics


Vladimir Sazonov
--
Computer Logic Lab.,		| Tel. +7-08535-98945 (Inst.),
Program Systems Institute,  	| Tel. +7-08535-98365 (home),
Russian Acad. of Sci.		| Fax. +7-08535-20566
Pereslavl-Zalessky,		| e-mail: sazonov at logic.botik.ru
152140, RUSSIA			| http://www.botik.ru/~logic/SAZONOV/