Degrees of relations on ordinals

Article type: Research Article

Authors: Wright, Matthew^{; *}

Affiliations: Dropbox, Inc., United States. wrightm@gmail.com

Correspondence: [*] Corresponding author. wrightm@gmail.com.

Abstract: Downey, Khoussainov, Miller, and Yu examined degree spectra of unary relations on the structure (ω,<). We extend their results in several directions. First, we show that the degree spectrum of any unary relation on (ω,<) contains only the computable degree or consists of exactly the Δ2 degrees. We then show, using results from combinatorics, that the degree spectrum of an n-ary relation on (ω,<) either contains only the computable degree or contains all c.e. degrees. Finally, we examine unary relations on general computable ordinals and show that the degree spectrum always contains a maximum degree and that degree is always a (possibly infinite) iterate of the jump.

Keywords: Computable relations, computable structures, ordinals

DOI: 10.3233/COM-180086

Journal: Computability, vol. 7, no. 4, pp. 349-365, 2018