Изменения
→Доказательство
Рассмотрим язык <math>L \in \Sigma_{i+2}</math>.<br>
Если <math>x \in L </math>, значит, <math>\exists y_1 \forall y_2 \ldots Q y_{n+2} R(x, y_1 \ldots y_{n+2})</math>. Обозначим часть формулы (исключая <math>\exists y_1</math>) <math>\forall y_2 \ldots Q y_{n+2} R(x, y_1 \ldots y_{n+2}) = f(x, y_1)</math>. Тогда формула преобразуется в <math>\exists y_1 f(x, y_1)</math>.<br>
Тогда получим <math>x \in L \Leftrightarrow \exists y_1 \colon \langle x, y_1\rangle \in L_f = \{\langle x, y_1\rangle \colon f(x, y_1) = 1\}</math>.<br> Значит, <math>L_f \in \Pi_{n+1}</math>.<br>Тогда раз <math>\Sigma_i = \Sigma_{i+1}</math>, то <math>\Pi_i = \Pi_{i+1}</math>, то <math>L_f \in \Pi_n</math>
<math>\exists R_1 \colon \langle x, y_1 \rangle \in L_f \Leftrightarrow \forall y_2 \exists y_3 \ldots Q y_{n+1} R_1(\overline{x, y_1}, y_2 \ldots y_{n+1})</math>, где переменные <math>x</math> и <math>y_1</math> в этой формуле представляют собой одну переменную.
Получается, что <math>x \in L \Leftrightarrow \exists y_1 \forall y_2 \ldots Q y_{n+1} R_1(\overline{x, y_1}, y_2 \ldots y_{n+1})</math>, откуда следует <math>L \in \Sigma_{n+1} \Rightarrow \Sigma_n</math>, что и требовалось доказать.
