AUTHORS: Katie Brodhead
Download as PDF
ABSTRACT: A Π01 class is an effectively closed set of reals. One way to view it is as the set of infinite paths through a computable tree. We consider the notion of acceptably equivalent numberings of Π01 classes. We show that a permutation exists between any two acceptably equivalent numberings that preserves the computable content. Furthermore the most commonly used numberings of the Π01 classes are acceptably equivalent. We also consider decidable Π01 classes in enumerations. A decidable Π01 class may be represented by a unique computable tree without dead ends, but we show that this tree may not show up in an enumeration of uniformly computable trees which gives rise to all Π01 classes. In fact this is guaranteed to occur for some decidable Π01 class. These results are motivated by structural questions concerning the upper semi-lattice of enumerations of Π01 classes where notions such as acceptable equivalence arise
KEYWORDS: Effectively closed sets, Numberings
REFERENCES:[1] D. Cenzer, Effectively Closed Sets, ASL Lecture Notes in Logic, to appear.
[2] D. Cenzer and J. Remmel, Index Sets for Π" # Classes, Annals of Pure and Applied Logic, Vol. 93, 1998, pp. 3-61.
[3] D. Cenzer and J. Remmel, Index Sets for Computable Real Functions, Proceed- -ings of CCA03, Cincinnati, Preprint, 2003, pp. 163-182.
[4] Y. Ershov, Theory of Numberings, Handbook of Computability Theory (Edward R. Griffor, ed.), North-Holl- -and, Amsterdam, 1999.
[5] R. Friedberg, Three Theorems on Recursive Enumeration, Journal of Symbolic Logic, Vol. 23, 1958, pp. 309- 316.
[6] S. Goncharov, S. Lempp, and R. Solomon, Friedburg Numberings of Families of n-Computably Enumerable Sets, Algebra and Logic, Vol. 41, 2002, pp. 81-86.
[7] P. Hinman, Recursion-Theoretic Hier- -archies, Springer-Verlag, 1978.
[8] C. Jockusch and R. Soare, Π" # Classes and Degrees of Theories, Transactions of the American Mathematical Society, Vol. 173, 1972, pp. 35-56.
[9] P. Odifreddi, Classical Recursion The- -ory, Vol. 1, North-Holland, Amster- -dam- New York, 1989.
[10] A. Raichev, Relative Randomness via RK-Reducibility, Ph.D. thesis, Uni- -versity of Wisconsin-Madison, 2006.
[11] H. Rogers, Gödel numberings of partial recursive functions, Journal of Symbolic Logic, Vol. 23, 1958, pp. 331-341.
[12] H. Rogers, Theory of recursive functions and effective computability, McGraw Hill, 1967.
[13] R. Soare, Recursively Enumerable Sets and Degrees, Springer-Verlag, 1987.
[14] Y. Suzuki, Enumerations of recursive sets, Journal of Symbolic Logic, Vol. 24, 1959, pp. 311.