Please use this identifier to cite or link to this item:
https://doi.org/10.1016/j.apal.2008.06.010
| Title: | Computable categoricity and the Ershov hierarchy | Authors: | Khoussainov, B. Stephan, F. Yang, Y. |
Keywords: | Categoricity Ershov hierarchy Graphs with finite components Model theory Recursion theory |
Issue Date: | Nov-2008 | Citation: | Khoussainov, B., Stephan, F., Yang, Y. (2008-11). Computable categoricity and the Ershov hierarchy. Annals of Pure and Applied Logic 156 (1) : 86-95. ScholarBank@NUS Repository. https://doi.org/10.1016/j.apal.2008.06.010 | Abstract: | In this paper, the notions of Fα-categorical and Gα-categorical structures are introduced by choosing the isomorphism such that the function itself or its graph sits on the α-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 G2-categorical; in the latter case it is not Fα-categorical for any recursive ordinal α. © 2008 Elsevier B.V. All rights reserved. | Source Title: | Annals of Pure and Applied Logic | URI: | http://scholarbank.nus.edu.sg/handle/10635/103019 | ISSN: | 01680072 | DOI: | 10.1016/j.apal.2008.06.010 |
| 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.