|
This article is cited in 31 scientific papers (total in 31 papers)
Friedberg Numberings of Families of $n$-Computably Enumerable Sets
S. S. Goncharova, S. Lemppb, R. Solomonb a Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences
b University of Wisconsin-Madison
Abstract:
We establish a number of results on numberings, in particular, on Friedberg numberings, of families of d.c.e. sets. First, it is proved that there exists a Friedberg numbering of the family of all d.c.e. sets. We also show that this result, patterned on Friedberg's famous theorem for the family of all c.e. sets, holds for the family of all $n$-c.e. sets for any $n>2$. Second, it is stated that there exists an infinite family of d. c. e. sets without a Friedberg numbering. Third, it is shown that there exists an infinite family of c. e. sets (treated as a family of d. c. e. sets) with a numbering which is unique up to equivalence. Fourth, it is proved that there exists a family of d. c. e. sets with a least numbering (under reducibility) which is Friedberg but is not the only numbering (modulo reducibility).
Received: 22.11.2000
Citation:
S. S. Goncharov, S. Lempp, R. Solomon, “Friedberg Numberings of Families of $n$-Computably Enumerable Sets”, Algebra Logika, 41:2 (2002), 143–154; Algebra and Logic, 41:2 (2002), 81–86
Linking options:
https://www.mathnet.ru/eng/al177 https://www.mathnet.ru/eng/al/v41/i2/p143
|
Statistics & downloads: |
Abstract page: | 462 | Full-text PDF : | 159 | References: | 55 | First page: | 1 |
|