Order-Computable Sets
Status: published in the Notre Dame Journal of Formal Logic 48 (2007) 317 - 347
Availability: PostScript, DVI, and PDF
Abstract. We give a straightforward computable-model-theoretic
definition of a property of Delta02 sets, called
order-computability. We then prove various results about these
sets which suggest that, simple though the definition is, the property
defies any 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.
drh@math.uchicago.edu