Лемма о построении множества $[F]_{x1,x2}$

Лемма. Существует алгоритм построения множества $[F]_{x1,x2}$.

Доказательство. Построим по индукции последовательность множеств $$\Re_0, \Re_1,\dots , \Re_p, \dots $$ функций от двух переменных $x1,x2$

Базис индукции. Положим $\Re_0 = 0$.

Индуктивный переход. Пусть уже построены множества. $\Re_0, \Re_1,\dots , \Re_p$. Множество $\Re_{p+1}$ определяется так: для каждого $j = l,\dots ,s$ рассмотрим всевозможные функции вида.

$$f_1 (H_1(x_1, x_2),\dots , H_n(x_1, x_2)),$$

где $H_1(x_1, x_2)$ есть либо функция из $\Re_p$, либо переменная $x_1$ или $x_2$. Добавив все такие функции к множеству $\Re_p$, мы получим $\Re_{p+1}$.

Из построения ясно, что:

(1) если $\Re_{p+1} = \Re_{p}$, то $\Re_{p+2} = \Re_{p + 1}$ и т.д., т.е. построенная цепочка, множеств стабилизируется;

(2) стабилизация обязательно наступает, поскольку число различных функций от двух переменных $x_1,x_2$ не превосходит $k^{k^2}$;

Обозначим через $t$ минимальный номер множества, цепочки, начиная с которого наступает стабилизация. Непосредственно из определения формулы над $[F]$ следует, что $$[F]_{x1,x2} = \Re_t~~~\square$$