Order-Computable Sets

Notre Dame Journal of Formal Logic 48 (3):317-347 (2007)
  Copy   BIBTEX

Abstract

We give a straightforward computable-model-theoretic definition of a property of \Delta^0_2 sets called order-computability. We then prove various results about these sets which suggest that, simple though the definition is, the property defies any easy characterization in pure computability theory. The most striking example is the construction of two computably isomorphic c.e. sets, one of which is order-computable and the other not

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 98,418

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

Difference sets and computability theory.Rod Downey, Zoltán Füredi, Carl G. Jockusch & Lee A. Rubel - 1998 - Annals of Pure and Applied Logic 93 (1-3):63-72.
Minimal weak truth table degrees and computably enumerable Turing degrees.R. G. Downey - 2020 - Providence, RI: American Mathematical Society. Edited by Keng Meng Ng & Reed Solomon.
Computability of measurable sets via effective topologies.Yongcheng Wu & Decheng Ding - 2006 - Archive for Mathematical Logic 45 (3):365-379.
Intrinsic smallness.Justin Miller - 2021 - Journal of Symbolic Logic 86 (2):558-576.
Prime models of finite computable dimension.Pavel Semukhin - 2009 - Journal of Symbolic Logic 74 (1):336-348.

Analytics

Added to PP
2010-08-24

Downloads
72 (#242,522)

6 months
10 (#311,469)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Η-representation of sets and degrees.Kenneth Harris - 2008 - Journal of Symbolic Logic 73 (4):1097-1121.

Add more citations

References found in this work

Calibrating randomness.Rod Downey, Denis R. Hirschfeldt, André Nies & Sebastiaan A. Terwijn - 2006 - Bulletin of Symbolic Logic 12 (3):411-491.
Degrees coded in jumps of orderings.Julia F. Knight - 1986 - Journal of Symbolic Logic 51 (4):1034-1042.
Computable Models of Theories with Few Models.Bakhadyr Khoussainov, Andre Nies & Richard A. Shore - 1997 - Notre Dame Journal of Formal Logic 38 (2):165-178.

Add more references