×

Labelling systems and r.e. structures. (English) Zbl 0712.03021

In Ann. Pure Appl. Logic 32, 113-155 (1986; Zbl 0631.03016), the author introduced a formal framework for the development of inductive \(\underset{\tilde{}} 0^{(\alpha)}\)-priority arguments \((\alpha <\omega_ 1^{ck})\). This paper contained the first metatheorem for such arguments, and formalized the earlier ‘method of workers’ of Harrington and even earlier specific constructions such as L. Feiner’s in J. Symb. Logic 35, 365-374 (1970; Zbl 0222.02048). Since then the author and his students have refined and recast his metatheorem in a series of papers. In the one under review, he presents labelling systems which are appropriate for construction of r.e. (rather than only recursive) structures. Some applications (such as those in the lines of the paper reviewed above (see Zbl 0712.03020)) are discussed. The reader should also consult the author’s recent game theoretical formulation in “A construction for recursive linear orderings” [J. Symb. Logic (to appear)], as well as related work by J. F. Knight [Ann. Pure Appl. Logic 48, 237-259 (1990; Zbl 0712.03035)] and by S. Lempp and M. Lerman [Lect. Notes Math. 1432, 277-296 (1990; Zbl 0702.03019)].
Reviewer: R.Downey

MSC:

03C57 Computable structure theory, computable model theory
03D45 Theory of numerations, effectively presented structures
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ash, C. J., Stability of recursive structures in arithmetical degrees, Ann. Pure Appl. Logic, 32, 113-135 (1986) · Zbl 0631.03016
[2] Ash, C. J., Recursive labelling systems and stability of recursive structures in hyperarithmetical degrees, Trans. Amer. Math. Soc., 310, 497-514 (1988), Corrections · Zbl 0631.03017
[3] Ash, C. J., Categoricity of recursive structures in hyperarithmetical degrees, Ann. Pure Appl. Logic, 34, 1-14 (1987) · Zbl 0617.03016
[4] C.J. Ash, C. Jockusch and J.F. Knight, Jump degrees of orderings, Trans. Amer. Math. Soc., to appear; C.J. Ash, C. Jockusch and J.F. Knight, Jump degrees of orderings, Trans. Amer. Math. Soc., to appear · Zbl 0705.03022
[5] C.J. Ash and J.F. Knight, Pairs of recursive structures, Ann. Pure Appl. Logic, to appear; C.J. Ash and J.F. Knight, Pairs of recursive structures, Ann. Pure Appl. Logic, to appear
[6] Barker, E., Intrinsically \(Σ^0_σ\) relations, Ann. Pure Appl. Logic, 39, 105-130 (1988) · Zbl 0651.03034
[7] Keisler, H. J., Model theory for Infinitary Logic (1973), North-Holland: North-Holland Amsterdam · Zbl 0276.02032
[8] Rogers, H., Theory of Recursive Functions and Effective Computability (1967), McGraw-Hill: McGraw-Hill New York · Zbl 0183.01401
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.