##
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 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 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