Computable numberings of families of infinite sets
A Friedberg numbering of a set is an effective enumeration of the set's members without repetition. In [Bull. Acad. Pol. Sci., Sér. Sci. Math. Astron. Phys. 6, 1--5 (1958; Zbl 0084.24902)] \textit{R. M. Friedberg} gave such an enumeration of the c.e. sets. This paper shows by diagonal argument that there is no such enumeration for the infinite c.e. sets. Extending these arguments to the analytical hierarchy, there is neither a \(\pi^1_1\)-computable numbering for all infinite \(\pi^1_1\) sets, nor a \(\varepsilon^1_2\)-computable numbering for all infinite \(\varepsilon^1_2\) sets. Moreover, that for \(k>2\) there is no \(\varepsilon^1_k\)-computable numbering of the infinite \(\varepsilon^1_k\) sets is a consequence of Gödel's axiom of constructibility, whence existence of such an ordering is unprovable in ZF. Whether or not its nonexistence is provable in ZF is an open question.
- Elimination of metarecursion in a theorem of Owings
- Generalized computable numerations and nontrivial Rogers semilattices
- scientific article; zbMATH DE number 2167508 (Why is no real title available?)
- scientific article; zbMATH DE number 7139148 (Why is no real title available?)
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- Separation principles in the hierarchies of classical and effective descriptive set theory
- Set Theory
- Some consequences of the axiom of constructibility
- SOME CONSEQUENCES OF THE AXIOM OF DEFINABLE DETERMINATENESS
- The axiom of determinateness and reduction principles in the analytical hierarchy
- The Consistency of the Axiom of Choice and of the Generalized Continuum-Hypothesis
- The Meta-R.E. sets, but not the Π11 sets, can be enumerated without repetition
- Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication
- The number of nonequivalent computable indexations for a fixed family of sets
- Some absolute properties of \(A\)-computable numberings
- Positive numberings in admissible sets
- Computable positive and Friedberg numberings in hyperarithmetic
- Inductive inference and computable numberings
- Rogers semilattices with least and greatest elements in the Ershov hierarchy
- An infinite family of \(\Sigma_a^{-1}\)-sets with a unique computable numbering
- -principal numberings
- Numberings and randomness
- Almost computably enumerable families of sets
- On constructive and enumerable sets
- Effective Enumerations of Families of Finite Sets of Natural Numbers
- scientific article; zbMATH DE number 1534577 (Why is no real title available?)
- A note on partial numberings
- scientific article; zbMATH DE number 2167508 (Why is no real title available?)
- scientific article; zbMATH DE number 3995654 (Why is no real title available?)
- Rogers semilattices of punctual numberings
- Friedberg numbering in fragments of Peano arithmetic and -recursion theory
- Computable numberings of families of low sets and Turing jumps in the Ershov hierarchy
- On decomposition of Gödelnumberings into Friedbergnumberings
- Effectively infinite classes of numberings of computable families of reals
- Rogers semilattices of limitwise monotonic numberings
- Effectively infinite classes of numberings and computable families of reals
- Positive undecidable numberings in the Ershov hierarchy
- Effectively closed sets and enumerations
This page was built for publication: Computable numberings of families of infinite sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2300737)
