Gödel's beta-function lemma

[2/100%]

Show

LaTeX

Show LaTeX

Problem III.1.17 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.1 "Partial Recursive Functions"

Consider the Godel function

\beta (x, y, z) = \operatorname {rest}(x, 1 + y(z+1)).

Prove that, whatever the finite sequence of natural numbers $a_{1}, \ldots , a_{n}$ may be, the system of equations

\begin{cases} \beta (x, y, 0) = \alpha _{0}, \\ \makebox[0pt][l]{\dotfill } \\ \beta (x, y, n) = \alpha _{n}, \end{cases}

has at least one solution $x, y$ .

Problem III.1.30 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.1 "Partial Recursive Functions"

Prove that the function $f^{n+1}$ , obtained by means of the primitive recursion operator from everywhere defined functions $g^{n}$ and $h^{n+2}$ , can be obtained from these functions and the functions $+, \symdiff , s, o, I_{m}^{n}$ and $c, l, r, \beta$ from problems III.1.13, III.1.17, by means of superpositions and a $\mu$ -operator of the special form from problem III.1.29.

References

[LaMa02] Lavrov I.A., Maksimova L.L. Задачи по теории множеств, математической логике и теории алгоритмов. 5-е изд., Физматлит, 2002.