How to prove that two classes of simple primitive recursive functions are distinct

Let X, Y be classes of primitive recursive functions (for short PRF) and let it be required to prove the following statement: (I) It is not true that every function of class X belongs to class Y. Such an assertion is usually proved by exhibiting a PRF of class X which grows faster than any PRF of class Y, or by constructing some simple PRF's, e.g., x(x + 1); xy(x + y), from class X, which do not belong to class Y. A method is proposed which gives a proof of an assertion of type (I) for some classes of PRF's X and Y such that first, functions of class X do not increase faster than functions of class Y, and second, the class Y contains simple PRF's such as xy(x + y), xy(x–y), etc. The proposed method is as follows. We choose some class of PRF's Z and for each PRF f we construct an operation _f on the functions of the class Z such that for every f in Y, the class Z is closed with respect to the operation f, but on the other hand it is not true that for every f of X the class Z is closed with respect to _f. We describe one of the possible applications of the method. We shall not distinguish between word and number PRF's and predicates, bearing in mind the following one-to-one correspondence between words in the alphabet {1, 2} and natural numbers: the word a_na_n–1... a₁a₀ in the alphabet {1, 2} corresponds to the number . Let (x, i) equal the i-th letter in the word x (the last letter-is taken to be the 0-th sign), ¦x¦ is the length of x; con(x, y) is the result of concatenating the word y to the right of the word x; , ¯ are the characteristic functions of equality and inequality. Let RF be a class of PRF's obtained from the PRF's , ¯, con, x0, , I _k ⁿ , by the operation of bounded minimalization and composition of functions. We note that the class of relations of the class RF is equal to the class of rudimentary relations. Let R_sF(f₁, ..., f_l) be a class of PRF's obtained from the PRF's f₁, ..., f_l by the operation of composition and the operation of putting into correspondence with the function g an f such that , where tPy t is the subword y. We note that the characteristic function of every s-rudimentary predicate belongs to R_sF(, , con, x0, , I _k ⁿ ). We take as Z the class of such in RF which have the values 0, 1, 2 and if then . The operation _f is such that . Assertions of type (I) can be proved by the proposed method if for X we take RF, and as Y we take , where f and g belong to the class RF.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 68, pp. 115–122, 1977.