Computable Numberings of Families of Infinite Sets

M. V. Dorzhieva

doi:10.1007/s10469-019-09540-4

Computable Numberings of Families of Infinite Sets

M. V. Dorzhieva

Кафедра общей информатики ФИТ

Результат исследования: Научные публикации в периодических изданиях › статья

Аннотация

We state the following results: the family of all infinite computably enumerable sets has no computable numbering; the family of all infinite Π11 sets has no Π11 -computable numbering; the family of all infinite Σ21 sets has no Σ21 -computable numbering. For k > 2, the existence of a Σk1 -computable numbering for the family of all infinite Σk1 sets leads to the inconsistency of ZF.

Язык оригинала	английский
Страницы (с-по)	224-231
Число страниц	8
Журнал	Algebra and Logic
Том	58
Номер выпуска	3
DOI	https://doi.org/10.1007/s10469-019-09540-4
Состояние	Опубликовано - 1 июл 2019

Доступ к документу

10.1007/s10469-019-09540-4

Link to publication in Scopus

Fingerprint Подробные сведения о темах исследования «Computable Numberings of Families of Infinite Sets». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать

@article{8452c3a72b7f4fbf955ad61cb979a50b,

title = "Computable Numberings of Families of Infinite Sets",

abstract = "We state the following results: the family of all infinite computably enumerable sets has no computable numbering; the family of all infinite Π11 sets has no Π11 -computable numbering; the family of all infinite Σ21 sets has no Σ21 -computable numbering. For k > 2, the existence of a Σk1 -computable numbering for the family of all infinite Σk1 sets leads to the inconsistency of ZF.",

keywords = "analytical hierarchy, computability, computable numberings, Friedberg numbering, G{\"o}del{\textquoteright}s axiom of constructibility, Godel's axiom of constructibility, AXIOM",

author = "Dorzhieva, {M. V.}",

year = "2019",

month = jul,

day = "1",

doi = "10.1007/s10469-019-09540-4",

language = "English",

volume = "58",

pages = "224--231",

journal = "Algebra and Logic",

issn = "0002-5232",

publisher = "Springer US",

number = "3",

}

TY - JOUR

T1 - Computable Numberings of Families of Infinite Sets

AU - Dorzhieva, M. V.

PY - 2019/7/1

Y1 - 2019/7/1

N2 - We state the following results: the family of all infinite computably enumerable sets has no computable numbering; the family of all infinite Π11 sets has no Π11 -computable numbering; the family of all infinite Σ21 sets has no Σ21 -computable numbering. For k > 2, the existence of a Σk1 -computable numbering for the family of all infinite Σk1 sets leads to the inconsistency of ZF.

AB - We state the following results: the family of all infinite computably enumerable sets has no computable numbering; the family of all infinite Π11 sets has no Π11 -computable numbering; the family of all infinite Σ21 sets has no Σ21 -computable numbering. For k > 2, the existence of a Σk1 -computable numbering for the family of all infinite Σk1 sets leads to the inconsistency of ZF.

KW - analytical hierarchy

KW - computability

KW - computable numberings

KW - Friedberg numbering

KW - Gödel’s axiom of constructibility

KW - Godel's axiom of constructibility

KW - AXIOM

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

U2 - 10.1007/s10469-019-09540-4

DO - 10.1007/s10469-019-09540-4

M3 - Article

AN - SCOPUS:85074822859

VL - 58

SP - 224

EP - 231

JO - Algebra and Logic

JF - Algebra and Logic

SN - 0002-5232

IS - 3

ER -