Index Sets of Decidably Categorical Models that are Elementarily Equivalent to the Powers of Omega

Index Sets of Decidably Categorical Models that are Elementarily Equivalent to the Powers of Omega Full article

Journal

Algebra and Logic
ISSN: 0002-5232 , E-ISSN: 1573-8302

Output data

Year: 2026, Volume: 64, Number: 6, Pages: 397-401 Pages count : 5 DOI: 10.1007/s10469-026-09842-4

Tags

decidable structure, decidable categoricity, index set, computable ordinal, finitely axiomatizable class

Authors

Bazhenov N.A. ^1,3 , Zubkov M.V. ² , Marchuk M.I. ³

Affiliations

1	Novosibirsk State University, Novosibirsk, Russia
2	Kazan Federal University, Kazan and Innopolis University, Innopolis, Russia
3	Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk, Russia

Funding (2)

1	Министерство науки и высшего образования РФ	075-15-2025-349
2	Russian Science Foundation	25-21-00228

A strongly constructivizable model S is decidably categorical if for any decidable copies A and B of S, there exists a computable isomorphism from A onto B. The paper investigates the complexity of families of decidably categorical models belonging to familiar finitely axiomatizable classes. For a non-zero natural number n, the index set of decidably categorical linear orders elementarily equivalent to the ordinal ωn is an m-complete Σ0 2n+2-set. The index set of decidably categorical structures which are elementarily equivalent to ωn, enriched by the successor relation, is an m-complete Σ0 2n+1-set.

Bazhenov N.A. , Zubkov M.V. , Marchuk M.I.
Index Sets of Decidably Categorical Models that are Elementarily Equivalent to the Powers of Omega
Algebra and Logic. 2026. V.64. N6. P.397-401. DOI: 10.1007/s10469-026-09842-4 WOS Scopus OpenAlex

Submitted:	Apr 14, 2026
Accepted:	May 27, 2026
Published print:	Aug 27, 2026
Published online:	Aug 27, 2026

≡ Web of science:	WOS:001861392900001
≡ Scopus:	2-s2.0-105048653262
≡ OpenAlex:	W7204475852