×

zbMATH — the first resource for mathematics

A computably categorical structure whose expansion by a constant has infinite computable dimension. (English) Zbl 1055.03026
Summary: P. Cholak, S. Goncharov, B. Khoussainov, and R. A. Shore [ibid. 64, 13–37 (1999; Zbl 0928.03040)] showed that for each \(k>0\) there is a computably categorical structure whose expansion by a constant has computable dimension \(k\). We show that the same is true with \(k\) replaced by \(\omega\). Our proof uses a version of Goncharov’s method of left and right operations.

MSC:
03C57 Computable structure theory, computable model theory
Citations:
Zbl 0928.03040
PDF BibTeX XML Cite
Full Text: DOI Euclid
References:
[1] P. Cholak, S. S. Goncharov, B. Khoussainov, and R. A. Shore Computably categorical structures and expansions by constants , Journal of Symbolic Logic, vol. 64 (1999), pp. 13–37. JSTOR: · Zbl 0928.03040
[2] Y. L. Ershov, S. S. Goncharov, A. Nerode, and J. B. Remmel (editors) Handbook of recursive mathematics , Studies in Logic and the Foundations of Mathematics, vol. 138–139, Elsevier Science, Amsterdam,1998. · Zbl 0930.03037
[3] S. S. Goncharov Computable single-valued numerations , Algebra and Logic , vol. 19 (1980), pp. 325–356. · Zbl 0514.03029
[4] V. S. Harizanov Pure computable model theory , in Ershov et al. [?], pp. 3–114. · Zbl 0952.03037
[5] D. R. Hirschfeldt Degree spectra of intrinsically c. e. relations , Journal of Symbolic Logic, vol. 66 (2001), pp. 441–469. JSTOR: · Zbl 0988.03065
[6] D. R. Hirschfeldt, B. Khoussainov, R. A. Shore, and A. M. Slinko Degree spectra and computable dimension in algebraic structures , Annals of Pure and Applied Logic , vol. 115 (2002), pp. 71–113. · Zbl 1016.03034
[7] B. Khoussainov and R. A. Shore Computable isomorphisms, degree spectra of relations, and Scott families , Annals of Pure and Applied Logic , vol. 93 (1998), pp. 153–193. · Zbl 0927.03072
[8] T. Millar Recursive categoricity and persistence , Journal of Symbolic Logic, vol. 51 (1986), pp. 430–434. JSTOR: · Zbl 0631.03018
[9] R. I. Soare Recursively enumerable sets and degrees , Perspectives in Mathematical Logic, Springer-Verlag, Heidelberg,1987.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.