首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 0, and not above 0. This gives a first example of a computable structure with a degree of categoricity that does not belong to an interval of the form 0(α),0(α+1)] for any computable ordinal α. We then extend the technique to produce a rigid structure of computable dimension 3 such that if d0, d1, and d2 are the degrees of isomorphisms between distinct representatives of the three computable equivalence classes, then each di<d0d1d2. 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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号