Для доказательства в другую сторону понадобятся следующие леммы:
{{Лемма
Строим доказательство от противного. Пусть G \in A, G \subset H, H \notin A, K — перечислимое неразрешимое множество. Построим следующую вычислимую функцию: f(x, y) = \begin{cases} x \in H & y \in K\\ x \in G & y \notin K \end{cases}
Вычисляется эта функция следующим образом: параллельно запускаем проверки x \in G и y \in K. Если x \in G, то x \in H, следовательно, функция возвращает единицу вне зависимости от y. Если y \in K, то запускаем проверку x \in H.
С помощью этой функции можно разрешить множество K следующим образом: для проверяемого элемента y подготовим программу g:
g(x):
return f(x, y)
После этого запустим параллельно проверки
|statement=
Пусть <tex>A</tex> — перечислимое свойство языков, <tex>G \in A</tex>. Тогда верно следствие: <tex>G \subset H \Rightarrow H \in A</tex>.
