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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

Примеры[править | править исходный текст]

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

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

  • Существуют бесконечные разрешимые множества с бесконечным дополнением. Например, множество всех чётных чисел и множество всех простых чисел являются разрешимыми.
  • Дополнение разрешимого множества является разрешимым.
  • Объединение и пересечение конечного числа разрешимых множеств также являются разрешимыми.

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

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

См. также[править | править исходный текст]