1

So i have been recently introduced to computability and recursion. And we are doing everything very formally. That is why when forming a primitive recursion we need g,h to be computable and then f is when $f(x_1,x_2...x_n,0)=g(x_1,x_2...x_n)$ and $f(x_1,x_2...x_n,y+1)=h(x_1,x_2...x_n,f(x_1,x_2...x_n,y))$. Where arity is important so f has n+1 arity, g has n arity and h has n+1 arity. Now i was tasked with showing factorial is computable. It is obvious that (we will call factorial n) $n(0)=1$ (we know 1 is primitive and can have any arity, even 0?). Now $n(y+1)=S(y)*n(y)$ but clearly multiplication is of arity 2 so i have an arity problem. How do i remedy it?

Thank you

Sorfosh
  • 3,266

1 Answers1

0

Your current proof is fine, there is no arity problem. Currently you have $g \equiv 0$ of arity 0 and $h(x, y) = S(x) \cdot y$ of arity 2. Applying recursion using these two functions gives you the factorial function $n$ which has arity 1. Although multiplication has arity 2, you've composed multiplication with other functions so the function overall has arity 1.

bitesizebo
  • 4,153
  • How i see it, arity is not the number of distinct variables we plug in, bur rather how many "places" for a variable we have. If M is a function of multiplication we would get M(S(y),n(y)) so we have 2 "places" and so arity 2. – Sorfosh Apr 21 '18 at 00:52
  • @Sorfosh No, the arity of a function is the number of distinct variables we plug in. We say $f$ has arity $k$ if $f$ is a function $\mathbb N^k \to \mathbb N$ ($\mathbb N$ can be other sets in different contexts). See https://en.wikipedia.org/wiki/Arity – bitesizebo Apr 21 '18 at 00:55
  • That might be so, but the point is, that it does not fit the pattern I was given to show primitive recursion. So even if arities match up, the problem still stands we have M(S(y),n(y)) but we need f(n(y)). Now i need to find such f. – Sorfosh Apr 21 '18 at 01:00
  • @Sorfosh Your $n$ is your $f$, you've just called it $n$ for some reason – bitesizebo Apr 21 '18 at 01:01
  • ? I need to find $f$ such that $n(y+1)=f(n(y))$ where f is computable. – Sorfosh Apr 21 '18 at 01:03
  • @Sorfosh No, to construct $n$ by recursion you need to find $g$ of arity 0 (i.e. a constant) and $h$ of arity 2 such that $n(0) = g$ and $n(y + 1) = h(y, n(y))$. The choices $g = 0$ and $h(y, z) = S(y) \cdot z$ work for the factorial function. – bitesizebo Apr 21 '18 at 01:08
  • This is now how we defined primitive recursion. in your case $h$ has two entries, I need it to only have one. – Sorfosh Apr 21 '18 at 01:11
  • Let us continue this discussion in chat. – bitesizebo Apr 21 '18 at 01:12