Decidable Effectively Closed Sets and Acceptably Equivalent Numberings

Author:

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.

WSEAS Transactions on Mathematics, ISSN / E-ISSN: 1109-2769 / 2224-2880, Volume 16, 2017, Art. #29

PDF
XML
Cite
×
Citation Tools
WSEAS AMA
Katie Brodhead, "Decidable Effectively Closed Sets and Acceptably Equivalent Numberings," WSEAS Transactions on Mathematics, vol. 16, pp. 257-265, 2017, DOI:
Katie Brodhead. Decidable Effectively Closed Sets and Acceptably Equivalent Numberings. WSEAS Transactions on Mathematics. 2017;16:257-265.
Copy to Clipboard
Citation copied to Clipboard

Certification

---