10. Рекурсивная неотделимость

Говорят, что два рекурсивно перечислимых множества рекурсивно отделимы, если можно найти рекурсивное множество С, такое, что пусто.

Существует пара дизъюнктных рекурсивно перечислимых множеств натуральных чисел, которые не могут быть рекурсивно отделены.

Если два дизъюнктных рекурсивно перечислимых множества не могут быть рекурсивно отделены, то ни одно из них не рекурсивно. Поэтому приведенная выше теорема усиливает теорему Чёрча о существовании рекурсивно перечислимого множества, которое не рекурсивно.

Доказательство. Допустим, что уже доказано существование рекурсивной нумерации всех пар дизъюнктных рекурсивно перечислимых множеств натуральных чисел,

Пусть рекурсивно перечислимые множества, элементами которых являются соответственно те числа для которых Так как и

дизъюнктны для любого то также дизъюнктны. Мы покажем, что не могут быть рекурсивно отделены. Действительно, допустим, что и где дизъюнктные рекурсивно перечислимые множества, объединение которых есть множество всех натуральных чисел. Так как — пара дизъюнктных рекурсивно перечислимых множеств, мы можем найти такое, что Теперь влечет влечет Так как либо либо пусто, мы пришли к противоречию.

Остается построить рекурсивную нумерацию всех пар дизъюнктных рекурсивно перечислимых множеств натуральных чисел. Мы уже доказали теорему о нумерации для рекурсивно перечислимых множеств. С помощью рекурсивного взаимно однозначного соответствия между натуральными числами и парами натуральных чисел мы получаем отсюда рекурсивную нумерацию всех пар (не обязательно дизъюнктных) рекурсивно перечислимых множеств. Теперь мы сделаем их дизъюнктными с помощью рекурсивной процедуры модификации, которая не трогает те пары, которые были дизъюнктны с самого начала.

Пусть образуют произвольную пару рекурсивно перечислимых множеств. Порождаем последовательно их элементы методом, указанным в так что

и

— элементы, полученные из доказательств с номерами Мы поступаем так, пока имеет место а для всех Если это условие нарушено для некоторого значения то процедура модификации заканчивается, и модифицированные состоят из элементов, полученных к этому моменту. Ясно, что если дизъюнктны с самого начала, то они остаются неизменными после модификации. Доказательство закончено.