A computably categorical structure whose expansion by a constant has infinite computable dimension

, &
Journal of Symbolic Logic 68 (4):1199-1241 (2003)
  Copy   BIBTEX

Abstract

Cholak, Goncharov, Khoussainov, and Shore [1] 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 ω. Our proof uses a version of Goncharov's method of left and right operations

Categories

Keywords

Reprint years

DOI

10.2178/jsl/1067620182

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,612

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

A Computably Categorical Structure Whose Expansion By A Constant Has Infinite Computable Dimension.Denis Hirschfeldt, Bakhadyr Khoussainov & Richard Shore - 2003 - Journal of Symbolic Logic 68 (4):1199-1241.
Degree spectra of relations on structures of finite computable dimension.Denis R. Hirschfeldt - 2002 - Annals of Pure and Applied Logic 115 (1-3):233-277.
S. S. Goncharov. Autostability and computable families of constructivizations. Algebra and Logic, vol. 14 (1975), no. 6, pp. 392–409. - S. S. Goncharov. The quantity of nonautoequivalent constructivizations. Algebra and Logic, vol. 16 (1977), no. 3, pp. 169–185. - S. S. Goncharov and V. D. Dzgoev. Autostability of models. Algebra and Logic, vol. 19 (1980), no. 1, pp. 28–37. - J. B. Remmel. Recursively categorical linear orderings. Proceedings of the American Mathematical Society, vol. 83 (1981), no. 2, pp. 387–391. - Terrence Millar. Recursive categoricity and persistence. The Journal of Symbolic Logic, vol. 51 (1986), no. 2, pp. 430–434. - Peter Cholak, Segey Goncharov, Bakhadyr Khoussainov and Richard A. Shore. Computably categorical structures and expansions by constants. The Journal of Symbolic Logic, vol. 64 (1999), no. 1, pp. 13–137. - Peter Cholak, Richard A. Shore and Reed Solomon. A computably stable structure with no Scott family of finitary formulas. Archive for Mathematical. [REVIEW]Daniel Turetsky - 2012 - Bulletin of Symbolic Logic 18 (1):131-134.
S. S. Goncharov. Autostability and computable families of constructivizations. Algebra and Logic, vol. 14 , no. 6, pp. 392–409. - S. S. Goncharov. The quantity of nonautoequivalent constructivizations. Algebra and Logic, vol. 16 , no. 3, pp. 169–185. - S. S. Goncharov and V. D. Dzgoev. Autostability of models. Algebra and Logic, vol. 19 , no. 1, pp. 28–37. - J. B. Remmel. Recursively categorical linear orderings. Proceedings of the American Mathematical Society, vol. 83 , no. 2, pp. 387–391. - Terrence Millar. Recursive categoricity and persistence. The Journal of Symbolic Logic, vol. 51 , no. 2, pp. 430–434. - Peter Cholak, Segey Goncharov, Bakhadyr Khoussainov and Richard A. Shore. Computably categorical structures and expansions by constants. The Journal of Symbolic Logic, vol. 64 , no. 1, pp. 13–137. - Peter Cholak, Richard A. Shore and Reed Solomon. A computably stable structure with no Scott family of finitary formulas. Archive for Mathematical Logic, vol. 45 , no. 5, pp. 519–538. [REVIEW]Daniel Turetsky - 2012 - Bulletin of Symbolic Logic 18 (1):131-134.
Computable categoricity of trees of finite height.Steffen Lempp, Charles McCoy, Russell Miller & Reed Solomon - 2005 - Journal of Symbolic Logic 70 (1):151-215.
A computable ℵ 0 -categorical structure whose theory computes true arithmetic.Bakhadyr Khoussainov & Antonio Montalbán - 2010 - Journal of Symbolic Logic 75 (2):728-740.
The computable dimension of trees of infinite height.Russell Miller - 2005 - Journal of Symbolic Logic 70 (1):111-141.
Enumerations in computable structure theory.Sergey Goncharov, Valentina Harizanov, Julia Knight, Charles McCoy, Russell Miller & Reed Solomon - 2005 - Annals of Pure and Applied Logic 136 (3):219-246.
A computable [image] structure whose theory computes true arithmetic.Bakhadyr Khoussainov & Antonio Montalbán - 2010 - Journal of Symbolic Logic 75 (2):728 - 740.
Effective categoricity of equivalence structures.Wesley Calvert, Douglas Cenzer, Valentina Harizanov & Andrei Morozov - 2006 - Annals of Pure and Applied Logic 141 (1):61-78.

Analytics

Added to PP
2009-01-28

Downloads
212 (#15,393)

6 months
9 (#1,260,759)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

View all 7 citations / Add more citations

References found in this work

Degree spectra of intrinsically C.e. Relations.Denis R. Hirschfeldt - 2001 - Journal of Symbolic Logic 66 (2):441-469.

View all 7 references / Add more references