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