Сибирские электронные математические известия
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Сиб. электрон. матем. изв.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Сиб. электрон. матем. изв., 2020, том 17, страницы 1013–1026 (Mi semr1270)  

Математическая логика, алгебра и теория чисел

A note on decidable categoricity and index sets

N. Bazhenov, M. Marchuk

Sobolev Institute of Mathematics, 4, Acad. Koptyug Ave., Novosibirsk, 630090, Russia

Аннотация: A structure $S$ is decidably categorical if $S$ has a decidable copy, and for any decidable copies $A$ and $B$ of $S$, there is a computable isomorphism from $A$ onto $B$. Goncharov and Marchuk proved that the index set of decidably categorical graphs is $\Sigma^0_{\omega+2}$ complete. In this paper, we isolate two familiar classes of structures $K$ such that the index set for decidably categorical members of $K$ has a relatively low complexity in the arithmetical hierarchy. We prove that the index set of decidably categorical real closed fields is $\Sigma^0_3$ complete. We obtain a complete characterization of decidably categorical equivalence structures. We prove that decidably presentable equivalence structures have a $\Sigma^0_4$ complete index set. A similar result is obtained for decidably categorical equivalence structures.

Ключевые слова: decidable categoricity, autostability relative to strong constructivizations, index set, real closed field, equivalence structure, strong constructivization, decidable structure.

Финансовая поддержка Номер гранта
Министерство науки и высшего образования Российской Федерации 075-15-2019-1613
The work is supported by Mathematical Center in Akademgorodok under agreement No. 075-15-2019-1613 with the Ministry of Science and Higher Education of the Russian Federation.


DOI: https://doi.org/10.33048/semi.2020.17.076

Полный текст: PDF файл (481 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:

Тип публикации: Статья
УДК: 510.5
MSC: 03D45
Поступила 28 апреля 2020 г., опубликована 28 июля 2020 г.
Язык публикации: английский

Образец цитирования: N. Bazhenov, M. Marchuk, “A note on decidable categoricity and index sets”, Сиб. электрон. матем. изв., 17 (2020), 1013–1026

Цитирование в формате AMSBIB
\RBibitem{BazMar20}
\by N.~Bazhenov, M.~Marchuk
\paper A note on decidable categoricity and index sets
\jour Сиб. электрон. матем. изв.
\yr 2020
\vol 17
\pages 1013--1026
\mathnet{http://mi.mathnet.ru/semr1270}
\crossref{https://doi.org/10.33048/semi.2020.17.076}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000557456400001}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/semr1270
  • http://mi.mathnet.ru/rus/semr/v17/p1013

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Просмотров:
    Эта страница:40
    Полный текст:21
    Литература:2
     
    Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021