|
This article is cited in 2 scientific papers (total 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.
Received: 14.12.2020 Revised: 01.08.2021 Accepted: 11.08.2021
Citation:
K. V. Blinov, “Primitively recursive categoricity for unars and equivalence structures”, Sibirsk. Mat. Zh., 62:6 (2021), 1231–1251; Siberian Math. J., 62:6 (2021), 994–1009
Linking options:
https://www.mathnet.ru/eng/smj7625 https://www.mathnet.ru/eng/smj/v62/i6/p1231
|
Statistics & downloads: |
Abstract page: | 193 | Full-text PDF : | 85 | References: | 51 | First page: | 3 |
|