Computable categoricity versus relative computable categoricity

• Autorzy: Rodney G. Downey , Asher M. Kach , Steffen Lempp , Daniel D. Turetsky
• Języki publikacji: EN

Abstrakty

EN

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 Δ⁰₂ 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.

Kategorie tematyczne

• 03C57: Effective and recursion-theoretic model theory

• Wydawca: Institute of Mathematics Polish Academy of Sciences
• Czasopismo: Fundamenta Mathematicae
• Rocznik: 2013
• Tom: 221
• Numer: 2
• Strony: 129-159

Daty

wydano

2013

Twórcy

autor

Rodney G. Downey

• Department of Mathematics, Victoria University of Wellington, Wellington, New Zealand

autor

Asher M. Kach

• Department of Mathematics, University of Chicago, 5734 S. University Ave., Chicago, IL 60637, U.S.A.

autor

Steffen Lempp

• Department of Mathematics, University of Wisconsin, Madison, WI 53706-1388, U.S.A.

autor

Daniel D. Turetsky

• Kurt Gödel Research Center, for Mathematical Logic, Währinger Straße 25, 1090 Wien, Austria

Identyfikatory

DOI

10.4064/fm221-2-2