Разрешимое множество

Разрешимое множество

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

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

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

Примеры

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

См. также



Wikimedia Foundation. 2010.

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

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

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

  • РАЗРЕШИМОЕ И ПЕРЕЧИСЛИМОЕ МНОЖЕСТВА — осн. понятия теории алгоритмов и теории рекурсивных функций (и предикатов). (Определение этих понятий на основе понятия алгоритма см. в ст. Алгоритм, раздел Основные понятия теории А.) Простейшим примером разрешимого множества может служить… …   Философская энциклопедия

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

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

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

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

  • ДИОФАНТОВО МНОЖЕСТВО — множество состоящее из упорядоченных наборов из пцелых (целых неотрицательных, целых положительных) чисел, для к рого можно указать диофантово уравнение зависящее от ппараметров а 1, ..., а п, допустимыми значениями к рых являются целые… …   Математическая энциклопедия

  • АЛГОРИТМ —         [от algorithm!; algorismus, первоначально лат. транслитерация имени ср. азиат. учёного 9 в. Хорезми (Мухаммед бен Муса аль Хорезми)], программа, определяющая способ поведения (вычисления); система правил (предписаний) для эффективного… …   Философская энциклопедия

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

Книги



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

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

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.