Re: primitive recursive: obsolete?

On May 9, 7:03 pm, Aatu Koskensilta <aatu.koskensi...@xxxxxxxxx>
wrote:
On 2008-05-09, in sci.logic, MoeBlee wrote:

Do you have any thoughts on my question about the notion of
'finitistic'. Why do people limit 'finitistic' to primitive recursive?
Why not take finitistic as anything total recursive?

Because not all total recursive functions are recognisable as such by
finitistic principles.

The restriction to primitive recursive functions stems from the fact
that the principle of definition by primitive recursion is equivalent
to the principle of induction. Solely on basis of our basic
understanding of the naturals as what one obtains from 0 by repeatedly
applying the "add one"-operation the principle of induction and the
principle of definition by primitive recursive induction are equally
compelling. This is the reason for taking primitive recursive
arithmetic as the canonical formalisation for finitism; if we further
allow that properties definable from primitive recursive properties by
means of the usual logical operations of first-order logic --
including unrestricted quantification --, in effect accepting the
totality of the naturals as something determinate, we get PA.

After reading your response it occurred to me that the vagueness in my
original question is a problem. I didn't say what I mean by "taking
finitistic to be anything total recursive". What is it it that we
"take as finitistic"? A general approach to mathematics? Or more
specifically, particular theories? So, let me pursue your response in
the second sense - whether a specific theory qualifies as finitistic.
Now, it's clear enough to me the sense in which PRA is finitistic, but
now it occurs to me that I should have asked myself, "What THEORY
would I have in mind that is a counterpart to PRA but that has not
just axioms for the primitive recursive functions but axioms for all
the total recursive functions". And perhaps that leads right into your
response. If I surmise correctly, there is no recursive axiomatization
of the theory whose axioms are all and only the "defining" axioms for
the set of total recursive functions. Do I have that right?

Yet, you didn't mention lack of a recursive axiomatization of that
theory, but actually said "not recognizable as such by finitistic
principles". So, would I indeed be fair to say that the more formally
pertinent fact here is lack of a recursive axiomatization of the set
of defining formulas for the total recursive functions?

And that leads me to something else not clear to me. I can see that it
is plausible that the set of defining formulas of the primitive
recursive functions is a recursive set, but I don't quite see how one
would actually specify the set in a recursive way, i.e., in a way such
that not only do we know the set is recursive but that we have in
front of us a decision procedure for membership in the set. Could you
give at least a quick sketch of how PRA can be axiomatized so that it
is decidable whether a formula is or is not a defining formula of a
primitive recursive function?

Thanks,

MoeBlee

.

Relevant Pages

  • Re: primitive recursive: obsolete?
    ... Because not all total recursive functions are recognisable as such by ... that the principle of definition by primitive recursion is equivalent ... to the principle of induction. ... arithmetic as the canonical formalisation for finitism; ...
    (sci.logic)
  • Re: primitive recursive: obsolete?
    ... Because not all total recursive functions are recognisable as such by ... that the principle of definition by primitive recursion is equivalent ... to the principle of induction. ... arithmetic as the canonical formalisation for finitism; ...
    (sci.logic)
  • Re: Recursive functions
    ... used.I have to use recursive functions. ... teach you how to mis-apply a useful technique. ... is strongly emphasized that using recursion is absolutely ... Practical concerns must be applied during the learning ...
    (comp.lang.c)
  • Re: Recursively enumerable sets
    ... I was thinking of elliptic curves in general, ... Primitive Recursion ... If the characteristic function of X is primitively recursive, ...
    (sci.math)
  • Re: Recursively enumerable sets
    ... I was thinking of elliptic curves in general, ... Primitive Recursion ... If the characteristic function of X is primitively recursive then X ...
    (sci.math)