Abstract
We investigate the effects of adding uniformity requirements to concepts in computable structure theory such as computable categoricity (of a structure) and intrinsic computability (of a relation on a computable structure). We consider and compare two different notions of uniformity, previously studied by Kudinov and by Ventsov. We discuss some of their results and establish new ones, while also exploring the connections with the relative computable structure theory of Ash, Knight, Manasse, and Slaman and Chisholm and with previous work of Ash, Knight, and Slaman on uniformity in a general computable structure-theoretical setting.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
REFERENCES
R. G. Downey, “Computability theory and linear orderings,” in Handbook of Recursive Mathematics, Stud. Log. Found. Math., Vol. 139, Y. L. Ershov, S. S. Goncharov, A. Nerode, and J. B. Remmel (eds.), Elsevier, Amsterdam (1998), pp. 823–976.
S. S. Goncharov, “The problem of the number of nonautoequivalent constructivizations,” Algebra Logika, 19, No. 6, 621–639 (1980).
P. Cholak, S. Goncharov, B. Khoussainov, and R. A. Shore, “Computably categorical structures and expansions by constants,” J. Symb. Log., 64, No. 1, 13–37 (1999).
S. S. Goncharov, “The quantity of nonautoequivalent constructivizations,” Algebra Logika, 16, No. 3, 257–282 (1977).
T. Millar, “Recursive categoricity and persistence,” J. Symb. Log., 51, No. 2, 430–434 (1986).
C. J. Ash, J. F. Knight, M. S. Manasse, and T. A. Slaman, “Generic copies of countable structures,” Ann. Pure Appl. Logic, 42, No. 3, 195–205 (1989).
J. Chisholm, “Effective model theory vs. recursive model theory,” J. Symb. Log., 55, No. 3, 1168–1191 (1990).
C. F. McCoy, “Finite computable dimension does not relativize,” Arch. Math. Log., 41, No. 4, 309–320 (2002).
O. V. Kudinov, “An autostable 1-decidable model without a computable Scott family of ∃-formulas,” Algebra Logika, 35, No. 4, 458–467 (1996).
O. V. Kudinov, “Some properties of autostable models,” Algebra Logika, 35, No. 6, 685–698 (1996).
O. V. Kudinov, “A description of autostable models,” Algebra Logika, 36, No. 1, 26–36 (1997).
Yu. G. Ventsov, “Effective choice for relations and reducibilities in classes of constructive and positive models,” Algebra Logika, 31, No. 2, 101–118 (1992).
Yu. G. Ventsov, “Effective choice operations on constructive and positive models,” Algebra Logika, 32, No. 1, 45–53 (1993).
C. J. Ash, J. F. Knight, and T. A. Slaman, “Relatively recursive expansions. II,” Fund. Math., 142, No. 2, 147–161 (1993).
R. I. Soare, Recursively Enumerable Sets and Degrees, Persp. Math. Logic, Springer, Heidelberg (1987).
W. Hodges, Model Theory, Enc. Math. Appl., Vol. 42, Cambridge University, Cambridge (1993).
C. J. Ash and J. F. Knight, “Relatively recursive expansions,” Fund. Math., 140, No. 2, 137–155 (1992).
J. C. Shepherdson and J. Myhill, “Effective operations on partial recursive functions,” Z. Math. Log. Grund. Math., 1, No. 4, 310–317 (1955).
G. Kreisel, D. Lacombe, and J. R. Shoenfield, “Partial recursive functionals and effective operations,” in Constructivity in Mathematics: Proceedings of the Colloquium held at Amsterdam, 1957, Stud. Log. Found. Math., A. Heyting (ed.), North-Holland, Amsterdam (1959), pp. 195–207.
H. Rogers, Jr., Theory of Recursive Functions and Effective Computability, 2nd edn., MIT, Cambridge, Mass. (1987).
B. Khoussainov and R. A. Shore, “Computable isomorphisms, degree spectra of relations, and Scott families,” Ann. Pure Appl. Log., 93, Nos. 1–3, 153–193 (1998).
V. V. V'yugin, “Discrete classes of recursively enumerable sets,” Algebra Logika, 11, No. 3, 243–256 (1972).
C. J. Ash and A. Nerode, “Intrinsically recursive relations. Aspects of effective algebra,” in Proc. Conf. Monash Univ., Clayton, Australia (1981), pp. 26–41.
M. S. Manasse, “Techniques and counterexamples in almost categorical recursive model theory,” Ph.D. Thesis, University of Wisconsin, Madison (1982).
J. Chisholm, “The complexity of intrinsically r.e. subsets of existentially decidable models,” J. Symb. Log., 55, No. 3, 1213–1232 (1990).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Downey, R.G., Hirschfeldt, D.R. & Khoussainov, B. Uniformity in Computable Structure Theory. Algebra and Logic 42, 318–332 (2003). https://doi.org/10.1023/A:1025971406116
Issue Date:
DOI: https://doi.org/10.1023/A:1025971406116