Изменения

Рассмотрим язык <tex>L \in \mathrm{\Pi_2}</tex>, <tex>L = \{x \bigm| \forall y_1 . \exists y_2 \phi(x, y_1, y_2)\}</tex>.<br/>Рассмотрим семейство схем <tex>С_n^1...C_n^n</tex>из леммы. <br> Используем выходы схем <tex>C_n^1...C_n^{i-1}</tex> как вход <tex>b_1...b_{i-1}</tex> схемы <tex>C_n^i</tex>, при этом заменяя те схемы <tex>C_n^i</tex>, которые возвращают значения переменных <tex>x</tex> и <tex>y_1</tex> на простые входы. <br> Итого, получим схему <tex>C_n(\phi, x, y_1)</tex> и возвращающую такое значение <tex>y_2</tex>, что <tex> \phi(x, y_1, y_2) = 1</tex>, если <tex>\phi(x, y_1, y_2)</tex> удовлетворима для заданных <tex>x, y_1</tex>. <br> Теперь определение языка можно переписать так: <tex>L = \{x \bigm| \forall y_1 . \phi(x, y_1, C_n(\phi, x, y_1))\}</tex>. <br> Покажем что <tex>(\forall y_1 \phi(x, y_1, C_n(\phi, x, y_1)))</tex> <tex>\Leftrightarrow</tex> <tex>(\exists G \forall y_1 \phi(x, y_1, G(\phi, x, y_1)) )</tex>. <br> Очевидно, что из первого следует второе, т.к. <tex>\exists G = D_n</tex>. <br> Если первое ложно, то <tex>\exists y_1 = y_1^0 . \forall y_2 \phi(x, y_1^0, y_2) = 0</tex>, следовательно не существует такого <tex>G</tex>, что <tex>\forall y_1\phi(x, y_1, G(\phi, x, y_1)) )</tex>. <br>Теперь определение исходного языка можно записать как <tex>L = \{x\bigm|\exists G . \forall y_1 \phi(x, y_1, G(\phi, x, y_1))\}</tex>, значит <tex>L \in \Sigma_2</tex>