The Syntactic Characterization of Computability-Theoretic Properties
Open Access Depositedand relative dense immunity, relative dense simplicity. Through the analysis of these syntactic conditions, we deepen our understanding of the interplay between computability-theoretic properties and the syntactic properties of mathematical structures.
intrinsic lower density 0, c.e. sets with intrinsic upper density 1
relative intrinsic density 0, relativized c.e. sets with relative intrinsic density 1
relative intrinsic lower density 0, relativized c.e. sets with relative intrinsic upper density 1
Post’s Program led to the discovery of several computability-theoretic properties that play a very important role in computability theory and its applications. These include immune, simple, hyperimmune, hypersimple, cohesive, maximal, and others. Additional properties have expanded the landscape outlined by Post's Program. For example, Martin introduced dense simplicity and demonstrated the high computably enumerable (abbreviated by c.e.) Turing degrees are precisely those degrees containing dense simple sets. Astor introduced intrinsic density 0, identifying sets with asymptotic density 0 regardless of the computable permutation of their elements. Both dense simplicity and intrinsic density 0 have been of significant importance. Computable model theory studies the relationship between model-theoretic structures and computability. There are computability-theoretic properties of sets, and alternatively you have algebraic properties of structures—it is natural to ask, "how are they related?" The Ash-Nerode Theorem was the first theorem in a family of results that provide general syntactic conditions for various computability-theoretic properties. The original proof of the Ash-Nerode Theorem utilized the finite-injury method, where under some additional decidability conditions the equivalence holds in the effective setting. The method of forcing was later used to prove similar results in the relativized setting. This work examines the syntactic conditions for the properties introduced by Martin and Astor in both the effective and relativized settings. We consider
- All rights reserved
Notice to Authors
If you are the author of this work and you have any questions about the information on this page, please use the Contact form to get in touch with us.