On Turing degrees of points in computable topology

Mathematical Logic Quarterly 54 (5):470-482 (2008)
  Copy   BIBTEX

Abstract

This paper continues our study of computable point-free topological spaces and the metamathematical points in them. For us, a point is the intersection of a sequence of basic open sets with compact and nested closures. We call such a sequence a sharp filter. A function fF from points to points is generated by a function F from basic open sets to basic open sets such that sharp filters map to sharp filters. We restrict our study to functions that have at least all computable points in their domains.We follow Turing's approach in stating that a point is computable if it is the limit of a computable sharp filter; we then define the Turing degree Deg of a general point x in an analogous way. Because of the vagaries of the definition, a result of J. Miller applies and we note that not all points in all our spaces have Turing degrees; but we also show a certain class of points do. We further show that in ℝn all points have Turing degrees and that these degrees are the same as the classical Turing degrees of points defined by other researchers.We also prove the following: For a point x that has a Turing degree and lies either on a computable tree T or in the domain of a computable function fF, there is a sharp filter on T or in dom converging to x and with the same Turing degree as x. Furthermore, all possible Turing degrees occur among the degrees of such points for a given computable function fF or a complete, computable, binary tree T. For each x ∈ dom for which x and fF have Turing degrees, Deg) ≤ Deg. Finally, the Turing degrees of the sharp filters convergent to a given x are closed upward in the partial order of all Turing degrees

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 107,286

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Turing degrees of certain isomorphic images of computable relations.Valentina S. Harizanov - 1998 - Annals of Pure and Applied Logic 93 (1-3):103-113.
On computable numberings of families of Turing degrees.Marat Faizrahmanov - 2024 - Archive for Mathematical Logic 63 (5):609-622.
Degrees That Are Not Degrees of Categoricity.Bernard Anderson & Barbara Csima - 2016 - Notre Dame Journal of Formal Logic 57 (3):389-398.
Degrees of Unsolvability of Continuous Functions.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (2):555 - 584.
The complexity of central series in nilpotent computable groups.Barbara F. Csima & Reed Solomon - 2011 - Annals of Pure and Applied Logic 162 (8):667-678.

Analytics

Added to PP
2013-11-03

Downloads
38 (#693,494)

6 months
5 (#989,305)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Add more citations

References found in this work

On Computable Numbers, with an Application to the Entscheidungsproblem.Alan Turing - 1936 - Proceedings of the London Mathematical Society 42 (1):230-265.
Degrees of Unsolvability of Continuous Functions.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (2):555 - 584.
On effective topological spaces.Dieter Spreen - 1998 - Journal of Symbolic Logic 63 (1):185-221.
A blend of methods of recursion theory and topology.Iraj Kalantari & Larry Welch - 2003 - Annals of Pure and Applied Logic 124 (1-3):141-178.

View all 6 references / Add more references