Applications of Kolmogorov complexity to computable model theory

Bakhadyr Khoussainov, Pavel Semukhin, Frank Stephan

Journal of Symbolic Logic · 2007 · 21 citations · 7 references

Concepts

Abstract

Abstract In this paper we answer the following well-known open question in computable model theory. Does there exist a computable not ℵ 0 -categorical saturated structure with a unique computable isomor-phism 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 an ℵ 1 -categorical but not ℵ 0 -categorical saturated -structure with a unique computable isomorphism type. In addition, using the construction we give an example of an ℵ 1 -categorical but not ℵ 0 -categorical theory whose only non-computable model is the prime one.

References

7