FOM: Was sind und was sollen die Zahlen

Vladimir Sazonov sazonov at logic.botik.ru
Tue Nov 4 18:48:52 EST 1997


I am a newcomer of this FOM list. Sorry for any possible 
misunderstanding of its goals. Also, sorry for my English.


First, I would like to mention the following attractive to me 
fragments from different postings of Vaughan Pratt:

> Mathematics is like art and fashion, it is defined by its producers and
> consumers and it has its trends and staples.  Everything changes in
> mathematics, some faster than others.

Harvrey Friedman replies:

> Basic classical mathematics is relatively unchanged. The classical number
> systems are unchanged. So what do you mean by this?

Again Pratt:

> Even on earth, let alone Quasar X9, mathematicians disagree wildly among
> themselves as to "was sind und was sollen die Zahlen".

> ... proof and truth
> as equal partners, not proof as the servant of truth.

Also Neil Tennant <neilt at hums62.cohums.ohio-state.edu> wrote:

> [Please do not reply that the lesson of Goedel's incompleteness theorem
> for arithmetic is that there could be 'alternative arithmetics'.  For
> in response to such a suggestion one can make two fatal points.
> First, ALL these arithmetics would have to contain the same
> quantifier-free statements such as '7+5=12'.  Secondly, we all agree
> that the independent Goedel sentence for a given (intuitively sound)
> arithmetical theory is TRUE in the intended model.]

I do not agree, because the Goedel's consistency statement does 
not have precisely (if we could ever have any hope on a precision 
here) the intended meaning. Actually, what is *the* intended 
model/meaning of PA, etc.?  Of course, so called `standard 
natural numbers' are characterized uniquely, up to isomorphism, 
in the framework of ZFC. But what is proper relation of these 
`standard natural numbers' to natural numbers from our `real 
world'?  (Cf. the discussion below.) Alternatively, why should we 
consider only ZFC (or PA) perspective as the unique way of 
formalizing the `naive' notion of natural numbers which is given 
to each of us BEFORE any learning this concept in school or in 
our universities. For example, my daughter once asked me (when I 
counted "1,2,3,...,100,...,1000, and so on") why not use one 
sufficiently big number which will be `enough' for us. In a sense 
she was right. (This is a way to describe PTIME computability 
in terms of recursive arithmetic relativised to such a finite row 
of natural numbers.  However, this story slightly deviates from the 
following below considerations, but is related.)

Joe Shipman <JSHIPMAN at bloomberg.net> wrote:

> Not all mathematics is logically prior to physics; as Godel saw
> we could get new axioms from physics.  In my thesis (TAMS 10/90)
> I showed some theories of Quantum Mechanics were independent of
> ZFC, and in the '92 PhysComp Proc. discussed how a noncomputable
> number might be measurable (to more digits than ZFC decides).-JS


In connection with these notes and instead of debating whether 
7+5=12 (I think that this question is simultaneously too simple 
and too difficult to be resolved/understood) I would like to 
suggest to FOM more concrete discussion on non-traditional 
`alternative' Arithmetic Systems, specifically, on Feasible Numbers 
[cf. an old paper by R.Parikh in JSL, 36 (3) 1971 and more recent 
my paper in LNCS, Vol.960 also available by 
http://www.botik.ru/~logic/SAZONOV/papers.html; of course, 
Yesenin-Volpin and some other authors should be mentioned, too; 
there are also very interesting related notes in the book 
"Constructivism in Mathematics", 1988 by Troelstra and van 
Dalen].

Let us consider so called *feasible numbers*, i.e. natural 
numbers allowing to count sets of objects which *really exist*, 
say, the number of symbols in a real computer file or the like.  
The `semi-set' of these numbers is denoted by F. Intuitively, F 
is closed under successor (F+1\subseteq F) and even under 
addition (F+F\subseteq F). Evidently, 0,1\in F. Now, let us 
denote by log n the integer part of binary logarithm of n. Then 
we may check (say, by using a computer) that for each concrete n 
\in F

	log log n < 10					(*)

where 10 is, of course, `ten' (8 is also good). Anybody who 
doubts are welcome to give counterexample!

This is some *experimental low of arithmetic* with n represented 
in unary notation as any *real* sequence 111...1 which any of us 
could print on a keyboard of a computer. Moreover, if you have 
any other computer which sends to the given computer (evaluating 
log log n) arbitrarily big (but physically existing, i.e. 
feasible) input n then the result will be the same, i.e.  (*) 
still holds. Of course, this *physically true low* (which is very 
much like Newton Mechanic lows or commutativity and distributivity 
lows of Arithmetic) contradicts to what we know from our teachers: 
that logarithm is unbounded function or that mathematical induction 
axiom is inevitably true for the numbers, etc.

Is this only a non-serious childish question on big and small 
numbers or a real possibility of some different `Feasible 
Arithmetic'?  Is it possible any formalization of such an 
arithmetic (let only some oversimplified version for a while) as 
rigorous and consistent as Peano Arithmetic? Yes, it is!  Now I 
can say: "Nothing starnge", because the above axioms are `true' 
in a reasonable sense. But this was not so evident at the 
beginning, however the solution proves to be not very difficult. 
(The details, which are actually essential and interesting, are 
omitted.) 

As I know, the first rigorous approach 
to feasible numbers with analogous but essentially weaker axiom 
than (*) was suggested by Rohit Parikh (cf. op.cit.). The case of 
(*) follows the main idea of Parikh and gives more precise upper 
bound 2^1024 (i.e.  approximately 2^1000) for F than his original 
`non-elementary' exponential tower of exponential height.  Also 
our consideration differs from that of Parikh in imposing some 
feasibility restriction on abbreviating mechanisms implicitly 
used by mathematicians and logicians in First-Order Logic (cf.  
op.cit.).

It follows that the number 2^1000 of all possible strings of a 
given length 1000, in the fixed two latter alphabet {0,1} can not 
be considered as feasible one according to the axiom (*). (It is 
only an `imaginary number'.) This seems to contradict to the 
ordinary opinion that this set is very concrete, or that all its 
elements `physically exist' in our world `altogether'. Of course, 
we can write (even by hands) some examples of such strings of the 
length 1000, say `010101010101...0101' or randomly, by using a coin. 
But how could we understand (if not stay `inside' any formal or 
semiformal system like PA or ZFC) what is a precise meaning of 
`the set of *all* such strings of the length 1000'. I believe 
that this is a genuine vague/fuzzy set, as well as F.  Is not 
this vagueness problem of this `set' analogous to the Continuum 
Problem (in my edition):

What does it mean precisely the set of *all* infinite binary 
strings (isomorphic to the powerset of the set of natural numbers)?
What is precise cardinality of this set? (Kantor)
Are all such strings `simple' or constructive(ible) in a 
reasonable sense or there are `random', very `complex' strings? 
(Goedel, Kolmogorov)

We know from Goedel and Cohen that these questions are 
non-resolvable in ZFC what witnesses (at least by my personal 
opinion) that continuum is just a vague set. We can prove very 
formally many interersting theorems on the continuum.  But this 
does not mean that it is not vague and uniquelly determined. 
Formally, its cardinality is 2^\aleph0, but this information is 
too poor. More or less the same holds for 2^1000.

There are additional interesting and debatable foundational 
issues arising in formalizing Feasible Numbers (cf. op.cit.).  
E.g., What is a formal axiomatic system?, What is a rigorous 
mathematical proof?, Which abbreviating mechanisms are actually 
used by mathematicians and can we assert without knowing this 
that formal logic was indeed properly and `completely' 
formalized? Which abbreviations are admissible in `feasible' 
mathematics/logic?, What is a contradiction?, What about 
mathematical truths such as (*)?  Is mathematical induction axiom 
true/reasonable?, How `expensive' is using Modus Ponens or Cut 
Rule?

I interrupt to mention here (without comments) the following 
related note by Harvey Friedman:

> In the usual foundational setups, as I said earlier, no really interesting
> mathematical proof is cut-free.

I continue:
What about a model theory for `feasible' logic?  Is it possible 
corresponding Feasible (Nonstandard) Analysis or Algorithms 
Theory or Constructivism (compare with op.cit. of Troelstra and 
van Dalen)? etc.

Let me mention one effect which Feasible Arithmetic seems to 
explain:  It is our ability to see any picture on computer 
display (`Feasible Continuum') BOTH as discrete and continuous 
just by switching something in our brains.  (No optic, just a 
logic; Cf. op.cit.) It is interesting whether this will have any 
non-trivial/useful/illuminating consequences in description of 
physical lows concerning micro-world (consisting of elementary 
particles/waves) in terms of Feasible Arithmetic/Mathematics. 


Vladimir Sazonov
-- 
Program Systems Institute,  	| Tel. +7-08535-98945 (Inst.), 
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