|
This article is cited in 4 scientific papers (total in 4 papers)
Computable numberings of families of infinite sets
M. V. Dorzhieva Novosibirsk State University
Abstract:
We state the following results: the family of all infinite
computably enumerable sets has no computable numbering; the family
of all infinite $\Pi^{1}_{1}$ sets has no
$\Pi^{1}_{1}$-computable numbering; the family
of all infinite
$\Sigma^{1}_{2}$ sets has no
$\Sigma^{1}_{2}$-computable numbering. For $k>2$,
the existence of a
$\Sigma^{1}_{k}$-computable numbering for the family of all
infinite
$\Sigma^{1}_{k}$ sets leads to the inconsistency of $ZF$.
Keywords:
computability, analytical hierarchy, computable numberings,
Friedberg numbering, Gödel's axiom of constructibility.
Received: 27.01.2018 Revised: 24.09.2019
Citation:
M. V. Dorzhieva, “Computable numberings of families of infinite sets”, Algebra Logika, 58:3 (2019), 334–343; Algebra and Logic, 58:3 (2019), 224–231
Linking options:
https://www.mathnet.ru/eng/al898 https://www.mathnet.ru/eng/al/v58/i3/p334
|
Statistics & downloads: |
Abstract page: | 206 | Full-text PDF : | 19 | References: | 28 | First page: | 3 |
|