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