Вычислимо неразделимы

В теории вычислимости два непересекающихся множества натуральных чисел называются вычислимо неразделимыми или рекурсивно неразделимыми, если они не могут быть «разделены» вычислимым множеством . ^[1] Эти множества возникают при изучении самой теории вычислимости, особенно в связи с $\Pi _{1}^{0}$ классы . Вычислимо неразделимые множества возникают также при изучении теоремы Гёделя о неполноте .

Определение

Натуральные числа – это набор $\mathbb {N} =\{0,1,2,\dots \}$ . Учитывая непересекающиеся подмножества $A$ и $B$ из $\mathbb {N}$ , разделительный набор $C$ является подмножеством $\mathbb {N}$ такой, что $A\subseteq C$ и $B\cap C=\emptyset$ (или, что то же самое, $A\subseteq C$ и $B\subseteq C'$ , где $C'=\mathbb {N} \setminus C$ обозначает дополнение $C$ ). Например, $A$ сам по себе является разделяющим набором для пары, как и $B'$ .

Если пара непересекающихся множеств $A$ и $B$ не имеет вычислимого разделяющего множества, то эти два множества вычислимо неразделимы .

Примеры

Если $A$ невычислимое множество, то $A$ и его дополнение вычислимо неразделимы. Однако существует множество примеров множеств. $A$ и $B$ которые не пересекаются, не дополняют друг друга и вычислимо неразделимы. Более того, возможно для $A$ и $B$ быть вычислимо неразделимыми, непересекающимися и вычислимо перечислимыми .

Позволять $\varphi$ — стандартная индексация частично вычислимых функций . Тогда множества $A=\{e:\varphi _{e}(0)=0\}$ и $B=\{e:\varphi _{e}(0)=1\}$ вычислимо неразделимы ( William Gasarch 1998, стр. 1047).
Позволять $\#$ — стандартная нумерация Гёделя для формул арифметики Пеано . Тогда набор $A=\{\#(\psi ):PA\vdash \psi \}$ доказуемых формул и множества $B=\{\#(\psi ):PA\vdash \lnot \psi \}$ опровержимых формул вычислимо неразделимы. Неразделимость множеств доказуемых и опровержимых формул справедлива для многих других формальных теорий арифметики (Смальян, 1958).

Ссылки

^ Монк 1976, с. 100

Цензер, Дуглас (1999), «Π ⁰
₁ класс теории вычислимости», Справочник по теории вычислимости , 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

[1] Монк 1976, с. 100

[1]