Question

10. Suppose g: N→ N is primitive recursive. Define f: N² → N by f(x, 0) = g(x) f(x,y+1) = f(f(x, y), y)

Note that the equations above do not show that f is p.r.-the second one is not in the proper form. Nevertheless, prove that ƒ is p.r. (Hint: Write out the formulas for f(x, 0), f(x, 1), f(x, 2), and f(x, 3). See a pattern? Prove the pattern holds using mathematical induction. Then apply the re- sult of problem 9 above.) You may assume that binary addition, multiplication, and exponentiation of natural numbers are p.r. functions.

Answer 1

To prove that the function f(x, y) = g(x)^y is primitive recursive, we start by writing out the formulas for f(x, 0), f(x, 1), f(x, 2), and f(x, 3). Using the given equations, we can see that f(x, 0) = g(x), f(x, 1) = f(g(x), 0), f(x, 2) = f(f(g(x), 0), 1), and f(x, 3) = f(f(f(g(x), 0), 1), 2). By observing the pattern, we can conclude that f(x, y) = f(g(x), y). To prove that this pattern holds, we can use mathematical induction.

Step-by-step explanation:

To prove that the function f(x, y) = g(x)^y is primitive recursive, we start by writing out the formulas for f(x, 0), f(x, 1), f(x, 2), and f(x, 3). Using the given equations, we can see that f(x, 0) = g(x), f(x, 1) = f(g(x), 0), f(x, 2) = f(f(g(x), 0), 1), and f(x, 3) = f(f(f(g(x), 0), 1), 2). By observing the pattern, we can conclude that f(x, y) = f(g(x), y). To prove that this pattern holds, we can use mathematical induction.

In the base case, when y = 0, we have f(x,0) = g(x) which matches the formula we started with. In the induction step, we assume that f(x, y) = f(g(x), y) is true for some y and prove that it holds for y + 1. Using the recursive definition of f, we have f(x, y + 1) = f(f(x, y), y). By substituting f(x, y) = f(g(x), y), we get f(x, y + 1) = f(f(g(x), y), y) which matches the formula we wanted to prove.

Since g(x) is primitive recursive and we have shown that f(x, y) = f(g(x), y), we can conclude that f(x, y) is also primitive recursive.