Вычислимо неотделим

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

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

Если пара непересекающихся множеств не имеет вычислимого разделяющего множества, то эти два множества вычислимо неразделимы .${\displaystyle А}$${\displaystyle Б}$

Если — невычислимое множество, то и его дополнение вычислимо неотделимы. Однако существует множество примеров множеств и , которые являются непересекающимися, недополняющими и вычислимо неотделимыми. Более того, возможно, что и будут вычислимо неотделимы, непересекающимися и вычислимо перечислимыми . ${\displaystyle А}$${\displaystyle А}$${\displaystyle А}$${\displaystyle Б}$${\displaystyle А}$${\displaystyle Б}$

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

• Цензер, Дуглас (1999), "П⁰
  ₁классы в теории вычислимости", Справочник по теории вычислимости , Stud. Logic Found. Math., т. 140, Амстердам: Северная Голландия, стр.  37–85 , doi :10.1016/S0049-237X(99)80018-4, MR  1720779
• Gasarch, William (1998), "Обзор рекурсивной комбинаторики", Справочник по рекурсивной математике, т. 2 , Stud. Logic Found. Math., т. 139, Амстердам: Северная Голландия, стр.  1041– 1176, doi :10.1016/S0049-237X(98)80049-9, MR  1673598
• Монк, Дж. Дональд (1976), Математическая логика , Graduate Texts in Mathematics, Берлин, Нью-Йорк: Springer-Verlag , ISBN 978-0-387-90170-1
• Смаллян, Раймонд М. (1958), «Неразрешимость и рекурсивная неразделимость», Zeitschrift für Mathematische Logik und Grundlagen der Mathematik , 4 ( 7–11 ): 143–147 , doi : 10.1002/malq.19580040705, ISSN  0044-3050, МР  0099293