Inseparability Notions
James S. Royer, John Case · Birkhäuser Boston eBooks · 1994
Inseparability notions are concerned with describing how hard it is to put a “fence” between two disjoint sets. Kleene [Kle52,Rog67] introduced the first such notion, recursive inseparability . We say a set S separates A from B if and only if A ⊆ S ⊆ \(\bar B\) , i.e., S is a fence around A that separates it from B . Two sets A and B are recursively inseparable if and only if A and B are disjoint and there is no recursive set that separates A from B . The motivation for this notion came from Gödel’s First Incompleteness Theorem [Göd86,Men86]: Kleene noted [Kle52,Rog67] that the set of sentences P provable in Peano Arithmetic is recursively inseparable from the set of sentences R refutable in Peano Arithmetic. If a complete, recursive axiomatization of arithmetic existed, its deductive closure C would be a recursive set separating P from R . These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.