Labelling systems and r.e. structures

DOI10.1016/0168-0072(90)90065-AMaRDI QIDQ923076zbMATH OpenOpenAlexFDO

Authors C. J. Ash

Publication date 1990

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0168-0072(90)90065-a

zbMATH Keywords

\(\alpha \) -systemslabelling systemsrecursively enumerable structures

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45)

Review text

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 \textit{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 \textit{J. F. Knight} [Ann. Pure Appl. Logic 48, 237-259 (1990; Zbl 0712.03035)] and by \textit{S. Lempp} and \textit{M. Lerman} [Lect. Notes Math. 1432, 277-296 (1990; Zbl 0702.03019)].

Recommendations

• Constructions by transfinitely many workers
• Recursive Labelling Systems and Stability of Recursive Structures in Hyperarithmetical Degrees
• Priority constructions
• Mixed systems
• Requirement systems

Cites work

• Categoricity in hyperarithmetical degrees
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• Intrinsically \(\Sigma ^ 0_{\alpha}\) relations
• Jumps of Orderings
• Model theory
• Pairs of recursive structures
• Recursive Labelling Systems and Stability of Recursive Structures in Hyperarithmetical Degrees
• Stability of recursive structures in arithmetical degrees

Cited in

(21)

• Sticker systems
• Coding a family of sets
• Hyperarithmetical relations in expansions of recursive structures
• Inseparability in recursive copies
• Ramified systems
• Completeness of the hyperarithmetic isomorphism equivalence relation
• The isomorphism problem for computable Abelian _p-groups of bounded length
• A metatheorem for constructions by finitely many workers
• A construction for recursive linear orderings
• Annual meeting of the Association for Symbolic Logic, Notre Dame, 1993
• Mixed systems
• Requirement systems
• A General Framework for Priority Arguments
• 1994–1995 Winter Meeting of the Association for Symbolic Logic
• 1995 Annual Meeting of the Association for Symbol Logic
• The property ``arithmetic-is-recursive on a cone
• PRIORITY ARGUMENTS VIA TRUE STAGES
• Degrees of categoricity on a cone via -systems
• Iterated priority arguments in descriptive set theory
• Incomparable prime ideals of recursively enumerable degrees
• Constructions by transfinitely many workers

This page was built for publication: Labelling systems and r.e. structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q923076)