9.* A function is elementary if it can be obtained from the functions s, n, u;, +, - by a finite sequence of applications of composition, bounded summation, and bounded product. (By application of bounded summa- tion we mean obtaining the function !-of(t, xp,...,xn) from f(t, x,,...,x), and similarly for bounded product.) (a) Show that every elementary function is primitive recursive. (b) Show that x.y, x', and x! are elementary. (c) Show that if n + 1-ary predicates P and Q are elementary, then So are ~P, PV, P & Q, (VI)s ,P(1, X1,...,xn), (31)s, P(t, x), ..., X.,), and min, syP(t, x1,...,x.). (d) Show that Prime(x) is elementary. (e) Let the binary function exp, (x) be defined expo(x) = x expy+(x) = 2exp,(x). Show that for every elementary function f(x,...,xn), there is a constant k such that f(x},...,xn) s exp (max{x1,...,x,}). (Hint: Show that for every n there is an m = n such that x exp,(x) s exp.(x) for all x.) (f) Show that expy(x) is not elementary. Conclude that the class of elementary functions is a proper subset of the class of primitive recursive functions. 9.* A function is elementary if it can be obtained from the functions s, n, u;, +, - by a finite sequence of applications of composition, bounded summation, and bounded product. (By application of bounded summa- tion we mean obtaining the function !-of(t, xp,...,xn) from f(t, x,,...,x), and similarly for bounded product.) (a) Show that every elementary function is primitive recursive. (b) Show that x.y, x', and x! are elementary. (c) Show that if n + 1-ary predicates P and Q are elementary, then So are ~P, PV, P & Q, (VI)s ,P(1, X1,...,xn), (31)s, P(t, x), ..., X.,), and min, syP(t, x1,...,x.). (d) Show that Prime(x) is elementary. (e) Let the binary function exp, (x) be defined expo(x) = x expy+(x) = 2exp,(x). Show that for every elementary function f(x,...,xn), there is a constant k such that f(x},...,xn) s exp (max{x1,...,x,}). (Hint: Show that for every n there is an m = n such that x exp,(x) s exp.(x) for all x.) (f) Show that expy(x) is not elementary. Conclude that the class of elementary functions is a proper subset of the class of primitive recursive functions