TY - JOUR

T1 - Computable Positive and Friedberg Numberings in Hyperarithmetic

AU - Kalimullin, I. Sh

AU - Puzarenko, V. G.

AU - Faizrakhmanov, M. Kh

PY - 2020/3/1

Y1 - 2020/3/1

N2 - We point out an existence criterion for positive computable total Π11 -numberings of families of subsets of a given Π11 -set. In particular, it is stated that the family of all Π11 -sets has no positive computable total Π11 -numberings. Also we obtain a criterion of existence for computable Friedberg Σ11 -numberings of families of subsets of a given Σ11 - set, the consequence of which is the absence of a computable Friedberg Σ11 -numbering of the family of all Σ11 -sets. Questions concerning the existence of negative computable Π11 - and Σ11 -numberings of the families mentioned are considered.

AB - We point out an existence criterion for positive computable total Π11 -numberings of families of subsets of a given Π11 -set. In particular, it is stated that the family of all Π11 -sets has no positive computable total Π11 -numberings. Also we obtain a criterion of existence for computable Friedberg Σ11 -numberings of families of subsets of a given Σ11 - set, the consequence of which is the absence of a computable Friedberg Σ11 -numbering of the family of all Σ11 -sets. Questions concerning the existence of negative computable Π11 - and Σ11 -numberings of the families mentioned are considered.

KW - admissible set

KW - analytical hierarchy

KW - computable numbering

KW - Friedberg numbering

KW - negative numbering

KW - positive numbering

KW - FAMILIES

KW - PRESENTATIONS

UR - http://www.scopus.com/inward/record.url?scp=85087002640&partnerID=8YFLogxK

U2 - 10.1007/s10469-020-09578-9

DO - 10.1007/s10469-020-09578-9

M3 - Article

AN - SCOPUS:85087002640

VL - 59

SP - 46

EP - 58

JO - Algebra and Logic

JF - Algebra and Logic

SN - 0002-5232

IS - 1

ER -