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.
Index Sets of Decidably Categorical Models that are Elementarily Equivalent to the Powers of Omega. // Graphs and Combinatorics. – 2026. – DOI: 10.1007/s10469-026-09842-4. – URL: https://link.springer.com/article/10.1007/s10469-026-09842-4
(2026). Index Sets of Decidably Categorical Models that are Elementarily Equivalent to the Powers of Omega. Graphs and Combinatorics. https://doi.org/10.1007/s10469-026-09842-4
“Index Sets of Decidably Categorical Models that are Elementarily Equivalent to the Powers of Omega.” Graphs and Combinatorics, 2026. doi:10.1007/s10469-026-09842-4.
@article{article34259,
title = {Index Sets of Decidably Categorical Models that are Elementarily Equivalent to the Powers of Omega},
journal = {Graphs and Combinatorics},
year = {2026},
doi = {10.1007/s10469-026-09842-4},
url = {https://link.springer.com/article/10.1007/s10469-026-09842-4}
}
We study the complexity of the existence problem of a ∀-sentence (∃-sentence) equivalent to a given sentence in signatures containing only unary symbols. We prove that if the signature consists of an at most one function symbol and an...
We obtain a criterion for decidable categoricity of injective unars. Exact complexity estimates are established for the index sets of the classes of strongly constructivizable injective unars and decidably categorical injective unars....
Some conditions are given under which the union of an increasing chain of Jónsson algebras is again a Jónsson algebra. Conditions are found under which there exists a countable increasing chain of Jónsson groups whose union is not a...
We study a categorical approach to the concept of varieties of chiral algebras. We prove that the class of chiral algebras in the variety defined by a binary quadratic operad Var, whose conformal structure is abelian, coincides with the...