Изменения

|proof = Из Для доказательства теоремы достаточно показать, что если такое <tex>i</tex> существует, то <tex>\forall j > i</tex> верно, что <tex>\Sigma_i = \Sigma_{i+1}Sigma_j</tex> очевидным образом следует .<br/>Докажем по индукции.<br/>'''База'''. <tex>\Pi_i Sigma_i = \Pi_Sigma_{i+1}</tex>из условия.<br/> '''Индукционный переход'''. Докажем, что если <tex>\Sigma_n = \Sigma_{n+1}</tex>, то <tex>\Sigma_n = \Sigma_{n+2}</tex>.<br/>Рассмотрим язык <tex>L \in \Sigma_{n+2}</tex>.<br>Если По определению сложностного класса <tex>x \in L Sigma_{n+2}</tex>, значит, слово <tex>x \in L \Leftrightarrow \exists y_1 \forall y_2 \ldots Q y_{n+2} R(x, y_1 \ldots y_{n+2})</tex>. Обозначим часть формулы (исключая <tex>\exists y_1</tex>) <tex>\forall y_2 \ldots Q y_{n+2} R(x, y_1 \ldots y_{n+2}) = f(x, y_1)</tex>. Тогда формула преобразуется в <tex>\exists y_1 f(x, y_1)</tex>.<br>Тогда получим <tex>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\}</tex>.<br/> Значит, Тогда <tex>L_f \in \Pi_{n+1}</tex>.<br>Тогда раз <tex>\Sigma_i = \Sigma_{i+1}</tex>, то <tex>\Pi_i = \Pi_{i+1}</tex>и из вышедоказанной леммы следует, то что <tex>L_f \in \Pi_n</tex>.<br/> Из определения сложностного класса <tex>\Pi_n\;\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{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_1(\overline{langle x, y_1}\rangle, y_2 \ldots y_{n+1})</tex>, откуда следует . То есть язык <tex>L \in \Sigma_{n+21} </tex>. Отсюда следует, что <tex>\Rightarrow L \in Sigma_{n+1} = \Sigma_{n+12}</tex>, что и требовалось доказать.