Finite computable dimension and degrees of categoricity |
| |
Authors: | Barbara F Csima Jonathan Stephenson |
| |
Institution: | 1. Department of Pure Mathematics, University of Waterloo, Waterloo, ON, N2L 3G1, Canada;2. Department of Mathematics and Statistics, Valparaiso University, Valparaiso, IN, 46383, USA |
| |
Abstract: | We first give an example of a rigid structure of computable dimension 2 such that the unique isomorphism between two non-computably isomorphic computable copies has Turing degree strictly below , and not above . This gives a first example of a computable structure with a degree of categoricity that does not belong to an interval of the form for any computable ordinal α. We then extend the technique to produce a rigid structure of computable dimension 3 such that if , , and are the degrees of isomorphisms between distinct representatives of the three computable equivalence classes, then each . The resulting structure is an example of a structure that has a degree of categoricity, but not strongly. |
| |
Keywords: | 03D45 03C57 03D80 03D99 Computability theory Computable structure theory |
本文献已被 ScienceDirect 等数据库收录! |
|