Order-Computable Sets

by Denis R. Hirschfeldt, Russell Miller, and Sergei Podzorov



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