Degrees of relations on ordinals
Matthew Wright · Computability · 2018
Downey, Khoussainov, Miller, and Yu examined degree spectra of unary relations on the structure [Formula: see text]. We extend their results in several directions. First, we show that the degree spectrum of any unary relation on [Formula: see text] contains only the computable degree or consists of exactly the [Formula: see text] degrees. We then show, using results from combinatorics, that the degree spectrum of an n-ary relation on [Formula: see text] 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.