129
правок
Изменения
Нет описания правки
Зафиксируем произвольное <tex>n \in \mathbb{N}</tex> и построим следующую функцию
<tex>Vn(x) = \begin{cases}
p_\infty(x), n \notin X; \\
\end{cases} </tex>
<code>
'''function''' <tex>V_n</tex>(x):
'''if''' <tex>p_X</tex>(n)== 1
'''return''' <tex>p_a</tex>(x)
'''while''' ''true''
</code>
Получили, что если <tex>n \in X</tex>, то <tex>Vn(x) \in L(\overline S)</tex>, а если <tex>n \notin X</tex>, то <tex>Vn(x) \in L(S)</tex>. Таким образом, <tex>n \in X \iff V_n(x) \in L(\overline S)</tex>.
Так как <tex>\overline S</tex> - разрешимо, то можно проверить для любого <tex>a</tex>, лежит ли оно в <tex>\overline{S}</tex>. Но это тоже самое, что и проверка <tex>n \in X</tex>. Тогда можно для каждого <tex>n</tex> проверить лежит ли оно в <tex>X</tex>, а следовательно и построить разрешитель для <tex>X</tex>. Так как <tex>X</tex> - неразрешимо, получили противоречие.
