Pairs of recursive structures (Q923075)

There are a large number of constructions in recursive algebra and model theory where we are given collections \(\{A_ n\}\), \(\{B_ n\}\) of recursive structures and a \(\Pi^ 0_{\alpha}\) set S and construct a recursive collection of recursive structures \(C_ n\) with \(C_ n\cong A_ n\) if \(n\in S\) and \(C_ n\cong B_ n\) otherwise. The main result of the present paper is that for any recursive ordinal \(\alpha\), and \(\Pi^ 0_{\alpha}\) set S if A and B are recursive structures such that the \(\Sigma_{\alpha}\) formulae true of A are a subset of the \(\Sigma_{\alpha}\) formulae true of B, then if (A,B) satisfy an additional decidability condition (``\(\alpha\)-friendliness'') one can construct a (uniformly) recursive family \(\{C_ n\}\) of recursive structures such that \(C_ n\cong A\) if \(n\in S\) and \(C_ n\cong B\) otherwise. The decidability condition is along the lines of those discovered by the first author in, e.g., Ann. Pure Appl. Logic 32, 113- 135 (1986; Zbl 0631.03016), and is designed for the inductive component in the constructions. The authors look at some extensions. The proof technique is that of inductive \(\underset{\tilde{}} 0^{(\alpha)}\)- priority arguments cast in Ash's model theoretic framework of \(\alpha\)- systems.