Класс 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$