Skip to main content
added 16 characters in body
Source Link
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k

The class PR of primitive recursive functions is the smallest class of functions containing a few simple functions (successor, zero, projection) and closed under composition and definition of functions by recursion.

If $f:\mathbb{N}^k\to \mathbb{N}$ is any function at all, one can form the class $PR(f)$ of functions that are primitive recursive relative to $f$, simply by adding $f$ as one of the simple functions and then closing under composition and recursion. If $f$ is total, then every function in $PR(f)$ is total, and if $f$ is computable, then every function in $PR(f)$ will be computable. This amounts to using $f$ as an oracle, as mentioned by Max. There is a clear hierarchy here, because if $f\in PR(g)$, then $PR(f)\subset PR(g)$, and this hierarchy amounts to something like the hierarchy of Turing degrees, but with primitive recursion.

More generally, for any set $F$ of functions, we may form $PR(F)$ by adding all the functions in $F$ and closing under composition and recursion, and we still have the hierarchy that if $F\subset PR(G)$, then $PR(F)\subset PR(G)$. This more general situation seems fully general, since if you have a class $F$ of functions containing all primitive recursive functions and closed under composition and recursion, then $F=PR(F)$, and so this hierarchy seems to capture all the classes that you might wish to consider.

The class PR of primitive recursive functions is the smallest class of functions containing a few simple functions (successor, zero, projection) and closed under definition of functions by recursion.

If $f:\mathbb{N}^k\to \mathbb{N}$ is any function at all, one can form the class $PR(f)$ of functions that are primitive recursive relative to $f$, simply by adding $f$ as one of the simple functions and then closing under composition and recursion. If $f$ is total, then every function in $PR(f)$ is total, and if $f$ is computable, then every function in $PR(f)$ will be computable. This amounts to using $f$ as an oracle, as mentioned by Max. There is a clear hierarchy here, because if $f\in PR(g)$, then $PR(f)\subset PR(g)$, and this hierarchy amounts to something like the hierarchy of Turing degrees, but with primitive recursion.

More generally, for any set $F$ of functions, we may form $PR(F)$ by adding all the functions in $F$ and closing under composition and recursion, and we still have the hierarchy that if $F\subset PR(G)$, then $PR(F)\subset PR(G)$. This more general situation seems fully general, since if you have a class $F$ of functions containing all primitive recursive functions and closed under composition and recursion, then $F=PR(F)$, and so this hierarchy seems to capture all the classes that you might wish to consider.

The class PR of primitive recursive functions is the smallest class of functions containing a few simple functions (successor, zero, projection) and closed under composition and definition of functions by recursion.

If $f:\mathbb{N}^k\to \mathbb{N}$ is any function at all, one can form the class $PR(f)$ of functions that are primitive recursive relative to $f$, simply by adding $f$ as one of the simple functions and then closing under composition and recursion. If $f$ is total, then every function in $PR(f)$ is total, and if $f$ is computable, then every function in $PR(f)$ will be computable. This amounts to using $f$ as an oracle, as mentioned by Max. There is a clear hierarchy here, because if $f\in PR(g)$, then $PR(f)\subset PR(g)$, and this hierarchy amounts to something like the hierarchy of Turing degrees, but with primitive recursion.

More generally, for any set $F$ of functions, we may form $PR(F)$ by adding all the functions in $F$ and closing under composition and recursion, and we still have the hierarchy that if $F\subset PR(G)$, then $PR(F)\subset PR(G)$. This more general situation seems fully general, since if you have a class $F$ of functions containing all primitive recursive functions and closed under composition and recursion, then $F=PR(F)$, and so this hierarchy seems to capture all the classes that you might wish to consider.

Source Link
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k

The class PR of primitive recursive functions is the smallest class of functions containing a few simple functions (successor, zero, projection) and closed under definition of functions by recursion.

If $f:\mathbb{N}^k\to \mathbb{N}$ is any function at all, one can form the class $PR(f)$ of functions that are primitive recursive relative to $f$, simply by adding $f$ as one of the simple functions and then closing under composition and recursion. If $f$ is total, then every function in $PR(f)$ is total, and if $f$ is computable, then every function in $PR(f)$ will be computable. This amounts to using $f$ as an oracle, as mentioned by Max. There is a clear hierarchy here, because if $f\in PR(g)$, then $PR(f)\subset PR(g)$, and this hierarchy amounts to something like the hierarchy of Turing degrees, but with primitive recursion.

More generally, for any set $F$ of functions, we may form $PR(F)$ by adding all the functions in $F$ and closing under composition and recursion, and we still have the hierarchy that if $F\subset PR(G)$, then $PR(F)\subset PR(G)$. This more general situation seems fully general, since if you have a class $F$ of functions containing all primitive recursive functions and closed under composition and recursion, then $F=PR(F)$, and so this hierarchy seems to capture all the classes that you might wish to consider.