|
This article is cited in 11 scientific papers (total in 11 papers)
Index sets for $n$-decidable structures categorical relative to $m$-decidable presentations
E. B. Fokinaa, S. S. Goncharovbc, V. Harizanovd, O. V. Kudinovbc, D. Turetskye a Vienna University of Technology, Institute of Discrete Mathematics and Geometry, Wiedner Hauptstrase 8-10/104, 1040, Vienna, Austria
b Sobolev Institute of Mathematics, pr. Akad. Koptyuga 4, Novosibirsk, 630090, Russia
c Novosibirsk State University, ul. Pirogova 2, Novosibirsk, 630090, Russia
d George Washington Univ, Washington, DC, 20052, USA
e Kurt Gödel Research Center for Mathematical Logic, University of Vienna, Währinger Strase 25, 1090, Vienna, Austria
Abstract:
We say that a structure is categorical relative to $n$-decidable presentations (or autostable relative to $n$-constructivizations) if any two $n$-decidable copies of the structure are computably isomorphic. For $n=0$, we have the classical definition of a computably categorical (autostable) structure. Downey, Kach, Lempp, Lewis, Montalbán, and Turetsky proved that there is no simple syntactic characterization of computable categoricity. More formally, they showed that the index set of computably categorical structures is $\Pi^1_1$-complete.
We study index sets of $n$-decidable structures that are categorical relative to $m$-decidable presentations, for various $m,n\in\omega$. If $m\ge n\ge0$, then the index set is again $\Pi^1_1$-complete, i.e., there is no nice description of the class of $n$-decidable structures that are categorical relative to $m$-decidable presentations. In the case $m=n-1\ge0$, the index set is $\Pi^0_4$-complete, while if $0\le m\le n-2$, the index set is $\Sigma^0_3$-complete.
Keywords:
index set, structure categorical relative to $n$-decidable presentations, $n$-decidable structure categorical relative to $m$-decidable presentations.
Received: 12.09.2015
Citation:
E. B. Fokina, S. S. Goncharov, V. Harizanov, O. V. Kudinov, D. Turetsky, “Index sets for $n$-decidable structures categorical relative to $m$-decidable presentations”, Algebra Logika, 54:4 (2015), 520–528; Algebra and Logic, 54:4 (2015), 336–341
Linking options:
https://www.mathnet.ru/eng/al708 https://www.mathnet.ru/eng/al/v54/i4/p520
|
Statistics & downloads: |
Abstract page: | 277 | Full-text PDF : | 46 | References: | 46 | First page: | 8 |
|