Applications of Kolmogorov Complexity to Computable Model Theory
No Thumbnail Available
Date
2006-09-07T06:46:20Z
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
In this paper we answer the following well-known open question in computable model theory. Does there exist a computable not countably categorical saturated structure with a unique computable isomorphism type? Our answer is affirmative and uses a construction based on Kolmogorov complexity.
With a variation of this construction, we also provide an example of a uncountably categorical but not countably categorical saturated Sigma-0-1-structure with a unique computable isomorphism type.
In addition, using the construction we give an example of an uncountably categorical but not countably categorical theory whose only non-computable model is the prime one.