Класс Te . Теорема о замкнутости Te

Определение. Пусть $\Large\varepsilon $ --- произвольное подмножество $\mathbb {E_k}$. Будем говорить, что функция $f (х_1,\dots ,x_n)$ из $\mathbb {P_k}$ сохраняет множество $\Large\varepsilon $, если для любых $\alpha_1 ,\dots ,\alpha_n \in \Large\varepsilon$ имеет место $f (\alpha_1 ,\dots ,\alpha_n) \in \Large\varepsilon$.

Обозначим через $T_{\varepsilon}$ класс всех функций $k$-значной логики, сохраняющих множество $\Large\varepsilon$. Следующая теорема очевидна.

Теорема. Класс $T_{\varepsilon}$ замкнут.

Пример. Докажем, что система $A = {\sim x, max (x_1,x_2)}$ не является полной в $\mathbb {P_k}$. Пусть $\Large\varepsilon = {0, k — 1}$. Так как обе функции системы $A$ сохраняют $\Large\varepsilon$, то $$[A] \subseteq [T_{\varepsilon}] = T_{\varepsilon}.$$

Поскольку $T_{\varepsilon}$ нс содержит константу $1$, то $T_{\varepsilon} \neq \mathbb {P_k}$ Значит, при к $k\geq 3$ $А$ не будет полной системой.$~~~\square$