Computable Categoricity and the Ershov Hierarchy
No Thumbnail Available
Date
2007-08-31
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
In this paper, the notions of F[alpha]-categorical and G[alpha]-categorical structures are introduced by choosing the isomorphism such that the function itself or its graph sits on the alpha-th level of the Ershov hierarchy, respectively. Separations obtained by natural graphs which are the disjoint unions of countably many finite graphs. Furthermore, for size-bounded graphs, an easy criterion is given to say when it is computable-categorical and when it is only G[2]-categorical; in the latter case it is not F[alpha]-categorical for any recursive ordinal alpha.