The Journal of Symbolic Logic

Research Article

η-representation of sets and degrees

Kenneth Harris

Department of Computer Science, University of Chicago 1100 E. 5TH Street, Chicago, IL 60637, USA, E-mail: kaharris@cs.uchicago.edu

Abstract

We show that a set has an η-representation in a linear order if and only if it is the range of a 0′-computable limitwise monotonic function. We also construct a Δ3 Turing degree for which no set in that degree has a strong η-representation, answering a question posed by Downey.

(Received November 17 2005)