RUS  ENG
Full version
JOURNALS // Algebra i logika // Archive

Algebra Logika, 2020 Volume 59, Number 1, Pages 66–83 (Mi al935)

This article is cited in 3 papers

Computable positive and Friedberg numberings in hyperarithmetic

I. Sh. Kalimullina, V. G. Puzarenkobc, M. Kh. Faizrakhmanova

a Kazan (Volga Region) Federal University
b Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences, Novosibirsk
c Novosibirsk State University

Abstract: We point out an existence criterion for positive computable total $\Pi^1_1$-numberings of families of subsets of a given $\Pi^1_1$-set. In particular, it is stated that the family of all $\Pi^1_1$-sets has no positive computable total $\Pi^1_1$-numberings. Also we obtain a criterion of existence for computable Friedberg $\Sigma^1_1$-numberings of families of subsets of a given $\Sigma^1_1$-set, the consequence of which is the absence of a computable Friedberg $\Sigma^1_1$-numbering of the family of all $\Sigma^1_1$-sets. Questions concerning the existence of negative computable $\Pi^1_1$- and $\Sigma^1_1$-numberings of the families mentioned are considered.

Keywords: computable numbering, admissible set, analytical hierarchy, positive numbering, Friedberg numbering, negative numbering.

UDC: 510.5

Received: 28.10.2018
Revised: 30.04.2018

DOI: 10.33048/alglog.2020.59.104


 English version:
Algebra and Logic, 2020, 59:1, 46–58

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024