Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Definability in the enumeration degrees

Theodore A. Slaman1 and W. Hugh Woodin1

(1)  Department of Mathematics, University of Chicago, Chicago, IL 60637, USA , US
Abstract.   We prove that every countable relation on the enumeration degrees, , is uniformly definable from parameters in . Consequently, the first order theory of is recursively isomorphic to the second order theory of arithmetic. By an effective version of coding lemma, we show that the first order theory of the enumeration degrees of the sets is not decidable.
Received: August 1, 1994

Fulltext Preview (Small, Large)
Image of the first page of the fulltext


Export this article
Export this article as RIS | Text
 
Remote Address: 38.107.191.113 • Server: mpweb15
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)