Obliczeniowo nierozłączne

W teorii obliczalności dwa rozłączne zbiory liczb naturalnych nazywane są obliczalnie nierozłącznymi lub rekurencyjnie nierozłącznymi, jeśli nie można ich „rozdzielić” za pomocą zbioru obliczalnego . Zbiory te powstają w badaniu samej teorii obliczalności, szczególnie w odniesieniu do klas Π ⁰
₁ . Obliczalnie nierozłączne zbiory pojawiają się również w badaniu twierdzenia Gödla o niezupełności .

Definicja

Liczby naturalne to zbiór . ${\ Displaystyle \ mathbb {N} = \ {0,1,2, \ kropki \}}$ . Biorąc pod uwagę rozłączne podzbiory $A$ i B z , oddzielający zbiór C jest takiego , że $B$ ⊆ C i ∩ C = ∅ (lub równoważnie , A ⊆ C i B ⊆ C ). Na przykład A jest zbiorem oddzielającym parę, podobnie jak B .

Jeśli para zbiorów rozłącznych A i B nie ma obliczalnego zbioru rozdzielającego, to te dwa zbiory są nierozłączne obliczeniowo .

Przykłady

Jeśli A jest zbiorem nieobliczalnym, to A i jego dopełnienie są nierozłączne obliczeniowo. Istnieje jednak wiele przykładów zbiorów A i B , które są rozłączne, niekomplementarne i nierozłączne obliczeniowo. Co więcej, A i B mogą być obliczalnie nierozłączne, rozłączne i przeliczalne .

• Niech φ będzie standardowym indeksowaniem częściowych funkcji obliczalnych . Wtedy zbiory A = { e : φ _e (0) = 0 } i B = { e : φ _e (0) = 1 } są obliczeniowo nierozłączne ( William Gasarch 1998, s. 1047).
• Niech # będzie standardową numeracją Gödla dla wzorów arytmetyki Peano . Wtedy zbiór A = { #(ψ) : PA ⊢ ψ } formuł dowodliwych i zbiór formuł obalalnych B = { #(ψ) : PA ⊢ ¬ψ } są nierozłączne obliczeniowo. Nierozłączność zbiorów formuł możliwych do udowodnienia i obalenia dotyczy wielu innych formalnych teorii arytmetyki (Smullyan 1958).

•   Cenzer, Douglas (1999), „Π ⁰
  ₁ zajęcia z teorii obliczalności”, Podręcznik teorii obliczalności , Stud. Znaleziono logikę. Matematyka, tom. 140, Amsterdam: Holandia Północna, s. 37–85, doi : 10.1016/S0049-237X(99)80018-4 , MR 1720779
•   Gasarch, William (1998), „Przegląd kombinatoryki rekurencyjnej”, Podręcznik matematyki rekurencyjnej, tom. 2 , Stadnina. Znaleziono logikę. Matematyka, tom. 139, Amsterdam: Holandia Północna, s. 1041–1176, doi : 10.1016/S0049-237X(98)80049-9 , MR 1673598
•   Monk, J. Donald (1976), Mathematical Logic , Graduate Texts in Mathematics , Berlin, Nowy Jork: Springer-Verlag , ISBN 978-0-387-90170-1
•    Smullyan, Raymond M. (1958), „Nierozstrzygalność i nierozłączność rekurencyjna”, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik , 4 : 143–147, doi : 10.1002/malq.19580040705 , ISSN 0044-3050 , MR 0099 293