On the Quasi-Peanity of Functions

G. P. GAVRILOV

(Presented by Academician P. S. Novikov on 20 I 1964)

As in the note \((^1)\), let the symbol \(G\) denote the set of all functions from \(P_{\aleph_0}\) that depend on no more than one variable. Further, a function which, together with the set \(G\), forms a complete system in \(P_{\aleph_0}\) will be called quasi-Peanian. In the note \((^1)\) one necessary and one sufficient condition for the quasi-Peanity of functions were formulated. In the present work a brief exposition is given of the complete solution of the question of the quasi-Peanity of functions. The basic result is the result establishing the existence in \(P_{\aleph_0}\) of only two precomplete classes containing the set \(G\). In connection with this fact it is of interest to note that in \(k\)-valued logics \((P_k)\), for each \(k \ge 2\), there is only one precomplete class containing the whole set \(G_k\) of functions depending on no more than one variable \((^2)\).

In \(k\)-valued logics \((k \ge 3)\) the theorem \((^2)\) is known: the system
\[ G_k \cup \{f(x_1,\ldots,x_n)\} \]
is complete in \(P_k\) if and only if the function \(f(x_1,\ldots,x_n)\) essentially depends on not fewer than two variables and assumes all \(k\) values (is a so-called essential function). The analogy between quasi-Peanian and essential functions is evident. Denote by \(CS_k\) the subset of \(G_k\) consisting of all functions which omit at least one value. It is easy to see that \(CS_k\) is a closed class (with respect to the operation of superposition). It turns out that in \(P_k\) \((k \ge 3)\) a function \(f(x_1,\ldots,x_n)\) is essential if and only if the system
\[ CS_k \cup \{f(x_1,\ldots,x_n)\} \]
is complete in \(P_k\) \((^2)\). It is not difficult to show that the direct transfer of this assertion to the case of countably valued logic does not give a positive result. The question arises whether one can narrow the set \(G\) to some proper subset \(M\), which is a closed class and which, together with any quasi-Peanian function, forms a complete system in \(P_{\aleph_0}\). A closed class \(M\) from \(G\) (respectively from \(G_k,\ k \ge 3\)) will be called a \(\xi\)-class if, whatever the quasi-Peanian (respectively essential) function \(f\) may be, the system \(M \cup \{f\}\) is complete in \(P_{\aleph_0}\) (respectively in \(P_k\)). Denote by \(S_{E^{\aleph_0}}\) the set of all many-valued functions from \(G\) that assume every value from the set
\[ E^{\aleph_0}=\{0,1,2,\ldots\}. \]
In the present note a necessary and sufficient condition is formulated for a set containing \(S_{E^{\aleph_0}}\) to be a \(\xi\)-class. In connection with the indicated result let us recall that in \(P_k\), for \(k \ge 5\), every closed class containing the set \(S_k\) of all many-valued functions is a \(\xi\)-class \((^3)\). In \(P_3\), as is not difficult to show, only the set \(G_3\) is such a \(\xi\)-class. In \(P_4\), as we have established, of the six closed classes (from \(G_4\)) containing the subset \(S_4\), only three are \(\xi\)-classes.

\(1^\circ\). Let us introduce the necessary notation and definitions. By \(G^{(1)}\) we denote the set of all functions from \(P_{\aleph_0}\) that depend on one variable; \(C(m)\) will denote the subset of functions from the set \(G^{(1)}\) that assume exactly \(m\) different values \((1 \le m < \aleph_0)\);
\[ C_\omega=\bigcup_{m=1}^{\infty} C(m). \]

Let \(f(x,y)\) be an arbitrary function from \(P_{\aleph_0}\) depending on two variables. If either \(f(x,k)\in C_\omega\) for every \(k\), or \(f(l,y)\in C_\omega\) for every—

some $l$ ($k$ and $l$ belong to the set $E^{\aleph_0}$), then the function $f(x,y)$ will be called a function of the first kind. The set of all functions of the first kind from $P_{\aleph_0}$ will be denoted by $R_1$.

We shall say that a function $f(x,y)$ from $P_{\aleph_0}$ has a Peano angle in the first (respectively, second) variable if the function $f(x+y,y)$ (respectively, $f(x,x+y)$) is Peano $(^1)$. Further, we shall say that a function $f(x,y)$ from $P_{\aleph_0}$ has a quasi-Peano angle in the first (respectively, second) variable if there exist functions $g_1(x)$ and $g_2(x)$ from $G^{(1)}$ such that the function $\varphi(x,y)=f(g_1(x),g_2(y))$ has a Peano angle in the first (respectively, second) variable. It is clear that in this definition $g_1(x)$ and $g_2(x)$ are one-to-one functions. It is easy to show that in the above definition it suffices to restrict oneself to the subset of strictly monotone functions from $G^{(1)}$. We shall call $f(x,y)$ a function of the second kind if it does not have a quasi-Peano angle in either of the variables. The set of all functions of the second kind from $P_{\aleph_0}$ will be denoted by $R_2$.

Consider the set of variables $\{u_1,u_2\}$. Denote by $H^{(1)}$ the set of all functions from $P_{\aleph_0}$ depending on one of the two variables $u_1$ and $u_2$. Denote by $H^{(2)}$ the set of all functions from $P_{\aleph_0}$ depending on both variables $u_1$ and $u_2$. $G^{(0)}$ will denote the set of all functions from $P_{\aleph_0}$ depending on zero variables. By the symbol $F_1$ we denote the subset of $H^{(2)}$ consisting of all functions of the first kind, and by $F_2$—of all functions of the second kind. $T_i=G^{(0)}\cup H^{(1)}\cup F_i$, $i=1,2$. $\mathfrak{P}(T_i)$ is the closure class $(^2)$ of the set $T_i$ $(i=1,2)$.

$2^\circ$. Let us formulate a criterion for the quasi-Peano property of functions.

Theorem 1. A function $f(x_1,\ldots,x_n)$ $(n\geqslant 2)$ is quasi-Peano if and only if it does not belong to the set
\[ \mathfrak{P}(T_1)\cup \mathfrak{P}(T_2). \]

In the proof of this theorem several auxiliary assertions are used, the principal ones being the following.

Lemma 1. Let a function $f(x_1,\ldots,x_n)$ $(n\geqslant 2)$ not preserve $(^2)$ the set $T_1$. Then it does not preserve it also on the set $G^{(0)}\cup H^{(1)}$, i.e. there exist functions $g_1,\ldots,g_n$ from $G^{(0)}\cup H^{(1)}$, upon substituting which in place of the variables in the function $f$ one obtains a function (from $H^{(2)}$) not belonging to $T_1$.

Remark. By $I_0$ we denote the set of all functions of large range $(^4)$ from $G^{(1)}$. By the symbol $I_1$ we denote the set of all functions from $G^{(1)}$ satisfying the following two conditions: a) the function omits $\aleph_0$ values from the set $E^{\aleph_0}$; b) each level set $(^4)$ of the function (with respect to the number it assumes) is infinite. Using this notation, we formulate two assertions:

1. If a function $f(x_1,\ldots,x_n)$ $(n\geqslant 2)$ does not preserve the set $T_1$, then it does not preserve it also on the set $H^{(1)}\cap I_0$.

2. If a function $f(x_1,\ldots,x_n)$ $(n\geqslant 2)$ does not preserve the set $T_1$, then it does not preserve it also on the set $H^{(1)}\cap I_1$.

Lemma 2. If a function $f(x,y)$ does not have a quasi-Peano angle in the first variable, then there exist strictly monotone functions $g_1(x)$ and $g_2(x)$ such that the function $\varphi(x,y)=f(g_1(x),g_2(y))$ satisfies at least one of the two conditions (the first and the second conditions of degeneracy):
\[ 1.\ \varphi(x+y,y)=\varphi(y,y). \qquad 2.\ \varphi(x+y,y)=\varphi(x+y,0). \]

Lemma 3. If a function $f(x_1,\ldots,x_n)$ $(n\geqslant 2)$ does not preserve the set $T_2$, then it does not preserve it also on the set $G^{(0)}\cup H^{(1)}$.

Remark. In the formulation of this lemma, the set \(G^{(0)} \cup H^{(i)}\) may be replaced by either of the two sets \(H^{(1)} \cap I_0\) and \(H^{(1)} \cap I_1\).

Lemma 4. If a function \(f(x,y)\) has a quasi-Peano node with respect to the first (respectively, the second) variable, then there exist strictly monotone functions \(g_1(x)\) and \(g_2(x)\) and a function \(g(x)\) such that the function \(\varphi(x,y)=g(f(g_1(x),g_2(y)))\) has a Peano node with respect to the first (respectively, the second) variable and \(\varphi(x,x+y+1)\equiv0\) (respectively, \(\varphi(x+y+1,y)\equiv0\)).

\(3^\circ\). Theorem 2. If the function \(f(x_1,\ldots,x_n)\) \((n\ge2)\) is quasi-Peano, then it has quasi-Peano order \((^1)\) not exceeding 2.

Theorem 3. There exist only two precomplete classes containing the set of functions \(G\), namely, \(\mathfrak P(T_1)\) and \(\mathfrak P(T_2)\).

Theorem 4. A function \(f(x,y)\) is quasi-Peano of the first order if and only if there exist functions \(g_1(x)\) and \(g_2(x)\) such that the function \(\varphi(x,y)=f(g_1(x),g_2(y))\), when the first variable is fixed, is a many-valued function of the second variable, and when the second is fixed, is a many-valued function of the first.

Theorem 5. If the function \(f(x,y)\) does not belong to the set \(R_1\cup R_2\), then it is quasi-Peano.

\(4^\circ\). By \(\pi_0\) we shall denote the operation of substituting for the variables in a function \(f(x_1,\ldots,x_n)\in P_{\aleph_0}\) functions from the set \(G^{(1)}\), followed by a renaming of the variables.

Theorem 6. Let \(f(x_1,\ldots,x_n)\) be a quasi-Peano function. If \(n\ge5\), then by means of the operation \(\pi_0\) one can obtain from it a quasi-Peano function of a smaller number of variables. If, however, \(n=3\) or \(n=4\), then obtaining from the function \(f\), by means of the operation \(\pi_0\), a quasi-Peano function depending on a smaller number of variables is not always possible.

Consider a quasi-Peano function \(f(x_1,\ldots,x_n)\). Denote by \(K(f,n)\) the minimal number of functions from the set \(G^{(1)}\) that must be used in order, from the function \(f\) by means of the operation \(\pi_0\), to construct functions \(\varphi_1(x,y)\) and \(\varphi_2(x,y)\) not belonging respectively to the sets \(R_1\) and \(R_2\). Let \(K(n)=\max_f K(f,n)\), where the maximum is taken over all quasi-Peano functions of \(n\) variables.

Theorem 7. \(K(n)=n-2\).

\(5^\circ\). Consider several closed classes in the set \(G\): \(Q_5\) consists of the set \(G^{(0)}\) and all such functions from the set \(G^{(1)}\) which: 1) either assume no more than a finite number of values from \(E^{\aleph_0}\), 2) or have an infinite complement to the union of all singleton level sets; \(Q_6\) consists of the set \(G^{(0)}\) and all such functions from the set \(G^{(1)}\) which: 1) either have repetitions, 2) or do not assume a single value from \(E^{\aleph_0}\); \(S_0=I_0\cup G^{(0)}\cup S_{E^{\aleph_0}}\cup C(1)\cup(C(2)\cap I_1)\).

Theorem 8. Let \(Q\) be a closed class in \(G\) containing the set \(S_{E^{\aleph_0}}\) \((G\supseteq Q\supset S_{E^{\aleph_0}})\). In order that \(Q\) be a \(\xi\)-class, it is necessary and sufficient that the condition \(Q\supseteq S_0\) be satisfied.

Theorem 9. Let \(Q\) be a \(\xi\)-class containing the set \(S_{E^{\aleph_0}}\) and different from the whole set \(G\). Then either \(Q_5\supseteq Q\), or \(Q_6\supseteq Q\).

Remark. Everywhere in this item the conjunction “or” is inseparable.

Smolensk Branch
of the Moscow Power Engineering Institute

Received
15 I 1964

CITED LITERATURE

\(^{1}\) G. P. Gavrilov, DAN, 128, No. 1 (1959).
\(^{2}\) S. V. Yablonskii, Tr. Mat. inst. im. V. A. Steklova AN SSSR, 51, 5 (1958).
\(^{3}\) A. Salomaa, Turun Yliopiston Julkaisuja Ann. Univ. Turkuensis. Sarja-series A, I, 41, 1 (1960).
\(^{4}\) V. A. Uspenskii, Lectures on Computable Functions, Moscow, 1960.