The set of primitive recursive functions is [...] the smallest set containing the constant 0, the successor function, and projection functions, and closed under composition and primitive recursion.My question is about the way composition, which does not seem very intuitive to meIf f is a k-ary function and g 0 , … , g k − 1 are l-ary functions on the natural numbers, the composition of f with g 0 , … , g k − 1 is the l-ary function h defined by h ( x 0 , … , x l − 1 ) = f ( g 0 ( x 0 , … , x l − 1 ) , … , g k − 1 ( x 0 , … , x l − 1 ) ) .Is this just another way of stating composition as one may understand it in real analysis: that if we have g : N l → N k and f : N k → N ,then we can define some composed function h : N l → N ?Or, would there be any "risk" at looking at the definition in this simplistic way?

Question

The set of primitive recursive functions is [...] the smallest set containing the constant 0, the successor function, and projection functions, and closed under composition and primitive recursion.My question is about the way composition, which does not seem very intuitive to meIf   f is a   k-ary function and       g    0    ,  …  ,      g          k      −      1       are   l-ary functions on the natural numbers, the composition of   f with       g    0    ,  …  ,      g          k      −      1       is the   l-ary function   h defined by  h  (      x    0    ,  …  ,      x          l      −      1        )  =  f  (      g    0    (      x    0    ,  …  ,      x          l      −      1        )  ,  …  ,      g          k      −      1        (      x    0    ,  …  ,      x          l      −      1        )  )  .Is this just another way of stating composition as one may understand it in real analysis: that if we have  g  :        N    l    →        N    k      and    f  :        N    k    →  N  ,then we can define some composed function  h  :        N    l    →  N  ?Or, would there be any &quot;risk&quot; at looking at the definition in this simplistic way?

Ismael Blackwell · Accepted Answer

It&#039;s a matter of technical convenience. You could define the primitive recursive functions to be a set of functions from   N to   N, but then to deal with functions of more than one argument (like addition and multiplication), you&#039;d have to show how to represent pairs of natural numbers as natural numbers. Alternatively, you could define the primitive recursive functions to be functions from         N    m   to         N    n   for arbitrary   m and   n (so your   g would be a possible primitive recursive function), but any such function would really just comprise n functions from         N    m   to   N. Your text is taking the standard compromise of defining primitive recursive functions to map         N    m   to   N. This means that to construct a function like   (  x  ,  y  )  ↦      x    2    +      y    3   you need a notion of functional composition that lets you view it as a composition of the pair of functions   (  x  ↦      x    2    ,  y  ↦      y    3    ) with the function   (  a  ,  b  )  ↦  a  +  b.

The set of primitive recursive functions is [...] the smallest set containing the constant 0, the su

Answered question

Answer & Explanation

New Questions in College Statistics