FOM: counting - feasibility (Reply to Brian Rotman)
Vladimir Sazonov
sazonov at logic.botik.ru
Mon Aug 31 09:32:37 EDT 1998
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/
More information about the FOM
mailing list