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