On injective enumerability of recursively enumerable classes of cofinite sets
Tóm tắt
To date the problem of finding a general characterization of injective enumerability of recursively enumerable (r.e) classes of r.e. sets has proved intractable. This paper investigates the problem for r.e. classes of cofinite sets. We state a suitable criterion for r.e. classesC such that there is a boundn∈ω with |ω-A|≤n for allA∈C. On the other hand an example is constructed which shows that Lachlan's condition (F) does not imply injective enumerability for r.e. classes of cofinite sets. We also look at a certain embeddability property and show that it is equivalent with injective enumerability for certain classes of cofinite sets. At the end we present a reformulation of property (F).
Tài liệu tham khảo
[K] Kummer, M.: Numberings ofR 1 ⌣F, Computer Science Logic 1988. Lecture Notes in Computer Science385, 166–186 (1989)
[KD] Kummer, M.: Beiträge zur Theorie der Numerierungen: Eindeutige Numerierungen. Dissertation, Universität Karlsruhe, Germany (1989)
[L] Lachlan, A.: On recursive enumeration without repetition. Z. Math. Logik Grundlag. Math11, 209–220 (1965)
[LM] Lachlan, A.: Lower bounds for pairs of recursively enumerable degrees. Proc. London Math. Soc. (3)16, 537–569 (1966)
[LC] Lachlan, A.: On recursive enumeration without repetition: A correction. Z. Math. Logik Grundlag. Math.13, 99–100 (1967)
[M] Marchenkov, S.S.: On minimal numerations of systems of recursively enumerable sets (abstract). Sov. Math. Dokl.12, 843–845 (1971)
[P] Pour-El, M.B., Howard, W.A.: A structural criterion for recursive enumeration without repetition. Z. Math. Logik Grundlag. Math.10, 105–114 (1964)
[Yi] Yi, X.: Manuscript