Computability in structures representing a Scott set

DOI10.1007/S001530000060MaRDI QIDQ5945007zbMATH OpenOpenAlexFDO

Authors Alex M. McAllister

Publication date 28 November 2002

Published in Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s001530000060

zbMATH Keywords

arithmetical setscomputable structuresforcinggeneric objectsmodels of arithmeticScott set

Mathematics Subject Classification ID

Model-theoretic forcing (03C25) Models with special properties (saturated, rigid, etc.) (03C50) Computable structure theory, computable model theory (03C57) Models of arithmetic and set theory (03C62) Other degrees and reducibilities in computability and recursion theory (03D30) Undecidability and degrees of sets of sentences (03D35)

Review text

In this paper the author utilizes a notion of forcing for which the generic objects are are structures and which allows him to compute certain sets and enumerations. Considering a characterization of sets of natural numbers computable in all models of a given theory representing a given Scott set, the author shows that the characteristic function of such a set must be enumeration reducible to a complete existential type which is consistent with the given theory and is an element of the given Scott set. The author also shows that there exist models of of completions of ZF from which one cannot enumerate the family of sets represented by the theory.

Recommendations

• Completions of PA: Models and enumerations of representable sets
• Enumerations, countable structures and Turing degrees
• Computable structures in generic extensions
• scientific article; zbMATH DE number 4033714
• New Computational Paradigms

Cited in

(8)

• Computable Scott sentences for quasi-Hopfian finitely presented structures
• Computable structures in generic extensions
• Kleene, Rabin, and Scott Are Available
• scientific article; zbMATH DE number 4033714 (Why is no real title available?)
• Completions of PA: Models and enumerations of representable sets
• Bounded Scott Set Saturation
• SCOTT COMPLEXITY OF COUNTABLE STRUCTURES
• Computable trees of Scott rank ω₁^CK, and computable approximation

This page was built for publication: Computability in structures representing a Scott set

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