Вычислимо неразделимы
В теории вычислимости два непересекающихся множества натуральных чисел называются вычислимо неразделимыми или рекурсивно неразделимыми, если они не могут быть «разделены» вычислимым множеством . [1] Эти множества возникают при изучении самой теории вычислимости, особенно в связи с классы . Вычислимо неразделимые множества возникают также при изучении теоремы Гёделя о неполноте .
Определение
[ редактировать ]Натуральные числа – это набор . Учитывая непересекающиеся подмножества и из , разделительный набор является подмножеством такой, что и (или, что то же самое, и , где обозначает дополнение ). Например, сам по себе является разделяющим набором для пары, как и .
Если пара непересекающихся множеств и не имеет вычислимого разделяющего множества, то эти два множества вычислимо неразделимы .
Примеры
[ редактировать ]Если невычислимое множество, то и его дополнение вычислимо неразделимы. Однако существует множество примеров множеств. и которые не пересекаются, не дополняют друг друга и вычислимо неразделимы. Более того, возможно для и быть вычислимо неразделимыми, непересекающимися и вычислимо перечислимыми .
- Позволять — стандартная индексация частично вычислимых функций . Тогда множества и вычислимо неразделимы ( William Gasarch 1998, стр. 1047).
- Позволять — стандартная нумерация Гёделя для формул арифметики Пеано . Тогда набор доказуемых формул и множества опровержимых формул вычислимо неразделимы. Неразделимость множеств доказуемых и опровержимых формул справедлива для многих других формальных теорий арифметики (Смальян, 1958).
Ссылки
[ редактировать ]- ^ Монк 1976, с. 100
- Цензер, Дуглас (1999), "П. 0
1 класс теории вычислимости», Справочник по теории вычислимости , Stud. Logic Found. Math., т. 140, Амстердам: Северная Голландия, стр. 37–85, doi : 10.1016/S0049-237X(99)80018-4 , МР 1720779 - Гасарч, Уильям (1998), «Обзор рекурсивной комбинаторики», Справочник по рекурсивной математике, Vol. 2 , Студ. Логика найдена. Матем., вып. 139, Амстердам: Северная Голландия, стр. 1041–1176, doi : 10.1016/S0049-237X(98)80049-9 , MR 1673598.
- Монк, Дж. Дональд (1976), Математическая логика , Тексты для выпускников по математике, Берлин, Нью-Йорк: Springer-Verlag , ISBN 978-0-387-90170-1
- Смалльян, Раймонд М. (1958), «Неразрешимость и рекурсивная неразделимость», Журнал математической логики и основ математики , 4 (7–11): 143–147, doi : 10.1002/malq.19580040705 , ISSN 0044-3050 , MR 0099293