# [FOM] N vs. FOL

Vladimir Sazonov V.Sazonov at csc.liv.ac.uk
Fri Jun 6 14:11:11 EDT 2003

```Andrew Boucher wrote in reply to the recent posting
of Dana Scott:

> Perhaps I am misconstruing the remarks, but I would like to point out
> that induction can be stated in a system where only 0 exists:
>     From phi(0) and (n)(m)(Nn & Sn,m & phi(n) => phi(m)), conclude
> (n)(Nn => phi(n)),
> where Sn,m is the sequential relationship (i.e. totality is not assumed)
> and Nn means "n is a natural number".

Unfortunately, as it is mentioned above, in this approach we can
have only 0 as a provably existing number.  I would suggest
to add in the syntax the rule for creating numerals:
0 is a numeral, and if n is a numeral, then n' is a numeral.
Also add the axiom schemes Nn (I would prefer to use
the letter F - for feasible numbers - instead of N) and
Sn,n'. Then, it seems plausible that exactly feasible numbers
will be provably existing (by using only feasible proofs).
Analogously, a theory of binary strings could be considered.

On the other hand, I already have another formalization of
feasible numbers with the successor and "+" as total operations.
(I omit the details.) Here also only feasible numbers
are provably existing and, in particular, 2^1000 is not.
I only add that this formalization has rather unusual
(simple) theorems demonstrating some peculiarities
of the concept of feasible numbers.

>
> That is, induction can be stated in an ultrafinitist framework, indeed
> in a system where 0 is the only natural number assumed to exist.

In my system induction can be added only in a restricted form.
We should pay a lot for having successor and "+" as total operations.
But, paying this, we can get something interesting and new.

>
> Remark using such induction (and assuming other natural axioms), one can
> prove
>     (x)(y)(x + y = z => y + x = z)
> but not
>     (x)(y)( x + y = y + x).
> So one must be precise what e.g. one means by commutativity when talking
> in an ultrafinitist setting.
>
> Similarly, one can define a syntactical system making only very minimal
> assumptions - put baldly, you know what a formula is, if you are told
> conditions for something to be one, e.g. that it can be decomposed into
> smaller formula in specific ways.  You don't need to know that any
> exist, and in particular that one can construct ever bigger formula ad
> infinitum.
>
> One cannot, it is true, prove the Deduction Theorem as is, in a system
> described with this spirit.  To establish the DT one needs, given a
> proof, to construct a bigger proof.   But obviously,  someone with
> ultrafinitist leanings might not want to accept such an assertion.  That
> is, he would have no problem reasoning about the syntax; the blocking
> point would be the ontological presumption in the DT.
>
> I am not a card-carrying "ultrafinitist", since like Woody Allen, I
> refuse to join clubs that might admit me.  So I offer these remarks as a
> personal viewpoint, and not as official dogma of the ultrafinitist
> community.

Let me also add that some interest concerning feasible numbers
is expressed in the book of A.S. Troelstra and van Dalen,
"Constructivism in Mathematics. An Introduction", Vol. I, II,
North Holland, Amsterdam, 1988. See pages 5-6, 29, and 851.
In particular, they wrote: "On the other hand, intuitionistically
we do accept that "in principle" we can view 10^10^10 as a sequence
of units (i.e. we reject the ultrafinitist objection), and the
authors are not sure that this is really less serious than the
platonist extrapolation. At least it needs arguments." (P. 851)
Also Borel (1947) mentioned that "the very large finite offers
the same difficulties as the infinite".

Note, that the simple question what does it mean "the STANDARD
model of PA" leads us to the concept of feasibility. I do not say
- to ultrafinitism - just to some new concept for mathematics,
like irrational or complex numbers, or like the concepts related
with Analysis, or like non-Euclidean geometries, or infinite sets
and their cardinalities in older times, the concepts which changed
the face of mathematics. The possible role of the feasibility
concept in mathematics is not yet clear enough. But it is
interesting, at least, to make it really mathematical one.

But, anyway, what does it mean "the STANDARD model of PA"?
Is there any convincing answer to this question?
Is it possible at all?
```

More information about the FOM mailing list