Spectra of high(n) and non-low(n) degrees
We survey known results on spectra of structures and on spectra of relations on computable structures, asking when the set of all high(n) degrees can be such a spectrum, and likewise for the set of non-low(n) degrees. We then repeat these questions specifically for linear orders and for relations on the computable dense linear order Q. New results include realizations of the set of non-low(n) Turing degrees as the spectrum of a relation on Q for all n >= 1, and a realization of the set of all non-low(n) Turing degrees as the spectrum of a linear order whenever n >= 2. The state of current knowledge is summarized in a table in the concluding section.
relation computability spectrum linear order computable model theory