Kalkylmässigt oskiljaktiga

I beräkningsbarhetsteorin kallas två disjunkta uppsättningar av naturliga tal beräkningsbart oskiljaktiga eller rekursivt oskiljbara om de inte kan "separeras" med en beräkningsbar mängd . Dessa uppsättningar uppstår i själva studiet av beräkningsteorin, särskilt i förhållande till Π ⁰
₁ -klasser . Beräknbart oskiljaktiga mängder uppstår också i studiet av Gödels ofullständighetsteorem .

Definition

De naturliga talen är mängden $\mathbb {N} =\{0,1,2,\dots \}$ . Givet disjunkta delmängder A och B av $\mathbb {N}$ , är en separerande mängd C en delmängd av $\mathbb {N}$ så att A ⊆ C och B ∩ C = ∅ (eller motsvarande A ⊆ C och B ⊆ C ) . Till exempel är A själv en separerande uppsättning för paret, liksom B .

Om ett par disjunkta uppsättningar A och B inte har någon beräkningsbar separeringsmängd, är de två uppsättningarna beräkningsbart oskiljbara .

Exempel

Om A är en icke beräkningsbar mängd, är A och dess komplement beräkningsbart oskiljbara. Det finns dock många exempel på uppsättningar A och B som är disjunkta, icke-komplementära och beräkningsbart oskiljbara. Dessutom är det möjligt för A och B att vara beräkningsbart oskiljaktiga, osammanhängande och beräkningsbart uppräknade .

• Låt φ vara standardindexeringen av de partiella beräkningsbara funktionerna . Då är mängderna A = { e : φ _e (0) = 0 } och B = { e : φ _e (0) = 1 } beräkningsbart oskiljbara ( William Gasarch 1998, s. 1047).
• Låt # vara en standard Gödel-numrering för formlerna för Peanos aritmetik . Då är mängden A = { #(ψ) : PA ⊢ ψ } av bevisbara formler och mängden B = { #(ψ) : PA ⊢ ¬ψ } av vederläggbara formler beräkningsbart oskiljbara. Oskiljbarheten av uppsättningarna bevisbara och vederläggbara formler gäller för många andra formella teorier om aritmetik (Smullyan 1958).

•   Cenzer, Douglas (1999), "Π ⁰
  ₁ classes in computability theory", Handbook of computability theory , Stud. Logik hittad. Math., vol. 140, Amsterdam: North-Holland, s. 37–85, doi : 10.1016/S0049-237X(99)80018-4 , MR 1720779
•   Gasarch, William (1998), "A survey of recursive combinatorics", Handbook of recursive mathematics, Vol. 2 , Stud. Logik hittad. Math., vol. 139, Amsterdam: North-Holland, s. 1041–1176, doi : 10.1016/S0049-237X(98)80049-9 , MR 1673598
•   Monk, J. Donald (1976), Mathematical Logic , Graduate Texts in Mathematics, Berlin, New York: Springer-Verlag , ISBN 978-0-387-90170-1
•    Smullyan, Raymond M. (1958), "Obeslutbarhet och rekursiv oskiljaktighet", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik , 4 : 143–147, doi : 10.1002/malq.19580040705 , ISSN 0044 9, ISSN 0044 9 , ISSN 0049 2