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

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
Keywords order-computability   computable model theory   limitwise-monotonic functions
Categories (categorize this paper)
DOI 10.1305/ndjfl/1187031407
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 71,172
Through your library

References found in this work BETA

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

Citations of this work BETA

Η-Representation of Sets and Degrees.Kenneth Harris - 2008 - Journal of Symbolic Logic 73 (4):1097-1121.

Add more citations

Similar books and articles

The Block Relation in Computable Linear Orders.Michael Moses - 2011 - Notre Dame Journal of Formal Logic 52 (3):289-305.
Bounding Prime Models.Barbara F. Csima, Denis R. Hirschfeldt, Julia F. Knight & Robert I. Soare - 2004 - Journal of Symbolic Logic 69 (4):1117 - 1142.
Degree Spectra of Intrinsically C.E. Relations.Denis R. Hirschfeldt - 2001 - Journal of Symbolic Logic 66 (2):441-469.
The Computable Dimension of Trees of Infinite Height.Russell Miller - 2005 - Journal of Symbolic Logic 70 (1):111-141.
Stable Ramsey's Theorem and Measure.Damir D. Dzhafarov - 2011 - Notre Dame Journal of Formal Logic 52 (1):95-112.
The First-Order Structure of Weakly Dedekind-Finite Sets.A. C. Walczak-Typke - 2005 - Journal of Symbolic Logic 70 (4):1161 - 1170.
Uncomputably Noisy Ergodic Limits.Jeremy Avigad - 2012 - Notre Dame Journal of Formal Logic 53 (3):347-350.
Degree Spectra of Relations on Computable Structures.Denis R. Hirschfeldt - 2000 - Bulletin of Symbolic Logic 6 (2):197-212.
On Legal Order: Some Criticism of the Received View. [REVIEW]Riccardo Guastini - 2000 - Ethical Theory and Moral Practice 3 (3):263-272.

Analytics

Added to PP index
2010-08-24

Total views
48 ( #237,699 of 2,517,876 )

Recent downloads (6 months)
1 ( #409,482 of 2,517,876 )

How can I increase my downloads?

Downloads

My notes