- 17,507

- 7,077

Submitted and judged by: @Erland

Solution Credit: @SSequence for 2a, 2B, C, D

1) In order for a solution to count, a full derivation or proof must be given. Answers with no proof will be ignored.

2) It is fine to use nontrivial results without proof as long as you cite them and as long as it is "common knowledge to all mathematicians". Whether the latter is satisfied will be decided on a case-by-case basis.

3) If you have seen the problem before and remember the solution, you cannot participate in the solution to that problem.

4) You are allowed to use google, wolframalpha or any other resource. However, you are not allowed to search the question directly. So if the question was to solve an integral, you are allowed to obtain numerical answers from software, you are allowed to search for useful integration techniques, but you cannot type in the integral in wolframalpha to see its solution.

Definitions:

The following functions from ##\mathbb N^k## to ##\mathbb N##, with ##k\ge 0##, are called basic functions:

B1) The zero constant function ##Z:\mathbb N^0\to \mathbb N##, given by [tex]Z()=0[/tex](so ##Z## is actually the constant ##0##).

B2) For all ##n\ge 0## and ##i## such that ##1\le i\le n##, the i:th n-ary projection function ##P_i^n:\mathbb N^k\to\mathbb N##, given by [tex]P_i^n(x_1, x_2,\dots, x_n)=x_i,[/tex] for all ##x_1,x_2,\dots,x_n\in \mathbb N##.

B3) The successor function ##S:\mathbb N^1\to \mathbb N##, given by [tex]S(x_1)=x_1+1,[/tex] for all ##x_1\in \mathbb N##.

We obtain new functions from old ones by applying the following operations:

O1) Composition: For all ##m,n\ge 0## and all functions ##g:\mathbb N^m\to \mathbb N## and ##h_1,h_2,\dots, h_m:\mathbb N^n\to \mathbb N##, we obtain the function ##f:\mathbb N^n\to \mathbb N##, given by

[tex]f(x_1,x_2,\dots, x_n)=g(h_1(x_1,x_2,\dots,x_n),h_2(x_1,x_2,\dots,x_n),\dots,h_m(x_1,x_2,\dots,x_n)),[/tex]

for all ##x_1,x_2,\dots,x_n\in \mathbb N##.

O2) Primitive recursion: For all ##n\ge 0## and all functions ##g:\mathbb N^n\to\mathbb N## and ##h:\mathbb N^{n+2}\to\mathbb N##, we obtain the (unique) function ##f:\mathbb N^{n+1}\to\mathbb N## which satisfies the following conditions:

i)

[tex]f(x_1,x_2,\dots,x_n,0)=g(x_1,x_2,\dots,x_n),[/tex]

for all ##x_1,x_2,\dots,x_n\in\mathbb N##,

ii)

[tex]f(x_1,x_2,\dots,x_n,x_{n+1}+1)=h(x_1,x_2,\dots, x_n, x_{n+1},f(x_1,x_2,\dots,x_n,x_{n+1})),[/tex]

for all ##x_1,x_2,\dots,x_n,x_{n+1}\in\mathbb N##.

A function ##f:\mathbb N^n\to \mathbb N##, for any ##n\ge 0##, is called primitive recursive if it can be obtained from the basic functions B1-B3 by finitely many applications of the operations O1 and O2.

Ackermann's function is the (unique) function ##A:\mathbb N^2\to \mathbb N## which satisfies the following conditions:

a) ##A(0,n)=n+1##,

b) ##A(m+1,0)=A(m,1)##,

c) ##A(m+1,n+1)=A(m,A(m+1,n))##,

for all ##m,n\in \mathbb N##.

a) Prove that the factorial function ##n!## is primitive recursive.

b) Prove that the "truncated subtraction" ##f(a,b) = \max\{a-b,0\}## is primitive recursive.

c) Prove that to each primitive recursive function ##f:\mathbb N^n\to \mathbb N##, for any ##n\ge 0##, there is an ##m\in\mathbb N## such that

[tex]f(x_1,x_2,\dots,x_n)\le A(m, \max_{1\le i\le n} x_i),[/tex]

for all ##x_1,x_2,\dots, x_n\in\mathbb N##.

d) Prove that ##A## is not primitive recursive.

Solution Credit: @SSequence for 2a, 2B, C, D

**RULES:**1) In order for a solution to count, a full derivation or proof must be given. Answers with no proof will be ignored.

2) It is fine to use nontrivial results without proof as long as you cite them and as long as it is "common knowledge to all mathematicians". Whether the latter is satisfied will be decided on a case-by-case basis.

3) If you have seen the problem before and remember the solution, you cannot participate in the solution to that problem.

4) You are allowed to use google, wolframalpha or any other resource. However, you are not allowed to search the question directly. So if the question was to solve an integral, you are allowed to obtain numerical answers from software, you are allowed to search for useful integration techniques, but you cannot type in the integral in wolframalpha to see its solution.

**CHALLENGE:**Definitions:

The following functions from ##\mathbb N^k## to ##\mathbb N##, with ##k\ge 0##, are called basic functions:

B1) The zero constant function ##Z:\mathbb N^0\to \mathbb N##, given by [tex]Z()=0[/tex](so ##Z## is actually the constant ##0##).

B2) For all ##n\ge 0## and ##i## such that ##1\le i\le n##, the i:th n-ary projection function ##P_i^n:\mathbb N^k\to\mathbb N##, given by [tex]P_i^n(x_1, x_2,\dots, x_n)=x_i,[/tex] for all ##x_1,x_2,\dots,x_n\in \mathbb N##.

B3) The successor function ##S:\mathbb N^1\to \mathbb N##, given by [tex]S(x_1)=x_1+1,[/tex] for all ##x_1\in \mathbb N##.

We obtain new functions from old ones by applying the following operations:

O1) Composition: For all ##m,n\ge 0## and all functions ##g:\mathbb N^m\to \mathbb N## and ##h_1,h_2,\dots, h_m:\mathbb N^n\to \mathbb N##, we obtain the function ##f:\mathbb N^n\to \mathbb N##, given by

[tex]f(x_1,x_2,\dots, x_n)=g(h_1(x_1,x_2,\dots,x_n),h_2(x_1,x_2,\dots,x_n),\dots,h_m(x_1,x_2,\dots,x_n)),[/tex]

for all ##x_1,x_2,\dots,x_n\in \mathbb N##.

O2) Primitive recursion: For all ##n\ge 0## and all functions ##g:\mathbb N^n\to\mathbb N## and ##h:\mathbb N^{n+2}\to\mathbb N##, we obtain the (unique) function ##f:\mathbb N^{n+1}\to\mathbb N## which satisfies the following conditions:

i)

[tex]f(x_1,x_2,\dots,x_n,0)=g(x_1,x_2,\dots,x_n),[/tex]

for all ##x_1,x_2,\dots,x_n\in\mathbb N##,

ii)

[tex]f(x_1,x_2,\dots,x_n,x_{n+1}+1)=h(x_1,x_2,\dots, x_n, x_{n+1},f(x_1,x_2,\dots,x_n,x_{n+1})),[/tex]

for all ##x_1,x_2,\dots,x_n,x_{n+1}\in\mathbb N##.

A function ##f:\mathbb N^n\to \mathbb N##, for any ##n\ge 0##, is called primitive recursive if it can be obtained from the basic functions B1-B3 by finitely many applications of the operations O1 and O2.

Ackermann's function is the (unique) function ##A:\mathbb N^2\to \mathbb N## which satisfies the following conditions:

a) ##A(0,n)=n+1##,

b) ##A(m+1,0)=A(m,1)##,

c) ##A(m+1,n+1)=A(m,A(m+1,n))##,

for all ##m,n\in \mathbb N##.

a) Prove that the factorial function ##n!## is primitive recursive.

b) Prove that the "truncated subtraction" ##f(a,b) = \max\{a-b,0\}## is primitive recursive.

c) Prove that to each primitive recursive function ##f:\mathbb N^n\to \mathbb N##, for any ##n\ge 0##, there is an ##m\in\mathbb N## such that

[tex]f(x_1,x_2,\dots,x_n)\le A(m, \max_{1\le i\le n} x_i),[/tex]

for all ##x_1,x_2,\dots, x_n\in\mathbb N##.

d) Prove that ##A## is not primitive recursive.

Last edited: