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

Graphs and Combinatorics · Springer Nature · 2026-01-01 · DOI: 10.1007/s10469-026-09842-4

Аннотация

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 $${\Sigma}_{2\text{n}+2}^{0}$$-set. The index set of decidably categorical structures which are elementarily equivalent to ω n , enriched by the successor relation, is an m-complete $${\Sigma}_{2\text{n}+1}^{0}$$-set.

Читать у издателя →

Похожие статьи