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

Algebra i logika

RUS ENG

JOURNALS PEOPLE ORGANISATIONS CONFERENCES SEMINARS VIDEO LIBRARY PACKAGE AMSBIB

JavaScript is disabled in your browser. Please switch it on to enable full functionality of the website

	General information
	Latest issue
	Archive
	Impact factor

	Search papers
	Search references

	RSS
	Latest issue
	Current issues
	Archive issues
	What is RSS

Algebra Logika:
Year:
Volume:
Issue:
Page:
	Find

Personal entry:
Login:
Password:
	Save password
	Enter
	Forgotten password?
	Register

Algebra i logika, 2015, Volume 54, Number 4, Pages 520–528
DOI: https://doi.org/10.17377/alglog.2015.54.407 (Mi al708)

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. Fokina^a, S. S. Goncharov^bc, V. Harizanov^d, O. V. Kudinov^bc, D. Turetsky^e

^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

Full-text PDF (147 kB) Citations (11)

References:

PDF

HTML

DOI: https://doi.org/10.17377/alglog.2015.54.407

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, Montalbá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.

Funding agency	Grant number
Austrian Science Fund	V 206 I 1238
Russian Foundation for Basic Research	13-01-91001-АНФ_а
Ministry of Education and Science of the Russian Federation	НШ-860.2014.1
Supported by Austrian Science Fund FWF (projects V 206 and I 1238). Supported by RFBR (project No. 13-01-91001-ANF_a) and by the Grants Council (under RF President) for State Aid of Leading Scientific Schools (grant NSh-860.2014.1).

Received: 12.09.2015

English version:
Algebra and Logic, 2015, Volume 54, Issue 4, Pages 336–341
DOI: https://doi.org/10.1007/s10469-015-9353-6

Bibliographic databases:

Document Type: Article

UDC: 510.53

Language: Russian

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

Citation in format AMSBIB

\Bibitem{FokGonHar15}

\by E.~B.~Fokina, S.~S.~Goncharov, V.~Harizanov, O.~V.~Kudinov, D.~Turetsky

\paper Index sets for $n$-decidable structures categorical relative to $m$-decidable presentations

\jour Algebra Logika

\yr 2015

\vol 54

\issue 4

\pages 520--528

\mathnet{http://mi.mathnet.ru/al708}

\crossref{https://doi.org/10.17377/alglog.2015.54.407}

\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3468414}

\transl

\jour Algebra and Logic

\yr 2015

\vol 54

\issue 4

\pages 336--341

\crossref{https://doi.org/10.1007/s10469-015-9353-6}

\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000365784700007}

\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84957967781}

Linking options:

https://www.mathnet.ru/eng/al708

https://www.mathnet.ru/eng/al/v54/i4/p520

This publication is cited in the following 11 articles:

Caleb Camrud, Isaac Goldbring, Timothy H. McNicholl, “On the complexity of the theory of a computably presented metric structure”, Arch. Math. Logic, 62:7-8 (2023), 1111
N. A. Bazhenov, M. I. Marchuk, “O spektrakh razreshimoi kategorichnosti dlya pochti prostykh modelei”, Algebra i logika, 62:4 (2023), 441–457
N. A. Bazhenov, M. I. Marchuk, “Decidable Categoricity Spectra for Almost Prime Models”, Algebra Logic, 62:4 (2023), 291
M. N. Gaskova, “Bulevy algebry, avtoustoichivye otnositelno $n$ -razreshimykh predstavlenii”, Algebra i logika, 61:4 (2022), 443–460
M. N. Gaskova, “Boolean Algebras Autostable Relative to n-Decidable Presentations”, Algebra Logic, 61:4 (2022), 301
M. I. Marchuk, “Razreshimaya kategorichnost pochti prostykh modelei signatury grafov”, Matem. tr., 24:1 (2021), 117–141
M. I. Marchuk, “On Decidable Categoricity for Almost Prime Models of the Signature of Graphs”, Sib. Adv. Math., 31:4 (2021), 283
S. S. Goncharov, V. Harizanov, R. Miller, “On Decidable Categoricity and Almost Prime Models”, Sib. Adv. Math., 30:3 (2020), 200
N. Bazhenov, M. Harrison-Trainor, I. Kalimullin, A. Melnikov, K. M. Ng, “Automatic and polynomial-time algebraic structures”, J. Symb. Log., 84:4 (2019), 1630–1669
N. Bazhenov, “Autostability spectra for decidable structures”, Math. Struct. Comput. Sci., 28:3, SI (2018), 392–411
M. Harrison-Trainor, “There is no classification of the decidably presentable structures”, J. Math. Log., 18:2 (2018), UNSP 1850010

Citing articles in Google Scholar: Russian citations, English citations
Related articles in Google Scholar: Russian articles, English articles

Statistics & downloads:
Abstract page:	304
Full-text PDF :	53
References:	53
First page:	10

Что такое QR-код?

Registration to the website

Logotypes