Order-Computable Sets
Status: to appear in the Notre Dame Journal of Formal Logic
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