RUS  ENG
Full version
JOURNALS // Sibirskii Matematicheskii Zhurnal // Archive

Sibirsk. Mat. Zh., 2021 Volume 62, Number 6, Pages 1231–1251 (Mi smj7625)

This article is cited in 2 papers

Primitively recursive categoricity for unars and equivalence structures

K. V. Blinov

Sobolev Institute of Mathematics, Novosibirsk, Russia

Abstract: This continues the study of the primitively recursive categoricity of structures for which there exists a primitively recursive decision algorithm with witnesses of all $\Sigma$-formulas. Considering the equivalence structures, we find a complete criterion for primitively recursive categoricity over the class $K_\Sigma$, which coincides with the already known criterion for computable categoricity. As regards unars, the structures with one arbitrary unary function, we distinguish some conditions for primitively recursive categoricity over $K_\Sigma$ and also for the absence of this categoricity. In particular, we find a full description of primitively recursive injective unars categorical over $K_\Sigma$.

Keywords: primitively recursive categoricity, equivalence structure, unars, decidability with primitively recursive witnesses, injective structure.

UDC: 510.57

MSC: 35R30

Received: 14.12.2020
Revised: 01.08.2021
Accepted: 11.08.2021

DOI: 10.33048/smzh.2021.62.603


 English version:
Siberian Mathematical Journal, 2021, 62:6, 994–1009

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025