[FOM] N vs. FOL

[Andrew Boucher]

Dana Scott wrote:

>Vladimir Sazonov wrote (in part):
>
>  >> Say, PA consists of several axioms and one axiom schema. It is
>  >> based on FOL based on several (schematic) rules. We easily
>  >> understand how to use these rules.  All of this is quite
>  >> concrete, unlike N, which is both illusive and not determined
>  >> enough (as ANY illusion).
>
>In order to understand fully schematic rules, one has to understand
>syntax.  A theory of syntax (just as arithmetic) could be based on
>finite strings of 0s and 1s under concatenation.  Call this domain B
>(for "binary").  I say, B and N amount to the same thing.  
>
>Now for PARTICULAR strings (formulae) I can see how to operate on them
>following the rules of FOL -- just as I can see how to use the rules
>of arithmetic to operate on certain particular numbers met in everyday
>life in the way we learn in school.  I agree these particullar
>operations are "concrete".  However, for any GENERAL RESULTS, say even
>for the Deduction Theorem, I need some kind of induction principle to
>argue that some desirable property holds for ALL (provable) formulae
>-- just as I need induction to prove in PA that, say, addition is
>associative and commutative.
>
>Yes, I have gone up to the metalanguage here in discussing the
>formalization of theories.  But if B is "illusive and not determined
>enough", what justifies my using these syntactical arguments?
>
>I sense an infinte regress.
>_______________________________________________
>FOM mailing list
>FOM at cs.nyu.edu
>http://www.cs.nyu.edu/mailman/listinfo/fom
>
>  
>
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".

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

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.