Geodesic
Computable categoricity versus relative computable categoricity
Rodney G. Downey1 ; Asher M. Kach2 ; Steffen Lempp3 ; Daniel D. Turetsky4
1 Department of Mathematics Victoria University of Wellington Wellington, New Zealand
2 Department of Mathematics University of Chicago 5734 S. University Ave. Chicago, IL 60637, U.S.A.
3 Department of Mathematics University of Wisconsin Madison, WI 53706-1388, U.S.A.
4 Kurt Gödel Research Center for Mathematical Logic Währinger Straße 25 1090 Wien, Austria
Fundamenta Mathematicae, Tome 221 (2013) no. 2, pp. 129-159

Voir la notice de l'article provenant de la source Institute of Mathematics Polish Academy of Sciences

We study the notion of computable categoricity of computable structures, comparing it especially to the notion of relative computable categoricity and its relativizations. We show that every 1 decidable computably categorical structure is relatively $\Delta ^0_2$ categorical. We study the complexity of various index sets associated with computable categoricity and relative computable categoricity. We also introduce and study a variation of relative computable categoricity, comparing it to both computable categoricity and relative computable categoricity and its relativizations.
DOI : 10.4064/fm221-2-2
Keywords: study notion computable categoricity computable structures comparing especially notion relative computable categoricity its relativizations every nbsp decidable computably categorical structure relatively delta nbsp categorical study complexity various index sets associated computable categoricity relative computable categoricity introduce study variation relative computable categoricity comparing computable categoricity relative computable categoricity its relativizations

Rodney G. Downey 1 ; Asher M. Kach 2 ; Steffen Lempp 3 ; Daniel D. Turetsky 4

1 Department of Mathematics Victoria University of Wellington Wellington, New Zealand
2 Department of Mathematics University of Chicago 5734 S. University Ave. Chicago, IL 60637, U.S.A.
3 Department of Mathematics University of Wisconsin Madison, WI 53706-1388, U.S.A.
4 Kurt Gödel Research Center for Mathematical Logic Währinger Straße 25 1090 Wien, Austria 
@article{10_4064_fm221_2_2,
     author = {Rodney G. Downey and Asher M. Kach and Steffen Lempp and Daniel D. Turetsky},
     title = {Computable categoricity
 versus relative computable categoricity},
     journal = {Fundamenta Mathematicae},
     pages = {129--159},
     publisher = {mathdoc},
     volume = {221},
     number = {2},
     year = {2013},
     doi = {10.4064/fm221-2-2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.4064/fm221-2-2/}
}
TY  - JOUR
AU  - Rodney G. Downey
AU  - Asher M. Kach
AU  - Steffen Lempp
AU  - Daniel D. Turetsky
TI  - Computable categoricity
 versus relative computable categoricity
JO  - Fundamenta Mathematicae
PY  - 2013
SP  - 129
EP  - 159
VL  - 221
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.4064/fm221-2-2/
DO  - 10.4064/fm221-2-2
LA  - en
ID  - 10_4064_fm221_2_2
ER  - 
%0 Journal Article
%A Rodney G. Downey
%A Asher M. Kach
%A Steffen Lempp
%A Daniel D. Turetsky
%T Computable categoricity
 versus relative computable categoricity
%J Fundamenta Mathematicae
%D 2013
%P 129-159
%V 221
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.4064/fm221-2-2/
%R 10.4064/fm221-2-2
%G en
%F 10_4064_fm221_2_2
Rodney G. Downey; Asher M. Kach; Steffen Lempp; Daniel D. Turetsky. Computable categoricity
 versus relative computable categoricity. Fundamenta Mathematicae, Tome 221 (2013) no. 2, pp. 129-159. doi: 10.4064/fm221-2-2

Cité par Sources :