계산적으로 분리할 수 없음

계산가능성 이론에서, 자연수의 두 분리된 집합은 계산 가능한 집합과 "분리"될 수 없는 경우 계산적으로 분리되거나 반복적으로 분리될 수 없는 집합이라고 불린다.^[1]이러한 집합은 계산가능성 이론 자체에 대한 연구, 특히 π⁰
₁ 등급에 관한 연구에서 발생한다.계산적으로 불가분의 집합은 괴델의 불완전성 정리 연구에서도 발생한다.

정의

The natural numbers are the set ${\displaystyle \mathbb {N} =\{0,1,2,\dots \}}$. Given disjoint subsets A and B of ${\displaystyle \mathbb {N} }$, a separating set C is a subset of ${\displaystyle \mathbb {N} }$ such that A ⊆ C and B ∩ C = ∅ (or equivalently, A ⊆ C and B ⊆ C).예를 들어 A 자체는 B와 같이 쌍을 위한 분리 집합이다.

만약 한 쌍의 디스조인트 세트가 A와 B에 계산 가능한 분리 세트가 없다면, 두 세트는 계산적으로 분리할 수 없다.

예

만약 A가 계산이 불가능한 집합이라면, A와 그 보완물은 계산적으로 분리할 수 없다.그러나, A와 B 세트의 많은 예들이 분리되고, 완성되지 않으며, 계산적으로 분리할 수 없는 경우가 있다.더욱이 A와 B는 계산적으로 분리되고, 분리되며, 계산적으로 열거할 수 있는 것이 가능하다.

• 부분 계산 가능한 함수의 표준 인덱싱이 되도록 한다.그러면 A = {e : φ_e(0) = 0}, B = {e : φ_e(0) = 1} 세트는 계산상 분리할 수 없다(William Gasarch1998, 페이지 1047).
• # 페아노 산수의 공식에 대한 표준 괴델 번호 매기기가 되자.그러면 검증 가능한 공식의 집합 A = { (ψ) : PA ⊢ ψ }}과 반박 가능한 공식의 집합 B = { #(ψ) : PA } } ¬ } }}은 계산적으로 분리할 수 없다.입증 가능하고 반박할 수 있는 공식 집합의 불가분성은 다른 많은 공식 산술 이론에 적용된다(Smullyan 1958).

참조

• Cenzer, Douglas (1999), "Π⁰
  ₁ classes in computability theory", Handbook of computability theory, Stud. Logic Found. Math., vol. 140, Amsterdam: North-Holland, pp. 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. Logic Found. Math., vol. 139, Amsterdam: North-Holland, pp. 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), "Undecidability and recursive inseparability", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 4: 143–147, doi:10.1002/malq.19580040705, ISSN 0044-3050, MR 0099293