Изменения

'''Индукционный переход'''. Докажем, что если <tex>\Sigma_n = \Sigma_{n+1}</tex>, то <tex>\Sigma_n Sigma_{n+1} = \Sigma_{n+2}</tex>.<br/>Рассмотрим язык <tex>L \in \Sigma_{n+2}</tex>. По определению сложностного класса <tex>L = \Sigma_{n+2}</tex> слово <tex>x \in L \Leftrightarrow | \exists y_1 \forall y_2 \ldots Q y_{n+2} RR_L^{n+2}(x, y_1 \ldots y_{n+2})\}</tex>. Обозначим <tex>\forall y_2 \ldots Q y_{n+2} RR_L^{n+2}(x, y_1 \ldots y_{n+2}) = f(x, y_1)</tex>.Тогда получим язык <tex>L_f = \{\langle x, y_1\rangle \colon | f(x, y_1) = 1\}</tex>.<br/>Тогда Заметим, что <tex>L_f \in \Pi_{n+1}</tex>, и из вышедоказанной леммы следует, что <tex>L_f \in \Pi_n</tex>.<br/>Из определения сложностного класса <tex>\Pi_n\;</tex> получаем, что <tex>\exists R_1 R_{L_f}^{n} \colon \langle x, y_1 \rangle \in L_f \Leftrightarrow \forall y_2 \exists y_3 \ldots Q y_{n+1} R_1R_{L_f}^{n}(\langle x, y_1\rangle, y_2 \ldots y_{n+1})</tex>, где переменные <tex>x</tex> и <tex>y_1</tex> представляют собой одну переменную. ПолучаетсяСледовательно, что <tex>x \in L \Leftrightarrow \exists y_1 \forall y_2 \ldots Q y_{n+1} R_1R_{L_f}^{n}(\langle x, y_1\rangle, y_2 \ldots y_{n+1})</tex>. То есть язык <tex>L \in \Sigma_{n+1}</tex>. Отсюда следует, что <tex>\Sigma_{n+1} = \Sigma_{n+2}</tex>.