Please use this identifier to cite or link to this item:
https://doi.org/10.2178/jsl/1191333855
Title: | Applications of kolmogorov complexity to computable model theory | Authors: | Khoussainov, B. Semukhin, P. Stephan, F. |
Issue Date: | Sep-2007 | Citation: | Khoussainov, B., Semukhin, P., Stephan, F. (2007-09). Applications of kolmogorov complexity to computable model theory. Journal of Symbolic Logic 72 (3) : 1041-1054. ScholarBank@NUS Repository. https://doi.org/10.2178/jsl/1191333855 | Abstract: | In this paper we answer the following well-known open question in computable model theory. Does there exist a computable not N0- 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 an N 1 -categorical but not N0-categorical saturated Σ1 0-structure with a unique computable isomorphism type. In addition, using the construction we give an example of an N 1-categorical but not N0-categorical theory whose only non-computable model is the prime one. © 2007, Association for Symbolic Logic. | Source Title: | Journal of Symbolic Logic | URI: | http://scholarbank.nus.edu.sg/handle/10635/102869 | ISSN: | 00224812 | DOI: | 10.2178/jsl/1191333855 |
Appears in Collections: | Staff Publications |
Show full item record
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.