Перечислимое множество

Не следует путать со счётным множеством.

Перечисли́мое мно́жество (эффекти́вно перечислимое, рекурси́вно перечислимое, полуразреши́мое множество) — множество конструктивных объектов (например, натуральных чисел), все элементы которого могут быть получены с помощью некоторого алгоритма. Дополнение перечислимого множества называется корекурсивно перечислимым. Всякое перечислимое множество является арифметическим. Корекурсивно перечислимое множество может не быть перечислимым, но всегда является арифметическим. Перечислимые множества соответствуют уровню [math]\displaystyle{ \Sigma^0_1 }[/math] арифметической иерархии, а корекурсивно перечислимые — уровню [math]\displaystyle{ \Pi^0_1. }[/math]

Всякое разрешимое множество является перечислимым. Перечислимое множество является разрешимым тогда и только тогда, когда его дополнение также перечислимо. Другими словами, множество является разрешимым в том и только том случае, когда оно и перечислимо, и корекурсивно перечислимо. Подмножество перечислимого множества может не быть перечислимым (и даже может не быть арифметическим).

Совокупность всех перечислимых подмножеств [math]\displaystyle{ \N }[/math] является счётным множеством, а совокупность всех неперечислимых подмножеств [math]\displaystyle{ \N }[/math] — несчётным.

Варианты определения

Различным формализациям представления об алгоритме отвечают различные формальные определения понятия перечислимого множества, оказывающиеся эквивалентными. Так, на основе понятия рекурсивной функции перечислимые множества натуральных чисел могут быть определены как образы частично рекурсивных функций одной переменной (поэтому перечислимые множества натуральных чисел иногда называют «рекурсивно перечислимыми множествами»). Аналогично, перечислимые множества слов в некотором алфавите A могут быть введены как множества результатов работы машин Тьюринга с внешним алфавитом A, или как множества являющихся словами в алфавите A результатов работы нормальных алгоритмов над алфавитом A.

В теории алгоритмов доказывается утверждение о том, что областями значений алгоритмов могут служить перечислимые множества, и только они. Это позволяет ввести ещё один эквивалентный способ определения понятия перечислимого множества. Так, перечислимыми множествами натуральных чисел могут считаться области значений рекурсивных функций, множествами слов — области применимости машин Тьюринга или нормальных алгоритмов с соответствующими алфавитами.

Примеры

• Пустое множество является перечислимым.
• Любое разрешимое множество (в частности, любое конечное множество) является перечислимым.
• Множество номеров машин Тьюринга, останавливающихся на пустом входе, также является перечислимым (хотя и не является разрешимым, так как его дополнение неперечислимо).
• Проекция перечислимого множества является перечислимой.
• Объединение и пересечение конечного числа перечислимых множеств также являются перечислимыми.
• Множество натуральных чисел, десятичная запись которых встречается в качестве подстроки в десятичной записи числа π, является перечислимым, а в случае нормальности числа π — даже разрешимым тривиальным образом (всё множество натуральных чисел).
• Множество рациональных чисел, меньших постоянной Хайтина Ω, перечислимо, но не разрешимо.
• Но множество рациональных чисел, больших постоянной Хайтина Ω, неперечислимо (хотя и арифметично и корекурсивно перечислимо).
• Множество доказуемых утверждений в арифметике первого порядка перечислимо.
• Но множество истинных утверждений в арифметике первого порядка не является ни перечислимым, ни корекурсивно перечислимым (и даже не является арифметическим, что составляет утверждение теоремы Тарского о невыразимости истины в арифметике).

Диофантовость

Любое перечислимое множество целых чисел (или кортежей целых чисел) имеет диофантово представление, то есть является проекцией множества всех решений некоторого алгебраического диофантова уравнения.

Это означает, в частности, что любое перечислимое множество совпадает с множеством положительных значений, принимаемых при целых параметрах некоторым полиномом с целыми коэффициентами. Данный результат был установлен Юрием Матиясевичем.

См. также

• Иммунное множество

Литература

• Роджерс Х. Теория рекурсивных функций и эффективная вычислимость = Theory of recursive functions and effective computability : [пер. с англ.] / под ред. В. А. Успенского : пер. с англ. В. А. Душского, М. И. Кановича, Е. Ю. Ногиной. — М. : Мир, 1972.