Constructions by transfinitely many workers (Q923078): Difference between revisions

There have been quite a number of constructions in recursion theory, particularly recursive algebra and model theory, where one constructs a recursive (or r.e.) object with certain highly nonrecursive properties. For instance, \textit{L. Feiner} [Thesis, MIT 1967] constructed an r.e. boolean algebra not isomorphic to a recursive one by coding in \(\underset{\tilde{}} 0^{(\omega)}\) in a highly nonuniform way. Similarly \textit{R. Watnick} [J. Symb. Logic 49, 563-569 (1984; Zbl 0585.03015)] essentially showed that if A is an ordering presentable in \(\underset{\tilde{}} 0^{n+2}\) then there is a copy of \((\omega +\omega^*)A\) presentable in \(\underset{\tilde{}} 0^{(n)}\). The first explicit mention of a general technique for `higher level' priority and coding arguments has an unpublished result of Harrington via what he called the ``method of workers''. This is a (not clearly described) way of imagining certain types of priority argument that is particularly suited to inductive arguments. For instance a normal \(\Pi_ 2\) argument has 3 workers, one (the true path worker) worker (2) at level \(\underset{\tilde{}} 0''\) and issues instructions knowing the `true path', worker 1 approximates this at level \(\underset{\tilde{}} 0'\) via relativised limit lemma and worker 0 works at the recursive level to approximate workers 1's instructions. This idea, whilst easy to describe is difficult to formalize, and there have been a number of attempts of metatheorems and formalizations. Ash and his students have produced a series of papers [e.g. \textit{C. J. Ash}, Ann. Pure Appl. Logic 47, 99-119 (1990; Zbl 0712.03021)] where precise model theoretical metatheorems are given for inductive arguments using so-called ``\(\alpha\)-systems''. In the present paper, as well as in J. Symb. Logic 55, 787-804 (1990), the author proposes a different formalization closer to the spirit of Harrington's original. Again the formulation is rather model theoretical. The current paper looks at systems for transfinitely many workers (i.e. \(n<\omega_ 1^{ck})\). As with most of the metatheorems the difficulty in using them seems to be in verifying the hypotheses. As with many (all?) worker arguments the proofs are presented in a slightly sketchy fashion. There is some further different but related recent work by \textit{S. Lempp} and \textit{M. Lerman} on iterated trees of strategy [see, e.g., Lect. Notes Math. 1432, 277-296 (1990; Zbl 0702.03019)].