Доказательство несовпадения классов простых примитивно рекурсивных функций

Пусть $X$, $Y$ – классы примитивно рекурсивных функций (сокращенно прф) и пусть требуется доказать следующее утверждение:
(1) неверно, что всякая функция из класса $X$ принадлежит классу $Y$. Такое утверждение обычно доказывается указанием прф из класса $X$, растущей быстрее любой прф из класса $Y$, или “простой” прф, например $\lambda x(x+1)$, $\lambda xy(x+y)$, из класса $X$, которая не принадлежит классу $Y$. Предлагается метод, позволяющий доказывать утверждения вида (1) для некоторых классов прф и $Y$ таких, что во-первых, функции класса $X$ растут не быстрее функций класса $Y$, во-вторых, класс $Y$ содержит “простые” прф, такие как $\lambda xy(x+y)$, $\lambda xy(x-y)$ и др.
Предлагаемый метод заключается в следующем. Выбирается некоторый класс прф $Z$ и для каждой прф $f$ строится такая операция $\delta_f$ над функциями из класса $Z$, что для всякой $f$ из $Y$ класс $Z$ замкнут относительно операции $\delta_f$, с другой стороны неверно, что для всякой $f$ из $X$ класс $Z$ замкнут относительно $\delta_f$.
Опишем одно из возможных применений предлагаемого метода. Не будем различать словарные и числовые прф и предикаты, имея в виду следующее взаимно однозначное соответствие между словами в алфавите $\{1,2\}$ и натуральными числами: слову $a_na_{n-1}\dots a_1a_0$ в алфавите $\{1,2\}$ соответствует число $\sum^n_{i=0}a_i2^1$. Пусть $\nu(x,i)$ равно $i$-ому знаку в слове $x$ (последняя буква считается $0$-ым знаком), $|x|$–длина $x$; $\operatorname{con}(x,y)$ – результат приписывания справа к слову $x$ слова $y$; $\theta$, $\overline\theta$ – характеристические функции равенства и неравенства. Пусть $RF$ – класс прф, получаемых из прф $\theta$, $\overline\theta$, $\operatorname{con}$, $\lambda x0$, $\sigma$, $I^n_k$ посредством операции ограниченной минимизации и подстановки функций. Отметим, что класс отношений класса $RF$ равен классу рудиментарных отношений. Пусть $R_sF(f_1,\dots,f_l)$ – класс прф, получаемых из прф $f_1,\dots,f_l$ посредством операции подстановки и операции, ставящей в соответствие функции $g$, такую $f$, что $f(\overline x,y)=\mu t_{\leqslant y}[tPy\& g(\overline x,t)=0]$, где $tPy\leftrightharpoons t$ – подслово $y$. Отметим, что характеристическая функция всякого $s$-рудиментарного предиката принадлежит $R_sF_\alpha(\theta,\overline\theta,\operatorname{con},\lambda x0,\sigma,I^n_k)$. В качестве $Z$ возьмем класс таких $\alpha$ из $RF$, которые принимают значения 0, 1, 2 и если $\alpha(\overline z,i)=0$, то $\forall\,k[\alpha(\overline z,i+k)=0]$. Операция $\delta_f$, такова, что $[\delta_f(\alpha_1,\dots,\alpha_n)](\overline x,\overline z,j)=\nu(f(\sum^{x_1}_{i=0}\alpha_1(\overline z,i),2^i),j)$. Предложенным методом можно доказать утверждение вида (1), если в качестве $X$ взять $RF$, в качестве $Y-R_sF_\alpha(\theta,\overline\theta,\operatorname{con},\lambda x0,\sigma,I^n_k,\lambda xy(x+y),\lambda xy(x-y),\lambda xf(|x|),\lambda x2^{g(|x|)})$, где $f$ и $g$ принадлежат классу $RF$. Библ. 7 назв.