[FOM] predicative foundations

[Vladimir Sazonov]

The quote from Nik Weaver gives me an occasion for the following
reply which is, in fact, a reaction to various similar views.

Quoting Nik Weaver <nweaver at math.wustl.edu> Thu, 16 Feb 2006:

I can describe N in a metaphysically
> uncontroversial way in terms of making marks on paper.

So simple? And will we get in this way a *unique* row of natural
numbers 0,1,2,...? I think we should mention at least the abstraction
of potential infinity. But what does this abstraction really mean, if
not just a magical incantation? The first, simplest idea is the
closure of 0,1,2,... under taking the successor (no last element in
this row). But even only feasible numbers (which are definitely < 
2^1000) *intuitively* satisfy this requirement (no last element -
we cannot show any).

Now, what can we say *formally*, that is, not only as a matter of
speculation?

(1) Recall that Rohit Parikh (in his paper "Feasibility in
Arithmetic", JSL 1971) has demonstrated a (feasibly) consistent
*formal* version of arithmetic (actually based on the classical logic
with cut rule) such that "the" row of natural numbers 0,1,2,... is
closed under + and * and, nevertheless,

0,1,2,... < exponential tower of twos of the *height* 2^1000

where "..." assumes closure under successor giving rise to an
*infinite*, never ending series of natural numbers.

(2) In my posting
http://www.cs.nyu.edu/pipermail/fom/2006-February/009746.html
I have shown that even postulating

0,1,2,... < 2^1000

is (feasibly) consistent assuming only the closure under + and also
that the underlying logic is restricted by not allowing abbreviations
for terms (although formulas can be abbreviated). (Please note that
this is a *formal* result; so the precise consiferations from
the above link should be taken into account to understand the proper
meaning of this statement! I should make this note because I know
that there is a serious possibility of misunderstanding.)

(3) Moreover, it is even feasibly consistent that

0,1,2,... < 1000, and even 0,1,2,... < 100.

(There is a subtle formal difference with (2), but let me omit
comments.) All of this is mathematically quite precise (see the link
above).

(4) If we postulate that 0,1,2,... is closed under iterations of +, *
and arbitrary (primitive) recursive operations we should get much
much higher concrete upper bound for 0,1,2,... than demonstrated
above. Even in the case of Peano arithmetic or ZFC, etc., etc., we
should have some "concrete" upper bounds in each case. (I hope
somebody here, may be Harvey Friedman, could confirm this.)

The important point is that an upper bound for 0,1,2,... satisfying
some formal theory can be shown by using some stronger theory. So,
this upper bound is a relative concept.

Then, once we have various informal and formal views on N and
concrete upper bounds,

WHAT IS THE "PROPER LENGTH" OF THE ROW OF NUTURAL NUMBERS 0,1,2,... ?

Is it fixed anyway? Does it make a sense to speak on a limit
"length"? Do we "really" have a unique ("longest" possible) row of
natural numbers (having no concrete upper bound?) that we are dealing
with in mathematics but which cannot be grasped by any of a lot of
formal (existing or considered in the future) theories "describing"
natural numbers? What is the reason to hope that these various rows
of numbers "coverge" to something unique? May be they are even
branching? What are we talking about when mention "natural numbers"?
Does this concept have a proper, well understood meaning, or do we
just mistekenly *ignore* the highest vagueness of this concept (even
higher than the vagueness of feasible numbers which are evidently
used in the iterated and imaginary processes of generating N)?

I agree that the vagueness of P(N) has intuitively somewhat different
character, than that of N.  May be this vagueness is "worse" than
that of N. But I think that this is not the reason to assert that
what we call "N" is something uniquely defined and well understood.
The "natural numbers" is only a generic name to denote some set of
inevitably vague ideas related with the counting process "zero, one,
two, ..." going *indefinitely* long. And this "indefinitely" is
highly indefinite itself.

By the way, if to consider 1000 as the set N_1000={0,1,2,...,999},
what about the (im)predicativity of P(N_1000)? Is this (definitely
non-feasible) set given to us as an actual one? We can observe some
concrete examples of subsets of N_1000 (say, represented as a finite
binary string of the length 1000). But what about ALL of them? Does
this "ALL" make a "real", "absolute", sense? This note is related in
some way with Kolmogorov complexity. Some related idea in the
framework of feasibility is also discussed in the full version of
the above link, my paper "On feasible numbers".


As a conclusion: I hope that I have *explicated* the idea that there
is NO such a unique and well understood thing as N. This was done by
referring to some concrete formalisms and existing or possible proof
theoretic results on *concrete upper bounds* of N. The illusion on a
unique N can appear only on the base of a non-critical, "ignoring"
position allowing to use wordings like "potential infinity",
"absolute truth", etc., just as magical incantations without
a serious attempt to explain what does this ever mean and which are
the problems related with such a meaning.


Vladimir Sazonov


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