Что значит "разрешимое множество"

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

В теории множеств , теории алгоритмов и математической логике , множество натуральных чисел называется разреши́мым или рекурси́вным, если существует алгоритм , который, получив на вход любое натуральное число, через конечное число шагов завершается и определяет, принадлежит ли оно данному множеству. Другими словами, множество является разрешимым, если его характеристическая функция вычислима . Множество, не являющееся разрешимым, называется неразреши́мым. Также можно говорить о разрешимом множестве, состоящем из любых конструктивных объектов , кодируемых натуральными числами. Любое разрешимое множество является перечислимым и арифметическим . Разрешимые множества соответствуют уровню Δ .

Существуют перечислимые множества, не являющиеся разрешимыми. Более того, перечислимое множество является разрешимым тогда и только тогда, когда его дополнение также перечислимо. Проекция разрешимого множества является перечислимой, но может не быть разрешимой. Подмножество разрешимого множества может не быть разрешимым .

Совокупность всех разрешимых подмножеств $\N$ является счётным множеством , а совокупность всех неразрешимых подмножеств $\N$ — несчётным .