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

General Informatics Section

Research output: Contribution to journal › Article › peer-review

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.

Original language	English
Pages (from-to)	224-231
Number of pages	8
Journal	Algebra and Logic
Volume	58
Issue number	3
DOIs	https://doi.org/10.1007/s10469-019-09540-4
Publication status	Published - 1 Jul 2019

Keywords

analytical hierarchy
computability
computable numberings
Friedberg numbering
Gödel’s axiom of constructibility
Godel's axiom of constructibility
AXIOM

Access to Document

10.1007/s10469-019-09540-4

Cite this

@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 -

Computable Numberings of Families of Infinite Sets

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this