Hyperarithmetical relations in expansions of recursive structures (Q1315834)

Let \({\mathfrak A}\) be a model of a theory \(T\). Depending on whether \({\mathfrak A}\) is decidable or recursive, and on whether \(T\) is strongly minimal or \({\mathcal O}\)-minimal, we find conditions on \({\mathfrak A}\) which guarantee that every infinite independent subset of \({\mathfrak A}\) is not recursively enumerable. For each of the same four cases we also find conditions on \({\mathfrak A}\) which guarantee that every infinite independent subset of \({\mathfrak A}\) has Turing degree \(\geq \mathbf{0}'\). More generally, let \({\mathfrak A}\) be a recursive \({\mathfrak L}\)-structure, \(R\) a relation symbol not in \({\mathfrak L}\), \(\psi\) a recursive infinitary \(\Pi_ 2\) sentence in the language \({\mathfrak L} \cup\{R\}\), and let \(0<\alpha< \omega_ 1^{CK}\). We discuss conditions under which we can construct a recursive \({\mathfrak L}\)-structure \({\mathfrak B}\simeq {\mathfrak A}\) such that \(\langle {\mathfrak B}, R_{\mathfrak B} \rangle \not\models \psi\) for every \(\Delta_ \alpha^ 0\) relation \(R_{\mathfrak B}\) on \({\mathfrak B}\). We first provide high-level conditions on \({\mathfrak A}\) which will change, depending on whether \(\alpha\) is a successor or a limit ordinal. We accordingly employ different versions of a metatheorem of C. Ash which gives conditions under which a high-level priority argument will succeed. If \(\alpha\) is a successor, we use an ``\(\alpha\)-system'', since all requirements are \(\Delta_ \alpha^ 0\). If \(\alpha\) is a limit, we let \(\langle \alpha_ n \rangle\) be a recursive increasing sequence of (notations for) successor ordinals whose supremum is \(\alpha\), and employ an ``\(\langle \alpha_ n\rangle\)-system'', enabling us to meet a single \(\Delta_{\alpha-n}^ 0\) requirement for each \(n\). Finally, using an \(\alpha\)-system, we find uniform low-level conditions on \({\mathfrak A}\) which are independent of whether \(\alpha\) is a successor or a limit.