Arity of Primitive Recursive Functions The Next CEO of Stack OverflowPrimitive recursive functions, Recursive functions and recursive setPrimitive recursive functions with a restriction on the arity of projectionsProof-theoretic characterization of the primitive recursive functions?Computable function that enumerates the primitive recursive functionsRecursive and Primitive recursive functionsUniversal languages are primitive recursive.Recursive Enumeration of Total Recursive Functions vs Partial Recursive FunctionsPrimitive recursive functions definition (understanding “composition” and “primitive recursion”)Show that function is primitive recursive.Is enumeration by primitive recursive functions a useful concept?

Arrows in tikz Markov chain diagram overlap

How to show a landlord what we have in savings?

Shortening a title without changing its meaning

Find a path from s to t using as few red nodes as possible

Is it possible to create a QR code using text?

How exploitable/balanced is this homebrew spell: Spell Permanency?

Does the Idaho Potato Commission associate potato skins with healthy eating?

How badly should I try to prevent a user from XSSing themselves?

Why doesn't Shulchan Aruch include the laws of destroying fruit trees?

What steps are necessary to read a Modern SSD in Medieval Europe?

Direct Implications Between USA and UK in Event of No-Deal Brexit

Prodigo = pro + ago?

Can a PhD from a non-TU9 German university become a professor in a TU9 university?

How can I replace x-axis labels with pre-determined symbols?

Is a distribution that is normal, but highly skewed, considered Gaussian?

Avoiding the "not like other girls" trope?

Strange use of "whether ... than ..." in official text

pgfplots: How to draw a tangent graph below two others?

How can the PCs determine if an item is a phylactery?

My boss doesn't want me to have a side project

Is it a bad idea to plug the other end of ESD strap to wall ground?

Finitely generated matrix groups whose eigenvalues are all algebraic

How can I separate the number from the unit in argument?

That's an odd coin - I wonder why



Arity of Primitive Recursive Functions



The Next CEO of Stack OverflowPrimitive recursive functions, Recursive functions and recursive setPrimitive recursive functions with a restriction on the arity of projectionsProof-theoretic characterization of the primitive recursive functions?Computable function that enumerates the primitive recursive functionsRecursive and Primitive recursive functionsUniversal languages are primitive recursive.Recursive Enumeration of Total Recursive Functions vs Partial Recursive FunctionsPrimitive recursive functions definition (understanding “composition” and “primitive recursion”)Show that function is primitive recursive.Is enumeration by primitive recursive functions a useful concept?










2












$begingroup$


I'm currently working through a few books on computability and I am having a little bit of trouble with the primitive recursive scheme. When defining the primitive recursive scheme for unary functions most authors give something like the following:



$textFor function $h$ which is primitive recursive, the function $f$ defined by$ $$f(0)=m $$ $$f(n+1)=h(n,f(n))$$
is primitive recursive where $m$ is a zero-ary constant function and where $h$ is a binary function.



My question is can we view $h$ as a unary function since it seems to depend on only $n$? I feel like I could define $g(n)=h(n,f(n))$ where g is unary. This would then violate the requirement that the arity of $h$ be $k+1$ if the arity of $f$ is $k$. I'm just a little confused about how the arity requirement works in the unary case.



Edit: In addition to the above question, I'm curious about performing primitive recursion on zero-ary functions. For example, one of the authors I'm reading defines the zero-ary constant function $o'()=0$. He then proceeds to define the family of zero-ary constant functions $c_i'()=i$ as follows: $$c_0'(0)=o'()$$ and $$c_n+1'()=S((c_n'())$$ where S is the successor function. It seems like this violates the primitive recursive scheme conditions as well with $c_0'(0)$ having arity 1 and $c_n+1'()$ having the same arity as $S((c_n'())$ . I'm guessing something is going on in the background, but I can't seem to see it.










share|cite|improve this question











$endgroup$
















    2












    $begingroup$


    I'm currently working through a few books on computability and I am having a little bit of trouble with the primitive recursive scheme. When defining the primitive recursive scheme for unary functions most authors give something like the following:



    $textFor function $h$ which is primitive recursive, the function $f$ defined by$ $$f(0)=m $$ $$f(n+1)=h(n,f(n))$$
    is primitive recursive where $m$ is a zero-ary constant function and where $h$ is a binary function.



    My question is can we view $h$ as a unary function since it seems to depend on only $n$? I feel like I could define $g(n)=h(n,f(n))$ where g is unary. This would then violate the requirement that the arity of $h$ be $k+1$ if the arity of $f$ is $k$. I'm just a little confused about how the arity requirement works in the unary case.



    Edit: In addition to the above question, I'm curious about performing primitive recursion on zero-ary functions. For example, one of the authors I'm reading defines the zero-ary constant function $o'()=0$. He then proceeds to define the family of zero-ary constant functions $c_i'()=i$ as follows: $$c_0'(0)=o'()$$ and $$c_n+1'()=S((c_n'())$$ where S is the successor function. It seems like this violates the primitive recursive scheme conditions as well with $c_0'(0)$ having arity 1 and $c_n+1'()$ having the same arity as $S((c_n'())$ . I'm guessing something is going on in the background, but I can't seem to see it.










    share|cite|improve this question











    $endgroup$














      2












      2








      2





      $begingroup$


      I'm currently working through a few books on computability and I am having a little bit of trouble with the primitive recursive scheme. When defining the primitive recursive scheme for unary functions most authors give something like the following:



      $textFor function $h$ which is primitive recursive, the function $f$ defined by$ $$f(0)=m $$ $$f(n+1)=h(n,f(n))$$
      is primitive recursive where $m$ is a zero-ary constant function and where $h$ is a binary function.



      My question is can we view $h$ as a unary function since it seems to depend on only $n$? I feel like I could define $g(n)=h(n,f(n))$ where g is unary. This would then violate the requirement that the arity of $h$ be $k+1$ if the arity of $f$ is $k$. I'm just a little confused about how the arity requirement works in the unary case.



      Edit: In addition to the above question, I'm curious about performing primitive recursion on zero-ary functions. For example, one of the authors I'm reading defines the zero-ary constant function $o'()=0$. He then proceeds to define the family of zero-ary constant functions $c_i'()=i$ as follows: $$c_0'(0)=o'()$$ and $$c_n+1'()=S((c_n'())$$ where S is the successor function. It seems like this violates the primitive recursive scheme conditions as well with $c_0'(0)$ having arity 1 and $c_n+1'()$ having the same arity as $S((c_n'())$ . I'm guessing something is going on in the background, but I can't seem to see it.










      share|cite|improve this question











      $endgroup$




      I'm currently working through a few books on computability and I am having a little bit of trouble with the primitive recursive scheme. When defining the primitive recursive scheme for unary functions most authors give something like the following:



      $textFor function $h$ which is primitive recursive, the function $f$ defined by$ $$f(0)=m $$ $$f(n+1)=h(n,f(n))$$
      is primitive recursive where $m$ is a zero-ary constant function and where $h$ is a binary function.



      My question is can we view $h$ as a unary function since it seems to depend on only $n$? I feel like I could define $g(n)=h(n,f(n))$ where g is unary. This would then violate the requirement that the arity of $h$ be $k+1$ if the arity of $f$ is $k$. I'm just a little confused about how the arity requirement works in the unary case.



      Edit: In addition to the above question, I'm curious about performing primitive recursion on zero-ary functions. For example, one of the authors I'm reading defines the zero-ary constant function $o'()=0$. He then proceeds to define the family of zero-ary constant functions $c_i'()=i$ as follows: $$c_0'(0)=o'()$$ and $$c_n+1'()=S((c_n'())$$ where S is the successor function. It seems like this violates the primitive recursive scheme conditions as well with $c_0'(0)$ having arity 1 and $c_n+1'()$ having the same arity as $S((c_n'())$ . I'm guessing something is going on in the background, but I can't seem to see it.







      functions logic computability






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited 4 hours ago







      Newman

















      asked 5 hours ago









      NewmanNewman

      350213




      350213




















          2 Answers
          2






          active

          oldest

          votes


















          2












          $begingroup$

          You can indeed define $g(n)=h(n,f(n))$ (as I assume you intended to write) -- but in order to argue that this $g$ is primitive recursive, you need to already know that $f$ (as well as $h$) is primitive recursion, and for that you need to apply the primitive recursion rule, which depends on knowing that $h$ is primitive recursive.



          Note well that what the primitive recursion rule demands as a premise is that $h$ is primitive recursive as a two-argument function. That is the function that describes how to combine $n$ and $f(n)$ in order to find the number you want to be $f(n+1)$. In principle this $h$ needs to be applicable to every pair of numbers, not just ones where the second element happens to be $f$ applied to the first one. If you can't give such a general rule for $h$, the primitive recursion construction does not -- by definition -- necessarily produce a primitive recursive $f$.




          In response to the added material headed "edit": The construction you're quoting seems to be confusing at best. Note that primitive recursion does not define a sequence of functions, but a single function. And it does not make sense to use primitive recursion without having an argument to recurse over.



          The best way I can get what you quote to make sense is to say that "$c'_i()$" must be merely an obfuscated way to write "$c'(i)$". The construction defines a complete unary function $c'$ all at once. One may then prefer to speak about this function like an infinite sequence of constants, but that does not change what was "really" going on at the formal level.



          Alternatively, the author you quote is doing model theory, and is using recursion at the metalevel to define meanings for an infinity of new constant symbols. Then there's a priori nothing that constrains him to be using primitive recursion, or even recursion at all -- indeed, any way of defining the meanings in the (usually informal) style of reasoning he's using at the metalevel would work.






          share|cite|improve this answer











          $endgroup$












          • $begingroup$
            So it isn't possible to perform primitive recursion on a zero-ary function?
            $endgroup$
            – Newman
            3 hours ago










          • $begingroup$
            @Newman: zero-ary function $equiv$ constant?
            $endgroup$
            – hardmath
            3 hours ago










          • $begingroup$
            @hardmath Yes, I believe that's the convention this author is using. He actually defines a zero-ary zero function $c_0'()=0$ and a unary zero function $c_0(n)=0$ for every n.
            $endgroup$
            – Newman
            3 hours ago



















          2












          $begingroup$

          Any function $f$ that is obtained from primitive recursion is constructed from two prim. rec. functions g,h. If $g colon mathbbN^k rightarrow mathbbN$ and $h colon mathbbN^k + 2 rightarrow mathbbN$ are both primitive recursive then there is a unique function $f colon mathbbN^k + 1 rightarrow mathbbN$ such that $$ f(x,0) = g(x)\ f(x,y+1) = h(x,y,f(x,y))$$ both hold for all $x in mathbbN^k, y in mathbbN$. $g$ tells us where we start the recursion, $h$ is the recursive rule.



          Technically, however, in primitive recursion all functions are total (i.e. are defined on all inputs and always converge). So, in particular, $h$ is really defined for all $z in mathbbN$, not only for previous values of $f$! That is, we define $h(x,y,z)$ rather than $h(x,y,f(x,y))$.
          To answer your second question, recursion is based on the idea of defining the next value of a function given the previous input and, crucially, the previous value of said function. So no, $h$ must be of arity $mathbbN^k + 2$. Also note that you cannot use $f$ in the definition of $h$ as the existence of $f$ is implied by the existence and primitive recursiveness of both $g$ and $h$.






          share|cite|improve this answer











          $endgroup$












          • $begingroup$
            @hardmath Indeed, fixed it -- thanks!
            $endgroup$
            – MacRance
            3 hours ago











          Your Answer





          StackExchange.ifUsing("editor", function ()
          return StackExchange.using("mathjaxEditing", function ()
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
          );
          );
          , "mathjax-editing");

          StackExchange.ready(function()
          var channelOptions =
          tags: "".split(" "),
          id: "69"
          ;
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function()
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled)
          StackExchange.using("snippets", function()
          createEditor();
          );

          else
          createEditor();

          );

          function createEditor()
          StackExchange.prepareEditor(
          heartbeatType: 'answer',
          autoActivateHeartbeat: false,
          convertImagesToLinks: true,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: 10,
          bindNavPrevention: true,
          postfix: "",
          imageUploader:
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          ,
          noCode: true, onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          );



          );













          draft saved

          draft discarded


















          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3171258%2farity-of-primitive-recursive-functions%23new-answer', 'question_page');

          );

          Post as a guest















          Required, but never shown

























          2 Answers
          2






          active

          oldest

          votes








          2 Answers
          2






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes









          2












          $begingroup$

          You can indeed define $g(n)=h(n,f(n))$ (as I assume you intended to write) -- but in order to argue that this $g$ is primitive recursive, you need to already know that $f$ (as well as $h$) is primitive recursion, and for that you need to apply the primitive recursion rule, which depends on knowing that $h$ is primitive recursive.



          Note well that what the primitive recursion rule demands as a premise is that $h$ is primitive recursive as a two-argument function. That is the function that describes how to combine $n$ and $f(n)$ in order to find the number you want to be $f(n+1)$. In principle this $h$ needs to be applicable to every pair of numbers, not just ones where the second element happens to be $f$ applied to the first one. If you can't give such a general rule for $h$, the primitive recursion construction does not -- by definition -- necessarily produce a primitive recursive $f$.




          In response to the added material headed "edit": The construction you're quoting seems to be confusing at best. Note that primitive recursion does not define a sequence of functions, but a single function. And it does not make sense to use primitive recursion without having an argument to recurse over.



          The best way I can get what you quote to make sense is to say that "$c'_i()$" must be merely an obfuscated way to write "$c'(i)$". The construction defines a complete unary function $c'$ all at once. One may then prefer to speak about this function like an infinite sequence of constants, but that does not change what was "really" going on at the formal level.



          Alternatively, the author you quote is doing model theory, and is using recursion at the metalevel to define meanings for an infinity of new constant symbols. Then there's a priori nothing that constrains him to be using primitive recursion, or even recursion at all -- indeed, any way of defining the meanings in the (usually informal) style of reasoning he's using at the metalevel would work.






          share|cite|improve this answer











          $endgroup$












          • $begingroup$
            So it isn't possible to perform primitive recursion on a zero-ary function?
            $endgroup$
            – Newman
            3 hours ago










          • $begingroup$
            @Newman: zero-ary function $equiv$ constant?
            $endgroup$
            – hardmath
            3 hours ago










          • $begingroup$
            @hardmath Yes, I believe that's the convention this author is using. He actually defines a zero-ary zero function $c_0'()=0$ and a unary zero function $c_0(n)=0$ for every n.
            $endgroup$
            – Newman
            3 hours ago
















          2












          $begingroup$

          You can indeed define $g(n)=h(n,f(n))$ (as I assume you intended to write) -- but in order to argue that this $g$ is primitive recursive, you need to already know that $f$ (as well as $h$) is primitive recursion, and for that you need to apply the primitive recursion rule, which depends on knowing that $h$ is primitive recursive.



          Note well that what the primitive recursion rule demands as a premise is that $h$ is primitive recursive as a two-argument function. That is the function that describes how to combine $n$ and $f(n)$ in order to find the number you want to be $f(n+1)$. In principle this $h$ needs to be applicable to every pair of numbers, not just ones where the second element happens to be $f$ applied to the first one. If you can't give such a general rule for $h$, the primitive recursion construction does not -- by definition -- necessarily produce a primitive recursive $f$.




          In response to the added material headed "edit": The construction you're quoting seems to be confusing at best. Note that primitive recursion does not define a sequence of functions, but a single function. And it does not make sense to use primitive recursion without having an argument to recurse over.



          The best way I can get what you quote to make sense is to say that "$c'_i()$" must be merely an obfuscated way to write "$c'(i)$". The construction defines a complete unary function $c'$ all at once. One may then prefer to speak about this function like an infinite sequence of constants, but that does not change what was "really" going on at the formal level.



          Alternatively, the author you quote is doing model theory, and is using recursion at the metalevel to define meanings for an infinity of new constant symbols. Then there's a priori nothing that constrains him to be using primitive recursion, or even recursion at all -- indeed, any way of defining the meanings in the (usually informal) style of reasoning he's using at the metalevel would work.






          share|cite|improve this answer











          $endgroup$












          • $begingroup$
            So it isn't possible to perform primitive recursion on a zero-ary function?
            $endgroup$
            – Newman
            3 hours ago










          • $begingroup$
            @Newman: zero-ary function $equiv$ constant?
            $endgroup$
            – hardmath
            3 hours ago










          • $begingroup$
            @hardmath Yes, I believe that's the convention this author is using. He actually defines a zero-ary zero function $c_0'()=0$ and a unary zero function $c_0(n)=0$ for every n.
            $endgroup$
            – Newman
            3 hours ago














          2












          2








          2





          $begingroup$

          You can indeed define $g(n)=h(n,f(n))$ (as I assume you intended to write) -- but in order to argue that this $g$ is primitive recursive, you need to already know that $f$ (as well as $h$) is primitive recursion, and for that you need to apply the primitive recursion rule, which depends on knowing that $h$ is primitive recursive.



          Note well that what the primitive recursion rule demands as a premise is that $h$ is primitive recursive as a two-argument function. That is the function that describes how to combine $n$ and $f(n)$ in order to find the number you want to be $f(n+1)$. In principle this $h$ needs to be applicable to every pair of numbers, not just ones where the second element happens to be $f$ applied to the first one. If you can't give such a general rule for $h$, the primitive recursion construction does not -- by definition -- necessarily produce a primitive recursive $f$.




          In response to the added material headed "edit": The construction you're quoting seems to be confusing at best. Note that primitive recursion does not define a sequence of functions, but a single function. And it does not make sense to use primitive recursion without having an argument to recurse over.



          The best way I can get what you quote to make sense is to say that "$c'_i()$" must be merely an obfuscated way to write "$c'(i)$". The construction defines a complete unary function $c'$ all at once. One may then prefer to speak about this function like an infinite sequence of constants, but that does not change what was "really" going on at the formal level.



          Alternatively, the author you quote is doing model theory, and is using recursion at the metalevel to define meanings for an infinity of new constant symbols. Then there's a priori nothing that constrains him to be using primitive recursion, or even recursion at all -- indeed, any way of defining the meanings in the (usually informal) style of reasoning he's using at the metalevel would work.






          share|cite|improve this answer











          $endgroup$



          You can indeed define $g(n)=h(n,f(n))$ (as I assume you intended to write) -- but in order to argue that this $g$ is primitive recursive, you need to already know that $f$ (as well as $h$) is primitive recursion, and for that you need to apply the primitive recursion rule, which depends on knowing that $h$ is primitive recursive.



          Note well that what the primitive recursion rule demands as a premise is that $h$ is primitive recursive as a two-argument function. That is the function that describes how to combine $n$ and $f(n)$ in order to find the number you want to be $f(n+1)$. In principle this $h$ needs to be applicable to every pair of numbers, not just ones where the second element happens to be $f$ applied to the first one. If you can't give such a general rule for $h$, the primitive recursion construction does not -- by definition -- necessarily produce a primitive recursive $f$.




          In response to the added material headed "edit": The construction you're quoting seems to be confusing at best. Note that primitive recursion does not define a sequence of functions, but a single function. And it does not make sense to use primitive recursion without having an argument to recurse over.



          The best way I can get what you quote to make sense is to say that "$c'_i()$" must be merely an obfuscated way to write "$c'(i)$". The construction defines a complete unary function $c'$ all at once. One may then prefer to speak about this function like an infinite sequence of constants, but that does not change what was "really" going on at the formal level.



          Alternatively, the author you quote is doing model theory, and is using recursion at the metalevel to define meanings for an infinity of new constant symbols. Then there's a priori nothing that constrains him to be using primitive recursion, or even recursion at all -- indeed, any way of defining the meanings in the (usually informal) style of reasoning he's using at the metalevel would work.







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited 4 hours ago

























          answered 4 hours ago









          Henning MakholmHenning Makholm

          243k17308553




          243k17308553











          • $begingroup$
            So it isn't possible to perform primitive recursion on a zero-ary function?
            $endgroup$
            – Newman
            3 hours ago










          • $begingroup$
            @Newman: zero-ary function $equiv$ constant?
            $endgroup$
            – hardmath
            3 hours ago










          • $begingroup$
            @hardmath Yes, I believe that's the convention this author is using. He actually defines a zero-ary zero function $c_0'()=0$ and a unary zero function $c_0(n)=0$ for every n.
            $endgroup$
            – Newman
            3 hours ago

















          • $begingroup$
            So it isn't possible to perform primitive recursion on a zero-ary function?
            $endgroup$
            – Newman
            3 hours ago










          • $begingroup$
            @Newman: zero-ary function $equiv$ constant?
            $endgroup$
            – hardmath
            3 hours ago










          • $begingroup$
            @hardmath Yes, I believe that's the convention this author is using. He actually defines a zero-ary zero function $c_0'()=0$ and a unary zero function $c_0(n)=0$ for every n.
            $endgroup$
            – Newman
            3 hours ago
















          $begingroup$
          So it isn't possible to perform primitive recursion on a zero-ary function?
          $endgroup$
          – Newman
          3 hours ago




          $begingroup$
          So it isn't possible to perform primitive recursion on a zero-ary function?
          $endgroup$
          – Newman
          3 hours ago












          $begingroup$
          @Newman: zero-ary function $equiv$ constant?
          $endgroup$
          – hardmath
          3 hours ago




          $begingroup$
          @Newman: zero-ary function $equiv$ constant?
          $endgroup$
          – hardmath
          3 hours ago












          $begingroup$
          @hardmath Yes, I believe that's the convention this author is using. He actually defines a zero-ary zero function $c_0'()=0$ and a unary zero function $c_0(n)=0$ for every n.
          $endgroup$
          – Newman
          3 hours ago





          $begingroup$
          @hardmath Yes, I believe that's the convention this author is using. He actually defines a zero-ary zero function $c_0'()=0$ and a unary zero function $c_0(n)=0$ for every n.
          $endgroup$
          – Newman
          3 hours ago












          2












          $begingroup$

          Any function $f$ that is obtained from primitive recursion is constructed from two prim. rec. functions g,h. If $g colon mathbbN^k rightarrow mathbbN$ and $h colon mathbbN^k + 2 rightarrow mathbbN$ are both primitive recursive then there is a unique function $f colon mathbbN^k + 1 rightarrow mathbbN$ such that $$ f(x,0) = g(x)\ f(x,y+1) = h(x,y,f(x,y))$$ both hold for all $x in mathbbN^k, y in mathbbN$. $g$ tells us where we start the recursion, $h$ is the recursive rule.



          Technically, however, in primitive recursion all functions are total (i.e. are defined on all inputs and always converge). So, in particular, $h$ is really defined for all $z in mathbbN$, not only for previous values of $f$! That is, we define $h(x,y,z)$ rather than $h(x,y,f(x,y))$.
          To answer your second question, recursion is based on the idea of defining the next value of a function given the previous input and, crucially, the previous value of said function. So no, $h$ must be of arity $mathbbN^k + 2$. Also note that you cannot use $f$ in the definition of $h$ as the existence of $f$ is implied by the existence and primitive recursiveness of both $g$ and $h$.






          share|cite|improve this answer











          $endgroup$












          • $begingroup$
            @hardmath Indeed, fixed it -- thanks!
            $endgroup$
            – MacRance
            3 hours ago















          2












          $begingroup$

          Any function $f$ that is obtained from primitive recursion is constructed from two prim. rec. functions g,h. If $g colon mathbbN^k rightarrow mathbbN$ and $h colon mathbbN^k + 2 rightarrow mathbbN$ are both primitive recursive then there is a unique function $f colon mathbbN^k + 1 rightarrow mathbbN$ such that $$ f(x,0) = g(x)\ f(x,y+1) = h(x,y,f(x,y))$$ both hold for all $x in mathbbN^k, y in mathbbN$. $g$ tells us where we start the recursion, $h$ is the recursive rule.



          Technically, however, in primitive recursion all functions are total (i.e. are defined on all inputs and always converge). So, in particular, $h$ is really defined for all $z in mathbbN$, not only for previous values of $f$! That is, we define $h(x,y,z)$ rather than $h(x,y,f(x,y))$.
          To answer your second question, recursion is based on the idea of defining the next value of a function given the previous input and, crucially, the previous value of said function. So no, $h$ must be of arity $mathbbN^k + 2$. Also note that you cannot use $f$ in the definition of $h$ as the existence of $f$ is implied by the existence and primitive recursiveness of both $g$ and $h$.






          share|cite|improve this answer











          $endgroup$












          • $begingroup$
            @hardmath Indeed, fixed it -- thanks!
            $endgroup$
            – MacRance
            3 hours ago













          2












          2








          2





          $begingroup$

          Any function $f$ that is obtained from primitive recursion is constructed from two prim. rec. functions g,h. If $g colon mathbbN^k rightarrow mathbbN$ and $h colon mathbbN^k + 2 rightarrow mathbbN$ are both primitive recursive then there is a unique function $f colon mathbbN^k + 1 rightarrow mathbbN$ such that $$ f(x,0) = g(x)\ f(x,y+1) = h(x,y,f(x,y))$$ both hold for all $x in mathbbN^k, y in mathbbN$. $g$ tells us where we start the recursion, $h$ is the recursive rule.



          Technically, however, in primitive recursion all functions are total (i.e. are defined on all inputs and always converge). So, in particular, $h$ is really defined for all $z in mathbbN$, not only for previous values of $f$! That is, we define $h(x,y,z)$ rather than $h(x,y,f(x,y))$.
          To answer your second question, recursion is based on the idea of defining the next value of a function given the previous input and, crucially, the previous value of said function. So no, $h$ must be of arity $mathbbN^k + 2$. Also note that you cannot use $f$ in the definition of $h$ as the existence of $f$ is implied by the existence and primitive recursiveness of both $g$ and $h$.






          share|cite|improve this answer











          $endgroup$



          Any function $f$ that is obtained from primitive recursion is constructed from two prim. rec. functions g,h. If $g colon mathbbN^k rightarrow mathbbN$ and $h colon mathbbN^k + 2 rightarrow mathbbN$ are both primitive recursive then there is a unique function $f colon mathbbN^k + 1 rightarrow mathbbN$ such that $$ f(x,0) = g(x)\ f(x,y+1) = h(x,y,f(x,y))$$ both hold for all $x in mathbbN^k, y in mathbbN$. $g$ tells us where we start the recursion, $h$ is the recursive rule.



          Technically, however, in primitive recursion all functions are total (i.e. are defined on all inputs and always converge). So, in particular, $h$ is really defined for all $z in mathbbN$, not only for previous values of $f$! That is, we define $h(x,y,z)$ rather than $h(x,y,f(x,y))$.
          To answer your second question, recursion is based on the idea of defining the next value of a function given the previous input and, crucially, the previous value of said function. So no, $h$ must be of arity $mathbbN^k + 2$. Also note that you cannot use $f$ in the definition of $h$ as the existence of $f$ is implied by the existence and primitive recursiveness of both $g$ and $h$.







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited 3 hours ago

























          answered 4 hours ago









          MacRanceMacRance

          1726




          1726











          • $begingroup$
            @hardmath Indeed, fixed it -- thanks!
            $endgroup$
            – MacRance
            3 hours ago
















          • $begingroup$
            @hardmath Indeed, fixed it -- thanks!
            $endgroup$
            – MacRance
            3 hours ago















          $begingroup$
          @hardmath Indeed, fixed it -- thanks!
          $endgroup$
          – MacRance
          3 hours ago




          $begingroup$
          @hardmath Indeed, fixed it -- thanks!
          $endgroup$
          – MacRance
          3 hours ago

















          draft saved

          draft discarded
















































          Thanks for contributing an answer to Mathematics Stack Exchange!


          • Please be sure to answer the question. Provide details and share your research!

          But avoid


          • Asking for help, clarification, or responding to other answers.

          • Making statements based on opinion; back them up with references or personal experience.

          Use MathJax to format equations. MathJax reference.


          To learn more, see our tips on writing great answers.




          draft saved


          draft discarded














          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3171258%2farity-of-primitive-recursive-functions%23new-answer', 'question_page');

          );

          Post as a guest















          Required, but never shown





















































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown

































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown







          Popular posts from this blog

          Are there any AGPL-style licences that require source code modifications to be public? Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern) Announcing the arrival of Valued Associate #679: Cesar Manara Unicorn Meta Zoo #1: Why another podcast?Force derivative works to be publicAre there any GPL like licenses for Apple App Store?Do you violate the GPL if you provide source code that cannot be compiled?GPL - is it distribution to use libraries in an appliance loaned to customers?Distributing App for free which uses GPL'ed codeModifications of server software under GPL, with web/CLI interfaceDoes using an AGPLv3-licensed library prevent me from dual-licensing my own source code?Can I publish only select code under GPLv3 from a private project?Is there published precedent regarding the scope of covered work that uses AGPL software?If MIT licensed code links to GPL licensed code what should be the license of the resulting binary program?If I use a public API endpoint that has its source code licensed under AGPL in my app, do I need to disclose my source?

          2013 GY136 Descoberta | Órbita | Referências Menu de navegação«List Of Centaurs and Scattered-Disk Objects»«List of Known Trans-Neptunian Objects»

          Button changing it's text & action. Good or terrible? The 2019 Stack Overflow Developer Survey Results Are Inchanging text on user mouseoverShould certain functions be “hard to find” for powerusers to discover?Custom liking function - do I need user login?Using different checkbox style for different checkbox behaviorBest Practices: Save and Exit in Software UIInteraction with remote validated formMore efficient UI to progress the user through a complicated process?Designing a popup notice for a gameShould bulk-editing functions be hidden until a table row is selected, or is there a better solution?Is it bad practice to disable (replace) the context menu?