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

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

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

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

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

Содержание

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

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

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

Примеры

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

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

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

См. также

Примечания

  1. Математическая теория формальных языков, А. Е. Пентус, М. Р. Пентус
  2. Барвайс, Кеннет Джон Справочная книга по математической логике. Часть 3: теория рекурсии. — М.: Наука, 1982.

Литература

  • Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. — М.:Мир, 1972.



Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Полезное


Смотреть что такое "Перечислимое множество" в других словарях:

  • Перечислимое множество —         рекурсивно перечислимое множество, множество натуральных чисел или каких либо других конструктивных объектов (См. Конструктивные объекты), занумерованных натуральными числами, являющееся множеством значений некоторой общерекурсивной… …   Большая советская энциклопедия

  • ПЕРЕЧИСЛИМОЕ МНОЖЕСТВО — множество, возникающее в результате развертывания какого либо конструктивного порождающего процесса. Такой процесс можно мыслить как процесс вычисления значений нек рого алгоритма с исходными данными в виде натуральных чисел, и потому, напр.,… …   Математическая энциклопедия

  • Рекурсивно перечислимое множество — Перечислимое множество множество конструктивных объектов (например, натуральных чисел), элементы которого могут быть эффективно перенумерованы (возможно, с повторениями). Варианты определения Различным формализациям представления об алгоритме… …   Википедия

  • рекурсивно перечислимое множество — — [http://www.iks media.ru/glossary/index.html?glossid=2400324] Тематики электросвязь, основные понятия EN recursively enumerable set …   Справочник технического переводчика

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

  • Разрешимое множество — В теории множеств, теории алгоритмов и математической логике, множество натуральных чисел называется разрешимым или рекурсивным, если существует алгоритм, который, получив на вход любое натуральное число, через конечное число шагов завершается и… …   Википедия

  • Арифметическое множество — В теории множеств и математической логике, множество натуральных чисел называется арифметическим, если оно может быть определено формулой в языке арифметики первого порядка, то есть если существует такая формула с одной свободной переменной что… …   Википедия

  • ПРОСТОЕ МНОЖЕСТВО — рекурсивно перечислимое множество натуральных чисел, дополнение к рого есть иммунное множество. П. м. являются промежуточными в смысле так наз. m сводимости (см. Рекурсивная теория множеств).между разрешимыми множествами и творческими… …   Математическая энциклопедия

  • КРЕАТИВНОЕ МНОЖЕСТВО — творческое множество, рекурсивно перечислимое множество Анатуральных чисел, дополнение к рого Адо натурального ряда является продуктивным множеством;иными словами, множество Акреативно, если оно рекурсивно перечислимо и существует такая частично… …   Математическая энциклопедия

  • ПРОДУКТИВНОЕ МНОЖЕСТВО — множество натуральных чисел А , для к рого существует такая частично рекурсивная функция j, что для всякого рекурсивно перечислимого множества Wx с геделевым номером х, содержащегося в А. Известно, что для всякого П. м. Асуществует такая… …   Математическая энциклопедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»