Definability in the enumeration degrees
The authors prove the following Coding Theorem for the enumeration degrees \(\mathcal G\): every countable relation on \(\mathcal G\) is uniformly definable from parameters in \(\mathcal G\). It follows that the first-order theory of \(\mathcal G\) is recursively isomorphic to the second-order theory of arithmetic. Further, the authors prove an ``effective version'' of the Coding Theorem, which implies undecidability of the first-order theory of the \(\Sigma_2^0\)-enumeration degrees. Also, the authors pose the following questions: Is the \(\exists\forall\)-theory of \(\mathcal G\) decidable? Is the first-order theory of \(\Sigma_2^0\)-enumeration degrees recursively isomorphic to the first-order theory of arithmetic?
scientific article; zbMATH DE number 1158098