A Computably Categorical Structure Whose Expansion by a Constant Has Infinite Computable Dimension

by Denis R. Hirschfeldt, Bakhadyr Khoussainov, and Richard A. Shore

Status: published in the Journal of Symbolic Logic 68 (2003) 1199 - 1241.

Availability: journal version and preprint

Abstract. Cholak, Goncharov, Khoussainov, and Shore [J. Symbolic Logic 64 (1999) 13 - 37] 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.