FOM: What is the standard model for PA?
Vladimir Sazonov
sazonov at logic.botik.ru
Sun Mar 15 13:45:45 EST 1998
Torkel Franzen wrote:
>
> Validimir Sazonov says:
>
> >By the way, can anybody here explain what is this fully
> >"determinate" "standard model"?
>
> Certainly. The natural numbers are 0,s(0),s(s(0)), and so on. Or,
> if you like, a natural number is anything obtainable from 0 by
> iterating the successor operation.
>
> Now, of course you already know this, but you don't think this is
> a "clear explanation". Here I'm sure you're right, in the sense that
> no "clear explanation" such as you ask for can be given.
I personally ask nothing extraordinary, nothing absolute. First note,
that "and so on" after "0,s(0),s(s(0))" explains almost nothing. It even
do not say (at least explicitly) that there is no last natural number.
Even if we assume infinity of this sequence, it is unclear how strong
is this "and so on". In particular this "and so on" is quite consistent
with the experimental arithmetical low I mentioned that for all natural
numbers x (in unary or in the above notation), log log x < 10.
(Actually, this essentially corresponds to my favorite
understanding of what are really standard natural numbers. But I
do not insist now on corresponding changing the terminology.)
Of course, we can postulate additionally to the above "and so on", say,
that the natural Turing machine that calculates the "concrete number"
2^{2^10} = 2^1024 halts in a finite number of steps. This allows us to
think or believe, if somebody would like to believe in such kind of
things, that "the" number 2^1024 occurs somewhere in the infinite
sequence
0,s(0),s(s(0)),... . Moreover, we can postulate that (some form
of) induction axiom (actually, a schema!) holds for this imaginary
sequence 0,s(0),s(s(0)),... and infer from it the existence of
2^1000, 2^{2^1000}, 2^{2^{2^1000}}, etc., etc., etc., until our
fantasy and expressive power of our arithmetical language(es)
will work. We can consider second order version of IA, etc., etc.
Where is the end? (I am sorry for all this triviality!)
> Where I
> disagree with you is in the conclusion that there is therefore some
> indeterminacy or unclarity about the notion "natural number".
Even if I forget on my own doubts that induction axiom is inevitable
in any attempt to formalize natural numbers, I do see the above
description as indeterminate. That is why I asked anybody to explain
where and in which sense this usually declared determinacy arise.
By the way, how to distinguish "standard" natural numbers from
"nonstandard" ones if these terms have a general sense (of course,
outside the framework of ZFC)? (Actually, in the light of the above
arithmetical low I would rather say that 2^1000 is nonstandard.)
On the other hand it is not me who asserts determinacy or
clarity about the notion "natural number". It seems that my
position is more safe: If somebody asserts this, let him explain
at least what does it mean. My opinion is that such a
determinacy is just an illusion, widespread among almost all
mathematicians and even logicians, which is probably a very
useful, stable, coherent and even almost objective illusion
in a reasonable sense. But it seems more honest and productive
to give account to oneself and to everybody about this than to
insist that here is NO illusion at all. (By "oneself" I mean,
first of all, myself.)
> I don't think Martin Davis meant to suggest that the justification
> for Lagrange's theorem has anything to do with experiments.
Anyway, he used those experiments to show the relation of "pure"
arithmetical "truth" to the truth in our real world. I do not
see why there could not be considered another direction from
experiment to theory. Actually this is one of the usual ways how
many applied mathematical theories arise. Also it is worth to note
that we often postulate some axioms (like induction) *despite* they
contradict to some evident truth in the real world. I conclude that
at least it is unnecessary to idolize them.
> What
> degree of support experimental observations give to arithmetical
> conjectures is, in general, a tricky and debated question. However,
> your suggestion, that "log log x < 10" is an "arithmetical law"
> justified by experimental findings simply lacks any obvious
> justification. Why should we regard it as an arithmetical law that log
> log x < 10 on the basis of the experience you refer to?
I do not know what else justification you need. Experiments
like in physics (and the lack of counterexamples) are also some
kind of justification. Of course, it is also necessary to
demonstrate mathematical and applied usefulness of such an
"arithmetical low" or illustrate how it works. I have some more
to say on this. See, e.g. my postings to FOM beginning from Nov
5, 1997 and my paper "On feasible numbers" in LNCS 960 available
also from my Web page. Much more is to be done. As to f.o.m.,
this low seems to demonstrate (or illustrate) that there is
actually no hope on having a unique notion of natural numbers
and of the absolute "truth" even in arithmetic. This also sheds
some light on the notion of mathematical proof. We should be
much more careful when formalizing (feasible) numbers theory
satisfying the above axiom. The very possibility to formalize
this theory as rigorously as the ordinary Peano Arithmetic
demonstrates that the class of (*almost*, in the sense of
R.Parikh) consistent theories is wider than we were able to
suppose. Thus, this extends axiomatic method, at least in
principle.
I am asking again those who do not agree with me,
WHAT DOES IT MEAN
full determinateness of "the" set of "all" natural numbers
IF IT IS NOT AN ILLUSION
(may be the best, the purest and divine illusion people ever had)?
Vladimir Sazonov
(interests: applied logic, descriptive complexity,
bounded arithmetic, bounded set theory)
the head of Computer Logic Laboratory,
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