Degree spectra of unary relations on \(\langle \omega, \leq \rangle\). (English) Zbl 1419.03038
Glymour, Clark (ed.) et al., Logic, methodology and philosophy of science. Proceedings of the 13th international congress, Beijing, China, August 2007. London: College Publications. 36-55 (2009).
Summary: A computable presentation of the linearly ordered set \((\omega,\le)\), where \(\omega\) is the set of natural numbers and \(\le\) is the natural order on \(\omega\), is any linearly ordered set \(\mathbf{L}=(\omega,\le_L)\) isomorphic to \((\omega,\le)\) such that \(\le_L\) is a computable relation. Let \(X\) be subset of \(\omega\) and \(X_L\) be the image of \(X\) in the linear order \(\mathbf{L}\) under the isomorphism between \((\omega,\le)\) and \(\mathbf{L}\). The degree spectrum of \(X\) is the set of all Turing degrees of \(X_L\) as one runs over all computable presentations of \((\omega,\le)\). In this paper we study the degree spectra of subsets of \(\omega\).
For the entire collection see [Zbl 1309.03002].
For the entire collection see [Zbl 1309.03002].
MSC:
03D20 | Recursive functions and relations, subrecursive hierarchies |
03D25 | Recursively (computably) enumerable sets and degrees |
03D45 | Theory of numerations, effectively presented structures |