Arity of Primitive Recursive Functions












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:



$text{For 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:



    $text{For 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:



      $text{For 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:



      $text{For 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 mathbb{N}^k rightarrow mathbb{N}$ and $h colon mathbb{N}^{k + 2} rightarrow mathbb{N}$ are both primitive recursive then there is a unique function $f colon mathbb{N}^{k + 1} rightarrow mathbb{N}$ such that $$ f(x,0) = g(x)\ f(x,y+1) = h(x,y,f(x,y))$$ both hold for all $x in mathbb{N}^k, y in mathbb{N}$. $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 mathbb{N}$, 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 $mathbb{N}^{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 mathbb{N}^k rightarrow mathbb{N}$ and $h colon mathbb{N}^{k + 2} rightarrow mathbb{N}$ are both primitive recursive then there is a unique function $f colon mathbb{N}^{k + 1} rightarrow mathbb{N}$ such that $$ f(x,0) = g(x)\ f(x,y+1) = h(x,y,f(x,y))$$ both hold for all $x in mathbb{N}^k, y in mathbb{N}$. $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 mathbb{N}$, 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 $mathbb{N}^{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 mathbb{N}^k rightarrow mathbb{N}$ and $h colon mathbb{N}^{k + 2} rightarrow mathbb{N}$ are both primitive recursive then there is a unique function $f colon mathbb{N}^{k + 1} rightarrow mathbb{N}$ such that $$ f(x,0) = g(x)\ f(x,y+1) = h(x,y,f(x,y))$$ both hold for all $x in mathbb{N}^k, y in mathbb{N}$. $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 mathbb{N}$, 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 $mathbb{N}^{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 mathbb{N}^k rightarrow mathbb{N}$ and $h colon mathbb{N}^{k + 2} rightarrow mathbb{N}$ are both primitive recursive then there is a unique function $f colon mathbb{N}^{k + 1} rightarrow mathbb{N}$ such that $$ f(x,0) = g(x)\ f(x,y+1) = h(x,y,f(x,y))$$ both hold for all $x in mathbb{N}^k, y in mathbb{N}$. $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 mathbb{N}$, 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 $mathbb{N}^{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 mathbb{N}^k rightarrow mathbb{N}$ and $h colon mathbb{N}^{k + 2} rightarrow mathbb{N}$ are both primitive recursive then there is a unique function $f colon mathbb{N}^{k + 1} rightarrow mathbb{N}$ such that $$ f(x,0) = g(x)\ f(x,y+1) = h(x,y,f(x,y))$$ both hold for all $x in mathbb{N}^k, y in mathbb{N}$. $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 mathbb{N}$, 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 $mathbb{N}^{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

          Knooppunt Holsloot

          Altaar (religie)

          Gregoriusmis