JEDNOSTKA NAUKOWA KATEGORII A+

Computable categoricity versus relative computable categoricity

Tom 221 / 2013

Rodney G. Downey, Asher M. Kach, Steffen Lempp, Daniel D. Turetsky Fundamenta Mathematicae 221 (2013), 129-159 MSC: Primary 03C57. DOI: 10.4064/fm221-2-2

Streszczenie

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.

Autorzy

  • Rodney G. DowneyDepartment of Mathematics
    Victoria University of Wellington
    Wellington, New Zealand
    e-mail
  • Asher M. KachDepartment of Mathematics
    University of Chicago
    5734 S. University Ave.
    Chicago, IL 60637, U.S.A.
    e-mail
  • Steffen LemppDepartment of Mathematics
    University of Wisconsin
    Madison, WI 53706-1388, U.S.A.
    e-mail
  • Daniel D. TuretskyKurt Gödel Research Center
    for Mathematical Logic
    Währinger Straße 25
    1090 Wien, Austria
    e-mail

Przeszukaj wydawnictwa IMPAN

Zbyt krótkie zapytanie. Wpisz co najmniej 4 znaki.

Przepisz kod z obrazka

Odśwież obrazek

Odśwież obrazek