129
правок
Изменения
Отмена правки 56309 участника AMaltsev (обсуждение)
Приведём доказательство от противного. Предположим, что <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> и построим следующую функцию
