Лемма о построении множества $[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$$