129
правок
Изменения
смысл a в индексе
Приведём доказательство от противного. Предположим, что <tex>A</tex> разрешимо.
Рассмотрим <tex>p_a</tex> (здесь <tex>a</tex> обозначает то, что <tex>p_a</tex> {{---}} программа из дополнения ('''''a'''ddendum'') ко множеству <tex>A</tex>) {{---}} программу, такую что <tex>p_a \in L(\overline A)</tex> (такое . Такое <tex>p_a</tex> существует, т.к. <tex>A</tex> {{---}} нетривиально), а также . Также рассмотрим произвольное перечислимое неразрешимое множество <tex>X</tex>. Пусть <tex>p_X(n)</tex> {{---}} полуразрешитель <tex>X</tex>.
Зафиксируем произвольное <tex>n \in \mathbb{N}</tex> и построим следующую функцию
